What is the best way to assign elements from queue to priority queue?

[woohyeon]

I made the following function called rearrangeSomething. I want to move all element from a queue to a priority queue.

I think it's slow if I implement a function like the following. but I have no idea the other way. is it the best way?

this function called quite often.

// member variable
// std::priority_queue<T> pq;
// sdt::queue<T> q

template <typename T>
void rearrangeSomething(std::queue<T> q) // bring queue you want as a copy
{
   pq = std::priority_queue<T>(); // to remove existing elements
   while(!q.empty())
   {
      pq.push(q.front());
      q.pop();
   }
}

[kbw]

Why do you think it's slow?

[woohyeon]

@ kbw

Um.. maybe I think I want a magic haha..

I thought the cycle that push & pop is slow, but now I think it's the only way to access queue's element

[jonnin]

you can push to pq whenever you push to q as data comes in. Its not 'better' but it distributes the workload so that you don't get a stop to iterate slowdown spike all at once. But you would need to be moving, what, a million+ (or *very* inefficient to copy objects??) items before iteration even registered to the user that it needed a fraction of a second to do it. Most likely you are doing that premature optimize thing :P

you could also just load pq to begin with and stop putting it into q where you apparently didn't want it to be? Is this a design flaw?

[doug4]

@OP,

You really need to decide if std::queue is the correct data structure for you. The fact that you are copying the input argument may be as much of a waste as the push/pop loop.

(BTW, use a profiler to see if there actually are performance issues before you try to fix something that isn't broken. That's what @jonnin means by "that premature optimize thing".

If you need to preserve the caller's version of the input and also put it into a std::priority_queue, consider making the original a std::deque. Pass the argument in as a const& and iterate over it while populating the std::priority_queue. No copy. No popping.

[jonnin]

^^^ That is slick. I have not spend enough time on the Q tools and would not have easily found that trick!