C++ default implementation of stack and queue

  • A+
Category:Languages

In C++ Primer 5th, it says that the default implementation of stack and queue is deque.

I'm wondering why they don't use list? Stack and Queue doesn't support random access, always operate on both ends, therefore list should be the most intuitive way to implement them, and deque, which support random access (with constant time) is somehow not necessary.

Could anyone explain the reason behind this implementation?

 


With std::list as underlying container each std::stack::push does a memory allocation. Whereas std::deque allocates memory in chunks and can reuse its spare capacity to avoid the memory allocation.

With small elements the storage overhead of list nodes can also become significant. E.g. std::list<int> node size is 24 bytes (on a 64-bit system), with only 4 bytes occupied by the element - at least 83% storage overhead.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: