What really is a deque in STL?

by

A deque is somewhat recursively defined: internally it maintains a double-ended queue of chunks of fixed size. Each chunk is a vector, and the queue (“map” in the graphic below) of chunks itself is also a vector.

schematic of the memory layout of a deque

There’s a great analysis of the performance characteristics and how it compares to the vector over at CodeProject.

The GCC standard library implementation internally uses a T** to represent the map. Each data block is a T* which is allocated with some fixed size __deque_buf_size (which depends on sizeof(T)).

More Related Contents:

  1. Why would I prefer using vector to deque
  2. STL deque accessing by index is O(1)?
  3. c++ push reference node to stl list
  4. Erasing elements from a vector
  5. Why can’t I make a vector of references?
  6. Concise explanation of reference collapsing rules requested: (1) A& & -> A& , (2) A& && -> A& , (3) A&& & -> A& , and (4) A&& && -> A&&
  7. Template Specialization VS Function Overloading
  8. Is std::vector or boost::vector thread safe?
  9. remove_if equivalent for std::map
  10. Iteration over std::vector: unsigned vs signed index variable
  11. Using a STL map of function pointers
  12. A proper way to create a matrix in c++
  13. Why does C++ allow an integer to be assigned to a string?
  14. How to read a growing text file in C++?
  15. Why is value taking setter member functions not recommended in Herb Sutter’s CppCon 2014 talk (Back to Basics: Modern C++ Style)?
  16. Initial capacity of vector in C++
  17. std::vector iterator invalidation
  18. Non-copyable elements in vector
  19. How to make elements of vector unique? (remove non adjacent duplicates)
  20. How does overloading of const and non-const functions work?
  21. How can I use Standard Library (STL) classes in my dll interface or ABI?
  22. Does boost have a datatype for set operations that is simpler than the STL?
  23. How can i estimate memory usage of std::map?
  24. Memory allocation and deallocation across dll boundaries
  25. Incrementing iterators: Is ++it more efficient than it++? [duplicate]
  26. Can std::vector emplace_back copy construct from an element of the vector itself?
  27. what does `using std::swap` inside the body of a class method implementation mean?
  28. error for hash function of pair of ints
  29. STL algorithms: Why no additional interface for containers (additional to iterator pairs)?
  30. Why does (i|o)fstream take a const char* parameter for a file name?

Leave a Comment