STL Container

[Alf@Uni]

Kann mir einer bitte mal erklären, wie ich in ein hash_multimap objekte vom Typ A* nach value sortiert (also nach der Adresse von B) eintrage? Ich hab das noch nie gemacht und seh da irgendwie noch nicht ganz durch. ^^



class A
{
B* value;
}

[Aqualon]

http://www.cppreference.com/cppalgorithm/sort.html

Als Comparefunktion musst du ne bool-Funktion schreiben, die 2 entsprechende Objekte vom Typ A aufgrund von value vergleicht und true zurückgibt, wenn value von ptr1 < value von ptr2 ist.
bool cmp(A* ptr1, A* ptr2) {...}
So in der Art sollte das gehen.

Aqua

[Trap]

Alf@Uni[/POST]']Kann mir einer bitte mal erklären, wie ich in ein hash_multimap objekte vom Typ A* nach value sortiert (also nach der Adresse von B) eintrage?
hash_multimap ist kein Container aus dem C++ Sprachstandard. Daher solltest du auch verraten wo du den hergenommen hast und wo es die Dokumentation dazu gibt.

[del_4901]

Trap[/POST]']hash_multimap ist kein Container aus dem C++ Sprachstandard. Daher solltest du auch verraten wo du den hergenommen hast und wo es die Dokumentation dazu gibt.
ok, guter Einwand :) Das ist so ein Microsoft Dingens.
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vcstdlib/html/vclrfhashmultimap_class.asp

würde auch noch gehn ... wobei die ja die gl. Schnittstelle haben:
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vcstdlib/html/vclrfHashset_class.asp

[del_4901]

GEil GEil GEil ... alle Tutorial etc. sind mit int, wo natürlich alles schon schoen implementiert ist ... solln sich doch alle erschießen!

[Trap]

Normaleweise sollte es reichen wenn du in deiner Klasse A einen bool operator<(const A& other) hinzufügst.

Ich bin mir aber nicht 100% sicher, dass das mit der hash_multimap funktioniert, sortiert und hash zusammen ist eher unüblich (und die Dokumentation ist da ziemlich unklar). Mit std::multimap geht es so auf jeden Fall.

[del_4901]

Trap[/POST]']Normaleweise sollte es reichen wenn du in deiner Klasse A einen bool operator<(const A& other) hinzufügst.

Ich bin mir aber nicht 100% sicher, dass das mit der hash_multimap funktioniert, sortiert und hash zusammen ist eher unüblich (und die Dokumentation ist da ziemlich unklar). Mit std::multimap geht es so auf jeden Fall.

Soweit hab ich auch schon probiert. das erzeugen eines Behälters schein er zu machen, doch dann beim einsetzen meckert er:
d:\programme\microsoft visual studio 8\vc\include\xhash(61) : error C2440: 'type cast' : cannot convert from 'const RenderObject' to 'size_t'

was ich ja nunmal gar nicht verstehen will.

template<class _Kty> inline
size_t hash_value(const _Kty& _Keyval)
{ // hash _Keyval to size_t value one-to-one
return ((size_t)_Keyval ^ _HASH_SEED);
}

[del_4901]

Super Pointer kann ich einsetzen (die sind auch "klein" genug für size_t) aber ich zweifle sehr sehr stark daran das meine <,>,... operatoren auch mit den Pointern funktioniern ... und ich zweife noch stärker daran, das man die vergleichsoperatoren für bestimmte Pointertypen überschreiben kann.

[Coda]

Eine hash_multimap gibts nicht in der STL.

Argh - zu spät :usad:

[del_4901]

Coda[/POST]']Eine hash_multimap gibts nicht in der STL.

Argh - zu spät :usad:

Du sammlest auch grad wieder Posts ^^

Hilf mir lieber, ich weiß selber das das nicht ganz STL konform ist ... das liegt aber vielen compilern mit bei. zumindestens behauptet google das ... ich weiß nur das es die MS Teile alle haben.

[Coda]

AlphaTier[/POST]']Du sammlest auch grad wieder Posts ^^.
Auf der Spielwiese wird eh nicht gezählt... und sonst naja...

AlphaTier[/POST]']Hilf mir lieber, ich weiß selber das das nicht ganz STL konform ist ... das liegt aber vielen compilern mit bei. zumindestens behauptet google das ... ich weiß nur das es die MS Teile alle haben.
Warum benützt du nicht einfach std::multimap, da ist der Zugriff auch O(log n) - Ist glaube ich fast immer ein Red-Black-Tree.

Da müsstest du dann einen Funktor basteln der den Pointer vergleicht ala
class AComp
{
bool operator(A &a, A &b) { return a.value > b.value; }
}

Das Problem ist, dass eine Hashmap gar keine Vergleiche macht, sondern einen Hashwert ermittelt. Das ist Implementierungsspezifisch, da kann ich dir nicht helfen.

[del_4901]

Coda[/POST]']Auf der Spielwiese wird eh nicht gezählt... und sonst naja...


Warum benützt du nicht einfach std::multimap, da ist der Zugriff auch O(log n) - Ist glaube ich fast immer ein Red-Black-Tree.

ja ich will aber auch einsetzen und löschen ... das ist im Baum nicht so toll


Hier ist übrigens ein Lösungsansatz:
http://www.codeguru.com/forum/showthread.php?s=&threadid=281880&highlight=hashmap

da unten ist ein kleiner Fehler (einmal string zuviel)

[Coda]

AlphaTier[/POST]']ja ich will aber auch einsetzen und löschen ... das ist im Baum nicht so toll
Son Schmarrn. Alle Ops auf nen Red-Black-Tree sind O(log n). Muss immer nur das Element finden und paar Rotationen durchführen. Machen wir grad in Algorithmen...

Das Problem ist dass z.B. in Visual C++ 2003 die hash_map in den stdext-Namespace gewandert ist, du müsstest also typedefs für verschiedene Compiler verwenden - auch nicht schön.

Eine andere Möglichkeit wenn du unbedingt eine Hashmap willst (warum auch immer) ist mal wieder boost (http://www.boost.org/doc/html/hash.html).

[del_4901]

Coda[/POST]']Son Schmarrn. Alle Ops auf nen Red-Black-Tree sind O(log n). Muss immer nur das Element finden und paar Rotationen durchführen. Machen wir grad in Algorithmen...

Das Problem ist dass z.B. in Visual C++ 2003 die hash_map in den stdext-Namespace gewandert ist, du müsstest also typedefs für verschiedene Compiler verwenden - auch nicht schön.

Eine andere Möglichkeit wenn du unbedingt eine Hashmap willst (warum auch immer) ist mal wieder boost (http://www.boost.org/doc/html/hash.html).

Ich bau mir eh noch meine eigene Hash DS ... es musste nur gerade schnell gehn und solange halten bis ich was Handfestes habe ^^

Außerdem brauch ich ja was für den profiler zum vergleichen, ob ich dann artig war^^

[Coda]

Ne Hashmap ist eh um Längen einfacher als nen Red-Black-Tree, dürfte also kein Problem sein.

But: Don't reinvent the wheel, just fucking stick to the STL

Ne multimap ist wirklich nicht so schlecht ;)

[del_4901]

Coda[/POST]']
Da müsstest du dann einen Funktor basteln der den Pointer vergleicht ala
class AComp
{
bool operator(A &a, A &b) { return a.value > b.value; }
}

Das Problem ist, dass eine Hashmap gar keine Vergleiche macht, sondern einen Hashwert ermittelt. Das ist Implementierungsspezifisch, da kann ich dir nicht helfen.

Das komische VergleichsdingensKlassenDingsdaBumsda ^^ braucht man auch in der Hash_multiset. Jedenfalls Läuft es jetzt. Sehr gut sogar.
Ich nehm das Teil nämlich für meinen Rendercache zum sortieren nach Material. Und er sortiert (frag mich nicht wie ... er macht es, allein das zählt) nach den Adressen meiner MaterialBäume. Das funzt sehr sehr gut und schnell.

[del_4901]

Coda[/POST]']
Ne multimap ist wirklich nicht so schlecht ;)
wenn dann MultiSet??? .. ich will das ja sortiert eingesetzt haben.
Was ist da eigendlich der Unterschied? ich bin nie über Vector und List hinausgekommen ... bis gestern

[Coda]

AlphaTier[/POST]']Das komische VergleichsdingensKlassenDingsdaBumsda ^^ braucht man auch in der Hash_multiset. Jedenfalls Läuft es jetzt. Sehr gut sogar.
Ich nehm das Teil nämlich für meinen Rendercache zum sortieren nach Material. Und er sortiert (frag mich nicht wie ... er macht es, allein das zählt) nach den Adressen meiner MaterialBäume. Das funzt sehr sehr gut und schnell.
Ein Hashmap sortiert aber normal gar nicht... :|

AlphaTier[/POST]']wenn dann MultiSet??? .. ich will das ja sortiert eingesetzt haben.
Was ist da eigendlich der Unterschied? ich bin nie über Vector und List hinausgekommen ... bis gestern
Eine Map ist Key->Value und ein Set nur Values. Allerdings brauchst du eigentlich nur std::map oder std::set, nicht std::multimap/set nehm ich an.

[del_4901]

Coda[/POST]']Ein Hashmap sortiert aber normal gar nicht... :|


Eine Map ist Key->Value und ein Set nur Values. Allerdings brauchst du eigentlich nur std::map oder std::set, nicht std::multimap/set nehm ich an.

grad erst aufgestanden ^^

hash_multiSET nehm ich. und ja er sortiert ... da bin ich 1000% sicher!

Der unetrschied zw. Multi und nicht multi ist das nicht Multi nur ne Menge beschreibt, und Multi einen Behälter der auch mehrere speichert.

[Coda]

Dann ist es kein Hashset, was die Sache noch misteriöser macht...

Wenn du sortiert haben willst dann nimm erst recht nen std::set Mensch X-D

Wie krank ist das denn... befass dich mal mit den Algorithmen bevor du sie benützt.

AlphaTier[/POST]']Der unetrschied zw. Multi und nicht multi ist das nicht Multi nur ne Menge beschreibt, und Multi einen Behälter der auch mehrere speichert.
Ja schön. Und du hast Objekte mit gleichen Pointern die du mehrfach speichern möchtest oder was? :|

[del_4901]

Coda[/POST]']Dann ist es kein Hashset, was die Sache noch misteriöser macht...

Wenn du sortiert haben willst dann nimm erst recht nen std::set mensch X-D

Wie krank ist das denn...


Ja schön. Und du hast Objekte mit gleichen Pointern die du mehrfach speichern möchtest oder was? :|

Ok, ich bin ein Drops, aber niemenden weitererzählen ... ich hatte zum Zeitpunkt des ersten Posts auch schon 2 Bier intus :) Also es handelt sich beim ersten Post nur um einen Tippfehler! Ich hab dabei schon an das richtige gedacht.

[del_4901]

Coda[/POST]']
Dann ist es kein Hashset, was die Sache noch misteriöser macht...

Wenn du sortiert haben willst dann nimm erst recht nen std::set Mensch X-D

Wie krank ist das denn... befass dich mal mit den Algorithmen bevor du sie benützt.

Das habe ich gemacht und nicht umsonnstd as hash_multiSET ausgewählt.
multiset würde auch gehn, aber da ist einsetzen und löschen nicht so schnell wie in hash_multiset (laut MSDN)

Ich ahbe die Algos schon in früheren Semerstern implementiert das ist mir alles schon ein Begriff ^^
Coda[/POST]']
Ja schön. Und du hast Objekte mit gleichen Pointern die du mehrfach speichern möchtest oder was? :|

Mehrere Objekte Teilen sich das gleiche material!

[Coda]

AlphaTier[/POST]']Ich ahbe die Algos schon in früheren Semerstern implementiert das ist mir alles schon ein Begriff ^^
Dann sollte dir doch klar sein, dass eine Hasmap/set nicht sortiert.

[Alf@Uni]

Coda[/POST]']Dann sollte dir doch klar sein, dass eine Hasmap/set nicht sortiert.

Die MS Hash_MultiSet sortiert ... sprich wenn ich durchitteriere, binde ich jedes Material nur 1x ... Das habe ich oft genug nachgeprüft.

[Coda]

Dann ist es keine Hashmap, also kannst gleich den standardkonformen std::multimap Container benützen.