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?
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.
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.
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];} );
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.
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)()) ;
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( ).
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.
9933100cookie-checkC++ Sortieren und Verfolgen von Indizesyes