Récupérer la plus grande valeur sur les itérateurs

Question

J'ai trois itérateurs à accès aléatoire parent, child1 et child2, qui pointent vers certaines valeurs dans un tableau permuté. (Contexte: J'implémente heapsort, ces itérateurs comprennent un sous-arbre binaire).

J'ai besoin de déterminer l'itérateur, qui a la plus grande valeur référencée (pour maintenir la propriété max-tas du tas). Donc, si *parent est le plus important, le retour parent, si *child1 est le plus important, le retour child1, etc.

pseudocode:

#include <algorithm> 

auto iterator = std::max({ parent, child1, child2 }); 

iterator est maintenant l'itérateur dont valeur sous-jacente est le plus grand.

Le problème est que l'utilisation de ce pseudo-code littéral, std::max comparerait les itérateurs lui-même ici, pas leurs valeurs référencées. Je pourrais faire std::max({ *parent, *child1, *child2 }), mais ça renvoie decltype(*parent), alors comment pourrais-je récupérer l'itérateur à partir de là?

Je sais qu'il est trivialement possible d'utiliser if s, mais n'y a-t-il pas une façon plus élégante? Est-ce que la bibliothèque standard a quelque chose là-bas? J'ai essayé plusieurs choses, mais elles semblent toutes volumineuses et gênantes.

Answer 1

Si vous faites ici, il est considères pas std::max avec un comparateur personnalisé volumineux,:

auto iterator = std::max({ parent, child1, child2 }, 
         [](auto it_a, auto it_b) { return *it_a < *it_b; }); 

Answer 2

std::max accepte un objet de fonction de comparaison:

auto iterator = std::max({ parent, child1, child2 }, 
         [](const auto& a, const auto& b){ 
    return *a < *b; 
}); 

---

Bien, vous pouvez préférer refactoriser en certaines parties fonctionnelles réutilisables:

template<class Fun> 
auto indirect_args(Fun&& fun = {}) { 
    return [fun = std::forward<Fun>(fun)](auto&&... args) { 
     std::forward<decltype(fun)>(fun)(
      *std::forward<decltype(args)>(args)...); 
    }; 
} 

auto iterator = std::max({ parent, child1, child2 }, 
         indirect_args<std::less<decltype(parent)>>(); 
}); 

Answer 3

depuis std::max a une surcharge pour un comparateur personnalisé, vous pouvez faire:

auto cmp = [](auto lhs, auto rhs){ return *lhs < *rhs; }; 
auto iterator = std::max({ parent, child1, child2 }, cmp);