C++ Sortieren und Verfolgen von Indizes

Lesezeit: 8 Minuten

C Sortieren und Verfolgen von Indizes
Mingus

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

Zum Beispiel habe ich einen Satz oder 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 einen anderen Satz erhalten kann, der wäre:
C : [2, 1, 4, 3, 0 ] – was dem Index jedes Elements in ‘B’ entspricht, im Original ‘A’.

In Matlab können Sie beispielsweise Folgendes tun:

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

Kann jemand eine gute Möglichkeit sehen, dies zu tun?

C Sortieren und Verfolgen von Indizes
Lukasz Wiklendt

Verwenden 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 verwenden

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 sort_indexes-Funktion mithilfe eines zusätzlichen Vektors automatisch neu anordnen.

  • Ich liebe diese Antwort. Wenn Ihr Compiler keine Lambdas unterstützt, können Sie eine Klasse verwenden: template class CompareIndicesByAnotherVectorValues ​​{ std::vector* _values; public: CompareIndicesByAnotherVectorValues(std::vector* values) : _values(values) {} public: bool operator() (const int& a, const int& b) const { return (_Werte)[a] > (_Werte)[b]; } };

    – Jaav

    18. Oktober 2012 um 7:47 Uhr


  • Ich liebe diese Antwort auch, es ist nicht notwendig, den ursprünglichen Vektor zu kopieren, um den Vektor von Paaren zu erstellen.

    – Kopf an Schulter

    28. Januar 2013 um 22:43 Uhr

  • Eher als Handarbeit for (size_t i = 0; i != idx.size(); ++i) idx[i] = i; Ich bevorzuge den Standard std::iota( idx.begin(), idx.end(), 0 );

    – Wyck

    30. April 2015 um 17:53 Uhr

  • verwenden #include <numeric> für Jota ()

    – kartikag01

    8. Januar 2017 um 10:16 Uhr


  • iota ist der am wenigsten offensichtlich benannte Algorithmus in der gesamten C++-Standardbibliothek.

    – Seth Johnson

    18. Februar 2019 um 0:06 Uhr

Sie könnten std::pair statt nur ints sortieren – das erste int sind Originaldaten, das zweite int ist der Originalindex. 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:

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 sollte unter Verwendung dieses Komparators sein:

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

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

  • Genau so würde ich es auch machen. Die grundlegende Sortierfunktion verfolgt nicht die alten und neuen Positionen, da dies zusätzlichen unnötigen Overhead verursachen würde.

    – der_Mandrill

    16. Oktober 2009 um 12:13 Uhr

  • Der Nachteil dieser Funktion besteht darin, dass Sie Speicher für alle Werte neu zuweisen müssen.

    – Jaav

    18. Oktober 2012 um 7:50 Uhr

  • Dies ist offensichtlich ein praktikabler Ansatz, hat jedoch den Nachteil, dass Sie Ihren ursprünglichen Container von “Container mit Zahlen” in “Container mit Paaren” ändern müssen.

    – Ruslan

    5. März 2018 um 10:23 Uhr


1646260449 699 Warum werden meine PHP Dateien als einfacher Text angezeigt duplicate
Mystische Kraft

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 Elemente von V zu vergleichen

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

  • Liebe deine Antwort. kannst du sogar verwenden std::iota() für eine elegantere Initialisierung von map

    – Nimrod Morag

    18. Februar 2018 um 5:24 Uhr

  • Ja, wir können es benutzen! Danke für den Vorschlag

    – Mystische Kraft

    21. Februar 2018 um 6:18 Uhr

  • std::iota(V.begin(),V.end(),x++); kann sein std::iota(V.begin(),V.end(),0);. keine Notwendigkeit zu erstellen und zu verwenden x.

    – Alex Xu

    28. November 2020 um 19:48 Uhr

1647078609 135 C Sortieren und Verfolgen von Indizes
Aditya Aswal

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

Jetzt a enthält sowohl unsere Werte als auch ihre jeweiligen Indizes in der Sortierung.

a[i].first = value bei i‘th.

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

1647078609 41 C Sortieren und Verfolgen von Indizes
hkyi

Ich habe eine generische Version von Index Sort 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 ist die gleiche wie die von std::sort, mit Ausnahme eines Indexcontainers zum Empfangen sortierter Indizes. 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 die 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 schreiben Sie std::sort as um

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

  • Hallo hkyi! Wie instanziieren wir diese Vorlagenfunktion? Es hat zwei Vorlagentypnamen und einer davon ist ein Iterator, wodurch diese Situation sehr selten wird. Könntest du helfen?

    – Scott Yang

    10. Dezember 2018 um 6:29 Uhr

Ich bin auf diese Frage gestoßen und habe herausgefunden, dass das direkte Sortieren der Iteratoren eine Möglichkeit wäre, die Werte zu sortieren und die Indizes zu verfolgen. Es besteht keine Notwendigkeit, einen zusätzlichen Container zu definieren pairs of ( value, index ), was hilfreich ist, wenn es sich bei den Werten um große Objekte handelt; Die Iteratoren bieten den Zugriff sowohl auf den Wert als auch auf 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 ) );
}

zum Anwendungsbeispiel:

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

  • Hallo hkyi! Wie instanziieren wir diese Vorlagenfunktion? Es hat zwei Vorlagentypnamen und einer davon ist ein Iterator, wodurch diese Situation sehr selten wird. Könntest du helfen?

    – Scott Yang

    10. Dezember 2018 um 6:29 Uhr

Erwägen Sie die Verwendung std::multimap 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 Zwischenzeit der Einfügung zu sortieren

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

Zum 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::multimap zu einem std::map ist es, gleiche Werte in Originalvektoren zuzulassen. Bitte beachten Sie auch, dass im Gegensatz zu z std::map, operator[] ist nicht definiert für std::multimap.

993310cookie-checkC++ Sortieren und Verfolgen von Indizes

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy