4

我正在阅读 Scott Meyers 的有效 STL。在第 1 项中，作者提到了如何在各种容器中进行选择，下面是我难以理解的文本片段。

拥有一个带有随机访问迭代器的序列容器是否会有所帮助，只要没有任何内容被擦除并且插入仅发生在容器的末端，对数据的指针和引用就不会失效？这是一个非常特殊的情况，但如果是你的情况，deque 就是你梦想的容器。（有趣的是，当只在容器的末端进行插入时，deque 的迭代器可能会失效。deque 是唯一的标准 STL 容器，其迭代器可能会失效，而不会使其指针和引用也失效。）

我对上述文字的问题

  1. 作者在上述上下文中的指针和引用是什么意思，它与迭代器有什么不同？

  2. 当仅在末尾进行插入并且我们仍然有有效的指针和引用时，如何使双端队列的迭代器失效？

要求用简单的例子回答以上两个问题。

感谢您的时间和帮助。

4

2 回答 2

2

对于第一部分，意思是这样的：

deque<int> foo(10, 1); // a deque with ten elements with value of 1
int& bar = foo.front(); // reference
int* baz = &foo.front(); // pointer
deque<int>::iterator buz = foo.begin(); // iterator
deque.push_front(0); 
// At this point bar and baz are still valid, but buz may have been invalidated

对于第二部分，这里详细介绍了它：

为什么 push_back 或 push_front 使双端队列的迭代器无效？

于 2012-11-20T13:57:58.640 回答
1

迭代器通常用于“循环”标准库容器的元素，就像您对数组索引所做的那样，例如在for循环中。

迭代器可能由于多种原因而无效。发生这种情况的一种常见情况是当您使用for如下循环时：

std::deque<int> c;

for(std::deque<int>::iterator i = c.begin(); i != c.end(); ++i) {
    // do some stuff to the deque's elements here
}

在上述循环结束时，迭代器i将指向双端队列中最后一个实际元素后一个块的“元素”。如果你试图做类似的事情

*i = 88;

在上述for循环结束之后，这将是一个问题，因为容器不“拥有”内存i“指向”。

但 Meyers 可能谈论的是标准将 deque 的大部分实现留给设计者。双端队列通常实现为包含多个元素的内存块的链表，因此与向量不同，不能保证元素在内存中彼此相邻。此外，迭代器必须包含有关这些“块”的信息，以便它们可以顺利地遍历它们（即迭代器不仅仅是指针）。

例如，如果我push_back()有一个新元素，但“最后一个”内存块中没有更多空间，那么 deque 将需要为新元素（以及添加到末尾的未来元素）分配一个新的内存块。由于我之前使用的迭代器可能不“知道”这个新的内存块，它可能是无效的。

另一方面，引用和实际指针将在此上下文中用于引用/指向容器中的各个对象。如果我写

int& j = *c.begin();

那么 j 是对 的第一个元素的引用c。如果我这样做

c.push_front(74);

j仍然引用之前的第一个元素，即使它不再位于双端队列的前面。

但是，如果你在双端队列的中间插入一些东西，那么你很可能会有效地分割那些连续的内存块之一，并试图将你的新元素挤入其中。为了腾出空间，必须在内存中移动一侧或另一侧的元素（并且可能需要分配新的内存）。这必然会使对插入“一侧”的元素的指针/引用无效。由于如何为插入的元素准确地留出空间取决于实现者，所以对于任何指针/引用，所有赌注都是关闭的，无论它在哪里插入。

于 2012-11-20T13:50:02.170 回答