Zeiger Template Methode / qsort

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> !

LordJaxom

hustbaer schrieb:

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.

Wieso casten? Ein Zeiger auf eine freie Templatefunktion oder statische Membertemplatefunktion (nicht Funktionstemplate!) ist das gleiche wie ein Zeiger auf eine normale Funktion.

sort(bla, bla, &myFunction<int>);

jencas

Kronos_m schrieb:

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?

Schau Dir nochmal mein Beispiel an, dort gibt es ein Objekt 'Person', welches aber nur nach dem Member 'nachname' sortiert wird. Welches der Objekte "kleiner" ist, legst Du im operator () des Funktors fest (das bei sort anzugebene Prädikat sollte immer Logik für aufsteigende Sortierung haben, deswegen "kleiner"). Da der Funktor von binary_function abgeleitet ist, kannst Du std::not1 voranstellen, um absteigende Sortierung zu erreichen. Vielleicht schaffe ich es zeitlich in der Mittagspause noch ein erweitertes Beispiel zusammenzuzimmern.

jencas

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct Person
{
   Person(string const & v, string const & n, int a) : vorname(v), nachname(n), alter(a) {}
   string vorname;
   string nachname;
   int alter;
};

ostream & operator << (ostream & os, Person const & p)
{
  os << p.nachname << ", " << p.vorname << " (" << p.alter << ')' << endl;
  return os;  
}

enum Kriterium
{
  Name,
  Alter
};

struct aufsteigend_nach : public binary_function<Person, Person, bool>
{
  aufsteigend_nach(Kriterium k) : kriterium(k) {}

  inline bool operator () (Person const & p1, Person const & p2) const
  {
    if (kriterium == Alter)
      return p1.alter < p2.alter;

    if (p1.nachname < p2.nachname)
      return true;

    if (p1.nachname == p2.nachname)
      return p1.vorname < p2.vorname;

    return false;
  }

private:
  Kriterium kriterium;
};

int main()
{
  vector<Person> vp;
  vp.push_back(Person("Klaus", "Thaler", 24));
  vp.push_back(Person("Maria", "Kron", 44));
  vp.push_back(Person("Paul", "Ahner", 29));
  vp.push_back(Person("Hans A.", "Pils", 37));
  cout << "aufsteigend nach Name:" << endl;
  sort(vp.begin(), vp.end(), aufsteigend_nach(Name));
  copy(vp.begin(), vp.end(), ostream_iterator<Person>(cout));
  cout << "\nabsteigend nach Alter:" << endl;
  sort(vp.begin(), vp.end(), not2(aufsteigend_nach(Alter)));
  copy(vp.begin(), vp.end(), ostream_iterator<Person>(cout)); 
}

Output:

aufsteigend nach Name:
Ahner, Paul (29)
Kron, Maria (44)
Pils, Hans A. (37)
Thaler, Klaus (24)

absteigend nach Alter:
Kron, Maria (44)
Pils, Hans A. (37)
Ahner, Paul (29)
Thaler, Klaus (24)

Live zu erleben unter: http://codepad.org/M5SENoRS

Kronos_m

Danke jencas!

Mir fällt auf, dass ich structs bisher föllig unterschätzt habe
Habe mir zum Üben das ganze mal in "einfach" gebaut:

#include <iostream>
#include <algorithm>

using namespace std;

struct MYSORT {
	template<class T> bool operator() (T a, T b) { return a < b; } 
} mysort;

int main (void)
{
	int iArray[] = {12,315,26,231,3,62,34526,432};
	for (int i = 0; i < 8; i++)
		cout << iArray[i] << endl;
	cout << endl;
	sort(iArray, iArray + 8, mysort);
	for (int i = 0; i < 8; i++)
		cout << iArray[i] << endl;

	return 0;
}

Warum ist es so wichtig, dass ich den '()' Operator überlade?
Ich dachte vorher immer, dass ich in ein struct nur Attribute einbauen kann! Ich vestehe noch nicht ganz, warum die Methode im struct wie aufgerufen wird. Muss der dritte Parameter bei std::sort() nicht ein Zeiger auf eine Funktion sein?

Wäre super, wenn mir jemand verständlich den Ablauf erklären könnte.

Ihr habt mir schon sehr weiter geholfen, danke an alle

PS.: Wenn ich das richtig sehe, dann kann ich doch jetzt alle PODs sortieren!?!

LordJaxom

Der dritte Parameter von sort muss ein "Callable" sein, also etwas, was man irgendwie aufrufen kann.

Callables können in C++ aber nicht nur Funktionszeiger, sondern auch Funktoren sein. Einen Funktor nennt man ein Objekt einer Klasse, welche den operator() implementiert hat. Dadurch kann man dieses Objekt ohne Methodenangabe aufrufen, wie eine freie Funktion.

mysort objekt; // erstelle Objekt vom Typ mysort
if ( objekt( a, b ) ) ... // da mysort ein Funktor ist, lässt es sich aufrufen

Für Dein Beispiel gilt noch, dass Du sort nicht den Namen der Klasse, sondern ein Objekt der Klasse übergeben muss.

sort( ..., ..., mysort() );
// oder:

mysort objekt;
sort( ..., ..., objekt );

PS: structs dürfen dasselbe enthalten wie class. Genaugenommen sind struct und class bis auf die Default-Sichtbarkeit und -Vererbung identisch.