如何根据某种数据结构自定义std::make_heap比较函数？

Question

我正在尝试使用 std::make_heap ，它具有我需要的大部分属性。 我有一个整数向量，它们只是我的数据结构的索引，我希望堆建立在该数据结构的某些属性上。 如果我想要一个 lambda 函数进行比较，那就很简单了：

[](int x, int y){return elementList[x]->lnc > elementList[y]->lnc;}

我面临的问题是比较函数只接受 2 个输入，我无法将

elementList

传递给它。 我心里有两个解决方案。首先，将指针存储在我拥有的向量中。其次是自己从头开始实现堆。 有没有更简单的解决方案？

更新：lambda 函数中的 capture 子句（Brian 提到的）是一个好方法。如果我不想使用 lambda 函数有什么解决方案吗？

Answer 1

std::make_heap

采用三个参数：两个表示随机访问范围的迭代器和一个比较函数。只需提供您的自定义比较函数作为第三个参数即可。

#include <algorithm>
#include <vector>

// ...

std::vector<Foo> v{/* ... */};

std::make_heap(v.begin(), v.end(), [&elementList](auto lhs, auto rhs){ 
    return elementList[lhs]->lnc > elementList[rhs]->lnc;
});