向量索引訪問與迭代器訪問的效率

Question

我有問題糾正我通過使用索引訪問（使用運算符[]）或使用迭代器訪問向量元素的效率的理解。

我的理解是「迭代器」比「索引訪問」更有效率。 （我認爲vector::end()比vector::size()更有效）。

現在我寫示例代碼測量它（在Windows 7下使用Cygwin，使用g ++ 4.5.3）

索引接入環路版本（以前標記爲隨機接入）：

int main() 
{ 
    std::vector<size_t> vec (10000000); 
    size_t value = 0; 

    for(size_t x=0; x<10; ++x) 
    { 
    for (size_t idx = 0; idx < vec.size(); ++idx) 
    { 
     value += vec[idx]; 
    } 
    return value; 
    } 
} 

該迭代循環代碼是這樣的：

for (std::vector<size_t>::iterator iter = vec.begin(); iter != vec.end(); ++iter) { 
     value = *iter; 
    } 

我很驚訝地看到「索引訪問」版本更快。我使用time命令來「測量」。數量分別爲：

結果使用g++ source.cpp（不優化） 索引訪問

真正的800ms

迭代器訪問

真正2200ms

，這些數字有意義嗎？ （我拉肚子多次重複的），我不知道什麼細節我想，爲什麼我錯了......

結果使用G ++ -02 索引訪問，時間真：〜200ms的

迭代器訪問，真實時間：〜200毫秒

我重複不同的平臺上測試（AMD64瓦特/ g ++以及POWER7瓦特方xIC）和看到，我使用的所有時間優化的代碼的示例方案也有類似的執行時間。

編輯更改代碼以添加值（value += *iter）而不是僅使用賦值。增加了關於編譯器選項添加了使用-O2的新號碼。 * edit2將標題改爲「迭代器效率」改爲「訪問效率」。

Answer 1

沒有看到測試線束，編譯器選項以及您如何測量時間，很難說什麼。此外，一個好的編譯器可以在一種情況下或另一種情況下消除循環，因爲循環具有 對返回的值沒有影響。儘管如此，依賴於 的實現，我不會驚訝地發現迭代器顯着地比索引更快（反之亦然）。

關於「理解」，關於迭代器類型及其性能沒有任何內在的含義。您可以編寫快速或非常慢的轉發迭代器 ，就像您可以編寫非常快或非常慢的迭代器一樣。在全球範圍內，將支持隨機訪問迭代器的數據類型可能比沒有訪問迭代器的數據類型具有更好的局部性，這可能有利於 隨機訪問迭代器;但這實在不足以使 有任何合理的概括。

Answer 2

通過優化，兩個代碼應該（近似）相同。嘗試-O2。

如果不進行優化並添加調試信息，您的測量結果將非常具有誤導性。

Answer 3

當我用-O2（Linux，GCC 4.6.1）編譯這兩個程序時，它們的運行速度同樣快。

然後：你的第一個程序是使用迭代器，它使用指數不。這些是不同的概念。

你的第二個程序實際上是使用隨機訪問迭代器，因爲那是std::vector<T>::iterator。對std::vector的限制是這樣設計的，即迭代器可以被實現爲一個簡單的指針到一個vector封裝的動態數組中。

begin應該和size一樣快。 std::vector的典型實現中兩者之間的唯一區別在於end可能需要計算begin() + size()，但size也可以實現爲（大致）end() - begin()。不過，編譯器可能會優化循環。

Answer 4

在第一個示例中，您使用value = vec[idx];取消引用每個單獨的項目，這會導致每次訪問元素時計算偏移量element_size * index。由於矢量是由連續的內存塊中排列的元素組成的，所以矢量迭代器通常只是作爲一個簡單的指針來實現，所以迭代遍歷一個矢量（就像在第二個例子中一樣）只需要將指針前進一個元素每次迭代後。然而，如果啓用優化（嘗試-O2或-O3），則編譯器可能會優化第一個示例中的循環，類似於第二個示例，從而使性能幾乎相同。

Answer 5

實際上，我發現迭代器更快。嘗試重構你的迭代循環，類似於下面的東西，你可能會看到這個問題，以及：

#include <ctime> 
#include <vector> 
#include <iostream> 
using namespace std; 

int main() 
{ 
    std::vector<size_t> vec (1000000); 
    size_t value = 0; 
    srand (time(NULL)); 
    clock_t start,stop; 
    int ncycle = 10000; 

    start = std::clock(); 
    for(size_t x=0; x<ncycle; ++x) { 
    for (size_t idx = 0; idx < vec.size(); ++idx) 
     vec[idx] += rand(); 
    } 
    stop = std::clock(); 
    cout << start << " " << stop << endl; 
    cout << "INDEX: " << (double((stop - start))/CLOCKS_PER_SEC)/ncycle << " seconds per cycle" << endl; 

    start = std::clock(); 
    for(size_t x=0; x<ncycle; ++x) { 
    for (std::vector<size_t>::iterator iter = vec.begin(), end = vec.end(); iter != end; ++iter) 
     *iter += rand(); 
    } 
    stop = std::clock(); 
    cout << "ITERATOR: " << (double((stop - start))/CLOCKS_PER_SEC)/ncycle << " seconds per cycle" << endl; 
} 

結果在我的電腦下面，顯示出迭代器有一個微弱的領先優勢：

INDEX: 0.012069 seconds per cycle 
ITERATOR: 0.011482 seconds per cycle 

你應該注意我使用了rand（）;這可以防止編譯器優化出它可以在編譯時計算出來的東西。編譯器對於內在數組來說似乎比使用向量要容易得多，並且這會誤導性地給出數組相對於向量的優勢。

我用「icpc -fast」編譯了上面的代碼。當使用迭代器（ala指針）時，slavik正確地做了關於必須對指數進行計算與遞增計算的說法。