c++ - 对 n 维点进行排序并跟踪原始索引

Question

我在 vector< vector<double> > 中有一组 n 维点存储

ex A[0][1].............[N], and A[0][0] = X, A[0][1] = Y, A[0][2] = Z

我想对所有维度的 vector 进行排序

ex sort X, Y, Z ,.........N in ascending order


ex              A[0] = (1,5,3), A[1] = (3,2,1) A[2] = (2,8,4) after sorting
index:            0               1             2
                A[0] = (1,5,3), A[1] = (2,8,4) A[2] = (3,2,1)
original index :  0               2             1

我发现 sort(vector.begin(), vector.end())可以对它进行排序，但我如何使用附加 vector 记录原始索引？

有算法或者C++特性可以解决吗？

提前致谢。

Answer 1

您需要以某种方式保留有关索引的信息。我可以看到两种方法:

1-因为你用 vector 表示你的点，你可以有另一个维度来表示原始索引:

//Adding index info, inportant that your index be the last dimension , otherwise the sort is incorrect for(auto point = vector.begin(),unsigned int index=0;point != vector.end(); ++point,++index){ point->push_back(index) };

然后按照与现在相同的方式排序:

sort(vector.begin(), vector.end())

然后您使用 A[0][n] 访问原始索引

这很酷的一点是，它允许您以一种非常方便的方式跟踪索引，但您需要能够修改您的点的表示。

2- 另一种方法是使用外部索引表并使用自定义 comp 对其进行排序。运算符(operator):

首先创建一个索引 vector

std::vector indices(vector.size());

for(unsigned int index =0;index != indicies.size(); ++point){ indicies[index] = index ; };

//and sort...

std::sort(indices.begin(),indices.end(),[&](unsigned int i,unsigned int j) { return vector[i] < vector[j]})

现在您需要一个额外的间接级别来按排序顺序遍历您的点:A[指数[0]],A[指数[1]],...所以 A[indices[x]] 的原始位置就是 x

在这两种方法之间要记住的主要是，第一种方法是移动数据，而不是第二种方法，这取决于你在做什么，一个可能比顺序更好