隨機訪問迭代器無效迭代器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

回答

相關問題