iterator vs reverse_iterator

Question

我使用std::map來存儲很多元素（元素對），我有一個「小」的疑問。迭代我的std::map，iterator或reverse_iterator上的所有元素會更有效嗎？

Answer 1

真的很重要嗎？這些是你必須儘量避免恕我直言的微觀優化類型。此外，即使迭代時間在地圖上的大量元素中發生變化，您嘗試遍歷如此大地圖的所有元素的事實意味着最有可能您選擇了錯誤的數據結構。

Answer 2

除非你對你的代碼進行了剖析，發現它們之間存在顯着差異，否則我就不會關心它。

「不成熟的優化是所有邪惡的根源。」 - Donald Knuth

Answer 3

可能沒有區別。 std :: reverse_iterator只是一個在編譯時將++轉換爲 - 的模板填充程序。

對於一個向量或其他連續的存儲容器，前向迭代器可能與緩存的交互性要好於反向迭代器（不太可能會檢測到），但對於基於樹的容器，根本沒有任何區別 - 不會有任何地方提到利用。

Answer 4

我認爲使用reverse_iterator沒有意義;這是違反直覺的。

這會讓代碼更難理解，有人會看代碼並轉到「wtf」;如果你需要發表評論來解釋爲什麼，這可能意味着它不是最好的代碼。

Answer 5

我想知道是否需要迭代。 Map包含鍵值對，通常用於查找。如果由於某些原因仍然需要迭代地圖（可能會刪除地圖中包含的指針等），那麼您可以使用std::for_each。忘記微觀優化，你可以嘗試增加代碼的可讀性。

Answer 6

爲了記錄在案，提領reverse_iterator上std::map和std::set容器是慢一倍爲使用iterator - 既-O3 GCC 3.4.6和MSVC在Intel/AMD處理器（幾乎3倍於PPC慢）同樣適用於const_reverse_iterator與const_iterator。這是因爲reverse_iterator實際上是指向緊接樹節點的樹節點將被解除引用，因此需要額外的工作。 std::vector迭代器展現出非常溫和的差異（reverse_iterator在PPC上只有〜30％較慢，在Intel/AMD上幾乎沒有區別。）順便說一句，迭代器的迭代器速度比迭代器的迭代器速度快20倍。

#include <set> 
#include <vector> 
#include <stdio.h> 
#ifdef _WIN32 
#include <sys/timeb.h> 
#else 
#include <sys/time.h> 
#endif 
#include <time.h> 

#define CONTAINER std::set<int> 

double 
mygettime(void) { 
# ifdef _WIN32 
    struct _timeb tb; 
    _ftime(&tb); 
    return (double)tb.time + (0.001 * (double)tb.millitm); 
# else 
    struct timeval tv; 
    if(gettimeofday(&tv, 0) < 0) { 
    perror("oops"); 
    } 
    return (double)tv.tv_sec + (0.000001 * (double)tv.tv_usec); 
# endif 
} 


int main() { 
    int i, x = 0; 
    CONTAINER bla; 
    for (i = 0; i < 10000; bla.insert(bla.end(), i++)) ; 

    double t1 = mygettime(); 

    for (i = 0; i < 100; ++i) { 
    for (CONTAINER::iterator it = bla.begin(); it != bla.end(); ++it) { 
     x ^= *it; 
    } 
    } 

    printf("forward: %f\n", mygettime() - t1); 

    double t2 = mygettime(); 

    for (i = 0; i < 100; ++i) { 
    for (CONTAINER::reverse_iterator it = bla.rbegin(); it != bla.rend(); ++it) { 
     x ^= *it; 
    } 
    } 

    printf("reverse: %f\n", mygettime() - t2); 

    return 0; 
}