How is deque implemented in c++ stl

Question

I just wanted to know how deque is implemented and how are the basic operations like push_front and random access operator are provided in that implementation.

From [this `std::deque` reference](https://en.cppreference.com/w/cpp/container/deque): "typical implementations use a sequence of individually allocated fixed-size arrays". In short, it's a list of arrays. — Some programmer dude, May 27 '19 at 07:45
Possible duplicate of [What really is a deque in STL?](https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl) — Silvano Cerza, May 27 '19 at 07:52
@Someprogrammerdude if it was implemented as a "list" of arrays, the constant random access wouldn't be possible. Typically it is an array of pointers to arrays with data. — Dmitry Kuzminov, May 27 '19 at 07:53

score 3 · Accepted Answer · answered May 27 '19 at 08:15

I just wanted to know how deque is implemented

It's always a good to have an excuse for doing ASCII art:

+-------------------------------------------------------------+                       
| std::deque<int>                                             |                       
|                                                             |                       
|  subarrays:                                                 |                       
| +---------------------------------------------------------+ |                       
| |           |           |           |         |           | |                       
| | int(*)[8] | int(*)[8] | int(*)[8] |int(*)[8]|int(*)[8]  | |                       
| |           |           |           |         |           | |                       
| +---------------------------------------------------------+ |                       
|                        /            \                       |                       
|                       /              \                      |                       
|                      /                \                     |                       
|                     /                  \                    |                       
|                    /                    \                   |                       
|                   /                      \                  |                       
|                  /                        \                 |                       
|                 /                          \                |                       
|                -                            -               |                       
|               +------------------------------+              |                       
|               | ?, ?, 42, 43, 50, ?, ?, ?, ? |              |                       
|               +------------------------------+              |                       
|                                                             |
| additional state:                                           |                       
|                                                             |                       
| - pointer to begin of the subarrays                         |                       
| - current capacity and size                                 |                       
| - pointer to current begin and end                          |                       
+-------------------------------------------------------------+

how are the basic operations like push_front and random access operator are provided in that implementation?

First, std::deque::push_front, from libcxx:

template <class _Tp, class _Allocator>
void
deque<_Tp, _Allocator>::push_front(const value_type& __v)
{
    allocator_type& __a = __base::__alloc();
    if (__front_spare() == 0)
        __add_front_capacity();
    __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v);
    --__base::__start_;
    ++__base::size();
}

This obviously checks whether the memory already allocated at the front can hold an additional element. If not, it allocates. Then, the main work is shifted to the iterator: _VSTD::addressof(*--__base::begin()) goes one location before the current front element of the container, and this address is passed to the allocator to construct a new element in place by copying v (the default allocator will definitely do a placement-new).

Now random access. Again from libcxx, std::deque::operator[] (the non-const version) is

template <class _Tp, class _Allocator>
inline
typename deque<_Tp, _Allocator>::reference
deque<_Tp, _Allocator>::operator[](size_type __i) _NOEXCEPT
{
    size_type __p = __base::__start_ + __i;
    return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size);
}

This pretty much computes an index relative to some start index, and then determines the subarray and the index relative to the start of the subarray. __base::__block_size should be the size of one subarray here.

Any idea what is the purpose of the subarrays rather than using just a single array? — Qwert Yuiop, Nov 30 '22 at 19:32
It guarantees that iterators/references into the data structure aren't invalidated when adding/removing elements. The standard imposes this behaviour. — lubgr, Dec 01 '22 at 16:32
What am I missing then? How do the subarrays solve it? If I just have a single resizable array with pointers to the data, they don't invalidate the references either. — Qwert Yuiop, Dec 01 '22 at 18:55
They do. If you search for "C++ vector iterator invalidation" or something similar you'll quickly find an explanation why this happens. — lubgr, Mar 07 '23 at 22:11
@QwertYuiop When dynamic array runs out of capacity, the whole contiguous block must be reallocated, moving the elements to a new location in memory. When deque runs out of capacity, it is enough to allocate a new block and prepend/append it to existing ones. — marski, May 31 '23 at 17:07
@marski, when the dynamic array allocates a new block and copies the pointers from the old block to the new block, the data itself is still in the same place, so pointers to them are not invalidated. — Qwert Yuiop, Jun 05 '23 at 14:04
@QwertYuiop Dynamic array holds values not pointers to values. If you copy a value to a different block, it lives under a different address. — marski, Jun 06 '23 at 09:21
@marski, yeah so my comment was that if you used a vector of pointers instead, you wouldn't invalidate references either. So where do the subarrays come in, why are they needed? — Qwert Yuiop, Jun 06 '23 at 14:46
@QwertYuiop Storing pointers to *single* elements would defeat the biggest advantage of the array: memory locality of a contiguous memory block. You can look at chunked design as storing pointers to *multiple* contiguous elements to get a balanced compromise. Many data structures, such as B-trees, tries and ropes use a similar principle. In a similar manner AoSoA is a compromise between AoS and SoA. — marski, Jun 07 '23 at 15:14

How is deque implemented in c++ stl

1 Answers1