Unklarheit zur std::map definition

[retter]

Hallo!

Ich bekomme es einfach nicht zustande Klarheit über das genaue Verhalten beim Einfügen von Elementen in eine std::map zu erlangen.

...
typedef struct S
{
  int a,b,c;
  bool operator () (const S& l, const S& r) const {return !memcmp(...);}
};

std::map<S, K*, S> karte;

...
S       s = {1,2,3};
void*   p = GibMirEinZeiger();

karte[s] = p;

So wie ich das heraugelesen habe, nutzt std::map das Funktionobjekt um festzustellen ob der Schlüssel l (im Beispiel) vor dem Schlüssel r eingefügt werden soll.

Ist also der erste Paramter des Funktionsobjektes der Schlüssel, der hinzugefügt wird?
Wie erfährt std::map ob die Schlüssel gleich sind?

Währe wirklich toll wenn mir da jemand weiterhelfen könnte!

PS.: Wo kann man allgemein solche Dinge über die STL am besten erfahren? Google lieferte mir da kaum taugliche Seiten.

[volkard]

würde der code mir auf arbeit begegnen, würde ich mich erstmal nach der versteckten kamera umdrehen.
stl ohne buch geht kaum. nachher ist http://www.cppreference.com/wiki/stl/map/start ideal.

[retter]

volkard schrieb:

würde der code mir auf arbeit begegnen, würde ich mich erstmal nach der versteckten kamera umdrehen.

Wie meinst du das?

stl ohne buch geht kaum. nachher ist http://www.cppreference.com/wiki/stl/map/start ideal.

Danke, aber das hilft mir überhaupt nicht weiter.

[retter]

Lösung selbst gefunden:

"Two objects x and y are equivalent if both f(x, y) and f(y, x) are false. Note that an object is always (by the irreflexivity invariant) equivalent to itself."
http://www.sgi.com/tech/stl/StrictWeakOrdering.html

[unskilled]

retter schrieb:

volkard schrieb:

würde der code mir auf arbeit begegnen, würde ich mich erstmal nach der versteckten kamera umdrehen.

Wie meinst du das?

weil das nicht viel mit C++ zu tun hat, was du dort machst^^

typedef struct S
{
  int a,b,c;
  bool operator () (const S& l, const S& r) const {return !memcmp(...);}
};

das typedef ist falsch - wundert mich auch gerad, dass das überhaupt kompiliert...
der name ist auch iwie nichts sagend, meinst du nicht auch?!
nen konstruktor wäre auch klasse
den op() in der klasse an sich zu überladen ist auch keine gute idee
wenn es sinn ergibt, nen op< zu erstellen, dann mach das - ansonsten nimm nen extra struct als comparer

std::map<S, K*, S> karte;

wie gesagt - entweder
std::map<S, K*> karte; und op< überladen
oder
std::map<S, K*, S_cmp> karte; (wenn S nicht logisch sortierbar ist) und in S_cmp den op() überladen

Jz könnte man noch diskutieren, wieso du rohe Zeiger verwendest - aber das kannst du vll wirklich nicht beeinflussen...

S       s = {1,2,3};
void*   p = GibMirEinZeiger();

karte[s] = p;

wieso void*?

retter schrieb:

stl ohne buch geht kaum. nachher ist http://www.cppreference.com/wiki/stl/map/start ideal.

Danke, aber das hilft mir überhaupt nicht weiter.

ist aber die beste dokumentation, die es gibt (zumindest hab ich noch keine andere gesehen, die so toll ist und zu nahezu jeder funktion nen bsp. bietet)

die map bekommt die äquivalenz (wie auch jeder andere stl-container) raus, indem sie auf x<y und y<x prüft.
strict weak ordering hat nur teilweise was damit zu tun - das sagt nämlich nur aus, dass für x<y nicht auch x>y gelten darf.
und das aus x<y und y<z auch x<z folgen muss.
das steht so gar auch auf der von dir geposteten seite:
a is less than b then b is not less than a, if a is less than b and b is less than c then a is less than c, and so on.
hat imho aber nicht so viel mit deiner wirklichen frage zu tun...

bb

[retter]

Also ich komme noch immer nicht klar:

...
struct Schlüssel
{
   int a,b,c;
};
struct Schlüssel_Vergleich
{
  bool operator () (const Schlüssel* links, const Schlüssel* rechts) const
  {
     return links.a != rechts.a || links.b != rechts.b || links.c != rechts.c;
  }
};

map<const Schlüssel*, Wert*, Schlüssel_Vergleich> karte;

for(...)
{
  ...
  map<const Schlüssel*, Wert*, Schlüssel_Vergleich>::iterator suchergebnis;
  suchergebnis = karte.find(meinSchlüssel);

  pair<map<const Schlüssel*, Wert*, Schlüssel_Vergleich>::iterator, bool> drin;
  drin = karte.insert(pair<const Schlüssel*, Wert*>(meinSchlüssel, meinWert));

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

Also warum werden da Einträge nicht gefunden, obwohl map::insert false liefert?

Vielen Dank für Eure Hilfe!

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

[retter]

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

[retter]

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.

[retter]

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?

[retter]

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

[retter]

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]

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!

[retter]

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?