std::priority_queue的模板参数是什么？

Question

我正在浏览一些 STL 文档。我看到按降序存储的优先级队列的语法是：

std::priority_queue<int> q ;
//gives 9 8 7 6 5 4 3 2 1  when pushed and obtained

但是，对于以升序方式存储，它是：

std::priority_queue< int, std::vector<int>, std::greater<int> > q ;
//gives 1 2 3 4 5 6 7 8 9 when pushed and obtained

我想知道第二个例子中额外模板参数的具体用途是什么。例如，std::vector<int> 在该示例中做了什么？

另外，有人可以进一步解释这个声明吗？

priority_queue< pair<int ,int > , vector< pair<int ,int > > , greater< pair<int ,int > > > q ;

Answer 1

std::priority_queue本身不是容器，它是一个容器适配器，这意味着它在内部使用另一个容器来存储队列中的实际数据。

默认情况下，它使用 std::vector 存储在队列中的类型。

这里的问题是，就像将参数传递给具有默认参数的函数一样，您不能跳过模板列表中的参数，即使它们具有默认类型，您必须始终提供以前的模板参数。

如果您看到链接引用，您会看到 std::priority_queue 的第二个和第三个模板参数具有默认类型。如果您想更改第三个模板参数，您还必须提供第二个模板参数，它是实际的底层容器。因此，对于 std::priority_queue 的 int，您需要提供 std::vector<int>.

然而，有一种方法可以不将比较器的类型作为模板参数传递，std::priority_queue constructor 也为比较器函数接受一个（可选）参数。您可以在这里提供任何函数、函数对象、lambda 或其他可调用对象。

在你的情况下你可以这样做

std::priority_queue<int> q{std::greater<int>()};

~~上面的声明创建了一个 std::greater<int> 对象并将其作为比较器传递给 std::priority_queue 构造函数。~~

Answer 2

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

std::priority_queue 是一个包装另一个容器的容器，这意味着它只在另一个容器之上提供 priority 和 queue 抽象，只要这个容器与SequenceContainer concept.

如果用户想要不同的时间和内存复杂度约束，则可以更改容器。或者提供自己的容器。

std::greater<T> 是 T 类型元素的比较器。需要满足全序。

std::priority_queue的模板参数是什么？

What are the template parameters of std::priority_queue?

c++

c++11

vector

stl

priority-queue