Reputation: 4354
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
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
Reputation: 373512
Setting the underlying container makes it possible to separate out two logically separate concerns:
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