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

Question

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

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

我面临的问题是比较函数只接受 2 个输入，我无法将 elementList 传递给它。我有两个解决方案。首先，将指针存储在我拥有的向量中。其次是自己从头开始实现堆。有更简单的解决方案吗？

更新：lambda 函数中的捕获子句（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;
});

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

How to customize std::make_heap comparison function based on some data structure?

c++

heap

stdvector