创建排序向量的索引向量

Question

变量x是一个nint 的向量,我想按升序对向量进行排序.但是,由于这个问题范围之外的原因,我想要保持不变.因此,x我想创建另一个n索引向量,而不是实际排序内容,其中每个索引引用相应的值x,如果x已经排序的话.

例如:

std::vector<int> x = {15, 3, 0, 20};
std::vector<int> y;
// Put the sorted indices of x into the vector y
for (int i = 0; i < 4; i++)
{
    std::cout << y[i];
}

应该给出输出:

2
1
0
3

对应于x中的值:

0
3
15
20

我可以想到很多及时实现这一点的方法,但我想知道STL是否有内置功能可以为我高效执行此操作？

Answer 1

1)创建y索引向量(整数范围)

2)使用比较器对此范围进行排序,该比较器返回x 使用标准库中的索引元素,它给出:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {

    std::vector<int> x = {15, 3, 0, 20};

    std::vector<int> y;

    std::vector<int> y(x.size());
    std::size_t n(0);
    std::generate(std::begin(y), std::end(y), [&]{ return n++; });

    std::sort(  std::begin(y), 
                std::end(y),
                [&](int i1, int i2) { return x[i1] < x[i2]; } );

    for (auto v : y)
        std::cout << v << ' ';

    return 0;
}

现场演示.

Answer 2

填写y所有指数x然后使用std::sort,y但提供比较器,比较相应的元素x:

  std::vector<int> y(x.size());
  std::iota(y.begin(), y.end(), 0);
  auto comparator = [&x](int a, int b){ return x[a] < x[b]; };
  std::sort(y.begin(), y.end(), comparator);