Benefits of setting priority_queue Container

Question

With stl priority_queue you can set a base container, like vector . What are some of the benefits of specifying a container for stl priority_queue ?

Answer 1

Setting up the base container allows you to identify two logically separate problems:

• How do you store the actual items that make up the priority queue (container), and
• How to organize these elements to efficiently execute the priority queue (adapter class priority_queue ).

As an example, the standard implementation of vector does not need to shrink when its capacity is significantly larger than its actual size. This means that if you have a priority queue supported by vector , you can end up losing memory if you insert a lot of elements and then delete them all, since vector will keep its former capacity. If, on the other hand, you implement your own shrinking_vector class, which really reduces its capacity when necessary, you can get all the advantages of the priority_queue interface when using the storage more efficiently.

Another possible example is that you can change the allocator used so that the priority queue elements are allocated from a special resource pool. You can do this by simply setting the container type priority_queue as vector using a special allocator.

Another thought - suppose you store priority_queue very large objects, the copy time of which is very long. In this case, the fact that vector dynamically resizes and copies its old elements (or at least in the C ++ 03 compiler) may be what you are not willing to pay for. Thus, you can switch to some other type, perhaps deque , which makes efforts not to copy elements when resizing and could not achieve big performance gains.

Hope this helps!

Answer 2

The priority_queue class is an example adapter template. It provides a way to provide priority queue services over an existing dataset. As an adapter, a basic container is actually required. By default, it specifies vector . (from here ).

In terms of benefits, it is simply more flexible. priority_queue uses the following backup storage methods and requires it to support random access iterators.

• front
• push_back
• pop_back

By providing it as an adapter, you can control performance characteristics by providing a different implementation.

Two examples that implement this in STL are vector and deque . Both of them have different performance characteristics. For example, a vector usually limited in memory, while a deque usually not. The push_back operation in a vector is only an amortized constant time (you may need to redistribute the vector), while for deque it is specified in constant time.