Wie arbeitet die find Methode der Map?

camper

kleiner schrieb:

Und der Kleiner-Operator kann schon anhand der Länge die Entscheidung treffen.

wie das? btrachte einfach mal: "a", "aa" und "b"

Simon2

Hi,

das sollte doch eigentlich in dem map-Header stehen, oder ?
Letztlich ist die Frage schon beantwortet, zieht aber die Frage nach sich: "Wie arbeitet der operator<() für Strings ?" ...
... die aber eigentlich auch im string-Header beantwortet werden müsste (WENN man das template-Zeugs lesen kann ).

Gruß,

Simon2.

camper schrieb:

kleiner schrieb:

Und der Kleiner-Operator kann schon anhand der Länge die Entscheidung treffen.

wie das? btrachte einfach mal: "a", "aa" und "b"

Das ändert nichts daran dass zuerst nach der Länge geguckt wird. Das ist gut so.

Braunstein

In meiner string-Implementation findet der vergleich (operator<) über die Funktion
char_traits::compare statt. Die zu vergleichende Länge wird dabei auf die kleinere der beiden Längen festgelegt.
Die Funktion compare sieht so aus

static int compare (const char_type* s1, const char_type* s2, size_t n)
    {
      size_t i=0;

      while ( i < n )
      { 
        if ( !eq( s1[i], s2[i] ) )
        {
          if ( lt( s1[i], s2[i]) )
            return -1;
          else
            return 1;               
        }
        i++;
      }
      return 0;
    }

Bashar

l schrieb:

Das ändert nichts daran dass zuerst nach der Länge geguckt wird. Das ist gut so.

Es wird zuerst nach der Länge geguckt, aber nicht danach entschieden:

21.3.6.8 - basic_string::compare [lib.string::compare]

int compare(const basic_string<charT,traits,Allocator>& str ) const

-1- Effects: Determines the effective length rlen of the strings to compare as the smallest of size() and str.size(). The function then compares the two strings by calling traits::compare(data(), str.data(), rlen).

-2- Returns: the nonzero result if the result of the comparison is nonzero. Otherwise, returns a value as indicated in Table ??:

compare() results Condition Return Value
size() < str .size() < 0
size() == str .size() 0
size() > str .size() > 0

Im Endeffekt ergibt sich eine lexikographische Ordnung, genau wie mit strcmp.

Bashar schrieb:

l schrieb:

Das ändert nichts daran dass zuerst nach der Länge geguckt wird. Das ist gut so.

Es wird zuerst nach der Länge geguckt, aber nicht danach entschieden

Ich sehe worauf du hinauswillst, ich sehe auch den obigen Codeausschnitt der Implementierung (ich hatte mich geirrt). Dennoch verstehe ich nicht warum. In meinen Augen ist es eine erhebliche Leistungssteigerung wenn man sofort nach der Länge entscheidet, da, so behaupte ich, es irgendwie unwahrscheinlich ist, dass man in der Praxis "a", "aa" und "b" miteinander vergleicht.

Wenn doch, so wäre es nett, wenn man zwei unterschiedliche Implementierungen von operator< anbieten und den Programmierer entscheiden lassen könnte. Aber das ist ja leider nicht möglich.

Oder es ist möglich, aber sehr unbequem.

MFK

l schrieb:

Dennoch verstehe ich nicht warum.

Also ich möchte String normalerweise lexikographisch sortiert haben, eben wie im Lexikon. Da stehen auch nicht die kurzen Wörter vor den langen.

Wenn doch, so wäre es nett, wenn man zwei unterschiedliche Implementierungen von operator< anbieten und den Programmierer entscheiden lassen könnte. Aber das ist ja leider nicht möglich.

Du kannst der map doch sagen, wie sie sortieren soll.

MFK schrieb:

l schrieb:

Dennoch verstehe ich nicht warum.

Also ich möchte String normalerweise lexikographisch sortiert haben, eben wie im Lexikon. Da stehen auch nicht die kurzen Wörter vor den langen.

Uh, ja, macht Sinn.

Wenn doch, so wäre es nett, wenn man zwei unterschiedliche Implementierungen von operator< anbieten und den Programmierer entscheiden lassen könnte. Aber das ist ja leider nicht möglich.

Du kannst der map doch sagen, wie sie sortieren soll.[/quote]
Wie das?

THX 1138

In dem du selber ein Funktionsobjekt schreibst, dass die Strings so vergleicht, wie du möchtest, und es der Map als Paramter übergeben (siehe Compare in der STL Docu )

1310-Logik schrieb:

In dem du selber ein Funktionsobjekt schreibst, dass die Strings so vergleicht, wie du möchtest, und es der Map als Paramter übergeben (siehe Compare in der STL Docu )

Hab vielen Dank.

Simon2

l schrieb:

...In meinen Augen ist es eine erhebliche Leistungssteigerung wenn man sofort nach der Länge entscheidet, ...

ich glaube, Dir schwebt nicht der "operator<()", sondern der "operator!=()" vor.
IMO ist der Fall, dass zwei zu vergleichend Strings gleich lang sind eher die Ausnahme sind....

Gruß,

Simon2.