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.
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 ?
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.