Inside STL: Understanding the Implementation of the deque in C++

The article provides an in-depth look into the implementation details of the deque in C++. The three major implementations of the standard library, including Microsoft Visual C++, gcc, and clang, maintain an array of pointers to blocks, which they refer to as a 'map'. The article highlights the differences in how spare blocks are handled by each implementation. The Microsoft Visual C++ implementation retains all spare blocks, while the gcc implementation frees blocks as soon as they become empty. The clang implementation retains one spare block at each end. Another interesting difference is how the map is treated as a circular array of blocks in the Microsoft Visual C++ implementation, eliminating the need for further allocations or element movement. It is important for developers to note that none of the implementations automatically shrink the map, requiring the use of 'shrink_to_fit()' to achieve this. The article also discusses the different formats used for iterators in each implementation. Overall, this article provides valuable insights into the inner workings of the deque in C++, helping developers understand its implementation and make informed decisions when using it in their projects.