我正在使用 std::map
来存储很多元素(元素对),我有一个“小”疑问。在我的 std::map
、iterator
或 reverse_iterator
上迭代所有元素哪个更有效?
最佳答案
根据记录,在 std::map
和 std::set
容器上取消引用 reverse_iterator
是 < strong>比使用 iterator
慢两倍——在 Intel/AMD 处理器上同时使用 -O3 gcc 3.4.6 和 MSVC(在 PPC 架构上慢近 3 倍)同样适用于 const_reverse_iterator
与 const_iterator
。这是因为 reverse_iterator
实际上 指向紧跟在要取消引用的树节点之后的树节点,因此需要额外的工作。 std::vector
迭代器表现出更温和的差异(reverse_iterator
在 PPC 上仅慢 ~30%,在 Intel/AMD 上几乎无法区分。)顺便说一句,std::vector
迭代器比 std::map
或 std::set
迭代器快大约 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;
}
关于c++ - 迭代器与反向迭代器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/889262/