緩存結束迭代器 - 好主意還是壞主意？

一般來說，爲了效率和速度的目的，緩存一個結束迭代器（特別是STL容器）是一個好主意嗎？例如在以下代碼位中：緩存結束迭代器 - 好主意還是壞主意？

std::vector<int> vint; 
const std::vector<int>::const_iterator end = vint.end(); 
std::vector<int>::iterator it = vint.begin(); 

while (it != end) 
{ 
    .... 
    ++it; 
}

在什麼情況下會使最終值失效？將從容器中刪除原因結束被取消全部 STL容器還是隻是一些？

來源

2010-06-21 Hippicoder

首先問自己，你的分析器告訴你std :: vector :: end（）的調用花費了大量的處理時間嗎？ – daramarak 2010-06-21 12:34:50

在vector的簡單情況下，當您向容器添加或移除元素時，迭代器將發生更改;儘管如此，假設如果在遍歷容器的同時改變容器，所有的迭代器都會失效，這通常是最安全的。迭代器可以在任何給定的STL實現中以不同的方式實現。

關於緩存迭代器 - 緩存它當然是有效的，但爲了確定它是否實際上更快，最好的方法是讓你分析代碼並查看。雖然檢索end迭代器從vector很可能是一個快速實現與最近的STL庫和編譯器，我有工作過去的項目，其中緩存迭代器給我們一個顯着的速度提升。（這是在PlayStation 2上，所以請盡情享用。）

來源

2010-06-21 12:03:17

從您當前迭代的容器中擦除始終是一個糟糕的主意。結束迭代器的實際緩存不會改變這一點。 h。

h。

來源

2010-06-21 11:17:25 haavee

一點都不，如果你做得對。例如，std :: vector的'erase'成員會返回一個合適的新迭代器。所以只要你正確地編寫你的代碼（也就是說，記住其他迭代器現在是無效的），你將不會從你正在迭代的容器中刪除問題。 – 2010-06-21 11:36:36

如果我們談論效率和速度：由於編譯器優化和內聯，緩存結束迭代器是不必要的。

來源

2010-06-21 11:28:03

真的嗎？我所看到的大多數使用STL算法的建議（如'for_each'）都會緩存'end'迭代器，因此在每次迭代時都不會計算。 – 2010-06-21 13:24:02

@Matthieu：迭代器不能保證在某些容器的修改過程中不能存活（例如，調整矢量無效化*全部*迭代器到矢量的大小）。 for_each不給函數對象訪問迭代器，容器不能改變，因此可以緩存迭代器。但是如果欺騙系統和函數對象以使迭代器無效的方式修改容器，那麼很顯然，當通過現在無效的迭代器訪問容器時，會導致* undefined behavior *，可能會崩潰。 – Dummy00001 2010-06-21 16:18:00

實際上，調整矢量大小隻會在迭代器發生重新分配時使迭代器失效，並且如果只調整容量，則可以確保它不會調整大小。但是我的問題仍然存在，我不確定編譯器是否能夠優化循環中'end（）'的計算，即使將編譯器作爲先驗內聯也無法知道該值是否可能得到據我所知，由循環內的操作修改。但後來我不太瞭解編譯器優化，因此我的問題:) – 2010-06-21 17:35:19

我經常使用這種風格的迭代容器：

// typedef std::vector<Person> Persons; 
Persons::iterator it = persons.begin(), end = persons.end(); 
for (; it != end; ++it) 
{ 
    Person & person = *it; 
    // ... 
}

刪除從向量元素無效擦除的位置畢竟迭代器。

我不確定其他容器類型。無論如何，我認爲假設所有迭代器在擦除後變得無效是安全的。如果你真的需要非常具體的信息，那麼你總是可以查看它。我很少需要這個，因爲我的編碼風格比較保守。

來源

2010-06-21 11:51:08 StackedCrooked

通常，緩存結束迭代器應該沒有關係。如果你覺得它確實很重要，那麼你應該已經在你的代碼中使用了一個分析器，並且能夠分析這兩個變體。我懷疑它會根據容器類型而有所不同 - 但是鑑於給定的編譯器，優化和STL供應商，分析器將是唯一可以確定的方法。

來源

2010-06-21 12:01:32

一般來說是一個好主意緩存的效率和速度目的的結束迭代器（特別是 STL容器）？

如果使用STL容器算法，無論如何都會發生結束迭代器的緩存（因爲您將container.end（）的結果作爲參數傳遞）。

如果修改容器的內存（插入/移除元素），這是一個壞主意。另外，高效緩存很少有意義：在大多數情況下，end（）是由編譯器內聯的，如果不是，那麼很可能您的效率不會掛在end（）結果上被緩存。 YMMV。

來源

2010-06-21 12:02:28 utnapistim

無效規則（對於迭代器）是爲每種類型的容器都非常明確地定義的。我發現SGI現場非常有用http://www.sgi.com/tech/stl/table_of_contents.html

具體而言爲載體我發現：

[5]時，其重新分配內存的矢量的迭代器被無效。另外，在向量中插入或刪除元素會使所有指向插入或刪除點後面元素的迭代器無效。因此，如果使用reserve（）預先分配向量將使用的儘可能多的內存，並且所有的插入和刪除都位於向量的末尾，則可以防止向量的迭代器失效。

來源

2010-06-21 15:17:07

緩存結束迭代器 - 好主意還是壞主意？

回答

相關問題