A priority queue container should be implemented as a special kind of vector container, where push = (vector push_back and incremental sort) and pop = vector pop_back (pop the highest priority values from the container).
A priority deque container should be implemented as a special kind of deque container, where push = (deque push_back and incremental sort), pop_back = deque_pop_back (pop highest priority entry from container), and pop_front = deque_pop_front (pop lowest priority entry from container).
Actually, I now think priority queue and priority deques should be discarded in favour of a menagerie of containers that each express a different underlying implementation, e.g. std/splay_tree etc
A priority queue container should be implemented as a special kind of vector container, where push = (vector push_back and incremental sort) and pop = vector pop_back (pop the highest priority values from the container).
A priority deque container should be implemented as a special kind of deque container, where push = (deque push_back and incremental sort), pop_back = deque_pop_back (pop highest priority entry from container), and pop_front = deque_pop_front (pop lowest priority entry from container).