为何vector操作耗时远低于unordered_map？时间复杂度测试疑问

你遇到的测试结果差异，核心原因有三个，下面逐个拆解：

1. 容器按值传递带来的巨大复制开销 #

你的测试函数iterateUMap和iterateVector的参数都是按值接收容器：

void iterateUMap(std::unordered_map<int, Test> map) // 每次调用都会复制整个unordered_map
void iterateVector(std::vector<Test> vector) // 每次调用都会复制整个vector

而funcComplexity循环调用了10000次这些函数——这意味着：

• 每次调用iterateUMap，都要复制包含1000个元素的unordered_map：哈希表的复制需要逐个复制节点，还要重新构建哈希结构，开销极大。
• vector是连续内存，复制是整块内存的拷贝（memcpy级别的操作），速度比哈希表复制快几个数量级。
  这部分复制的开销，才是测试结果差距的主要来源，远大于删除/查找操作本身的耗时。

2. 实际执行的操作本质不同 #

删除测试的差异 #

• 对unordered_map调用的map.erase(500)：是真正的删除操作，需要找到对应哈希桶的节点，从链表中移除，还要维护哈希表的结构，本身有固定开销。
• 对vector调用的std::remove_if：它并没有真正删除元素，只是把所有不满足删除条件的元素移动到容器前半部分，容器的size()并没有变化。你没有调用vector.erase()完成最终删除，所以这个操作的实际工作量比unordered_map的erase小得多。

查找测试的差异 #

• unordered_map的map[500]：需要先计算key的哈希值，找到对应的哈希桶，再遍历桶内链表定位元素；哈希计算+链表遍历的开销本身就比vector的遍历大。
• vector的查找是遍历到第501个元素就break，而且因为是连续内存，CPU的缓存预取机制会把后续元素提前加载到缓存，遍历速度非常快，实际耗时极低。

3. 数据局部性与CPU缓存的影响 #

• vector的元素存储在连续内存块中，CPU可以高效利用缓存预取，一次加载多个相邻元素到L1/L2缓存，访问速度接近寄存器级别。
• unordered_map的元素分散在内存中（哈希桶节点是动态分配的），内存地址不连续，CPU缓存命中率极低，每次访问元素都可能触发缓存miss，需要从内存加载，速度比缓存访问慢几十到上百倍。

修正测试的建议 #

如果要真正测试删除/查找操作本身的耗时，需要：

• 把函数参数改成引用传递，避免容器复制的开销：

  void iterateUMap(std::unordered_map<int, Test>& map) // 引用传递
  void iterateVector(std::vector<Test>& vector) // 引用传递
  

• 对于vector的删除测试，要加上erase完成真正的删除：

  auto it = std::remove_if(vector.begin(), vector.end(), [](Test& val){
      return val.mId == 500;
  });
  vector.erase(it, vector.end());
  

内容的提问来源于stack exchange，提问作者Windings-Lab