我刚刚尝试在 std::vector 上对 std::sort 进行基准测试(填充了 push_back 操作) 和普通的 std::pair 数组(使用 new 分配，然后一一填充)。 compare 函数只是比较了对的浮点部分。
令人惊讶的是，当用于 16M 值时，在 std::vector 上只需要大约 1940 毫秒，但在数组上大约需要 2190 毫秒。谁能解释一下 vector 如何更快？是因为缓存，还是只是数组版本的 std::sort 实现不好？
gcc (GCC) 4.4.5 20110214(红帽 4.4.5-6)
Intel(R) Core(TM) i7 CPU 870 @ 2.93GHz - 缓存大小 8192 KB(计算机有两个四核 CPU，但我假设排序只是单线程)
编辑:现在你可以称我为笨蛋，但是当我试图重现我用于测量的代码时(我已经删除了原来的代码)我无法重现结果 - 现在是数组版本大约需要 1915 +- 5ms(在 32 次运行中测量)。我只能发誓我已经(手动)对 10 次测量进行了 3 次测试，结果相似，但这并不是一个严格的证明。
原始代码中可能存在一些错误，后台进程似乎不太可能，因为我已经交替测量 vector 和数组版本并且 vector 结果保持不变并且没有用户登录。
请将此问题视为已结束。感谢您的努力。
最佳答案
std::vector<std::pair<float, unsigned int>>(filled with push_back operation)
这将所有数据连续存储，因此内存局部性非常好
std::pair<float, unsigned int>> *array (allocated using new and then filled one by one)
这会将数据分散到整个内存中。
您在 vector 和一个简单数组之间进行了非常不公平的比较。数组案例中涉及的额外间接性会受到伤害，缺乏局部性会降低缓存性能。我很惊讶你没有看到有利于连续存储的更大胜利。
关于c++ - std::vector 比普通数组快吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6372685/