Unklarheit zur std::map definition

Sebastian Pizer

Gib uns doch mal nen kleines, kompilierbares Beispiel, und nicht so etwas aus dem Kopf runtergeschriebenes mit Üs in Klassennamen, Syntaxfehlern, u.s.w.

Tipp1: Versuche die Benutzung des unären *-Operators einzuschränken (weniger Zeiger)
Tipp2: typedef kann praktisch sein.

Sebastian Pizer schrieb:

Tipp1: Versuche die Benutzung des unären *-Operators einzuschränken (weniger Zeiger)

Warum sollte es besser sein hier Werte über call by value zu übergeben?

Bei dem Versuch ein compilierbares Beispiel zu schreiben bin ich auf ein neues Problem gestoßen:

#include "stdafx.h"
#include <map>

using namespace std;

struct Key {int a,b,c;};
struct Key_Cmp
{
  bool operator () (const Key* links, const Key* rechts) const
  {
     return links->a != rechts->a || links->b != rechts->b || links->c != rechts->c;
  }
};

struct Value{int x,y,z;};

typedef map<const Key*, Value*, Key_Cmp> Karte;
Karte karte;

int _tmain(int argc, _TCHAR* argv[])
{
	Key	keyA	= {1,2,3};
	Key	keyB	= {1,3,3};
	Value  value   = {4,5,6};

	karte[&keyA] = &value;

	Karte::iterator suchergebnis;
	suchergebnis = karte.find(&keyB);  // <---

	pair<Karte::iterator, bool> drin;
	drin = karte.insert(pair<const Key*, Value*>(&keyB, &value));

	if(drin.second == false && suchergebnis == karte.end())
		bool retterVerstehtDasNicht = true;

	return 0;
}

Bei dem markiertem find schlägt eine assertion fehl: "invalid operator <"
Ich dachte es reicht hier das Funktionsobjekt? Und warum wird das nicht zur compile-Zeit angemeckert?

Sebastian Pizer

retter schrieb:

Sebastian Pizer schrieb:

Tipp1: Versuche die Benutzung des unären *-Operators einzuschränken (weniger Zeiger)

Warum sollte es besser sein hier Werte über call by value zu übergeben?

Kommt drauf an, was Du machen willst. Die Schlüssel-Objekte in einer map sind üblicherweise klein und handlich, schnell kopierbar. Das ist bei Dir auch der Fall. Wenn Du allerdings Zeiger als Schlüssel verwendest, kannst Du das, worauf sie zeigen, immernoch verändern und die map "durcheinander bringen". Außerdem musst Du Dich dann um die Verwaltung dieser Objekte selbst kümmern, also zusehen, dass die Zeiger nicht ungültig werden oder Du kein Speicherleck bekommst.

retter schrieb:

Bei dem Versuch ein compilierbares Beispiel zu schreiben bin ich auf ein neues Problem gestoßen:
...
struct Key {int a,b,c;};
struct Key_Cmp
{
  bool operator () (const Key* links, const Key* rechts) const
  {
     return links->a != rechts->a || links->b != rechts->b || links->c != rechts->c;
  }
};
...
Bei dem markiertem find schlägt eine assertion fehl: "invalid operator <"
Ich dachte es reicht hier das Funktionsobjekt? Und warum wird das nicht zur compile-Zeit angemeckert?

Dem Compiler ist es ziemlich egal, was Deine Funktion ausrechnet. std::map erwartet, dass die Funktion eine vernünftige, "<"-artige Ordnungsrelation ist. Das ist sie aber in Deinem Fall nicht. std::map stellt während das Programm läuft fest, dass die boolschen Werte, die Du da berechnest, einer "<"-artigen Relation widersprechen. Was Du da geschrieben hast, ist eigentlich so etwas wie "!=".

Gruß,
SP

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?