0

I know that std::deque has the different chunks of contiguous memory and iterator is invalidated by inserting or erasing the middle of deque.

In addition to it, if I insert to the end side of element of deque, iterator is not valid but reference is valid.

There are some other unintuitive behavior of iterator of deque. Refer to the link below.

enter link description here

I'm very curious why does the iterator should work like that. If I know the underlying data structure of deque, I can clearly understand it. But I can't find any detailed explanation of how does std::deque works yet.

Could anyone explain the underlying data structure of std::deque and why it's iterator works like that ?

myoldgrandpa
  • 871
  • 7
  • 21
  • "In addition to it, if I insert to the end side of element of deque, iterator is not valid but reference is valid." what do you mean by that? DO you refer to ["All iterators, including the past-the-end iterator, are invalidated. References are invalidated too, unless pos == begin() or pos == end(), in which case they are not invalidated. "](https://en.cppreference.com/w/cpp/container/deque/insert) ? – 463035818_is_not_an_ai May 06 '22 at 11:48
  • 1
    pedantically the actual reasoning is the other way around. The standard specifes how a `deque` should behave and then implementations can implement whatever that meets the specification. Of course the specification is written with some implementation in mind, but when the standard says: Inserting elements invalidates iterators, then that is the reason why iterators are invalidated – 463035818_is_not_an_ai May 06 '22 at 11:50
  • Related, possibly dupes: [Why does push_back or push_front invalidate a deque's iterators?](https://stackoverflow.com/q/913070/580083), [What really is a deque in STL?](https://stackoverflow.com/q/6292332/580083) – Daniel Langr May 06 '22 at 11:52
  • @463035818_is_not_a_number I refered to https://en.cppreference.com/w/cpp/container. I know what you mean, but the behavior of iterator of std::deque could have some reason based on it's underlying data structure. That's what I want to know. – myoldgrandpa May 06 '22 at 12:03
  • 2
    Short answer: A deque needs to keep the information about the allocated chunks. This information is typically stored in an array (called a _map_). Iterators need to be able to traverse chunks, therefore, they keep the information related to this array as well (libstdc++ link: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_deque.h#L145). When the number of chunks grow, the array may need to be reallocated. This invalidates iterators. – Daniel Langr May 06 '22 at 12:05
  • @DanielLangr For the case that inserting to the both end of deque, you makes me clear. But how can you explain modifying the middle of deque makes both reference and iterator invalidated? – myoldgrandpa May 06 '22 at 12:17
  • @myoldgrandpa Because inserting to the middle reuiqres to shift the elements from the inserted position to the end. (It's a bit similar to insertion into the ordinary array/vector.) – Daniel Langr May 06 '22 at 12:38

1 Answers1

3

The key point is that a deque is made of several chunks of contiguous memory.

When you add an element in the first position then there are two situations:

Either the first chunk has still place to add an element:

 |   |   | first element | second element | .... | ...
       ^
       inserted element can be placed here

Or there is no place in the first chunk, then the inserted element is placed in a different chunk that was empty before the insertion.

In both cases, the elements that were already in the container need not be moved in memory. Hence references to them are still valid. Iterators are different, because they need addtional book-keeping (for example to reach the next chunk when you increment an iterator to the last element in a contiguous chunk). The same holds for inserting an element at the end. Inserting elements in the middle however requires to rearrange already existing elements.

463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
  • My understanding is that deque consists of chunks and map of chunks. If inserting happens to chunk both reference and iterator is invalidated, if inserting happens to map, only iterator is invalidated. – myoldgrandpa May 07 '22 at 00:58