创建排序向量的索引向量 [英] Creating a vector of indices of a sorted vector

问题描述

变量 x 是 n 整数的向量，我想按升序对向量进行排序。但是，出于超出此问题范围的原因，我希望保持不变。因此，我不是真正地对 x 的内容进行排序，而是要创建另一个 n 索引的向量，其中每个索引如果要对 x 进行排序，则表示 x 中的相应值。

Variable x is a vector of n ints, and I want to sort the vector in ascending order. However, for reasons outside the scope of this question, I want to vector to remain untouched. Therefore, rather than actually sorting the contents of x, I want to create another vector of n indices, where each index refers to the respective value in x, if x were to have been sorted.

例如：

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是否有内置的东西可以为我高效执行此操作？

I can think of plenty of timely ways of implementing this, but I'm wondering whether the STL has something build-in to perform this efficiently for me?

推荐答案

1） y 作为索引的向量（整数范围）

1) Create y as a vector of index (an integer range)

2）对此进行排序使用比较器返回范围，该比较器使用标准库返回 x
中的索引元素，从而得出：

2) Sort this range with a comparator that returns the indexes elements from x Using the Standard Library, that gives :

#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;
}

实时演示。

这篇关于创建排序向量的索引向量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！