使用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

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


当前回答

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

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;

其他回答

在函数中创建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

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

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是一个函数,它接受数组,数组大小,搜索项,并返回被搜索项的位置

考虑使用@Ulrich Eckhardt建议的std::multimap。只是代码可以变得更简单。

鉴于

std::vector<int> a = {5, 2, 1, 4, 3};  // a: 5 2 1 4 3

在插入的平均时间内排序

std::multimap<int, std::size_t> mm;
for (std::size_t i = 0; i != a.size(); ++i)
    mm.insert({a[i], i});

检索值和原始索引

std::vector<int> b;
std::vector<std::size_t> c;
for (const auto & kv : mm) {
    b.push_back(kv.first);             // b: 1 2 3 4 5
    c.push_back(kv.second);            // c: 2 1 4 3 0
}

首选std::multimap而不是std::map的原因是允许原始向量的值相等。另外请注意,与std::map不同,操作符[]没有为std::multimap定义。

我最近接触了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,使用投影!

我的解法使用了余数法。我们可以把需要排序的值放在上面2个字节,而把元素的下标放在下面2个字节:

int myints[] = {32,71,12,45,26,80,53,33};

for (int i = 0; i < 8; i++)
   myints[i] = myints[i]*(1 << 16) + i;

然后像往常一样对数组myint进行排序:

std::vector<int> myvector(myints, myints+8);
sort(myvector.begin(), myvector.begin()+8, std::less<int>());

在此之后,您可以通过渣滓访问元素的指数。下面的代码输出按升序排序的值的索引:

for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
   std::cout << ' ' << (*it)%(1 << 16);

当然,这种技术只适用于原始数组myint中相对较小的值(即可以装入int的前2个字节的值)。但是它还有一个额外的好处,可以区分相同的myint值:它们的下标将按正确的顺序打印。