设置priority_queue容器的优点

Question

使用stl,priority_queue您可以设置基础容器,例如a vector.为stl指定容器有哪些优点priority_queue？

Answer 1

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

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

例如,当标准vector容量远大于其实际大小时,标准实现不需要自行缩减.这意味着如果你有一个由a支持的优先级队列vector,你可能最终会浪费内存,如果你排队了很多元素然后将所有元素出列,因为vector它将保留其旧容量.另一方面,如果您实现自己的shrinking_vector类,在需要时实际上会降低其容量,则可以在priority_queue更高效地使用存储的同时获得接口的所有好处.

另一个可能的示例 - 您可能希望更改正在使用的分配器,以便从特殊资源池分配优先级队列的元素.您可以通过使用自定义分配器设置容器类型来实现此priority_queue目的vector.

还有一个想法 - 假设您正在存储一个priority_queue非常大的对象,其复制时间非常长.在这种情况下,vector动态调整自身大小并复制其旧元素(或者至少在C++ 03编译器中)的事实可能是您不愿意支付的.因此,您可以切换到其他类型,也许是一种deque,在调整大小时不会复制元素并且可以实现一些重大的性能获胜.

希望这可以帮助!