std::queue, std::stack, std::priority_queue are NOT sequence containers, instead, they are wrappers around std::deque, and std::vector to provide a restricted interface. (FIFO for queue, LIFO for stack). The common interface we examine are:
push,poptop,front- No iterators or allow traversals.
std::queue vs std::deque
std::queue<LoopCandidate> loop_candidate_queue_; vs std::deque
std::queue<T>is a restricted interface (adapter). By default it’s implemented on top ofstd::deque<T>.- Ops you get:
push,emplace,front,back,pop,empty,size - You can’t iterate, index, erase arbitrary elements, etc.
- It clearly communicates intent: this is FIFO, don’t poke at it.
- Ops you get:
std::deque<T>is a general-purpose container (double-ended queue).- Ops you get: everything above plus iteration,
operator[],insert/erase(in middle),push_front, etc. - More flexible, but easier for callers (including future you) to accidentally rely on non-FIFO behavior.
- Ops you get: everything above plus iteration,
Performance (practical view)
std::queue<T>adds essentially no runtime overhead vs using the underlying container directly; it’s just a thin wrapper.- Both
std::dequeand astd::queue-over-dequegive amortized O(1) push/pop at ends. - amortized (on average) std::queuewon’t magically be faster; it just prevents misuse.
