c++ - 设置priority_queue容器的好处

Question

使用 STL priority_queue，您可以设置底层容器，例如 vector。为 STL priority_queue 指定容器有哪些优点？

Answer 1

设置底层容器可以分离出两个逻辑上独立的关注点:

1. 如何存储构成优先级队列(容器)的实际元素，以及
2. 如何组织这些元素以有效地实现优先级队列(priority_queue 适配器类)。

例如，vector 的标准实现不需要在其容量远大于其实际大小时自行缩小。这意味着如果您有一个由 vector 支持的优先级队列，如果您将大量元素入队然后将所有元素出队，您可能最终会浪费内存，因为 vector 将保持其旧容量。另一方面，如果您实现自己的 shr​​inking_vector 类，该类在需要时确实会减少其容量，则您可以在拥有存储空间的同时获得 priority_queue 接口(interface)的所有好处更有效地使用。

另一个可能的例子——你可能想改变正在使用的分配器，以便优先级队列的元素是从一个特殊的资源池中分配的。您只需将 priority_queue 的容器类型设置为带有自定义分配器的 vector 即可。

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

希望这对您有所帮助!