std::priority_queue 中的比较器

Question

std::priority_queue 的构造函数通过常量引用接受比较器是否有原因？如果比较器超出范围怎么办？

正如@LightnessRacesInOrbit 指出的那样，我是在可能移动比较器的背景下考虑这个问题的！

很抱歉，如果已经有关于此的 post。我还没找到呢！

Answer 1

std::priority_queue 的构造函数复制了所提供的比较器，因此即使它超出范围也不成问题。

您可以使用 std::function<bool(const T&, const T&)> 作为比较器类型或直接使用 lambda 作为比较器：

auto comp = [](int x, int y) { return x > y; };
std::priority_queue<int, std::vector<int>, decltype(comp)> q(comp);

您可以使用辅助函数来促进此操作：

template<typename T, typename Compare>
auto make_priority_queue(Compare&& comp) {
    return std::priority_queue<T, std::vector<T>, Compare>(std::forward<Compare>(comp));
}

int main() {
    auto q = make_priority_queue<int>([](int x, int y) { return x > y; });
}

Answer 2

它没有超出范围——它是复制构造到容器中的。 cppreference.com 上的描述指出：

explicit priority_queue( const Compare& compare = Compare(),
                         const Container& cont = Container() );

Copy-constructs the underlying container c with the contents of cont. Copy-constructs the comparison functor comp with the contents of compare. Calls std::make_heap(c.begin(), c.end(), comp). This is also the default constructor.

还有各种其他形式的构造函数，但在所有情况下，内部比较器都是从提供的构造函数复制或移动构造的。

Answer 3

我以前从来没有真正想过这个，const-ref 确实有点误导。然而，函数签名是在移动语义出现之前被想到的，并且通过值接受一切变得流行起来。确实，比较器被复制了！

[C++14: 23.6.4.1/4]: Effects: Initializes comp with x and c with y (copy constructing or move constructing as appropriate); calls c.insert(c.end(), first, last); and finally calls make_heap(c.begin(), c.end(), comp).

Lambda 不可复制赋值，但它们是可复制构造的，所以这里没有问题。

[C++14: 5.1.2/20]: The closure type associated with a lambda-expression has a deleted (8.4.3) default constructor and a deleted copy assignment operator. It has an implicitly-declared copy constructor (12.8) and may have an implicitly-declared move constructor (12.8). [..]

这会阻止比较器本身的移动构造吗？是的，它确实。我将假设这个约定，即通过 const-ref 获取比较器然后复制它，源于 STL 时代，早于移动语义。我想并没有认真考虑添加重载以按值获取比较器，因为这会增加复杂性，你不应该首先拥有一个复杂的、可移动增强的比较器（给它们状态，当然，但不是 太多了)。不过，如果您能想出一个移动比较器的可靠用例，这个可能值得向委员会提出。

std::priority_queue 中的比较器

Comparators in std::priority_queue

c++

heap

stl

priority-queue

c++11