10

As read on cplusplus.com, std::queue is implemented as follows:

queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed into the "back" of the specific container and popped from its "front".

The underlying container may be one of the standard container class template or some other specifically designed container class. This underlying container shall support at least the following operations:

......

The standard container classes deque and list fulfill these requirements. By default, if no container class is specified for a particular queue class instantiation, the standard container deque is used.

I am confused as to why deque (a double-ended-queue on steroids) is used as a default here, instead of list (which is a doubly-linked list).

It seems to me that std::deque is very much overkill: It is a double-ended queue, but also has constant-time element access and many other features; being basically a full-featured std::vector bar the 'elements are stored contiguously in memory' guarantee.

As a normal std::queue only has very few possible operations, it seems to me that a doubly-linked list should be much more efficient, as there is a lot less plumbing that needs to happen internally.

Why then is std::queue implemented using std::deque as default, instead of std::list?

Qqwy
  • 5,214
  • 5
  • 42
  • 83
  • Possible duplicate of [Which STL container should I use for a FIFO?](http://stackoverflow.com/questions/1262808/which-stl-container-should-i-use-for-a-fifo) – nrussell Dec 12 '16 at 13:59
  • 1
    @nrussell whilst the answer to that question definitely touches on the subject of this question (and possibly answers it partially or fully), the _question_ that was asked in 'Which STL container should I use for a FIFO' is undoubtedly very different. – Qqwy Dec 12 '16 at 14:06
  • 1
    As I understand, this is sufficient for marking something as a duplicate; the *questions* themselves don't necessarily need to be duplicates. The TLDR of the accepted answer is "`std::deque` has a(n) (arguably) more favorable memory allocation strategy and is more cache friendly", and I think that answers your question pretty well. – nrussell Dec 12 '16 at 14:08

2 Answers2

11

Stop thinking of list as "This is awkward to use, and lacks a bunch of useful features, so it must be the best choice when I don't need those features".

list is implemented as a doubly-linked list with a cached count. There are a narrow set of situations where it is optimal; when you need really, really strong reference/pointer/iterator stability. When you erase and insert in the middle of a container orders of magnitude more often than you iterate to the middle of a container.

And that is about it.

The std datatypes were generally implemented, then their performance and other characteristics analyzed, then the standard was written saying "you gotta guarantee these requirements". A little bit of wiggle room was left.

So when they wrote queue, someone probably profiled how list and deque performed and discovered how much faster deque was, so used deque by default.

In practice, someone could ship a deque with horrible performance (for example, MSVC has a tiny block size), but making it worse than what is required for a std::list would be tricky. list basically mandates one-node-per-element, and that makes memory caches cry.

T.C.
  • 133,968
  • 17
  • 288
  • 421
Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
7

The reason is that deque is orders of magnitude faster than list. List allocates each element separately, while deque allocates large chunks of elements.

The advantage of list is that it is possible to delete elements in the middle, but a queue does not require this feature.

Sven Nilsson
  • 1,861
  • 10
  • 11
  • While the point about allocation is an interesting one that I did not know about, one is allowed to provide their own Allocator, so I question if that is really a reason. I think a full answer would point to committee proceedings or other committee communication. – AndyG Dec 12 '16 at 14:13
  • Yeah, deque can also be more memory efficient (less overhead) compared to list, but there are no guarantees – Sven Nilsson Dec 12 '16 at 14:26
  • 5
    And by large chunks, on MSVC we mean small chunks. – Yakk - Adam Nevraumont Dec 12 '16 at 14:39
  • 1
    large chunks is a gross overstatement. If you look at gcc STL queue, the size of bucket is 512 bytes (or the size of the object if it is bigger). There is nothing large about it when we are talking about even moderately sized objects. – SergeyA Dec 12 '16 at 14:52