reserve with std::priority_queue

[Tino]

In using std:riority_queue, I'm concerned about the expense of
memory allocation and copying as the priority_queue grows large.
std::vector has reserve() to address this concern, though there
doesn't seem to be anything like this for priority_queue. Also, I
don't know anything about how priority_queue is implemented
(specifically, MSVC++ 6.0), so maybe I don't have anything to worry
about. Guidance, please?

Regards,
Ryan

 

[John Harrison]

In using std:riority_queue, I'm concerned about the expense of
memory allocation and copying as the priority_queue grows large.
std::vector has reserve() to address this concern, though there
doesn't seem to be anything like this for priority_queue. Also, I
don't know anything about how priority_queue is implemented
(specifically, MSVC++ 6.0), so maybe I don't have anything to worry
about. Guidance, please?

Regards,
Ryan

priority_queue is not necessarily based on a vector, e.g. here's a priority
queue that uses a deque.

priority_queue<int, deque<int> > my_queue

I'd use a priority_queue based on a deque if you are worried about
reallocations as the queue grows.

For implementation, just look in the header file. priority_queue is llikely
to be pretty simple since most of the work is done by the underlying
container and other STL algorithms.

john

 

[Jeff Schwab]

In using std:riority_queue, I'm concerned about the expense of
memory allocation and copying as the priority_queue grows large.
std::vector has reserve() to address this concern, though there
doesn't seem to be anything like this for priority_queue. Also, I
don't know anything about how priority_queue is implemented
(specifically, MSVC++ 6.0), so maybe I don't have anything to worry
about. Guidance, please?

You could provide your own "underlying" container type for the
std:riority_queue, perhaps containing a std::vector. You custom
container could have its member vector reserve an arbitrary amount of
memory.

 

[rossum]

In using std:riority_queue, I'm concerned about the expense of
memory allocation and copying as the priority_queue grows large.
std::vector has reserve() to address this concern, though there
doesn't seem to be anything like this for priority_queue. Also, I
don't know anything about how priority_queue is implemented
(specifically, MSVC++ 6.0), so maybe I don't have anything to worry
about. Guidance, please?

Regards,
Ryan

std::vector guarantees that the memory it uses is contiguous so when
the allocated chunk of memory needs to be expanded a new chunk of
memory large enough for the whole vector needs to be allocated and all
the contents of the vector copied into the new memory before the old
memory is released.

The other containers do not have to be contiguous so they can leave
the old contents where they are and just allocate a new chunk of
memory large enough to hold the new object being added to the
container. They do not have to copy the existing contents since these
are left in the old memory.

Hence they do not need a reserve function like vector. Reserve is
useful when you know the size of the vector in advance and can
allocate all the memory needed in one chunk at the beginning and so
avoid having to copy large pieces of the vector.

rossum