当迭代器在双端队列中失效时，引用如何有效

Question

我在理解这个概念时遇到了一些困难。从这个线程here它指出

双端队列要求在前面或后面的任何插入都应保持对成员元素的任何引用有效。迭代器失效是可以的，但成员本身必须留在内存中的同一位置。

我对这个线程的印象是

指针实际上是一种迭代器。事实上，对于一些容器类型，对应的迭代器可以简单地实现为一个指针。

如果我们有一个指针和一个迭代器，它们都引用容器的相同元素，那么任何使一个无效的操作都会使另一个无效。

所以如果一个迭代器失效，那么引用也会失效。我的问题是这怎么可能。如果指向某个内存地址的迭代器无效，那么对该地址的引用如何有效？

更新：

我知道双端队列是由随机内存块实现的，这些内存块由独立的数据结构（例如动态数组）跟踪。但是，我很难理解迭代器如何无效但引用可能有效，因为迭代器本质上是数据结构内容的通用指针。这让我认为迭代器可能指向其他东西，而指针指向实际项目？考虑下面的向量图。

根据我在上图中对向量的理解，如果指针的内容发生变化，迭代器也会发生变化。deque 有什么不同。

Answer 1

Think of a deque in terms of the following:

template<typename T>
struct deque_stub {
 using Page = std::array<T, 32>; // Note: Not really, rather uninitialised memory of some size;
 std::vector<std::unique_ptr<Page>> pointers_to_pages;
 std::size_t end_insert{32};
 std::size_t start_elem{0};
 // read further
};

A deque is basically some container, storing pointers to pages which contain some elements. (The start_elem and end_insert members are to keep track of where, in terms of offset into a page, the valid range of elements starts and ends.)

Insertion eventually changes this container, when a new page is needed:

template<typename X>
void push_back(X&& element) {
 if (end_insert == 32) {
  // get a new page at the end
  pointers_to_pages.push_back(make_unique<Page>());
  end_insert = 0;
 }
 (*(pointers_to_pages.back()))[end_insert] = std::forward<X>(element);
 ++end_insert;
}

template<typename X>
void push_front(X&& element) {
 if (start_elem == 0) {
  pointers_to_pages.insert(
    pointers_to_pages.begin(), std::make_unique<Page>());
  start_elem = 32;
 }
 --start_elem;
 (*(pointers_to_pages.front()))[start_elem] = std::forward<X>(element);
}

An iterator into that deque needs to be able to "jump" across pages. The easiest way to achieve this is by having it keep an iterator to the current page it is in from the container pointers_to_pages:

struct iterator {
 std::size_t pos;
 std::vector<std::unique_ptr<Page>>::iterator page;
 // other members to detect page boundaries etc.
};

But since that page iterator, the iterator into the vector, may get invalidated when the vector gets changed (which happens when a new page is needed), the whole iterator into the deque might get invalidated upon insertion of elements. (This could be "fixed" by not using a vector as container for the pointers, though this would probably have other negative side effects.)

As an example, consider a deque with a single, but full page. The vector holding the pointers to pages thus holds only a single element, let's say at address 0x10, and let's further assume that its current capacity is also only 1 element. The page itself is stored at some address, let's say 0x100.

Thus the first element of the deque is actually stored at 0x100, but using the iterator into the deque means first looking at 0x10 for the address of the page.

Now if we add another element at the end, we need a new page to store that. So we allocate one, and store the pointer to that new page into the vector. Since its capacity is less than the new size (1 < 2), it needs to allocate a new larger area of memory and move its current contents there. Let's say, that new area is at 0x20. The memory where the pointers have been stored previously (0x10) is freed.

Now the very same element from above before the insertion is still at the same address (0x100), but an iterator to it would go via 0x20. The iterator from above, accessing 0x10, is thus invalid.

由于元素位于相同的地址，因此指向它的指针和引用仍然有效且困难。