C++ priority_queue underlying vector container capacity resize

Question

Hi all,

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 1

Use reserve function:

std::vector<Type>::reserve(size_t size)

Sample:

std::vector<int> vec;
vec.reserve(10000);
std::priority_queue<int> q (std::less<int>(), vec);

Answer 2

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.

Answer 3

David is right in his comment to Alexey's answer: there's not much chance the vector implementation will allocate what is reserved on a copy. So either provide your own container that does do this, or inherit from priority_queue and provide some members to play with the underlying container.

Answer 4

You cannot directly access the underlying container to modify the capacity. You can however change the container that is used internally to a std::deque. The std::deque container might be slightly slower (not in big-O notation) than a vector, but growing it is much faster as it does not need to relocate all existing elements.

Answer 5

As suggest David, using a std::deque is probably a good solution. The memory chunks are small enough to usually allow you to reserve most of your memory while the queue is growing. However it is just a more secure solution but not a safe solution.

If you don't care too much about efficiency you can use stlxxl wich is an implementation of the Standard Template Library for Extra Large Data Sets. This way the allocatable memory will be your entire harddrive (the library also support multiple harddrives or network drives).