In C++ Primer 5th, it says that the default implementation of
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?
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.