I'm writing an application in C++, where it's critical to have O(1) Dequeue operation for a Priority Queue, while it's not so important the complexity of Enqueue (well unless it becomes n^2 or 2^n of course) .
At first I used a linked list. It was very good for Dequeue (O(1)), and it had good enqueue complexity. The only problem was, sorting it. Not the fact that using Insertion Sort, with O(n) complexity it would have suited my needs. But sorting a linked list is a pain. It was sloooow.
A vector isn't good at all. Dequeue would be O(n) to move all elements a place back. Enqueue would be still O(n) but much faster.
Can you suggest more performant method? Thanks.