copy elements from a pq to a vector

[John]

I have a priority_queue that stores its elements in a vector.
What is the fastest way to copy all the elements of the
priority queue to this vector. Right now I use pop() to pop
all the elements one by one and copy it to the output vector.

I was thinking maybe one can inherit the priority_queue class
to get access to the internal vector so that copy would be fast.
Any ideas?

Thanks,
--j

 

[Victor Bazarov]

I have a priority_queue that stores its elements in a vector.
What is the fastest way to copy all the elements of the
priority queue to this vector. Right now I use pop() to pop
all the elements one by one and copy it to the output vector.

I was thinking maybe one can inherit the priority_queue class
to get access to the internal vector so that copy would be fast.
Any ideas?

No need to inherit. Just use the 'top' and copy as you would an array
of type T:

priority_queue<T> myq;
....
vector<T> outputvec(myq.size());
....
std::copy(&(myq.top()), &(myq.top()) + myq.size(), &outputvec[0]);

Since the underlying container of your queue is a vector, its continuity
can be used to extract contents. It's not a good idea if you expect to
change the underlying container to deque at any point.

V

 

[Ivan Vecerina]

: John wrote:
: > I have a priority_queue that stores its elements in a vector.
: > What is the fastest way to copy all the elements of the
: > priority queue to this vector. Right now I use pop() to pop
: > all the elements one by one and copy it to the output vector.
: >
: > I was thinking maybe one can inherit the priority_queue class
: > to get access to the internal vector so that copy would be fast.
: > Any ideas?
:
: No need to inherit. Just use the 'top' and copy as you would an array
: of type T:
:
: priority_queue<T> myq;
: ...
: vector<T> outputvec(myq.size());
: ...
: std::copy(&(myq.top()), &(myq.top()) + myq.size(), &outputvec[0]);
:
: Since the underlying container of your queue is a vector, its continuity
: can be used to extract contents. It's not a good idea if you expect to
: change the underlying container to deque at any point.

Hm, however I'm afraid that this will not be equivalent to pop()-ing the
items one by one, if the order of the elements matters: a priority queue
keeps its items sorted in non-linear fashion.
So at best the items in the output vector would need to be sorted
again in a second pass...

What I would like to question, though, is: why is a priority_queue used
in the first place?


Regards,
Ivan