Zeiger Template Methode / qsort

[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.

[moment mal!]

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.

[jencas]

Kronos_m schrieb:

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.

Na ja, mal salopp erklärt: der Compiler erwartet als 'pred' (drittes Argument von sort()) etwas, was wie

bool f(T const & t1, T const & t2) {...}

aussieht. Und der operator () von

struct f
{
  bool operator () (T const & t1, T const & t2) const {...}
}

sieht beim Aufruf (fast) genauso aus.

[Kronos_m]

Danke euch beiden

Gibt es eine Möglichkeit abzufragen, welcher Datentyp an ein template<class T> übergeben wurde. Sprich, um was für einen Datentypen handelt es sich bei 'T' und kann ich darauf prüfen mit einer if-Abrfage z.B.?

[Dravere]

Kronos_m schrieb:

Gibt es eine Möglichkeit abzufragen, welcher Datentyp an ein template<class T> übergeben wurde. Sprich, um was für einen Datentypen handelt es sich bei 'T' und kann ich darauf prüfen mit einer if-Abrfage z.B.?

Kommt ganz darauf an, was du erreichen möchtest. Es geht zur Laufzeit und zur Kompilezeit. Zur Kompilezeit wäre natürlich vorzuziehen, da es dann nicht die Performance des Programmes beeinflusst.

Grüssli

[Kronos_m]

Dravere schrieb:

Es geht zur Laufzeit und zur Kompilezeit

Zur Kompilezeit reicht aus, denke ich! Wie kann ich das umsetzen?

[Dravere]

Kronos_m schrieb:

Zur Kompilezeit reicht aus, denke ich! Wie kann ich das umsetzen?

Ich hätte gerne noch den Grund gewusst, bei solchen Sachen ist das immer wichtig, da die Leute schnell zu viele Unterscheidungen einbauen, was am Ende eher hinderlich ist. Aber gut, zum Beispiel beim Funktor für die Sortierung, kannst du das einfach durch Überladung machen:

struct MySort
{
  template<typename T>
  bool operator ()(T const& lhs, T const& rhs)
  {
    return lhs < rhs;
  }

  // Überladung:
  bool operator ()(MyClass const& lhs, MyClass const& rhs)
  {
    return lhs.compare(rhs) < 0;
  }
};

Es gibt noch andere Möglichkeiten, es kommt eben ganz darauf an, was du machen möchtest

Grüssli

[Kronos_m]

Ja, danke

Ich denke Überladen ist da wohl die passende Lösung.
Hatte erst an etwas abstrakteres gedacht:

if ( T = int ) { ... }

Aber das geht vermutlich nicht, nehme ich an

Es geht wie du schon erkannt haben wirst immer noch um die Sortierfunktion.

Danke

[Kronos_m]

Hab noch was vergessen:

Dravere schrieb:

struct MySort
{
  template<typename T>
  bool operator ()(T const& lhs, T const& rhs)
  {
    return lhs < rhs;
  }

  // Überladung:
  bool operator ()(MyClass const& lhs, MyClass const& rhs)
  {
    return lhs.compare(rhs) < 0;
  }
};

Es gibt noch andere Möglichkeiten, es kommt eben ganz darauf an, was du machen möchtest

Wenn er den Funktor aufruft. Woher weiß er denn, dass er z.B. die Überladung mit MyClass aufrufen muss? Schließlich könnte er doch auch die andere Variante nehmen, was er auch tun würde, wenn die letztere Überladung fehlt. Konnte ich mich einigermaßen verständlich ausdrücken?

Viele Grüße

[Nexus]

Kronos_m schrieb:

Hatte erst an etwas abstrakteres gedacht:

if ( T = int ) { ... }

Aber das geht vermutlich nicht, nehme ich an

Nein, das geht so nicht. if -Abfragen werden zur Laufzeit ausgewertet. Templatespezialisierung statt Überladung wäre hier übrigens auch eine Möglichkeit. Ach ja, und denk dran: == ist der Gleichheitsoperator, nicht =.

Kronos_m schrieb:

Wenn er den Funktor aufruft. Woher weiß er denn, dass er z.B. die Überladung mit MyClass aufrufen muss? Schließlich könnte er doch auch die andere Variante nehmen, was er auch tun würde, wenn die letztere Überladung fehlt. Konnte ich mich einigermaßen verständlich ausdrücken?

Der Compiler versucht immer, die Version aufzurufen, die am meisten spezialisiert ist. Hier hast du eine allgemeine für T und eine spezielle für MyClass . Wenn du ein MyClass -Objekt übergibst, wird also die entsprechende Überladung ausgewählt. Das Gleiche hast du zum Beispiel auch mit Basis- und abgeleiteten Klassen.

[Sebastian Pizer]

Kronos_m schrieb:

Wenn er den Funktor aufruft. Woher weiß er denn, dass er z.B. die Überladung mit MyClass aufrufen muss?

Man kann die "overload resolution"-Regeln schlecht in einem Satz zusammenfassen. Und wenn, das würde das etwa so aussehen: "Der Compiler wählt den am besten passenden/speziellsten Kandidaten aus."

Details können in einem schlauen C++ Buch nachgelesen werden. Hier spielt so einiges eine Rolle.... (template/non-template, conversions, partial ordering)

Gruß,
SP

[Kronos_m]

Ich habe jetzt mal ein paar Sachen durchprobiert. Hat auch ganz gut geklappt, jetzt hänge ich aber wieder an einer Kleinigkeit, bei der ich nicht verstehe, wieso er das nicht ausführen kann...

LordJaxom schrieb:

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.

Daraufhin habe ich mir folgendes überlegt:

#pragma once
#include <cstdlib>
#include <algorithm>

template <class T> class List
{
private:
	T* list;
	unsigned int count;
	template<class POD> friend int compare_POD(const void* a, const void* b);
public:
//...
	// comparison for sort method
	template<class T> bool operator() (T a, T b) {return a < b;};
//...
};
//...
template <class T> void List<T>::sort(void)
{
	//qsort(this->list, this->count, sizeof(T), &compare_POD<T>);
	std::sort(list, (list + this->count), this);
}
// friend of member
template <class POD> int compare_POD(const void* a, const void* b)
{
	if ( (*(POD*)a - *(POD*)b) < 0 )
		return -1;
	else
		return 1;
}
//...

In der List<T>::sort() Methode rufe ist std::sort() auf. als dritten Parameter übergebe ich den Funktor(?) this, der eine Addresse auf das Objekt darstellt. Ich überlade den operator() und bin somit davon ausgegangen, dass er die Methode automatisch aufruft. Stattdessen erhalte ich die Fehlermeldung:

1>c:\winxp\programme\microsoft visual studio 8\vc\include\algorithm(2823) : error C2064: Ausdruck ergibt keine Funktion, die 2 Argumente übernimmt
1>c:\winxp\programme\microsoft visual studio 8\vc\include\algorithm(2823) : fatal error C1903: Weiterverarbeitung nach vorherigem Fehler nicht möglich; Kompilierung wird abgebrochen.
1>Das Buildprotokoll wurde unter "file://d:\Dokumente und Einstellungen\Nico\Eigene Dateien\Visual Studio 2005\Projects\C++\List\Debug\BuildLog.htm" gespeichert.
1>List - 3 Fehler, 0 Warnung(en)

Anscheinend rufe ich die std::sort() Methode falsch auf, kann mir jemand sagen, wie ich das korrigieren kann?

[Sebastian Pizer]

Kronos_m, schafft Dir doch endlich ein schlaues C++ Buch an und lerne selbständig. Dieses "Versuch-und-Irrtum"-Ratespiel ist doch total unproduktiv.

Kronos_m schrieb:

Daraufhin habe ich mir folgendes überlegt:
[cpp]#pragma once
#include <cstdlib>
#include <algorithm>

template <class T> class List
{
private:
T* list;
unsigned int count;
[...]
public:
[...]
// comparison for sort method
template<class T> bool operator() (T a, T b) {return a < b;};
[...]
};

[...]

template <class T> void List<T>::sort(void)
{
std::sort(list, (list + this->count), this);
}

[/cpp]

#pramga once ist nicht Standard-konform ==> Wegschmeißen.

this ist ein Zeiger vom Typ List<T>* und kein Funktionszeiger/Funktor.

Dein operator() template hat absolut gar nichts mit dem Rest der Klasse zu tun ==> Wegschmeißen. Es gibt übrigends zwei std::sort Versionen. (hint hint)

Du scheinst viele der Beiträge hier ignoriert zu haben. Du kannst jetzt nicht erwarten, dass man sich wiederholt bzw Dir noch helfen will.

Gruß,
SP

[Kronos_m]

Sebastian Pizer schrieb:

#pramga once ist nicht Standard-konform ==> Wegschmeißen.

Hat meine Entwicklungsumgebung automatisch eingefügt, beim erstellen der Klasse (MVS2005). Werde es dann mal rausnehmen.

Sebastian Pizer schrieb:

this ist ein Zeiger vom Typ List<T>* und kein Funktionszeiger/Funktor.

Wusste nicht, dass das nicht geht. Da es beim struct mit dem Objektnamen geklappt hat.

Sebastian Pizer schrieb:

Dein operator() template hat absolut gar nichts mit dem Rest der Klasse zu tun ==> Wegschmeißen.

Soll die compare Funtkion sein. Wie auch in meinem Beispiel auf Seite 3.

Sebastian Pizer schrieb:

Es gibt übrigends zwei std::sort Versionen.

Das weiß ich. Übe doch nur, getreu dem Motto man lernt nie aus.

Sebastian Pizer schrieb:

Du scheinst viele der Beiträge hier ignoriert zu haben. Du kannst jetzt nicht erwarten, dass man sich wiederholt bzw Dir noch helfen will.

Nein, habe ich nicht. Habe auf Grund der vielen guten Hinweise auch schon einiges ausprobiert und geschafft.

Dann will ich mal nicht weiter stören...
Grüße

PS.: Danke noch mal für die zahlreichen nützlichen Infos.

[Michael E.]

Kronos_m schrieb:

Sebastian Pizer schrieb:

this ist ein Zeiger vom Typ List<T>* und kein Funktionszeiger/Funktor.

Wusste nicht, dass das nicht geht. Da es beim struct mit dem Objektnamen geklappt hat.

Hats nicht. Schau nochmal genau hin.