随机访问迭代器无效迭代器deque

我正在阅读Scott Meyers的有效STL。在第1项中，作者提及如何在各种容器中进行选择，下面是我很难理解的文本片段。随机访问迭代器无效迭代器deque

难道是有帮助的随机访问的顺序容器迭代器，其中的指针和引用数据不失效，只要没有被删除和插入只在容器的两端发生？这是一个非常特殊的情况，但如果你的情况是，那么deque就是你梦想中的容器。（有趣的是，双端队列的迭代可以被当插入在容器的端部仅由无效。双端队列为唯一的标准 STL容器，其迭代器可以在没有也无效它的指针和引用被无效。）

我上面的文字问题

是什么笔者在上述背景下指针和引用的意思和它是如何从不同的迭代器？
只有在最后插入时，deque的迭代器可能会失效，我们仍然有有效的指针和引用？

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

感谢您的时间和帮助。

来源

2012-11-20 venkysmarty

在开头或结尾插入不会更改内容的实际内存位置，因此任何指针或引用都将继续指向正确的对象。但是，如果迭代器存储为从头开始的偏移量，插入操作将使任何现有的迭代器都具有错误的偏移量。然而，这是一个完全的猜测，只是大声思考。 – BoBTFish

[为什么push \ _back或push \ _front使一个deque的迭代器失效？]（http://stackoverflow.com/questions/913070/why-does-push-back-or-push-front-invalidate-a -deques-iterators） – jrok

迭代器通常用于“循环”标准库容器的元素，就像使用数组索引（例如，在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将最后后指向一个“元件”一个块deque中的真实元素。如果你尝试了上述for循环，因为容器不“拥有”内存i“点”到这将是一个问题结束后有权这样做

*i = 88;

。

但是，梅耶斯可能会谈论的是，该标准留下了许多向设计师开放的实现。 Deques是通常是实现为拥有多个元素的内存块的链接列表，因此不像向量那样保证元素在内存中彼此相邻。此外，迭代器必须包含关于这些“块”的信息，以便它们可以平滑地遍历它们（即迭代器不仅仅是指针）。例如，如果我push_back()一个新的元素，但在“最后”的内存块中没有更多的空间，那么双转移将需要为新元素分配一个新的内存块（以及未来元素添加到结束）。由于我以前使用的迭代器可能不会“知道”这块新的内存，因此它可能是无效的。

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

int& j = *c.begin();

然后j是对第一个元素c的引用。如果我再做

c.push_front(74);

j还引用了以前的第一要素，即使它不再在双端队列的前面。

然而，如果插入双端队列中间的东西，那么很可能你被有效分裂的记忆那些连续块之一，要挤你的新的元素在里面。为了腾出空间，一方或另一方的元素必须在内存中进行洗牌（并且可能需要分配新的内存）。这必然会使插入的“侧”上的元素的指针/引用无效。由于要由实施者决定插入元素的确切空间，因此无论指向/插入的位置如何，所有投注都关闭。

来源

2012-11-20 13:50:02 llakais

如果我们push_front，我们可能会重新排列容器或分配新的内存垃圾，那么即使引用不再位于队列的前端，引用是如何有效的？ – venkysmarty

@venkysmarty该引用是有效的，因为它仍然引用一个有效的元素。该元素不再在前面，但参考仍然指向它。 'push_front'永远不会重新排列容器，但它可能会分配新的内存。重要的部分是过去在前面的元素保留在内存中。只是“前”的地址发生了变化。 – llakais

谢谢啦啦啦。现在我认为这很清楚。 – venkysmarty

在第一部分，什么意思是这样的：

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

对于第二部分，它已经涵盖在这里的细节：

Why does push_back or push_front invalidate a deque's iterators?

来源

2012-11-20 13:57:58

随机访问迭代器无效迭代器deque

回答

相关问题