使用c++(最好是标准库),我想对一个样本序列进行升序排序,但我也想记住新样本的原始索引。

例如,我有一个集合,或向量,或样本a的矩阵:[5,2,1,4,3]。我想把它们排序为B:[1,2,3,4,5],但我也想记住这些值的原始索引,所以我可以得到另一个集合,它将是: C:[2,1,4,3,0] -这对应于'B'中每个元素的索引,在原始'A'中。

例如,在Matlab中,你可以这样做:

 [a,b]=sort([5, 8, 7])
 a = 5 7 8
 b = 1 3 2

有谁能想到一个好办法吗?


当前回答

我最近接触了c++ 20 <ranges>的优雅投影特性,它允许编写更短/更清晰的代码:

std::vector<std::size_t> B(std::size(A));
std::iota(begin(B), end(B), 0);
std::ranges::sort(B, {}, [&](std::size_t i){ return A[i]; }); 

{}指通常的std::less<std::size_t>。因此,正如您所看到的,我们定义了一个函数,在任何比较之前调用每个元素。这个投影特性实际上是非常强大的,因为这个函数可以是,就像这里,或者它甚至可以是一个方法,或者一个成员值。例如:

struct Item {
    float price;
    float weight;
    float efficiency() const { return price / weight; }
};

int main() {
    std::vector<Item> items{{7, 9}, {3, 4}, {5, 3}, {9, 7}};
    std::ranges::sort(items, std::greater<>(), &Item::efficiency);
    // now items are sorted by their efficiency in decreasing order:
    // items = {{5, 3}, {9, 7}, {7, 9}, {3, 4}}
}

如果我们想通过增加价格来排序:

std::ranges::sort(items, {}, &Item::price);

不要定义操作符<或使用lambda,使用投影!

其他回答

如果可能的话,可以使用find函数构建位置数组,然后对数组排序。

或者你可以使用一个映射,其中键是元素,值是它在即将到来的数组(a, B和C)中的位置列表

这取决于以后对这些数组的使用。

vector<pair<int,int> >a;

for (i = 0 ;i < n ; i++) {
    // filling the original array
    cin >> k;
    a.push_back (make_pair (k,i)); // k = value, i = original index
}

sort (a.begin(),a.end());

for (i = 0 ; i < n ; i++){
    cout << a[i].first << " " << a[i].second << "\n";
}

现在a包含了我们的值和它们在排序中的下标。

[我]。First =第i条的值。

[我]。Second =初始数组中的idx。

在函数中创建std::pair,然后对pair进行排序:

通用版本:

template< class RandomAccessIterator,class Compare >
auto sort2(RandomAccessIterator begin,RandomAccessIterator end,Compare cmp) ->
   std::vector<std::pair<std::uint32_t,RandomAccessIterator>>
{
    using valueType=typename std::iterator_traits<RandomAccessIterator>::value_type;
    using Pair=std::pair<std::uint32_t,RandomAccessIterator>;

    std::vector<Pair> index_pair;
    index_pair.reserve(std::distance(begin,end));

    for(uint32_t idx=0;begin!=end;++begin,++idx){
        index_pair.push_back(Pair(idx,begin));
    }

    std::sort( index_pair.begin(),index_pair.end(),[&](const Pair& lhs,const Pair& rhs){
          return cmp(*lhs.second,*rhs.second);
    });

    return index_pair;
}

ideone

还有另一种方法来解决这个问题,使用地图:

vector<double> v = {...}; // input data
map<double, unsigned> m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
    m[*it] = it - v.begin();

这将消除非唯一元素。如果不能接受,使用multimap:

vector<double> v = {...}; // input data
multimap<double, unsigned> m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
    m.insert(make_pair(*it, it - v.begin()));

为了输出索引,迭代map或multimap:

for (auto it = m.begin(); it != m.end(); ++it)
    cout << it->second << endl;

对于这类问题 将原始数组数据存储到一个新数据中,然后将排序数组的第一个元素二进制搜索到复制的数组中,该索引应存储到一个矢量或数组中。

input array=>a
duplicate array=>b
vector=>c(Stores the indices(position) of the orignal array
Syntax:
for(i=0;i<n;i++)
c.push_back(binarysearch(b,n,a[i]));`

这里binarysearch是一个函数,它接受数组,数组大小,搜索项,并返回被搜索项的位置