c++ - 设置priority_queue容器的优点

使用STL priority_queue可以设置基础容器，例如vector。为STL priority_queue指定一个容器有哪些优点？

最佳答案

设置基础容器可以分离出两个逻辑上分开的关注点:

如何存储组成优先级队列的实际元素(容器)和

如何组织这些元素以有效地实现优先级队列(priority_queue适配器类)。

例如，当vector的容量大大超过其实际大小时，不需要缩减其本身的标准实现。这意味着，如果您有一个由vector支持的优先级队列，那么当您使很多元素入队然后将所有元素都出队时，您可能最终会浪费内存，因为vector将保留其旧容量。另一方面，如果您实现自己的shrinking_vector类，而该类实际上在需要时会降低其容量，则您可以获得priority_queue接口(interface)的所有好处，同时可以更有效地使用存储。

另一个可能的示例-您可能想要更改正在使用的分配器，以便从特殊的资源池分配优先级队列的元素。您可以通过使用自定义分配器将priority_queue的容器类型设置为vector来完成此操作。

再想一想-假设您存储的是非常大的对象的priority_queue，其复制时间非常长。在这种情况下，vector会自动调整自身大小并复制其旧元素(或者至少在C++ 03编译器中)，这一事实可能是您不愿意支付的。因此，您可以切换到其他类型，也许是deque，它会在调整大小时努力不复制元素，并且可能会获得一些巨大的性能优势。

希望这可以帮助!