C++ priority_queue underlying vector container capacity resize

c++ priority-queue
cagribal picture cagribal · Sep 8, 2010 · Viewed 8.9k times · Source

I'm using priority_queue with a vector as an underlying container. However I expect the size of the heap to be very large. I'm aware of problems with dynamic vector capacity resize. So I'm looking for ways to initially allocate enough space for the underlying vector in my priority_queue. Are there any suggestions out there to achieve this?

Thanks

Answer

visitor picture visitor · Sep 8, 2010

stdlib container adaptors provide a "back door" to access the underlying container: the container is a protected member called c.

Therefore you can inherit from the adapter to gain access to the container:

#include <queue>
#include <iostream>

template <class T>
class reservable_priority_queue: public std::priority_queue<T>
{
public:
    typedef typename std::priority_queue<T>::size_type size_type;
    reservable_priority_queue(size_type capacity = 0) { reserve(capacity); };
    void reserve(size_type capacity) { this->c.reserve(capacity); } 
    size_type capacity() const { return this->c.capacity(); } 
};

int main()
{
    reservable_priority_queue<int> q;
    q.reserve(10000);
    std::cout << q.capacity() << '\n';
}

If you feel bad about inheriting from a stdlib class, use private inheritance and make all the methods of priority_queue accessible with using declarations.

Related questions

declaring a priority_queue in c++ with a custom comparator

I'm trying to declare a priority_queue of nodes, using bool Compare(Node a, Node b) as the comparator function (which is outside the node class). What I currently have is: priority_queue<Node, vector<Node>, Compare&…

Read More
How can I create Min stl priority_queue?

The default stl priority queue is a Max one (Top function returns the largest element). Say, for simplicity, that it is a priority queue of int values.

Read More
How to remove element not at top from priority_queue?

In my program I need to delete an element from a priority queue that is not at the top. Can that be done? If not, please suggest a way to do so except creating your own heap.

Read More