为什么 std::pair 的分配和排序比 std::vector 快？

Question

今天刚想解决一个编程问题。我注意到 vector 的分配和排序比 vector> 慢得多。我进行了一些基准测试，发现嵌套向量代码比给定输入的嵌套对代码慢 4 倍 (https://pastebin.com/izWGNEZ7)。

下面是我用于基准测试的代码。

    auto t_start = std::chrono::high_resolution_clock::now();
    vector<pair<int, pair<int, int>>> edges;
    for (int i = 0; i < points.size(); i++)
        for (int j = i + 1; j < points.size(); j++)
            edges.push_back({abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), {i, j}});
    sort(edges.begin(), edges.end());
    auto t_end = std::chrono::high_resolution_clock::now();
    double elapsed_time_ms = std::chrono::duration<double, std::milli>(t_end - t_start).count();
    cout << elapsed_time_ms << endl;

    auto t_start1 = std::chrono::high_resolution_clock::now();
    vector<vector<int>> edges1;
    for (int i = 0; i < points.size(); i++)
        for (int j = i + 1; j < points.size(); j++)
            edges1.push_back({abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), i, j});
    sort(edges1.begin(), edges1.end());
    auto t_end1 = std::chrono::high_resolution_clock::now();
    double elapsed_time_ms1 = std::chrono::duration<double, std::milli>(t_end1 - t_start1).count();
    cout << elapsed_time_ms1 << endl;

输出：

241.917
1188.11

有谁知道为什么会有这么大的性能差异？

Answer 1

A std::pair 或 std::array 具有在编译时已知的固定大小，并将直接将对象包含在 class 本身中。另一方面，std::vector 必须处理动态大小，需要在堆上分配一块内存来保存对象。

对于小对象，std::pair 或 std::array 会更好，因为分配和释放内存的开销会影响您的性能。这就是你所看到的。例如，指针所涉及的额外间接寻址也会使您付出代价。比较元素以及必须在运行时间检查大小。

另一方面，对于大型对象，std::vector 应该更好，因为它支持移动语义。交换 2 个向量只会交换指向数据的指针，而 std::pair 或 std:array 将必须 move/copy 每个元素，这对于大对象来说是昂贵的。

所以你看到的不是那个对比向量快，而是那个对在那个用例中比向量快。

为什么 std::pair 的分配和排序比 std::vector 快？

Why allocation and sort of std::pair is faster than std::vector?

c++

performance

vector

std-pair