为什么分配和某种STD ::对比STD :: vector快？

Question

今天，我只是试图解决编程问题。我注意到向量的分配和分类＆lt; vector＆gt;比vector＆lt; pair＆lt; int，pair＆lt; int，int，int＆gt;。我采用了一些基准测试，并知道嵌套向量代码比给定输入的嵌套对码慢4倍（ https：// 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

std :: Pair或std :: Array在编译时已知固定大小，并且将直接在类本身中包含对象。另一方面，std :: vector必须处理动态大小，并且需要在堆上分配大量内存以容纳对象。

对于小对象，std :: Pair或std :: array会更好，因为分配和释放内存的开销会陷入您的性能中。那就是您所看到的。当比较元素以及必须在运行时检查大小时，指针涉及的额外间接方向也将使您付出代价。

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

因此，您所看到的不是该对比向量快，而是该对中的速度比向量更快。