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 的内容。 ，特别是以下功能:

• 大小()
• 容量()
• 调整大小()
• reserve()
• push_back()
• 运算符[]
• at()
• emplace_back()
• 以及所有构造函数。

此外，学会正确命名变量并与其保持一致。

希望有帮助。