Zeiger Template Methode / qsort

Kronos_m

Hallo zusammen,
kann mit jemand sagen, wie ich dieses kleine problem gelöst bekomme?

// Prototyp
	friend int compare_int(const void* a, const void* b);
// ...

template <class T> void List<T>::sort(void)
{
	qsort(this->list, this->count, sizeof(T), compare);
}

// friend of member
template <class T> int compare(const void* a, const void* b)
{
	return *(T*)a - *(T*)b;
}

Ich möchte gern Daten mit qsort sortieren und muss der Funktion einen Zeiger auf eine compare Funktion übergeben. Das ganze soll mit einem template gelöst werden, weil ich Daten sortieren möchte unabhängig davon, ob es sich um einen 'int' oder 'double' oder 'char' handelt!

Ist nur ein Ansatz, ich weiß nicht genau, wie ich das lösen kann.

Danke für eure Hilfe!

jencas

qsort() geht davon aus, dass die Daten sequentiell im Speicher liegen. Bist Du sicher, dass Deine List-Klasse das leistet? Warum verwendest Du nicht std::list und deren Memberfunktion sort()?

pumuckl

schau mal im Tutorial deiner Wahl nach Komparatoren/Funktoren. Dann kannst du dem qsort z.B. ein std::less<T> übergeben. natürlich muss es dafür entsprechend angepasst werden.

pumuckl

jencas schrieb:

Bist Du sicher, dass Deine List-Klasse das leistet? Warum verwendest Du nicht std::list und deren Memberfunktion sort()?

ist er.. er nennt seine vector-Klasse List, um die Leute hier im Forum zu verwirren und sich an C# zu orientieren

Kronos_m

Perfekt erkannt

Danke für die Hilfe, ich werde mal nach Komparatoren/Funktoren suchen. Mal sehen was dabei rumkommt! Melde mich bestimmt wieder

Nexus

Kronos_m, hast du schon von std::sort() gehört? Das wird in C++ eigentlich benutzt, da kannst du dir auch das void* -Rumgefrickel sparen. Und wenn du sowieso schon Templates verwendest...

jencas

pumuckl schrieb:

ist er.. er nennt seine vector-Klasse List, um die Leute hier im Forum zu verwirren und sich an C# zu orientieren

omg

jencas

Kurzes instruktives Beispiel: http://codepad.org/vNbu2I4F

Kronos_m schrieb:

template <class T> void List<T>::sort(void)
{
	qsort(this->list, this->count, sizeof(T), compare);
}

Wieder einmal drückst Du einer C-Funktion etwas auf, was sie gar nicht leisten kann. qsort tauscht zwei Elemente, indem es einfach die rohen Bytes im Speicher vertauscht. Das ganze geht nur so lange gut, bis Dein T mal ein nicht-POD ist, welches so ein Gefrickel auf Byte-Ebene nicht verkraftet.

Es gibt auch nicht-PODs, die soetwas verkraften (also "trivial vertauschbar" sind). Aber verlassen kannst Du dich darauf nicht.

Ich hoffe, das Wort "Gefrickel" kommt auch so negativ beladen an, wie ich's gemeint habe.

Kronos_m schrieb:

Ich möchte gern Daten mit qsort sortieren und muss der Funktion einen Zeiger auf eine compare Funktion übergeben. Das ganze soll mit einem template gelöst werden, weil ich Daten sortieren möchte unabhängig davon, ob es sich um einen 'int' oder 'double' oder 'char' handelt!

Wie schon erwähnt: Nimm einfach std::sort aus dem <algorithm> Header. Das ist typsicher, scheller und weiß auch ohne explizite Angabe einer Vergleichsfunktion, was zu tun ist, sofern der Typ mit dem < Operator vergleichbar ist.

Gruß,
SP

Sebastian Pizer schrieb:

Wie schon erwähnt: Nimm einfach std::sort aus dem <algorithm> Header. Das ist typsicher, scheller und weiß auch ohne explizite Angabe einer Vergleichsfunktion, was zu tun ist, sofern der Typ mit dem < Operator vergleichbar ist.

Wieso ist std::sort schneller?

hustbaer

C++Fan 2009 schrieb:

Sebastian Pizer schrieb:

Wie schon erwähnt: Nimm einfach std::sort aus dem <algorithm> Header. Das ist typsicher, scheller und weiß auch ohne explizite Angabe einer Vergleichsfunktion, was zu tun ist, sofern der Typ mit dem < Operator vergleichbar ist.

Wieso ist std::sort schneller?

inlining

C++Fan 2009 schrieb:

Wieso ist std::sort schneller?

Der Vergleich zwischen std::sort<> und qsort ist eines der Paradebeispiele, bei denen C++ besser wegkommt.

std::sort<> ist ein Funktions-Template und der Compiler kann eine spezielle Sortierfunktion generieren, in der die Vergleichsfunktion schon direkt eingebaut ist. Das ist dann der Fall, wenn als Sortierfunktion ein Funktor benutzt wird, dessen operator()-Funktion als inline-Funktion deklariert wurde.

Das Äquivalent in C wäre eine eigens für die bestimmte Typ/Vergleichsfunktion-Kombination handgeschriebene Sortierfunktion. Da keiner jedesmal eine neue Sortierfunktion schreiben will, benutzt qsort stattdessen einen Typ-agnostischen Funktionszeiger für die Vergleichsfunktion. Nachteile: Es ist Typ-unsicher (void*), langsamer (so ein Funktionsaufruf auch ein bischen Zeit) und nicht für non-PODs geeignet.

Gruß,
SP

Kronos_m

Sebastian Pizer schrieb:

Wieder einmal drückst Du einer C-Funktion etwas auf, was sie gar nicht leisten kann. qsort tauscht zwei Elemente, indem es einfach die rohen Bytes im Speicher vertauscht. Das ganze geht nur so lange gut, bis Dein T mal ein nicht-POD ist, welches so ein Gefrickel auf Byte-Ebene nicht verkraftet.

Ich habe mit qsort auch schon stuct arrays und der weiteren sortiert, so schlimm kann das also nicht sein! Man muss lediglich die compare Funktion für einen solchen Fall anpassen.

Außerdem wollte ich auch nur PODs (erstmal) sortieren.

Ich weiß das man(n) das Rad nicht immer neu erfinden muss, wenn es doch schon da ist. Aber auch nur Übung macht den Meister. ^^ Also muss man manchmal eigene Wege gehen um etwas dazu zu lernen, was ich hier gerade versuche Danke für eure Tatkräftige Hilfe dabei

Nexus

Kronos_m schrieb:

Ich habe mit qsort auch schon stuct arrays und der weiteren sortiert, so schlimm kann das also nicht sein! Man muss lediglich die compare Funktion für einen solchen Fall anpassen.

"So schlimm kann das nicht sein" ist eine sehr weise Behauptung, noch dazu, da du bisher nur mit PODs hantiert hast. In modernem C++ sind aber POD-Structs und Arrays eher die Ausnahme, Klassen sind da angesagt. Entsprechend versagt dein qsort() .

Wenn du den Leuten hier nicht glaubst, dass du einen unnötig schweren Weg auf dich nimmst und später garantiert Probleme damit haben wirst, ist das deine Sache. Schliesslich musst du ja wissen, wie du programmierst, wir können dir nur einen Rat geben. Aber du lernst durch qsort() nicht einmal viel, eher beginnst du, dir die C-Sichtweise anzueignen und void* zu verharmlosen. Wie auch immer, wir haben dich gewarnt...

Kronos_m

Jetzt hast du mich aber falsch verstanden

Freue mich über die Hilfe. Und ich beschäftige mich auch mit den Tipps, z.B. std::sort()!

Eigentlich wollte ich ja auch nur zahlen und strings sortieren. Wie kann ich denn Objekte sortieren? Wie wird denn festgelegt welches "größer" als das andere ist?
Kann ich jede beliebiges Objekt als Parameter an

std::sort()

übergeben?

Kronos_m schrieb:

Eigentlich wollte ich ja auch nur zahlen und strings sortieren.

Mit "strings" geht's ja schon los. Meinst Du std::string? Das ist übrigens eine nicht-POD-Klasse.

Kronos_m schrieb:

Wie kann ich denn Objekte sortieren? Wie wird denn festgelegt welches "größer" als das andere ist?

Du hast wohl noch nicht auf jencas' Link (siehe Seite 1 dieses Threads) geklickt.

Kronos_m schrieb:

Kann ich jede beliebiges Objekt als Parameter an
std::sort()
übergeben?

Siehe Dokumentation for std::sort. Du kannst std::sort ziemlich viel geben. Das muss nicht mal 'nen Array sein.

Gruß,
SP

Kronos_m

Habe mich zu std::sort() mal schlau gemacht. Ist es "egal", ob ich einen Iterator oder einen Pointer übergebe?

Ja, ich meinte std::string!

Sebastian Pizer schrieb:

Kronos_m schrieb:

Wie kann ich denn Objekte sortieren? Wie wird denn festgelegt welches "größer" als das andere ist?

Du hast wohl noch nicht auf jencas' Link (siehe Seite 1 dieses Threads) geklickt.

Doch sicher, hab ich gemacht Das kann ich ja so mit qsort auch realisieren. Kann ich denn

std::sort(vp.begin(), vp.end(), myFunction())

auch template methoden als dritten Parameter übergeben?

So, dann bin ich auch soweit durch und kann dann fast schon durchstarten ohne euch noch die letzten Nerven kosten zu müssen

Danke

pumuckl

Kronos_m schrieb:

Habe mich zu std::sort() mal schlau gemacht. Ist es "egal", ob ich einen Iterator oder einen Pointer übergebe?

Iteratoren sind ein Konzept, das das Pointer-Konzept erweitert. Andersrum sind Pointer ein Spezialfall des Iteratorkonzepts. Sollte in jedem halbwegs ordentlichen Einsteigerbuch im Kapitel über Iteratoren drinstehen, dass wo immer ein Template einen Iterator-Typ erwartet, ein Pointer auch tut.

pumuckl schrieb:

Iteratoren sind ein Konzept, das das Pointer-Konzept erweitert.

Die Bedeutung des Begriffs "Konzept" ist ja spätestens seit dem "C++0x concepts proposal" eine ganz besondere im Bereich generischer Programmierung. Hier ist die Rede von Konzepten, Modellen und Typen. Ein Typ T kann Modell eines Konzeptes K sein. Die Parallele zu OOP ist zu erkennen: Ein Objekt O kann Instanz einer Klasse C sein. Die Sache mit den Konzepten wird nicht umsonst als "Typsystem für Typen" beschrieben.

Iterator ist also ein Konzept und ein Typ kann dieses Konzept "modellieren". Ein Zeiger-Typ ist ein solches Modell. Zeiger-Typen sind sogar recht speziell, da sie auch das "verfeinerte" RandomAccessIterator-Konzept modellieren.

Gruß,
SP

hustbaer

Kronos_m schrieb:

Kann ich denn
std::sort(vp.begin(), vp.end(), myFunction())
auch template methoden als dritten Parameter übergeben?

Nope.

Wenn du Funktions-Templates meinst (freie Funktionen), dann kannst du per static_cast<Funktionstyp>() einen Funktionszeiger auf eine Spezialisierung des Funktions-Templates bekommen, und diesen Funktionszeiger kannst du dann an std::sort übergeben.

Du kannst aber Funktoren übergeben, wobei der operator () des Funktors durchaus ein Template sein kann.

du meinst myFunction<typ> !