How do I efficiently copy an entire queue to a vector/an array in C++?

Question

How do I efficiently copy an entire queue to a vector/an array in C++?

say I have a std::queue and at some point I want to copy it to a vector/an array and then sort it.

Thanks for everyone's answers.

What I really want to do is to create a window with a fix length and at some point i need to copy all the elements inside this window and sort them. the window is moving and there are new data coming in through another interface so i want to use queue. is there any better implementations?

Solution 1

You wrote:

What I really want to do is to create a window with a fix length and at some point i need to copy all the elements inside this window and sort them. the window is moving and there are new data coming in through another interface so i want to use queue.

I suggest to take a step back, and reconsider whether you really want to use a queue. I suppose you want it because you

1. want to expose a minimal interface to the other component which adds data to the queue.
2. efficient addition/removal of elements at the front/back (to implement the 'fixed width window' concept)
3. an efficient way to access the data visible in the window sorted

Unfortunately, std::queue isn't very suitable for (3). Hence, I'd suggest to look for something which addresses (2) and (3), and then consider writing a wrapper of some sort (maybe a plain function which just adds an element to the queue will do?) to implement (1).

For instance, I'd consider using a plain std::deque. It can add/remove elements from the beginning/end of the queue in constant time. It's also very easy to get a sorted view on the window, e.g. if copying the elements of the queue is cheap you could use std::sort like:

std::vector<Elem> sortedView( queue.begin(), queue.end() );
std::sort( sortedView.begin(), sortedView.end() );

...you could of course also do something more clever by not copying the data but rather creating a vector of iterators into the queue, or by using a different sorting algorithm like partial_sort.

Solution 2

If you just want to keep a sorted queue, take a look at priority_queue.

Comments

[Benjamin Lindley]

If you're going to push the elements back onto the queue like that, it will never be empty, and so your loop will never terminate. Use a for loop counting up to Q.size() instead.

[maditya]

@BenjaminLindley Crap. Initially I had just the pop(), I added the pushing back as an afterthought. Should have tested ...

[Frerich Raabe]

Your numPops is declared twice; I guess if you wanted to be really pedantic, you'd declare it as std::queue<int>::size_type since that's what Q.size() returns - or just use auto with C++11.

[maditya]

@FrerichRaabe Thanks, fixed. This is why I shouldn't attempt to start the day without coffee.