C ++ menyortir dan melacak indeks

Menggunakan C ++, dan mudah-mudahan perpustakaan standar, saya ingin mengurutkan urutan sampel dalam urutan menaik, tetapi saya juga ingin mengingat indeks asli dari sampel baru.

Sebagai contoh, saya memiliki satu set, atau vektor, atau matriks sampel A : [5, 2, 1, 4, 3]. Saya ingin mengurutkan ini menjadi B : [1,2,3,4,5], tetapi saya juga ingin mengingat indeks asli dari nilai-nilai, sehingga saya bisa mendapatkan set lain yang akan menjadi: C : [2, 1, 4, 3, 0 ]- yang sesuai dengan indeks setiap elemen dalam 'B', dalam yang asli ' SEBUAH'.

Misalnya, di Matlab Anda dapat melakukan:

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

Adakah yang bisa melihat cara yang baik untuk melakukan ini?

Menggunakan C++11 lambdas:

#include <iostream>
#include <vector>
#include <numeric>      // std::iota
#include <algorithm>    // std::sort, std::stable_sort

using namespace std;

template <typename T>
vector<size_t> sort_indexes(const vector<T> &v) {

  // initialize original index locations
  vector<size_t> idx(v.size());
  iota(idx.begin(), idx.end(), 0);

  // sort indexes based on comparing values in v
  // using std::stable_sort instead of std::sort
  // to avoid unnecessary index re-orderings
  // when v contains elements of equal values 
  stable_sort(idx.begin(), idx.end(),
       [&v](size_t i1, size_t i2) {return v[i1] < v[i2];});

  return idx;
}

Sekarang Anda dapat menggunakan vektor indeks yang dikembalikan dalam iterasi seperti

for (auto i: sort_indexes(v)) {
  cout << v[i] << endl;
}

Anda juga dapat memilih untuk memasok vektor indeks asli Anda, fungsi sortir, pembanding, atau secara otomatis menyusun ulang v dalam fungsi sort_indexes menggunakan vektor tambahan.

Anda bisa mengurutkan std :: pair bukan hanya ints - int pertama adalah data asli, int kedua adalah indeks asli. Kemudian sediakan komparator yang hanya memilah pada int pertama. Contoh:

Your problem instance: v = [5 7 8]
New problem instance: v_prime = [<5,0>, <8,1>, <7,2>]

Urutkan instance masalah baru menggunakan pembanding seperti:

typedef std::pair<int,int> mypair;
bool comparator ( const mypair& l, const mypair& r)
   { return l.first < r.first; }
// forgetting the syntax here but intent is clear enough

Hasil std :: sort pada v_prime, menggunakan komparator itu, seharusnya:

v_prime = [<5,0>, <7,2>, <8,1>]

Anda dapat mengupas indeks dengan berjalan vektor, meraih .second dari setiap std :: pair.

Misalkan vektor yang diberikan adalah

A=[2,4,3]

Buat vektor baru

V=[0,1,2] // indicating positions

Sortir V dan sambil menyortir alih-alih membandingkan elemen V, bandingkan elemen A yang sesuai

 //Assume A is a given vector with N elements
 vector<int> V(N);
 int x=0;
 std::iota(V.begin(),V.end(),x++); //Initializing
 sort( V.begin(),V.end(), [&](int i,int j){return A[i]<A[j];} );

Saya menulis versi generik dari semacam indeks.

template <class RAIter, class Compare>
void argsort(RAIter iterBegin, RAIter iterEnd, Compare comp, 
    std::vector<size_t>& indexes) {

    std::vector< std::pair<size_t,RAIter> > pv ;
    pv.reserve(iterEnd - iterBegin) ;

    RAIter iter ;
    size_t k ;
    for (iter = iterBegin, k = 0 ; iter != iterEnd ; iter++, k++) {
        pv.push_back( std::pair<int,RAIter>(k,iter) ) ;
    }

    std::sort(pv.begin(), pv.end(), 
        [&comp](const std::pair<size_t,RAIter>& a, const std::pair<size_t,RAIter>& b) -> bool 
        { return comp(*a.second, *b.second) ; }) ;

    indexes.resize(pv.size()) ;
    std::transform(pv.begin(), pv.end(), indexes.begin(), 
        [](const std::pair<size_t,RAIter>& a) -> size_t { return a.first ; }) ;
}

Penggunaannya sama dengan std :: sort kecuali untuk wadah indeks untuk menerima indeks yang diurutkan. pengujian:

int a[] = { 3, 1, 0, 4 } ;
std::vector<size_t> indexes ;
argsort(a, a + sizeof(a) / sizeof(a[0]), std::less<int>(), indexes) ;
for (size_t i : indexes) printf("%d\n", int(i)) ;

Anda harus mendapatkan 2 1 0 3. untuk kompiler tanpa dukungan c ++ 0x, ganti ekspresi lamba sebagai templat kelas:

template <class RAIter, class Compare> 
class PairComp {
public:
  Compare comp ;
  PairComp(Compare comp_) : comp(comp_) {}
  bool operator() (const std::pair<size_t,RAIter>& a, 
    const std::pair<size_t,RAIter>& b) const { return comp(*a.second, *b.second) ; }        
} ;

dan tulis ulang std :: sortir sebagai

std::sort(pv.begin(), pv.end(), PairComp(comp)()) ;

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

Sekarang aberisi nilai kami dan indeks masing-masing dalam diurutkan.

a[i].first = valuepada i'th.

a[i].second = idx dalam array awal.

Saya menemukan pertanyaan ini, dan menemukan mengurutkan iterator secara langsung akan menjadi cara untuk mengurutkan nilai-nilai dan melacak indeks; Tidak perlu mendefinisikan wadah tambahan pairs (nilai, indeks) yang bermanfaat ketika nilai adalah objek besar; Iterator menyediakan akses ke nilai dan indeks:

/*
 * a function object that allows to compare
 * the iterators by the value they point to
 */
template < class RAIter, class Compare >
class IterSortComp
{
    public:
        IterSortComp ( Compare comp ): m_comp ( comp ) { }
        inline bool operator( ) ( const RAIter & i, const RAIter & j ) const
        {
            return m_comp ( * i, * j );
        }
    private:
        const Compare m_comp;
};

template <class INIter, class RAIter, class Compare>
void itersort ( INIter first, INIter last, std::vector < RAIter > & idx, Compare comp )
{ 
    idx.resize ( std::distance ( first, last ) );
    for ( typename std::vector < RAIter >::iterator j = idx.begin( ); first != last; ++ j, ++ first )
        * j = first;

    std::sort ( idx.begin( ), idx.end( ), IterSortComp< RAIter, Compare > ( comp ) );
}

adapun contoh penggunaan:

std::vector < int > A ( n );

// populate A with some random values
std::generate ( A.begin( ), A.end( ), rand );

std::vector < std::vector < int >::const_iterator > idx;
itersort ( A.begin( ), A.end( ), idx, std::less < int > ( ) );

sekarang, misalnya, elemen terkecil ke-5 dalam vektor yang diurutkan akan memiliki nilai **idx[ 5 ]dan indeksnya dalam vektor asli adalah distance( A.begin( ), *idx[ 5 ] )atau sederhana *idx[ 5 ] - A.begin( ).

Ada cara lain untuk menyelesaikan ini, menggunakan peta:

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();

Ini akan menghilangkan elemen non-unik. Jika itu tidak dapat diterima, gunakan 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()));

Untuk menampilkan indeks, lakukan iterasi pada peta atau multimap:

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

Solusi indah oleh @Lukasz Wiklendt! Meskipun dalam kasus saya, saya membutuhkan sesuatu yang lebih umum, jadi saya memodifikasinya sedikit:

template <class RAIter, class Compare>
vector<size_t> argSort(RAIter first, RAIter last, Compare comp) {

  vector<size_t> idx(last-first);
  iota(idx.begin(), idx.end(), 0);

  auto idxComp = [&first,comp](size_t i1, size_t i2) {
      return comp(first[i1], first[i2]);
  };

  sort(idx.begin(), idx.end(), idxComp);

  return idx;
}

Contoh: Temukan indeks yang mengurutkan vektor string berdasarkan panjangnya, kecuali untuk elemen pertama yang merupakan dummy.

vector<string> test = {"dummy", "a", "abc", "ab"};

auto comp = [](const string &a, const string& b) {
    return a.length() > b.length();
};

const auto& beginIt = test.begin() + 1;
vector<size_t> ind = argSort(beginIt, test.end(), comp);

for(auto i : ind)
    cout << beginIt[i] << endl;

cetakan:

abc
ab
a

Pertimbangkan untuk menggunakan std::multimapseperti yang disarankan oleh @Ulrich Eckhardt. Hanya saja kodenya bisa dibuat lebih sederhana.

Diberikan

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

Untuk mengurutkan waktu penyisipan rata-rata

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

Untuk mengambil nilai dan indeks asli

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
}

Alasan untuk memilih a std::multimapke a std::mapadalah untuk memungkinkan nilai yang sama dalam vektor asli. Perlu diketahui juga, tidak seperti untuk std::map, operator[]tidak ditentukan untuk std::multimap.

Membuat std::pair fungsi dalam lalu sortir pasangan:

versi generik:

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

Apakah item dalam vektor unik? Jika demikian, salin vektor, urutkan salah satu salinan dengan STL Sort maka Anda dapat menemukan indeks yang dimiliki setiap item dalam vektor asli.

Jika vektor seharusnya menangani item duplikat, saya pikir Anda lebih baik menerapkan rutinitas semacam Anda sendiri.

Nah, solusi saya menggunakan teknik residu. Kita dapat menempatkan nilai-nilai di bawah pengurutan di 2 byte atas dan indeks elemen - dalam 2 byte lebih rendah:

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

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

Kemudian urutkan array myintsseperti biasa:

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

Setelah itu Anda dapat mengakses indeks elemen melalui residuum. Kode berikut mencetak indeks nilai yang diurutkan dalam urutan naik:

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

Tentu saja, teknik ini hanya berfungsi untuk nilai-nilai yang relatif kecil dalam array asli myints(yaitu yang dapat masuk ke dalam 2 byte atas int). Tetapi memiliki manfaat tambahan untuk membedakan nilai identik myints: indeks mereka akan dicetak dalam urutan yang benar.

Jika memungkinkan, Anda dapat membuat susunan posisi menggunakan fungsi find, dan kemudian mengurutkan susunan.

Atau mungkin Anda dapat menggunakan peta di mana kunci akan menjadi elemen, dan nilai-nilai daftar posisinya di array yang akan datang (A, B dan C)

Itu tergantung pada penggunaan nanti dari array itu.

Untuk jenis pertanyaan ini Simpan data array orignal ke dalam data baru dan kemudian pencarian biner elemen pertama dari array yang diurutkan ke dalam array yang digandakan dan bahwa indice harus disimpan ke dalam vektor atau array.

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]));`

Di sini binarysearch adalah fungsi yang mengambil array, ukuran array, mencari item dan akan mengembalikan posisi item yang dicari

Ada banyak cara. Solusi yang agak sederhana adalah dengan menggunakan vektor 2D.

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

Berikut hasilnya:

   Index   Value
   3       1
   4       3
   1       4
   0       5
   2       7