在迭代器上检索最大值

Question

我有三个随机访问迭代器 parent、child1 和 child2，它们指向置换数组中的某些值。（上下文：我正在实现堆排序；那些迭代器包含一个二叉子树）。

我需要确定迭代器，它具有最大的引用值（以维护堆的max-heap 属性）。所以，如果*parent最大，returnparent，如果*child1最大，returnchild1，等等

伪代码：

#include <algorithm>

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

iterator 现在是基础值 最大的迭代器。

问题在于，使用此文字伪代码，std::max 会在此处比较迭代器 itsself，而不是它们的引用值。我可以做 std::max({ *parent, *child1, *child2 })，但它 returns decltype(*parent)，那么我如何从那里取回迭代器？

我知道使用一些 ifs 是非常可行的，但是没有更优雅的方法吗？标准库里有什么东西吗？我尝试了几种方法，但它们都显得笨重且不方便。

Answer 1

如果您不认为 std::max 使用自定义比较器笨重，这里是：

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

Answer 2

std::max接受一个比较函数对象：

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

不过，您可能更愿意重构一些 re-usable 功能部分：

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

因为 std::max 有自定义比较器的重载，你可以这样做：

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

在迭代器上检索最大值

Retrieve Largest Value On Iterators

c++

heapsort

c++-standard-library