CODEWITHSUNDEEP
c++stlpriority-queue
HighLife
HighLife

Reputation: 4354

Advantages of Setting priority_queue Container

With the stl priority_queue you can set the underlying container, such as a vector. What are some of the advantages of specifying a container for the stl priority_queue?

Upvotes: 15

Views: 8929

Answers (2)

Jeff Foster
Jeff Foster

Reputation: 44746

The priority_queue class is an example of the adapter pattern. It provides a way of providing the services of a priority queue over an existing data set. As an adapter, it actually requires an underlying container. By default, it specifies a vector. (from here).

In terms of the advantages, it's simply a more flexible. The priority_queue uses the following methods of the backing store and requires it to support random access iterators.

  • front
  • push_back
  • pop_back

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

Two examples that implement this in STL are vector and deque. These both have different performance characteristics. For example, a vector typically is continguous in memory, whereas a deque typically isn't. The push_back operation in a vector is only amortized constant time (it might have to reallocate the vector), whereas for the deque it's specified in constant time.

Upvotes: 3

templatetypedef
templatetypedef

Reputation: 373512

Setting the underlying container makes it possible to separate out two logically separate concerns:

  1. How do you store the actual elements that make up the priority queue (the container), and
  2. How do you organize those elements to efficiently implement a priority queue (the priority_queue adapter class).

As an example, the standard implementation of vector is not required to shrink itself down when its capacity is vastly greater than its actual size. This means that if you have a priority queue backed by a vector, you might end up wasting memory if you enqueue a lot of elements and then dequeue all of them, since the vector will keep its old capacity. If, on the other hand, you implement your own shrinking_vector class that does actually decrease its capacity when needed, you can get all the benefits of the priority_queue interface while having the storage be used more efficiently.

Another possible example - you might want to change the allocator being used so that the elements of the priority queue are allocated from a special pool of resources. You can do this by just setting the container type of the priority_queue to be a vector with a custom allocator.

One more thought - suppose that you are storing a priority_queue of very large objects whose copy time is very great. In that case, the fact that the vector dynamically resizes itself and copies its old elements (or at least, in a C++03 compiler) might be something you're not willing to pay for. You could thus switch to some other type, perhaps a deque, that makes an effort not to copy elements when resizing and could realize some big performance wins.

Hope this helps!

Upvotes: 26

Related Questions