使用对数组比使用向量对更有效吗？

Question

当我使用向量对时，我得到了TLE：

vector<pair<int,int>> v;

for(int i=0;i<n;++i)
v.push_back(make_pair(a,b));

sort(v.begin(),v.end());

当我将代码更改为：

时它被接受了

pair<int,int> v[n];
for(int i=0;i<n;++i)
{
       v[i].first=a;
       v[i].second=b;
}
sort(v,v+n);

我想了解这背后的逻辑。

Answer 1

如果您在编译时知道对的计数并且此计数是常数，请使用 std::array。否则，您可以使用 std::vector 或其他 STL 容器。

Answer 2

在这些行中

vector<pair<int,int>> v;

for(int i=0;i<n;++i)
   v.push_back(make_pair(a,b))

您创建了 std::pair<int,int> 的向量，并尝试在迭代 n 次时将元素放在它的末尾。在这些迭代期间，v（ 对向量）可能会经历多次重新分配，因为 std::vector::capacity 不足以插入 n 元素。这是一个昂贵的过程，因为需要将整个向量深度复制到适合新容量的新位置。因此，对于更大的 n，您的程序会变慢，因为它需要多次重新分配。

解决方案是使用std::vector::researve预先保留我们需要的内存（即在迭代和插入开始之前），这样就可以避免昂贵的深度复制/重新分配。这意味着使用 std::vector 解决方案执行以下操作也会成功解决时间限制问题。

#include <vector> #include <utility> // std::pair std::vector<std::pair<int, int>> v; const int n = 5; // lets say n = 5 v.reserve(n); // now, reserve the memory for `n` pairs for (int i = 0; i < n; ++i) // you can use `std::vector::emplace_back` to insert the pairs in place like this! v.emplace_back(a, b);

作为旁注，请不要practice with using namespace std;

使用对数组比使用向量对更有效吗？

Is it more efficient to use array of pairs than using vector pair?

c++

algorithm

time-complexity

stdvector

std-pair