sortproblem mit der stl

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