c++ - 为什么在定义结构的优先级队列时使用 vector ？

Question

我知道我们可以通过以下方式定义结构的优先级队列:

std::priority_queue<somestructure, vector<somestructure>, compare> pq;

其中compare是包含比较功能的结构。我想问为什么在这个声明中我们需要使用 vector 作为第二个参数。在定义上述优先级队列时， vector 与优先级​​队列有何关系？

Answer 1

std::priority_queue是我们称为容器适配器的容器。如您所知，在C++中，我们有类似std::vector，std:array或std::deque的容器。所有这些功能都可以将T类型的内容直接保存到它们中，各有利弊。

例如，std::stack是一个容器适配器，可以在std:deque之上使用。该适配器唯一要做的就是取消std::deque的功能以在末尾插入或从末尾取出。这样，用户被迫仅像堆栈一样使用std::deque。
std::priority_queue的情况与此类似，它会强制您仅按顺序插入基础容器(例如std::vector)。这样，您将获得一些不错的属性，可以了解如何在此容器中查找元素。在这种特殊情况下，通过花更多的精力来研究如何在基础容器中插入新元素，并摆脱了在任意位置随意插入元素的自由。因此，对于插入而不是O(1)，您将获得O(log(n))复杂度(例如，而不是在末尾插入)。但是这样一来，您只需要O(1)到的复杂度就可以找到而不是O(n)的最大元素。

在这种情况下，std::vector没什么特别的，您可以使用满足此容器适配器需求的任何容器，也可以使用std::deque或自己的容器或to quote:

The type of the underlying container to use to store the elements. The container must satisfy the requirements of SequenceContainer, and its iterators must satisfy the requirements of LegacyRandomAccessIterator. Additionally, it must provide the following functions with the usual semantics: front() push_back() pop_back() The standard containers std::vector and std::deque satisfy these requirements.