sortproblem mit der stl

headmyshoulder

Hallo allerseits,

ich will mit der STL sortieren, das ist prinzipiell einfach:

double a[n];
// schreibe irgendwas in a rein
sort( a , a+n );
// oder auch sort( a , a+n , comp );

Mein problem ist jetzt, wie ich gleichzeitig einen zweites beliebiges array b in die gleiche Reihenfolge wie a bringe, also sowas

soll danach

werden. Sieht jemand eine Moeglichkeit wie sowas elegant mit der STL geloest werden kann? Vielleicht wenn man iteratoren neu definiert?

Zur Not kann man das auch loesen indem man eine Struktur erstellt, die jeweils eine Zeile enthaelt und dann eine Vergleichsfunktion definiert. Ist dann allerdings nicht mehr so elegant.

Danke fuer Eure Hilfe.

asc

headmyshoulder schrieb:

Mein problem ist jetzt, wie ich gleichzeitig einen zweites beliebiges array b in die gleiche Reihenfolge wie a bringe, also sowas...

...Zur Not kann man das auch loesen indem man eine Struktur erstellt, die jeweils eine Zeile enthaelt und dann eine Vergleichsfunktion definiert. Ist dann allerdings nicht mehr so elegant.

Doch, genau das ist es sogar eher: elegant. Zumindestens in der von dir beschriebenen Situation.

Fellhuhn

Eine multi_sort Funktion wäre aber dennoch mal eine nette Sache. Aber hält einen ja keiner davon ab nicht eine selbst zu schreiben.

headmyshoulder

Ich benutze ziemlich oft Zeigerarithmetik, die wuerde man dann durch das Definieren von Strukturen nicht mehr benutzen koennen, bzw. muesste immer zwischen struct und array hin- und herspringen.

Prinzipiell muesste ja nur die swap Funktion im sort geaendert werden, dann waere das geloest. Ist vielleicht nicht mehr die schnellste Variante dann, aber er waere immer noch recht kleiner kompakter code.

headmyshoulder

Ahh, ich hab grad gesehen, dass die boost library sowas kann. Wenn ich weiss wie das funktioniert sag ich bescheid, es sei denn jemand ist schneller.

drakon

headmyshoulder schrieb:

Ich benutze ziemlich oft Zeigerarithmetik, die wuerde man dann durch das Definieren von Strukturen nicht mehr benutzen koennen, bzw. muesste immer zwischen struct und array hin- und herspringen.

Was soll da nicht mehr gehen?

headmyshoulder

drakon schrieb:

headmyshoulder schrieb:

Ich benutze ziemlich oft Zeigerarithmetik, die wuerde man dann durch das Definieren von Strukturen nicht mehr benutzen koennen, bzw. muesste immer zwischen struct und array hin- und herspringen.

Was soll da nicht mehr gehen?

Im oben genannten beispiel muesste ich dann sowas anlegen:

struct A {
  double a ;
  int b;
}

bool Comp( struct a , struct b ) { return a.a < b.a ; };

A a[n]
// populate A
sort( A , A+n , Comp );

Meistens benutze ich aber double oder int arrays:

double *a = new double[n];
int *b = new double[n];

und die jedesmal in eine struktur zu packen gefaellt mir nicht so gut.

headmyshoulder schrieb:

drakon schrieb:

headmyshoulder schrieb:

Ich benutze ziemlich oft Zeigerarithmetik, die wuerde man dann durch das Definieren von Strukturen nicht mehr benutzen koennen, bzw. muesste immer zwischen struct und array hin- und herspringen.

Was soll da nicht mehr gehen?

Im oben genannten beispiel muesste ich dann sowas anlegen:
struct A {
  double a ;
  int b;
}

bool Comp( struct a , struct b ) { return a.a < b.a ; };

A a[n]
// populate A
sort( A , A+n , Comp );
Meistens benutze ich aber double oder int arrays:
double *a = new double[n];
int *b = new double[n];
und die jedesmal in eine struktur zu packen gefaellt mir nicht so gut.

Was spricht denn gegen:

struct A {
  double a ;
  int b;
}

bool Comp( struct a , struct b ) { return a.a < b.a ; };

A *a = new A[n];
// populate A
sort( a , a+n , Comp );

?

drakon

Du kannst auch eine Vergleichsfunktion mit double's schreiben..

headmyshoulder

Belli schrieb:

Was spricht denn gegen:

struct A {
  double a ;
  int b;
}

bool Comp( struct a , struct b ) { return a.a < b.a ; };

A *a = new A[n];
// populate A
sort( a , a+n , Comp );

?

Eigentlich nichts. Mich wuerde trotzdem mal interessieren, ob es auch anderes geht .

headmyshoulder

drakon schrieb:

Du kannst auch eine Vergleichsfunktion mit double's schreiben..

Wie meinst Du das?

drakon

Eigentlich nichts. Mich wuerde trotzdem mal interessieren, ob es auch anderes geht .

Du solltest mal ein wenig konkreter werden, was du willst und was dein Problem ist.

Schlussendlich kannst du das auch mit einem std::pair, std::tr1::tuple lösen, oder was auch immer, aber die Daten irgendwie beieinander zu halten musst du offensichtlich ja. Und die getrennt zu speichern und dann mit einem komplizierten Algorithmus das wieder herbiegen zu wollen ist schwachsinn. Das gezeigte ist elegant sicher und kann auch leicht erweitert werden.
Also bitte ein wenig konkreter, was dir nicht passt, dann können wird dir auch helfen, aber "ein geht das auch anderst?" bringt niemandem etwas.

headmyshoulder

drakon schrieb:

Schlussendlich kannst du das auch mit einem std::pair, std::tr1::tuple lösen, oder was auch immer, aber die Daten irgendwie beieinander zu halten musst du offensichtlich ja. Und die getrennt zu speichern und dann mit einem komplizierten Algorithmus das wieder herbiegen zu wollen ist schwachsinn. Das gezeigte ist elegant sicher und kann auch leicht erweitert werden.
Also bitte ein wenig konkreter, was dir nicht passt, dann können wird dir auch helfen, aber "ein geht das auch anderst?" bringt niemandem etwas.

Ok, Du hast Recht ich werds ein bisschen ausfuehrlicher machen. Das konkrete Beispiel ist Algorithmus zur Eigenwert- und funktionsberechnung einer Matrix. Meistens werden dann die Eigenwerte sortiert und dazu muessen auch die entsprechen Eigenvektoren genauso mit sortiert werden. Im Code sieht das bei mir dann so aus (ja, kann man auch anders machen):

const int n = 10;
double matrix[n*n];
// populate matrix
double eval[n];
double evec[n*n];
CalcEigensystem( matrix , eval , evec );

Die Eigenwerte kann ich jetzt schnell mit

sort(eval,eval+n);

sortieren, allerdings muss das auch mit den Eigenvektoren in der gleichen Reihenfolge wie die Eigenwerte sein. Ich hab keine Lust da erst eine Struktur zu fuellen, die sortieren, und dann alles wieder in die urspruenglichen arrays zu schreiben. Es gibt viele Probleme dieser Art (sortieren einer Matrix nach einer Spalte, Sortieren von daten...) und ich wollte mal generell so fragen ob es auch clevere Methoden mit der stl gibt ohne vorher strukturen zu erstellen oder die sort routinen selbst zu schreiben. Das Problem scheint mir auch sehr generell zu sein und eine einfache Loesung gibts hoffentlich dafuer.

drakon

Wie schon gesagt, du kannst auch eine Vergleichsfunktion schreiben, die dir das übernimmt.

bool Comp1( double a , double b ) { return a < b ; };
bool Comp2 ( double a , double b ) { return a < (b+1) ; };
..

So kannst du dir die Bedingung, nach der sortiert wird selber bestimmen. (Wenn du noch mehr Argumente brauchst, musst du dir mal Binder anschauen, oder auch Funktoren nutzen).

headmyshoulder

drakon schrieb:

Wie schon gesagt, du kannst auch eine Vergleichsfunktion schreiben, die dir das übernimmt.
bool Comp1( double a , double b ) { return a < b ; };
bool Comp2 ( double a , double b ) { return a < (b+1) ; };
..
So kannst du dir die Bedingung, nach der sortiert wird selber bestimmen. (Wenn du noch mehr Argumente brauchst, musst du dir mal Binder anschauen, oder auch Funktoren nutzen).

Hmm, wie man die Vergleichsfunktion aendert ist mir klar, aber dadurch wird ein anderes array trotzdem nicht in die Reihenfolge wie ein anderes array gebracht. Oder was meinst Du mit Bindern und Funktoren?

Nexus

Für mich besteht die sauberste Lösung auch darin, ein Struct mit mehreren Werten (oder gleich std::pair ) zu erstellen. Dann kann man ein Array dieses Typs sortieren lassen.

Mit Vergleichskriterien ginge das schon, aber das ist auch nicht unbedingt einfacher. Man müsste eine eigene Klasse schreiben, die die Arrays wrappt und Iteratoren bereitstellt, um das STL-Konzept einzuhalten und korrekt sortiert zu werden. Ich weiss nicht, ob sich der Aufwand lohnt.

Willst du überhaupt rohe Arrays verwenden? So ist es beispielsweise mühsam, eine Spalte zu übergeben. Ein std::tr1::array könnte man verschachteln und so besser auf ein Unterarray (das einer Spalte entspricht) zugreifen.

drakon

Nexus schrieb:

Mit Vergleichskriterien ginge das schon, aber das ist auch nicht unbedingt einfacher. Man müsste eine eigene Klasse schreiben, die die Arrays wrappt und Iteratoren bereitstellt, um das STL-Konzept einzuhalten und korrekt sortiert zu werden. Ich weiss nicht, ob sich der Aufwand lohnt.

Es ginge, denke ich auch einfacher, wenn er da nur einen Zeiger auf den anderen Container übergibt. Schliesslich weiss er ja, wie viele Elemente dort drin sind und dann ginge das schon, aber das ist alles andere als sauber. Ich würde auch sagen, dass in dem Fall das ganze in ein struct zu werfen und dann zu sortieren.

Fellhuhn

Oder selbst einen Sortieralgorithmus implementieren der eben genau sowas beachtet. Nicht aufwändig und meiner Meinung nach sauberer als das krampfhaft mit der STL über irgendwelche Umwege und Umkopieren von Elementen in Strukturen etc. lösen zu wollen.

Wenn man std::sort noch einen "swap"-Operator/Funktor mitgeben könnte, wäre das natürlich alles kein Problem.

headmyshoulder

Fellhuhn schrieb:

Wenn man std::sort noch einen "swap"-Operator/Funktor mitgeben könnte, wäre das natürlich alles kein Problem.

Prinzipiell koennte man einen eigenen Iterator in die sort funktion stecken, der bei iter_swap gleichzeitig die andere Elemente mit swap. Ist aber nicht so schoen dafuer noch einen eigenen Iterator zu implementieren.

Ich hab aber ne einfachere Loesung fuer mich gefunden. Ich erstell einfach nur ein Index array, in welchem die Sortierreihenfolge drinsteckt:

template<class T> void GetIndexSet( T* val , int *index , int n )
{
  vector< pair<T,int> > temp;
  for( int i=0 ; i<n ; i++ ) temp.push_back( pair<T,int>( val[i] , i ) ) ;
  sort( temp.begin() , temp.end() );
  for( int i=0 ; i<n ; i++ ) index[i] = temp[i].second;
}

Jetzt kann man entweder alles nach der Ordnung sortieren:

GetIndexSet( array , index , n )
for( int i=0 ; i<n ; i++ ){
  temp1[i] = array[ index[i] ];
  temp2[i] = array2[ index[i] ];
  ...
}
array = temp1;  // oder sowas aehnliches

oder falls man das nicht braucht, kann man trotzdem auf die gewuenschte Sortierung zugreifen:

for( int i=0 ; i<n ; i++ ) DoSomething( array[ order[i] ] );

Eventuell koennte man die GetIndexSet Funktion noch auf beliebige Iteratoren verallgemeinern und eine Vergleichsfunktion/klasse verallgemeinern.

headmyshoulder

Nexus schrieb:

Willst du überhaupt rohe Arrays verwenden? So ist es beispielsweise mühsam, eine Spalte zu übergeben. Ein std::tr1::array könnte man verschachteln und so besser auf ein Unterarray (das einer Spalte entspricht) zugreifen.

Das mach ich schon die ganze Zeit^^. Wie gesagt, das sind meist numerische Daten. Unterarrays bilden ist dabei recht einfach, man uebergibt dem sort ja auch nur die Start- und Endpointer, bzw. Iteratoren. std::tr1::array seh ich grad zum ersten Mal, sieht ganz interessant aus, obwohl es eventuell problem mit nicht const Groessen hat.

drakon

headmyshoulder schrieb:

Nexus schrieb:

Willst du überhaupt rohe Arrays verwenden? So ist es beispielsweise mühsam, eine Spalte zu übergeben. Ein std::tr1::array könnte man verschachteln und so besser auf ein Unterarray (das einer Spalte entspricht) zugreifen.

Das mach ich schon die ganze Zeit^^. Wie gesagt, das sind meist numerische Daten. Unterarrays bilden ist dabei recht einfach, man uebergibt dem sort ja auch nur die Start- und Endpointer, bzw. Iteratoren. std::tr1::array seh ich grad zum ersten Mal, sieht ganz interessant aus, obwohl es eventuell problem mit nicht const Groessen hat.

std::tr1::array aka boost::array ist dazu gedacht eine STL ähnliche Schnittstelle für arrays zu bieten.
http://www.boost.org/doc/libs/1_37_0/doc/html/array.html

Somit, wenn du variable Grössen hast, kannst du bei std::vector bleiben/wechseln.