title: What is the best data structure to extract elements in descending order in O(1) time
body: <p>I insert elements as we do a certain operation and try to get the elements in the order of insertion(which is considered the element's age). <code>priority_queues</code> could be used but since they are implemented as heaps, the operation to visit the top element is O(1), but to get the next element in the next iteration I have to do a <code>pop()</code> along with the call to <code>top()</code>. <code>pop()</code> is log(n). I am thinking if I should just use a regular <code>queue</code> to add elements whenever I would add it into the <code>priority_queue</code> and keep <code>pop</code>ing from the queue to get elements in the order of their addition time. My confusion is that since we have a multi-threaded application, could there be elements out of order and so would be safe to visit all elements to make sure. This would make it <code>O(n)</code>. Can somebody help me in my choice of the data structure to use? </p>
  
  <p>Should I just go ahead with a <code>priority_queue</code> and get elements in <code>O(log n)</code> everytime? Or use a stack and assume the guarantee of the order of elements and get elements in O(1) everytime? Or use a totally different data structure?</p>
  
  <p>Please keep in mind that this is implemented in VC++ and have access to boost.</p>
  
  <p>Would like views on this. Thanks!</p>