我遇到了std :: set的一个奇怪的行为。
这里是代码：
#include <cstdio> #include <windows.h> #include <stdlib.h> #include <vector> #include <set> using namespace std; int main(int argc, char *argv[]) { set<int> b[100]; for (int o=0; o<10; o++) { int tt = GetTickCount(); for (int i=0; i<5000000; i++) { b[o].insert(i); } tt = GetTickCount() - tt; b[o].clear(); printf("%d\n", tt); } return 0; } 我在Windows XP上运行。
这里有一个有趣的部分：第一次打印的时间大约是3500毫秒，而接下来的所有时间都超过了9000毫秒！ 为什么会这样呢？
哦，这只发生在版本（-O2优化）上。
它不会发生在Linux上（改变代码后编译）。
还有一件事：当我使用英特尔®VTune进行性能分析时运行它总是需要大约3000毫秒，所以这是应该的。
更新：这是一些新的代码：
#include <cstdio> #include <windows.h> #include <stdlib.h> int main(int argc, char *argv[]) { const int count = 10000000; int **a = new int*[count]; for (int o=0; o<10; o++) { int ttt = GetTickCount(); for (int i=0; i<count; i++) { a[i] = new int; *a[i] = i; } int ttt2 = GetTickCount(); for (int i=0; i<count; i++) { int r1 = rand() * 10000 + rand(); int r2 = rand() * 10000 + rand(); r1 = r1%count; r2 = r2%count; int *e = a[r1]; a[r1] = a[r2]; a[r2] = e; } int ttt3 = GetTickCount(); for (int i=0; i<count; i++) { delete a[i]; } int ttt4 = GetTickCount(); printf("%d %d\n", ttt2-ttt, ttt4-ttt3); } return 0; }
这是同样的问题。 会发生什么是我分配很多很多的小对象，然后以随机顺序删除它们 – 所以它类似于它在std :: set。 所以这是Windows内存pipe理问题。 它不能真正处理很多小的分配和删除。
我无法解释为什么发生这种情况，但我可以提出一个解决方案。 我已经能够在我的电脑上重现这一点，当我在调试器（与F5 ）下运行发布版本。 当我从命令行或Ctrl-F5运行构建时，我不会得到这种行为。
这与在调试器下启动时默认打开的调试堆有关。 这里详细描述。 为了防止这种情况发生
Ctrl-F5 （Debug – > Start Without Debugging）运行。 _NO_DEBUG_HEAP=1 。 如果我不得不猜测，我会说，这与Windows / VS运行时内存分配跟踪的实现有关。 可能有些内部列表填满和重新分配或沿着这些线路的其他东西。
我认为std::set是作为二叉搜索树实现的。 因为每当你基本上为这种类型的数据结构创建一个敌对（最坏的情况）场景时，你正在增加1（几乎每个插入都需要重新平衡树）。
此外，它是5000万插入，所以有一段时间，但我不认为这将是5毫秒。
另外，在打印时间之后，我会做你的“清晰”，因为我没有看到你将基准插入和删除项目的原因。