c++ - 对数组进行排序并维护元素的旧索引

Question

我有一个数组 A:

A     =   [10 11 3 15 8 7]
index =    0   1 2  3 4 5

我想对这个数组进行排序。排序后我想要旧索引的信息。为此我可以创建这样的结构。

struct VnI{
  int value;
  int index;
};

根据值对结构数组进行排序解决了我的问题。但我想知道是否可以使用 sort 或 C++11 中的任何其他函数来解决此问题。

我试过这种方式:

struct VnI{
int V;
int I;
};

bool comparator(VnI x,VnI y){
    if(x.V < y.V)
        return true;
    return false;
}
int maximumGap(const vector<int> &A) {
   vector<VnI> B;
   for(int i = 0;i < A.size();i++){
      B[i].I = i;
      B[i].V = A[i];
}
sort(B.begin(),B.end(),comparator);
for(int i = 0;i < B.size();i++){
    cout<<B[i].I<<" "<<B[i].V<<endl;
  }
}

但是我遇到了运行时错误。请帮忙。

Answer 1

这段代码是错误的:

vector<VnI> B;  

for(int i = 0;i < A.size();i++){
   B[i].I = i;
   B[i].V = A[i];
}

当您编写 B[i] 时，它假定 B 的大小至少 i+1。由于 i(您使用 B 的索引)的最大值是 A.size()-1。您的代码中的假设是 B 的大小至少为 A.size()。 这个假设是错误的 — 事实上 B 的大小是 0。

不幸的是，std::vector 的operator[] 不检查超出范围 索引。如果使用at()，代码会抛出std::out_of_range异常:

vector<VnI> B;  

for(int i = 0;i < A.size();i++){
   B.at(i).I = i;
   B.at(i).V = A[i];
}

现在这会抛出 std::out_of_range 异常。

无论如何，一个简单的修复可能是这样的:

 vector<VnI> B (A.size());  //initialize B with the size of A.

 for(int i = 0;i < A.size();i++){
    B[i].I = i;
    B[i].V = A[i];
 }

但是，我建议采用以下解决方案:

 vector<VnI> B;      
 B.reserve(A.size()); 

 for(int i = 0;i < A.size(); i++){
    B.emplace_back(i, A[i]);
 }

我还建议您阅读更多关于 std::vector 的内容，尤其是以下功能:

• 大小()
• 容量()
• 调整大小()
• 保留()
• push_back()
• 运算符[]
• at()
• emplace_back()
• 和所有的构造函数。

另外，学习正确命名变量并与之保持一致。

希望对您有所帮助。