std::deque 的底层数据结构是什么？它的迭代器是如何工作的？
What is underlying data structure of std::deque and how does it's iterator work?
我知道 std::deque 具有不同的连续内存块，并且通过插入或擦除双端队列的中间部分使迭代器失效。
除此之外，如果我插入到双端队列元素的末尾，迭代器无效但引用有效。
双端队列的迭代器还有其他一些不直观的行为。参考下面的link。
我很好奇为什么迭代器会那样工作。如果我知道deque的底层数据结构，我就能清楚地理解它。但是我找不到任何关于 std::deque 是如何工作的详细解释。
谁能解释一下 std::deque 的底层数据结构以及为什么它的迭代器是这样工作的？
关键点是双端队列由几块连续的内存组成。
当你在第一个位置添加一个元素时，有两种情况：
要么第一个块还有地方可以添加元素：
| | | first element | second element | .... | ...
^
inserted element can be placed here
或者第一个chunk中没有位置，则插入的元素放在插入前为空的不同chunk中。
在这两种情况下，已经在容器中的元素不需要在内存中移动。因此，对它们的引用仍然有效。迭代器是不同的，因为它们需要额外的 book-keeping （例如，当您将迭代器递增到连续块中的最后一个元素时到达下一个块）。这同样适用于在末尾插入一个元素。然而，在中间插入元素需要重新排列已经存在的元素。
我知道 std::deque 具有不同的连续内存块，并且通过插入或擦除双端队列的中间部分使迭代器失效。
除此之外，如果我插入到双端队列元素的末尾，迭代器无效但引用有效。
双端队列的迭代器还有其他一些不直观的行为。参考下面的link。
我很好奇为什么迭代器会那样工作。如果我知道deque的底层数据结构，我就能清楚地理解它。但是我找不到任何关于 std::deque 是如何工作的详细解释。
谁能解释一下 std::deque 的底层数据结构以及为什么它的迭代器是这样工作的？
关键点是双端队列由几块连续的内存组成。
当你在第一个位置添加一个元素时，有两种情况：
要么第一个块还有地方可以添加元素：
| | | first element | second element | .... | ...
^
inserted element can be placed here
或者第一个chunk中没有位置，则插入的元素放在插入前为空的不同chunk中。
在这两种情况下，已经在容器中的元素不需要在内存中移动。因此，对它们的引用仍然有效。迭代器是不同的，因为它们需要额外的 book-keeping （例如，当您将迭代器递增到连续块中的最后一个元素时到达下一个块）。这同样适用于在末尾插入一个元素。然而，在中间插入元素需要重新排列已经存在的元素。