为何预分配容量的vector插入比迭代器构造更快？

我不理解为何案例2的执行速度比案例1更快，std::vector<int> vv(us.begin(), us.end())难道没有调用reserve吗？是什么导致了两者的性能差异？

测试代码 #

#include <iostream>
#include <list>
#include <unordered_map>
#include <vector>
#include <unordered_set>
#include <chrono>
using namespace std;


class Timer
{
public:
    Timer()
    {
        start = std::chrono::high_resolution_clock::now();
    }
    chrono::time_point<chrono::steady_clock> start;

    ~Timer()
    {
        cout << chrono::duration_cast<chrono::milliseconds>(std::chrono::high_resolution_clock::now() - start).count() << "ms\n";
    }
};

int main()
{
    std::unordered_set<int> us;
    constexpr int loopCount = 10'000'000;
    for (int i = 0; i < loopCount; ++i)
    {
        us.emplace(i);
    }

    cout << "us creat!" << endl;
    {
        // case 1
        Timer t;
        std::vector<int> vv(us.begin(), us.end());
    }

    {
        // case 2
        Timer t;
        std::vector<int> vv;
        vv.reserve(us.size());
        for (const auto& item : us)
        {
            vv.emplace_back(std::move(item));
        }
    }

    cout<<"end!";
}

测试输出 #

us creat!
1028ms
497ms
end!

测试环境 #

C++17，Release模式，x64架构，Windows 10专业版，VC编译器

性能差异的核心原因 #

1. 遍历次数不同
   std::unordered_set的迭代器属于前向迭代器，不支持随机访问（无法通过last - first直接计算元素数量）。vector的范围构造函数vector(InputIt first, InputIt last)面对这类迭代器时，必须执行两次完整遍历：

   • 第一次遍历：统计unordered_set的元素总数，用于调用reserve分配内存；
   • 第二次遍历：将元素复制到vector中。
     而案例2中，我们直接通过us.size()（unordered_set内部缓存了元素数量，是O(1)操作）获取大小，reserve后只需要遍历一次unordered_set完成插入，遍历次数少了一倍。

2. 缓存命中率差异
   unordered_set的元素分散在多个哈希桶中，遍历过程会频繁触发缓存失效。两次遍历会重复加载这些哈希桶的数据，导致CPU缓存的复用率降低；而单次遍历能更好地利用已加载的缓存数据，减少内存访问开销，进一步拉开性能差距。

3. 关于reserve的疑问
   案例1的范围构造函数确实会调用reserve，但问题不在于是否分配足够内存，而在于分配内存前多做了一次完整的遍历，这才是性能差距的关键。

内容的提问来源于stack exchange，提问作者SuperHong