C ++ Sortieren und Verfolgen von Indizes

Mit C ++ und hoffentlich der Standardbibliothek möchte ich eine Folge von Samples in aufsteigender Reihenfolge sortieren, aber ich möchte mich auch an die ursprünglichen Indizes der neuen Samples erinnern.

Zum Beispiel habe ich eine Menge, einen Vektor oder eine Matrix von Proben A : [5, 2, 1, 4, 3]. Ich möchte diese sortieren B : [1,2,3,4,5], aber ich möchte mich auch an die ursprünglichen Indizes der Werte erinnern, damit ich eine andere Menge erhalten kann, die wie folgt lautet: C : [2, 1, 4, 3, 0 ]- die dem Index jedes Elements in 'B' im Original entspricht ' EIN'.

In Matlab können Sie beispielsweise Folgendes tun:

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

Kann jemand einen guten Weg sehen, dies zu tun?

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

Jetzt können Sie den zurückgegebenen Indexvektor in Iterationen wie z

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

Sie können auch Ihren ursprünglichen Indexvektor, Ihre Sortierfunktion, Ihren Komparator angeben oder v in der Funktion sort_indexes mithilfe eines zusätzlichen Vektors automatisch neu anordnen.

Sie können std :: pair anstatt nur ints sortieren - das erste int sind Originaldaten, das zweite int ist der ursprüngliche Index. Geben Sie dann einen Komparator an, der nur nach dem ersten int sortiert. Beispiel:

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

Sortieren Sie die neue Probleminstanz mit einem Komparator wie folgt:

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

Das Ergebnis von std :: sort auf v_prime unter Verwendung dieses Komparators sollte sein:

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

Sie können die Indizes herausziehen, indem Sie den Vektor durchlaufen und von jedem std :: pair .second abrufen.

Angenommen, der gegebene Vektor ist

A=[2,4,3]

Erstellen Sie einen neuen Vektor

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

Sortieren Sie V und vergleichen Sie beim Sortieren die entsprechenden Elemente von A, anstatt die Elemente von V zu vergleichen

 //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];} );

Ich habe eine generische Version der Indexsortierung geschrieben.

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

Die Verwendung entspricht der von std :: sort, außer dass ein Indexcontainer sortierte Indizes empfängt. testen:

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

Sie sollten 2 1 0 3 erhalten. Ersetzen Sie für Compiler ohne C ++ 0x-Unterstützung den Lamba-Ausdruck als Klassenvorlage:

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

und schreibe std :: sort as um

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

Nun aenthält beide sowohl unsere Werte und ihre jeweiligen Indizes in der sortierten.

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

a[i].second = idx im anfänglichen Array.

Ich bin auf diese Frage gestoßen und habe herausgefunden, dass das direkte Sortieren der Iteratoren eine Möglichkeit ist, die Werte zu sortieren und die Indizes zu verfolgen. Es ist nicht erforderlich, einen zusätzlichen Container mit pairs von (Wert, Index) zu definieren. Dies ist hilfreich, wenn es sich bei den Werten um große Objekte handelt. Die Iteratoren bieten Zugriff auf den Wert und den Index:

/*
 * 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 ) );
}

wie für das Verwendungsbeispiel:

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

Jetzt hätte beispielsweise das fünftkleinste Element im sortierten Vektor einen Wert **idx[ 5 ]und sein Index im ursprünglichen Vektor wäre distance( A.begin( ), *idx[ 5 ] )oder einfach *idx[ 5 ] - A.begin( ).

Es gibt eine andere Möglichkeit, dies mithilfe einer Karte zu lösen:

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

Dadurch werden jedoch nicht eindeutige Elemente gelöscht. Wenn dies nicht akzeptabel ist, verwenden Sie eine 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()));

Um die Indizes auszugeben, iterieren Sie über die Karte oder Multimap:

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

Schöne Lösung von @Lukasz Wiklendt! Obwohl ich in meinem Fall etwas allgemeineres brauchte, habe ich es ein wenig modifiziert:

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

Beispiel: Suchen Sie nach Indizes, die einen Vektor von Zeichenfolgen nach Länge sortieren, mit Ausnahme des ersten Elements, das ein Dummy ist.

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;

Drucke:

abc
ab
a

std::multimapErwägen Sie die Verwendung wie von @Ulrich Eckhardt vorgeschlagen. Nur dass der Code noch einfacher gemacht werden könnte.

Gegeben

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

In der mittleren Einfügezeit sortieren

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

Abrufen von Werten und Originalindizes

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
}

Der Grund, a std::multimapgegenüber a vorzuziehen , std::mapbesteht darin, gleiche Werte in ursprünglichen Vektoren zuzulassen. Bitte beachten Sie auch , dass im Gegensatz zu std::map, operator[]ist nicht definiert für std::multimap.

Machen Sie eine std::pairIn-Funktion und sortieren Sie das Paar:

generische Version:

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

Sind die Elemente im Vektor eindeutig? Wenn ja, kopieren Sie den Vektor, sortieren Sie eine der Kopien mit STL Sort. Dann können Sie herausfinden, welchen Index jedes Element im ursprünglichen Vektor hatte.

Wenn der Vektor doppelte Elemente verarbeiten soll, ist es meiner Meinung nach besser, Ihre eigene Sortierroutine zu implementieren.

Nun, meine Lösung verwendet Rückstandstechnik. Wir können die Werte unter Sortieren in den oberen 2 Bytes und den Indizes der Elemente platzieren - in den unteren 2 Bytes:

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

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

Sortieren Sie dann das Array myintswie gewohnt:

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

Danach können Sie über Residuum auf die Indexe der Elemente zugreifen. Der folgende Code druckt die Indizes der Werte in aufsteigender Reihenfolge:

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

Natürlich funktioniert diese Technik nur für die relativ kleinen Werte im ursprünglichen Array myints(dh diejenigen, die in die oberen 2 Bytes von passen können int). Es hat jedoch den zusätzlichen Vorteil, identische Werte von zu unterscheiden myints: Ihre Indizes werden in der richtigen Reihenfolge gedruckt.

Wenn es möglich ist, können Sie das Positionsarray mit der Suchfunktion erstellen und dann das Array sortieren.

Oder Sie können eine Karte verwenden, in der der Schlüssel das Element ist, und die Werte eine Liste seiner Position in den kommenden Arrays (A, B und C).

Dies hängt von der späteren Verwendung dieser Arrays ab.

Für diese Art von Frage Speichern Sie die ursprünglichen Array-Daten in neuen Daten und suchen Sie dann binär das erste Element des sortierten Arrays in dem duplizierten Array. Dieser Index sollte in einem Vektor oder Array gespeichert werden.

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

Hier ist die Binärsuche eine Funktion, die das Array, die Größe des Arrays und das Suchelement übernimmt und die Position des gesuchten Elements zurückgibt

Es gibt viele Wege. Eine ziemlich einfache Lösung ist die Verwendung eines 2D-Vektors.

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

Hier ist die Ausgabe:

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