Unklarheit zur std::map definition

Aber ist die Äquivalenzanforderung nicht damit erfüllt, nur dass eben keine echte Sortierung erfolgt?
Wenn nicht, wie lautet die Definition?

Muss ich daher auf eine Hashtabelle umsteigen?
unordered_map ist mit meinem compiler (ICC 10) mit Laufzeittests extrem langsam.

Sebastian Pizer

Wie wär's mit RTFM !?

std::map will sortieren. Sortieren machen wir in C++ über eine strikte, schwache Ordnungsrelation (wie "<" eine ist). Aus einer solchen Relation leitet sich std::map alles ab, inklusive der Äquivalenz.

Ich verstehe nicht warum z.B. das keine strikte, schwache Ordnung ist:

struct Key_Cmp
{
  bool operator () (const Key* links, const Key* rechts) const
  {
	  if(links->a < rechts->a) return true;
	  if(links->b < rechts->b) return true;
	  return links->c < rechts->c;
  }
};

Jedenfalls fällt da wieder die genannte Assertion fehl. Aber diesmal nur wenn ich ein Element mit einem Wert a einfügen will, der bereits vorhandenen ist.

Sebastian Pizer

Probier mal das hier aus:

Key link = {2,0,1};   
  Key rech = {1,0,2};

Was soll Deine Vergleichsfunktion da zurückgeben und was gibt sie wirklich zurück?

OK, mir fehlt einfach der Schlaf.
So muss es natürlich aussehen:

struct Key_Cmp
{
  bool operator () (const Key* links, const Key* rechts) const
  {
	  if(links->a < rechts->a) return true;
	  if(links->a > rechts->a) return false;
	  if(links->b < rechts->b) return true;
	  if(links->b > rechts->b) return false;
	  return links->c < rechts->c;
  }
};

Lohnt es sich bei so etwas bereits eine hash_map / unsorted_map zu verwenden?

Sebastian Pizer

retter schrieb:

Lohnt es sich bei so etwas bereits eine hash_map / unsorted_map zu verwenden?

K.A. Wenn Du aber schon willig bist, unordered_map zu benutzen, kannst Du ja auch als Schlüssel einfach tuple<int,int,int> nehmen. Tuple kommt schon mit vorgefertigten Vergleichsoperatoren (lexikalische Sortierung) daher.

Gruß,
SP

unskilled

struct cmp
{
  bool operator() (const Key* lhs, const Key* rhs) const
  {
    if(lhs->a != rhs->a)
      return lhs->a < rhs->a;
    if(lhs->b != rhs->b)
      return lhs->b < rhs->b;
    return lhs->c < rhs->c;
  }
};

finde ich übersichtlicher...

kanns sein, dass du noch immer nicht geschrieben hast, _was_ du eigentlich machen möchtest?
wie sollen wir dir sagen, ob du es auch so und so machen kannst, wenn du nicht sagst, was du machen willst...
also tu das einfach mal und ich bin mir sicher, dass es ne hübschere lösung gibt, als das, was du bisher gepostet hast...

bb

Ich muß Objektzeiger über einen komplexen Schlüssel referenzieren.
Der Schlüssel ist in meinem ersten Problemfall ist wie im Beispiel ein Tripel vom Typ <int, int, int>.

Als nächstes muss ich die gleichen Objekte mit einem Schlüssel vom Typ <int, int, const char*> referenzieren.
Kann man für den Vergleich der Zeichenkette strcmp benutzen, daher erfüllt es die strikte, schwache Ordnungsrelation?

volkard

unskilled schrieb:

struct cmp
{
  bool operator() (const Key* lhs, const Key* rhs) const
  {
    if(lhs->a != rhs->a)
      return lhs->a < rhs->a;
    if(lhs->b != rhs->b)
      return lhs->b < rhs->b;
    return lhs->c < rhs->c;
  }
};

finde ich übersichtlicher...

Danke.

retter schrieb:

Als nächstes muss ich die gleichen Objekte mit einem Schlüssel vom Typ <int, int, const char*> referenzieren.
Kann man für den Vergleich der Zeichenkette strcmp benutzen, daher erfüllt es die strikte, schwache Ordnungsrelation?

Kann ich selber beantworten: ja klar.

Nochmal danke an alle die bei der schweren Geburt geholfen haben!

Noch eine Frage, warum bietet es sich wie behauptet nicht an, den Funktionoperator () für den Vergleich gleich in der Klasse/Struktur zu definieren, wo beide Argumente von dem selben Typ sind?

volkard

retter schrieb:

Noch eine Frage, warum bietet es sich wie behauptet nicht an, den Funktionoperator () für den Vergleich gleich in der Klasse/Struktur zu definieren, wo beide Argumente von dem selben Typ sind?

In der Klasse kannste gerne den op< definieren. Wozu da den op()?
Das mit dem op() ist gut geeignet, daß Du mal nach dem und mal nach anderem sortzieren kanns.

sort(leute.begin(),leute.end(),cmp_nachPostleitzahl);
ausgabe();
sort(leute.begin(),leute.end(),cmp_nachName);
ausgabe();

unskilled

retter schrieb:

Noch eine Frage, warum bietet es sich wie behauptet nicht an, den Funktionoperator () für den Vergleich gleich in der Klasse/Struktur zu definieren, wo beide Argumente von dem selben Typ sind?

beide argumente vom selben typ? Oo was hat das damit zu tun, wo die fkt deklariert wurde?
ich hab die vermutung, dass du iwie keine ahnung hast>.<
aber wenn du dein problem gelöst hast, ist ja alles in ordnung...

bb

volkard schrieb:

retter schrieb:

Noch eine Frage, warum bietet es sich wie behauptet nicht an, den Funktionoperator () für den Vergleich gleich in der Klasse/Struktur zu definieren, wo beide Argumente von dem selben Typ sind?

In der Klasse kannste gerne den op< definieren. Wozu da den op()?
Das mit dem op() ist gut geeignet, daß Du mal nach dem und mal nach anderem sortzieren kanns.
sort(leute.begin(),leute.end(),cmp_nachPostleitzahl);
ausgabe();
sort(leute.begin(),leute.end(),cmp_nachName);
ausgabe();

Danke. Ist es für den Compiler dann genauso möglich mittels inlining zu optimieren?
Ich frage micht weiterhin ob man für meine Problembeispiele nicht lieber gleich eine Hashtabelle nehmen sollte.

unskilled schrieb:

beide argumente vom selben typ? Oo was hat das damit zu tun, wo die fkt deklariert wurde?

Weil ich den Funktor zu dieser Klasse logisch zuordnen kann?

ich hab die vermutung, dass du iwie keine ahnung hast>.<

Wer hat das schon Meister?

volkard

retter schrieb:

Ist es für den Compiler dann genauso möglich mittels inlining zu optimieren?

Ja.

Ich frage micht weiterhin ob man für meine Problembeispiele nicht lieber gleich eine Hashtabelle nehmen sollte.

Ich auch. Aber das hängt dann doch von den zu erwartenden Daten ab und lässt sich im Voraus nicht gut abschätzen. Mach doch einfach beides und miss.

Nur noch eine kleine Frage...ist es legal memcmp im operator< für std::map zu verwenden? (im Sinne der geforderten Ordnung)

Fytch

retter schrieb:

Nur noch eine kleine Frage...ist es legal memcmp im operator< für std::map zu verwenden? (im Sinne der geforderten Ordnung)

Nach fünf Jahren hast du deinen alten Thread rausgesucht um in ihm zu posten statt einfach einen neuen aufzumachen? lol

Hoffentlich hab ich dich richtig verstanden:
Ja, ist erlaubt (sofern du im richtigen Speicherbereich vergleichst). Jedoch kannst du deine Elemente ja bestimmt auch normal vergleichen statt mit memcmp , oder?