sortproblem mit der stl

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.

Nexus

headmyshoulder schrieb:

std::tr1::array seh ich grad zum ersten Mal, sieht ganz interessant aus, obwohl es eventuell problem mit nicht const Groessen hat.

Die Klasse std::tr1::array verhält sich grundsätzlich wie normale Arrays, hat aber noch einige Funktionalität mehr. Beispielsweise kann es kopiert und zugewiesen werden und bietet STL-kompatible Funktionen wie begin() , end() , size() . Du arbeitest lieber damit als mit rohen Arrays, im Debug-Modus erhältst du auch Assertions beim Schreiben über Arraygrenzen.

Für std::tr1::array wurde der Weg einer Initialisierungsliste ausgewählt (dies, um noch ähnlicher zu Arrays zu sein). Das führt dazu, dass keine selbst definierten Konstruktoren bereitgestellt werden können. Eventuell muss man das Array daher mit std::fill() oder Ähnlichem initialisieren.

Drehleiter

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

Es gibt in der boost den zip_iterator, der iteratoren aus verschiedenen Containern mit einander verknüpft.

Gruß

Fellhuhn

headmyshoulder schrieb:

...

Einfach ein struct-template das als Konstruktor-Parameter eine Referenz auf den zu sortierenden Container bekommt schreiben. Dieser überlädt dann den bool operator()(int, int) und vergleicht da drin denn die Elemente des Referenzcontainers die mit den beiden Parameter-ints ausgezeichnet sind.
Die eigentliche Sortierfunktion (std::sort) rufst du dann auf einen neu erstellen Index-Container auf, der die Elemente 0 - (toSort.size() - 1) hat, wobei toSort der zu sortierende Container ist.

Anschließend kannst du entweder über den Index-Array auf die Elemente der "sortierten" Arrays zugreifen oder eben die selbst dann umsortieren. An welche Stelle welches Element gehört siehst du ja am Index-Array/Container.

headmyshoulder

Drehleiter schrieb:

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

Es gibt in der boost den zip_iterator, der iteratoren aus verschiedenen Containern mit einander verknüpft.
Gruß

Der Zip Iterator lässt sich leider nicht sortieren :http://lists.boost.org/Archives/boost/2004/07/68758.php