Key->Value ?

[zarilla]

folgendes Problem:
Ich möchte für die Funktion WndProc (WINAPI) einen Weg finden anhand der Windowsmessage und des whandle eine Funktion über den Zeiger auf die entsprechende Funktion aufzurufen.
Diese "Zeigersammlung" soll aber variabel sein, dh sie soll mittels einer Funktion registerEvent() veränderbar sein.
Das hatte ich mir ursprünglich in der Form funcArray[WM_EVENT][whandle]=func vorgestellt. (in PHP würde das sogar funktionieren )
Aber dieses Prinzip Key->Value scheint in C++ nicht praktikabel zu sein (Zugriff auf nichtexistierende Elemente usw).
verkettete Listen lassen sich hierbei auch nicht nutzen oder ?

Ich hoffe, ich konnte mein Problem einigermaßen verständlich schildern.
Gruß
zarilla

 

[chibisuke]

Das sieht aus als wolltest du eine HASHTABLE haben ;-)

vieleicht sogar eine aus dem namespace "std"
In der STL ist meines wissens nämlich so ne klasse enthalten. Leider ist die STL in vielen punkten nicht so ganz das gelbe vom Ei, vor allem was ihre verwendung betrifft...

Aber ne Templateklasse die eine hashtable darstellt ist einfach zu schreiben, kann z.B. mit verketteten listen oder aber auch als dynamisches array erstellt werden...

 

[Tobiasm]

Original geschrieben von chibisuke
Aber ne Templateklasse die eine hashtable darstellt ist einfach zu schreiben, kann z.B. mit verketteten listen oder aber auch als dynamisches array erstellt werden...

Moment, war da nicht was ? Ach ja - eine Hashtable kann man nicht mit einer verketteten Liste darstellen, weil es sich widerspricht. Eine verkettete Liste ist eine verkettete Liste und eine Hashmap eine Hashmap. Und auch die Möglichkeit ein Hasverfahren über ein dynamisches Array darzustellen ist unmöglich. Es gibt zwar dynamisches Hashing, aber auch das wird anders geregelt.

Ganz abgesehen davon, dass es nicht so geht, wie Du es vorschlägst wären eine verkettete Liste bzw. ein dynamisches Array performancetechnisch gesehen absolut nicht empfehlenswert, da eine verkettete Liste beim Suchen eine Laufzeit von O hat und das bei m Nachrichten macht das O(m*n). Wenn man davon ausgeht, dass es genauso viele Nachrichten wie Einträge in der Liste gibt, macht das grob O(n²) und das ist ziemlich schlecht.
Bei einem dynamischen Array hätte man das gleiche Problem, weil man sich, da es dynamisch ist, nicht auf die Adressen verlassen kann, also auch eine Laufzeit von O(n²).

@ Zarilla: Ich persönlich würde vorschlagen, Du machst Dir eine Klasse, die intern aus einer Hastable mit verketteten Überläufen besteht. Was das ist, kannst Du hier: http://www.num.math.uni-goettingen....kript/texte/Datenstrukturen.html#Hashtabellen nachlesen.

MfG

Tobias

 

[Daniel Toplak]

Man muss das Rad nicht neu erfinden, wie chibisuke schon sagte, bietet die STL was derartiges. die Templateklasse "map" wäre für deine Zwecke geeignet.

Gruß Homer

 

[chibisuke]

Moment, war da nicht was ? Ach ja - eine Hashtable kann man nicht mit einer verketteten Liste darstellen, weil es sich widerspricht. Eine verkettete Liste ist eine verkettete Liste und eine Hashmap eine Hashmap. Und auch die Möglichkeit ein Hasverfahren über ein dynamisches Array darzustellen ist unmöglich. Es gibt zwar dynamisches Hashing, aber auch das wird anders geregelt.

Dann erklär mit bitte wie ich es geschaft habe eine entsprechende Hashtable klasse zu schreiben ;-)
Aufbau:
Eine Vektor klasse (welche im übrigen ebenfalls selbst geschrieben ist, und auf dem prinzip der verketteten listen basiert)ähnlich der von Java dient als Grundlage, eingetragen wird jeweils ein objekt von einem hashtableentry typ, der 2 _CObject objekte einander zuordnet, natürlich kann das _CObject das ich zuordnet ein Vektor oder ein Hashtable sein, wodurch genau die funktionalität die gefragt ist realisiert wird. Damit kann ich entweder eine hashtable benutzen die nur ein element pro schlüssel zuläst, oder ich kann einen Vektor dran schalten um mehrere objekte pro schlüssel zu speichern.

Und was die Performance betrifft, so bin ich mir sicher meine Klasse keines falls merkbare unterschiede hatt zur STL klasse....

Naja aber wenn ich mir die aufgabenstellung nochmal anguck:

 funcArray[WM_EVENT][whandle]=func

und mal genau überlegt, dann wird man doch feststellen, das das eigendlich ein stink normales array ist auch in C, das ist keine zuordnung von key => value wie in einer hashtable sondern es handelt sich hier um eine zuordnung von intwert -> funktionspointer
das ist ein einfaches WNDPROC**
Nur musst du aufpassen mit den größen des arrays.... naja da kann eine vektor klasse sicher abhilfe schaffen... std::vector z.B.

 

[Tobiasm]

@Daniel Toplak: Ich weiß, std::map kenne ich. Allerdings habe ich so meine Probleme damit, da der operator [ ] nicht unbedingt sicher ist. Wenn ich nämlich in den eckigen Klammern einen nicht existierenden Schlüssel eintrage, kriege ich einen Standardwert zurück geliefert und dass kann zu sehr schwer zu findenden Fehlern führen.

@chibisuke: Das, was Du da geschrieben hast, war vielleicht ein Assoziativer Container aber definitiv keine Hashmap. Eine Hashmap arbeitet nämlich nach dem Prinzip, dass man einen Schlüssel hat, aus dem die Addresse in einer Tabelle errechnet wird und dieser nicht etwa, wie bei Dir, gesucht werden mus. Außerdem muss die Laufzeit O(1) sein.

Du hast nämlich eine verkettete Liste (das, was Du da als Vektor bezeichnest, ist nämlich gar keiner, weil bei einem Vektor gewährleistet sein muss, dass alle Elemente in einem zusammenhängenden Bereich liegen und das ist bei Dir nicht der Fall) in der Du jeden Eintrag suchst, was eine Laufzeit von O zur folge hat. Des weiteren wird von einer Hastable verlangt, dass ihre Laufzeit bei mehreren Dimensionen weiterhin O(1) bzw. O ist (wenn die Anzahl der Dimensionen n ist und diese Variabel ist), bei Dir ist dieser Wert aber O(n²).

Außerdem scheinst Du die STL nicht zu kennen, denn sonst wüsstest Du, dass in er STL gar keine Hashmap vorkommt. std::vector ist keine, da hier nicht eine allgemeine Form der Hashtable vorliegt, sondern nur der Speziallfall Array. Auch std::map und std::multimap sind keine Hastables sondern sind intern als Baum organisiert auß dem einfachen Grund, dass die beiden Klasse nur mit den Operatoren < und > auskommen müssen (der Standard schreibt außerdem auch nur eine Laufzeit von log vor).

MfG

Tobias

 

[zarilla]

mit vector kann man 2Dimensional arbeiten oder
also zb mvector[3][4] würde funktionieren ?

Wenn ich nämlich in den eckigen Klammern einen nicht existierenden Schlüssel eintrage, kriege ich einen Standardwert zurück geliefert und dass kann zu sehr schwer zu findenden Fehlern führen.

ist das nur bei map so oder auch bei vector ?

 

[chibisuke]

@chibisuke: Das, was Du da geschrieben hast, war vielleicht ein Assoziativer Container aber definitiv keine Hashmap. Eine Hashmap arbeitet nämlich nach dem Prinzip, dass man einen Schlüssel hat, aus dem die Addresse in einer Tabelle errechnet wird und dieser nicht etwa, wie bei Dir, gesucht werden mus. Außerdem muss die Laufzeit O(1) sein.

Ich glaub ich sagte HASHTABLE und nicht HASHMAP... das ist meines wissens immer noch ein unterschied... Auf jeden fall aber, ist mit vollig banane was dein standart vorschreibt, in meinen Programmen zählt MEINE auffassung von Standarts, und diese ist das es funktionieren muss, und halbwegs effizient dazu, wie das Realisiert wird, ob das irgendwie nach irgendwelchen standarts is is mit Wurst... dann nenn ich das ding nicht hashtable sondern pustekuchen und fertig...

Du hast nämlich eine verkettete Liste (das, was Du da als Vektor bezeichnest, ist nämlich gar keiner, weil bei einem Vektor gewährleistet sein muss, dass alle Elemente in einem zusammenhängenden Bereich liegen und das ist bei Dir nicht der Fall) in der Du jeden Eintrag suchst, was eine Laufzeit von O zur folge hat. Des weiteren wird von einer Hastable verlangt, dass ihre Laufzeit bei mehreren Dimensionen weiterhin O(1) bzw. O ist (wenn die Anzahl der Dimensionen n ist und diese Variabel ist), bei Dir ist dieser Wert aber O(n²).

Siehe oben....

Außerdem scheinst Du die STL nicht zu kennen, denn sonst wüsstest Du, dass in er STL gar keine Hashmap vorkommt. std::vector ist keine, da hier nicht eine allgemeine Form der Hashtable vorliegt, sondern nur der Speziallfall Array. Auch std::map und std::multimap sind keine Hastables sondern sind intern als Baum organisiert auß dem einfachen Grund, dass die beiden Klasse nur mit den Operatoren < und > auskommen müssen (der Standard schreibt außerdem auch nur eine Laufzeit von log vor).

Wer Lesen kann is klar im Vorteil.
1.) sagte ich das std::vector eine VEKTORKLASSE IST, denn für diesen anwendungsfall genügt ein vector, und es muss keine hash_map eingesetzt werden...
2.) schonmal std::hash_map versucht? definiert is <hash_map>
http://msdn.microsoft.com/library/d.../en-us/vcstdlib/html/vclrfhash_mapmembers.asp

Was das beispiel betrifft:
einfach 2 Vektoren ineinander schachteln, wie dus auch mit Arrays tun würdest

 

[Tobiasm]

@ chibisuke: So zuerst einmal zu std::hash_map. Dieser Fehler tut mir leid und ich nehme den gesamten letzten Absatz zurück und behaupte das Gegenteil. Entschuldige bitte.

Original geschrieben von chibisuke
Ich glaub ich sagte HASHTABLE und nicht HASHMAP... das ist meines wissens immer noch ein unterschied... Auf jeden fall aber, ist mit vollig banane was dein standart vorschreibt, in meinen Programmen zählt MEINE auffassung von Standarts, und diese ist das es funktionieren muss, und halbwegs effizient dazu, wie das Realisiert wird, ob das irgendwie nach irgendwelchen standarts is is mit Wurst... dann nenn ich das ding nicht hashtable sondern pustekuchen und fertig...

Ich glaube wir verstehen uns bei den ersten beiden Absätzen falsch. Hier beziehe ich mich gar nicht auf die STL sondern erst einmal auf die genannten Datenstrukturen/Algorithmen (Die Namen aus der STL sind - verständlicher Weise - ähnlich). Und da ist es wirklich so gesagt, wie ich gesagt habe - ich habe es sogar extra noch mal nachgelesen in "Algorithmen und Datenstrukturen" von T. Ottmann und P. Widmayer.
Und da hast Du ganz klar Müll geschrieben. Auf der einen Seite nennst Du Namen von Datenstrukturen und sagst dann noch im gleichen Satz wieder das Gegenteil. Wenn Du Dich nicht klar bzw falsch ausdrückst (so sind in der Informatik HASHTABLE und HASHMAP Synonyme), darfst Du Dich auch nicht wundern, dass jemand sagt, dass Du Müll schreibst.

Außerdem ist das, was Du da beschrieben hast, nicht wirklich effizient, zumindest nicht, wenn Du es so umgesetzt hast, wie Du beschrieben hast. Sicher, bei kleinen Datenmengen wird es nicht so ins Gewicht fallen, ganz einfach weil moderne Prozessoren so schnell sind aber sobald größere Datenmengen durchgejagt werden sollen, unterliegt eine verkettete Liste was die Zugriffsgeschwindigkeit angeht einfach einer Hashmap (oder auch Hashtable).

Original geschrieben von chibisuke
Wer Lesen kann is klar im Vorteil.
1.) sagte ich das std::vector eine VEKTORKLASSE IST[...]

Habe ich je etwas anderes gesagt? Aber es stimmt schon, std::vector ist eine Vektor-Klasse.

Original geschrieben von chibisuke

es muss keine hash_map eingesetzt werden...

Du hast doch gesagt, dass er eine Hashtable nutzen sollte.

@ zarilla: Auch bei std::vector gibt es das Problem, dass bei den [ ], wenn Du vorher nichts anderes eingetragen hast, ein Standardwert zurück gegeben wird. Außerdem kannst Du auch über die Grenzen des Vektors hinaus auf den Speicher zurück greifen. Ersteres Problem sollte keins sein, wenn Du verschachtelte Vektoren nimmst (schließlich ist ein Standard-Vektor einfach leer) und zweiteres kann man afaik über den Operator () umgehen.

MfG

Tobias

 

[chibisuke]

Nun wie schon gesagt, Irgendwelche definitionen von datenstrkturen oder so sind mir einfach nur egal... Denn es geht mir um die funktionsweise nach außen hin... und eine hashtable ordnet nunmal einem schlüssel einen wert zu. und ein Vector speichert nunmal daten aufeinanderfolgend, wobei wenn man ein element entfernt die anderen nachrücken.
Wie dies intern aussieht, das mir für meinen teil egal.... Ich steh auf dem standpunkt.. Funktionieren muss es, der rest kümmert mich herzlich wenig...
Und außerdem ist in dem Speziellen Anwendungsfall, für den ich das geschrieben hatte das in der weise besser geeignet. Und bei einem 3D Spiel das in bei einfachen 2D Operationen für die Lokalisierung auf solche elemente setzt, da fälle es absolut nicht ins gewicht, vor allem da die CPU auslastung so und so bei 100% festklebt. auch wenn nicht wirklich viel getan wird, und ob er nun n halbes FPS mehr hatt oder nich, das ist in einstellungsmenüs ziemlich egal.

Du hast doch gesagt, dass er eine Hashtable nutzen sollte.

Lies mal in einem meiner Späteren posts ;-)
Auf den ersten blick sah es aus wie wenn man ne hashtable brauchen würde, doch bei genauerem betrachen fällt auf das ja die WM_* als konstanden die INT werte abbilden definiert sind, und das wiederum erlaubt die verwendung eines Vektors, was um einiges einfacher is.