今天我只是试图解决编程中的一个问题。我注意到 vector<vector> 的分配和排序比 vector<pair<int, pair<int, int>> 慢得多.我进行了一些基准测试，发现对于给定的输入（https://pastebin.com/izWGNEZ7），嵌套 vector 代码比嵌套对代码慢 4 倍。
下面是我用于基准测试的代码。
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有谁知道为什么 performance 有很大的不同？
回答1
std::pair 或 std::array 具有在编译时已知的固定大小，并将直接将对象包含在类本身中。另一方面，std::vector 必须处理动态大小，并且需要在堆上分配一块内存来保存对象。
对于小对象，std::pair 或 std::array 会更好，因为分配和释放内存的开销会占用你的 performance。这就是你所看到的。例如，指针所涉及的额外间接也会使您付出代价。比较元素以及必须在运行时检查大小。
另一方面，对于大型对象，std::vector 应该更好，因为它支持移动语义。交换 2 vectors 只会交换指向数据的指针，而 std::pair 或 std:array 将不得不移动/复制每个元素，这对于大型对象来说代价高昂。
因此，您看到的不是该对比 vector 快，而是在该用例中该对比 vector 快。