Search code examples
c++stldeque

std::deque is contiguous memory container or not?


std::deque is contiguous memory container or not ?

The famous book Effective STL by Scott Meyers says like below

Contiguous-memory containers (also known as array-based containers] store their elements in one or more (dynamically allocated) chunks of memory, each chunk holding more than one container element. If a new element is inserted or an existing element is erased, other elements in the same memory chunk have to be shifted up or down to make room for the new element or to fill the space formerly occupied by the erased element. This kind of movement affects both performance (see Items 5 and 14) and exception safety (as we'll soon see). The standard contiguous-memory containers are vector, string, and deque. The nonstandard rope is also a contiguous-memory container.

But you can find opposite explanation in cppreference.com

As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector's indexed access which performs only one.

Which one is true ?


Solution

  • There is no conflict between the two quotes. Scott uses the term "contiguous container" in a sense a little wider than you might have seen it used elsewhere.

    Scott writes (emphasize mine):

    Contiguous-memory containers (also known as array-based containers] store their elements in one or more (dynamically allocated) chunks of memory, [...]

    As the quote from cppref states, std::deque uses multiple arrays to store the elements. Within each array the elements are contiguous. Scott does not claim that all elements in a std::deque are contiguous in one chunk of memory.