16

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

cagribal
  • 363
  • 2
  • 3
  • 8

5 Answers5

26

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.

visitor
  • 8,564
  • 2
  • 26
  • 15
  • 2
    +1 I would usually be against inheriting from a standard container on theoretical grounds, but in this case the engineering in me tells me this might be the best solution. – David Rodríguez - dribeas Sep 08 '10 at 11:00
  • 1
    I don't like this solution for 2 reasons: 1/ inheriting from a class that has a public non-virtual destructor makes feel bad, very bad, 2/ this backdoor is not mentioned either on cplusplus.com nor on http://www.sgi.com/tech/stl ... I have a bad feeling that this is implementation specific and NOT standard at all. – Matthieu M. Sep 08 '10 at 13:47
  • 2
    @Matthiew M. The backdoor is in the standard, so it is technically correct. I do agree that inheriting from a container is not the best advice in general... – David Rodríguez - dribeas Sep 08 '10 at 14:04
  • 1
    #define protected public :P – Herbert Jun 28 '14 at 13:24
  • @Herbert does that even work? That would be the best hack ever. `#define private public` and you've got access to everything. – tomsmeding Jul 06 '15 at 13:43
  • Not really, it is extremely dangerous!!! Changing the privateness of data members may change the ABI (application binary interface) of the class. So in case of a library, the .so is compiled against a version where certain data members are private, whereas your code is compiled against a version where all are public. So you when you link, you link together assembly (or whatever lowlevel stuff) which assumes different ABI's, and hence possibly different alignments of data members. Even though it does work in my experience with g++ – Herbert Jul 06 '15 at 14:40
  • If I want to pass a custom comparator to the object, how do I change the class declaration? – Sandeep Tuniki Oct 17 '16 at 09:54
3

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.

David Rodríguez - dribeas
  • 204,818
  • 23
  • 294
  • 489
  • I think there is a typo in last sentence. s/std::queue/std::deque/ no ? Otherwise I agree. This solution make the use of the priority more secure. Elements in a deque are allocated by chunks. – log0 Sep 08 '10 at 12:05
  • That's not true. You can access the underlying container via the member `c`. It's in fact standard. – Elizafox Jul 27 '16 at 16:48
  • @Elizafox: The `c` member is `protected`, you cannot access this member directly from your own code, unless you are inheriting from the container, and you use your own type instead of `std::priority_queue` – David Rodríguez - dribeas Jul 28 '16 at 11:44
0

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);
Alexey Malistov
  • 26,407
  • 13
  • 68
  • 88
  • 6
    I don't think this is a solution. The standard only requires that the internal container is initialized with the second argument of that particular constructor. That means that `std::vector` copy constructor will be called passing `vec` as argument, and then it all boils down on whether `std::vector::vector( std::vector const & )` is required to maintain the same capacity. That guarantee is not provided by the standard. EDIT: I have just tested with g++ 4.0 and the copy constructor does not `reserve()` to maintain the capacity in the copied vector. – David Rodríguez - dribeas Sep 08 '10 at 10:48
0

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.

stijn
  • 34,664
  • 13
  • 111
  • 163
0

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).

log0
  • 10,489
  • 4
  • 28
  • 62