Re: Einfache Frage zu STD::SORT

From: Holger Pollmann (hihp_at_uboot.com)
Date: 09/09/04 

Date: 9 Sep 2004 10:08:17 GMT

Ernst Baumann <carlox@web.de> schrieb:

> sort
> template<class RanIt>
> void sort(RanIt first, RanIt last);
> template<class RanIt, class Pred>
> void sort(RanIt first, RanIt last, Pred pr);
> The first template function reorders the sequence designated by
> iterators in the range [first, last) to form a sequence ordered by
> operator<. Thus, the elements are sorted in ascending order.

Ja. Jetzt fällt mir übrigens wieder was ein: VC++ 6.0 stammt noch aus
der Zeit vor dem Standard und hat noch einige Probleme mit Templates.
Manche Teile der standard library sind darum nur mit Tricks
implementiert. Wenn du die standard library lernen möchtest, solltest
du dich nicht an der Implementierung durch VC++ 6.0 orientieren.

>> So ein Iterator kann z.B. ein Pointer auf ein Objekt sein oder
>> auch was anderes, je nachdem halt, wie der jeweilige Iterator
>> definiert ist.
>
> Der Iterator bei einem Objekt, das über das Template vector
> erzeugt wurde, also z.B:
> std::vector<K> abc;
> (wobei K eine beliebige Klasse ist) ist ein Pointer auf ein Objekt
> von K. (falls es stimmt was ich in der Beschreibng des Templates
> vector herausgelesen habe). Ist das richtig?

Nein, nicht zwingend. Ein Iterator KANN ein Pointer sein, muß es aber
nicht.

>>> 2) AmeisenCompare() ist doch ein Konstruktor.
>>
>> Nein. Du rufst den Konstruktor auf. Und was ist das Ergebnis eines
>> Konstruktors? Eben, ein Objekt. Du erzeugst damit ein temporäres
>> Objekt, das nur für die Dauer des Befehlsaufrufs existiert.
>
> Es wird also ein temporäres Objekt der Klasse AmeisenCompare
> erzeugt, oder?

Exakt.

> Ich glaube, in Java sagt man dazu auch anonymes Objekt?

Keine Ahnung, Java mache ich nicht :-)

>>> die Funktion sort() benutzt intern das dritte
>>
>> Parameter (das auch Prädikat genannt wird, daher "Pred" =
>> Predicate) pr wie eine Funktion, also in etwa
>> pr(a, b);
>> Das geht eben deshalb, weil der ()-Operator definiert wurde.
>
> Das verstehe ich überhaupt nicht:
> 1) Was ist ein Prädikat?

Eine Funktion, die eine Frage mit Ja oder Nein (also in boolean: true
oder false) beantwortet.

Der kleiner-Operator ( < ) beantwortet z.B. die Frage, ob das erste
Argument kleiner ist als das zweite.

> 2) Durch den 3. Parameter AmeisenCompare() wird ein temporäres
> Objekt erzeugt (habe ich verstanden). _Wer_ oder _Was_ veranlaßt
> dann, daß dann der in der zu diesem Objekt gehörigen Klasse
> AmeisenCompare der dort implementierte (überladene) Operator ()
> aufgerufen wird und nicht ein anderer dort evtl. auch
> implementierter (oder gar keiner)?

sort() ruft das als Prädikat übergebene Objekt auf, und zwar mit den
zwei Iteratoren, die es gerne vergleichen möchte.

> Was wäre passiert, wenn ich nicht den Operator () implemetiert
> hätte, sondern z.B. den Operator * in der Klasse AmeisenCompare
> implemetiert (überladen) hätte, oder mehrere Operatoren?

Es dürfte einen Fehler geben, weil sort() eben das Objekt nicht mit dem
()-Operator aufrufen kann.

Weil so ein Aufruf eines solchen Objekts wie ein Funktiosnaufruf
aussieht (eben z.B. pr(a, b) ), bezeichnet man so ein Objekt übrigens
auch als Funktionsobjekt oder Functor.

> Welcher wird dann aufgerufen?

Immer der ()-Operator.

> Das ist mir absolut unklar. Muß man dazu wissen, was ein Prädikat
> ist?

Es hilft, die Funktionsweise zu verstehen.

> Besteht ein Zusammenhang zwischen einem Prädikat und einem
> Operator?

Als Prädikat werden eben üblicherweise Funktionsobjekte eingesetzt, und
zum Funktionsobjekt wird ein Objekt dadurch, daß es einen ()-Operator
hat :-)

> In meinen Büchern habe ich zu Prädikaten nichts gefunden.

Du solltest dir am besten ein Buch über die Standard Library zulegen.
Ich hab's auch vorher nicht verstanden.

>> Gar nicht. Der sort()-Funktion ist total schnuppe, woher die
>> Elemente kommen, über die es läuft; sort() will nur eine Sequenz
>> haben, deren Anfang und (Ende+1) es bekommt. Stelle dir das so
>> vor:
>>
>> template<class RanIt, class Pred>
>> void sort(RanIt first, RanIt last, Pred pr)
>> {
>> while(first != last){
>> // do something ++first; } }
>
> Dann muß aber ++ ein überladener Operator sein, der der für ein
> Objekt einer beliebigen Klasse (über Template) definiert sein muß,
> oder?

Nein, es kommt nur darauf an, daß für den Typ RanIt der
Präfix-++-Operator definiert ist.

Wenn du also
  std::vector<K>
benutzt hast, muß für
  std::vector<K>::iterator
u.a. der ++-Operator definiert sein. Sonst ist es halt kein Iterator. 

-- 
( ROT-13 if you want to email me directly: uvuc@ervzjrexre.qr ) 
"Sie tragen Trauer? Der Untergang der DDR?" - "Nein, Leni Riefenstahl. 
Der Führer hat sie zu sich genommen." -- Abschiedsshow Scheibenwischer, 
02.10.2003