时间戳

首页 > 解决方案 > 使用对数组比使用向量对更有效吗？

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

问题描述

当我使用一对向量时，我得到了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);

我想了解这背后的逻辑。

标签： c++algorithmtime-complexitystdvectorstd-pair

解决方案

在这些行中

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( vector of pairs ) 可能会经历多次重新分配，因为这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);

作为旁注，请不要练习using namespace std;

推荐阅读