logo标签列表

C++排序和索引跟踪

c++sortingstlindexing
280

我想使用C++标准库对一系列样本进行升序排序，同时还要记住新样本的原始索引。

例如，我有一个由样本组成的集合、向量或矩阵A : [5, 2, 1, 4, 3]。我想将它们排序为B : [1, 2, 3, 4, 5]，但我还想记住这些值在原始集合'A'中的索引，以便获取另一个集合，即：C : [2, 1, 4, 3, 0 ]——它对应于每个元素在'B'中的索引，在原始集合'A'中的位置。

例如，在Matlab中，您可以执行以下操作：

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

有人能想到一个好的方法吗？

16个回答
2

在函数中创建一个 std::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

1

我的解决方案使用了余数技术。我们可以将排序下的值放在上面的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;

然后像往常一样对数组myints进行排序：

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

之后，您可以通过residuum访问元素的索引。以下代码打印按升序排序的值的索引：

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

当然，这种技术仅适用于原始数组myints中相对较小的值（即适合于int的上2个字节的值）。但它还具有另一个好处，可以区分myints中相同的值：它们的索引将按正确顺序打印出来。
1
如果可能的话，您可以使用find函数构建位置数组，然后对该数组进行排序。
或者您可以使用一个映射，其中键是元素，值是其在即将到来的数组（A、B和C）中位置的列表。
这取决于以后对这些数组的使用。
0
针对这种类型的问题，将原始数组数据存储到新数据中，然后在复制的数组中二分搜索已排序的数组的第一个元素，该索引应存储到向量或数组中。
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是一个函数，它接受数组、数组大小、要搜索的项，并返回搜索项的位置。

0

向量中的项目是否唯一？如果是，复制向量，使用STL Sort对其中一个副本进行排序，然后您可以找到每个项目在原始向量中的索引。

如果向量应处理重复项，则最好实现自己的排序例程。

-2
一个解决方案是使用二维向量。
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
 vector<vector<double>> val_and_id;
 val_and_id.resize(5);
 for (int i = 0; i < 5; i++) {
   val_and_id[i].resize(2); // one to store value, the other for index.
 }
 // Store value in dimension 1, and index in the other:
 // say values are 5,4,7,1,3.
 val_and_id[0][0] = 5.0;
 val_and_id[1][0] = 4.0;
 val_and_id[2][0] = 7.0;
 val_and_id[3][0] = 1.0;
 val_and_id[4][0] = 3.0;

 val_and_id[0][1] = 0.0;
 val_and_id[1][1] = 1.0;
 val_and_id[2][1] = 2.0;
 val_and_id[3][1] = 3.0;
 val_and_id[4][1] = 4.0;

 sort(val_and_id.begin(), val_and_id.end());
 // display them:
 cout << "Index \t" << "Value \n";
 for (int i = 0; i < 5; i++) {
  cout << val_and_id[i][1] << "\t" << val_and_id[i][0] << "\n";
 }
 return 0;
}

这是输出结果：

   Index   Value
   3       1
   4       3
   1       4
   0       5
   2       7
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接