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

Setting the underlying container makes it possible to separate out two logically separate concerns: <ol> <li>How do you store the actual elements that make up the priority queue (the container), and</li> <li>How do you organize those elements to efficiently implement a priority queue (the <code>priority_queue</code> adapter class).</li> </ol> As an example, the standard implementation of <code>vector</code> 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 <code>vector</code>, you might end up wasting memory if you enqueue a lot of elements and then dequeue all of them, since the <code>vector</code> will keep its old capacity. If, on the other hand, you implement your own <code>shrinking_vector</code> class that does actually decrease its capacity when needed, you can get all the benefits of the <code>priority_queue</code> 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 <code>priority_queue</code> to be a <code>vector</code> with a custom allocator. One more thought - suppose that you are storing a <code>priority_queue</code> of very large objects whose copy time is very great. In that case, the fact that the <code>vector</code> 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 <code>deque</code>, that makes an effort not to copy elements when resizing and could realize some big performance wins. Hope this helps!

Advantages of Setting priority

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?

Which is better priority queue or set?

The priority queue only offers access to the largest element, while the set gives you a complete ordering of all elements. This weaker interface means that implementations may be more efficient (e.g. you can store the actual queue data in a vector , which may have better performance on account of its memory locality).

Which container class can be used as underlying container for priority_queue?

Suitable underlying container classes for priority_queue include deque Class and the default vector Class or any other sequence container that supports the operations of front , push_back , and pop_back and a random-access iterator.

What is container in priority queue?

class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue; A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

Can set be used as priority queue?

Priority queue of sets can be quite useful for designing complex data structures. Below is the implementation of the max-heap priority queue of set: C++

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

How do you store the actual elements that make up the priority queue (the container), and
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!

Advantages of Setting priority_queue Container

Tags:

c++

stl

priority-queue

HighLife

People also ask

1 Answers

templatetypedef

Recent Activity

Donate For Us