nicht angemeldet
Wann ist ein const_cast angebracht?
sethHallo,
es hat jetzt zwar nicht unbedingt irgendetwas mit Webprogrammierung zu tun, aber ich denke, dass ich in diesem Forum trotzdem richtig aufgehoben bin.
Mein Anliegen ist eine C++-Klasse, die ich zum Wrappen der std::unordered_multimap nutzen wollte. Dabei wollte ich die Schlüssel nicht direkt in der Tabelle speichern, sondern nur einen Pointer. Der Schlüssel selbst liegt in einer anderen Datenstruktur (einer std::list; damit wird bei mehreren Werten eines Schlüssels der Schlüssel trotzdem garantiert nur einmal gespeichert). Nun sieht eine Funktion beispielsweise so aus (ist hoffentlich selbsterklärend):
template<class Key, class Value, class Hash, class Equals>
inline const bool
UM_Wrapper<Key, Value, Hash, Equals>::key_exists(const Key& key) const
{
return data.find(&key) != data.end();
}
Nur habe ich nun das Problem, dass ich gerne eine saubere Schnittstelle einhalten möchte, nämlich das der Schlüssel, den ich erhalte, konstant ist. Das bewirkt allerdings, dass die Zusicherung bei "data.find(&key)" nicht mehr gilt, da hier nur zugesichert wird, dass der Pointer konstant ist, allerdings nicht, dass auch der Speicherbereich, auf den gezeigt wird, konstant ist.
Das könnte man allerdings durch einen Cast lösen:
return data.find(const_cast<Key*>(&key)) != data.end();
Leider liest man aber im Internet viel zu häufig, dass const_cast (genauso, wie reinterpret_cast) "böse" wären und meist auf ein schlechtes Konzept hindeuten. Nun stelle ich mir die Frage, ob in so einem Falle der Cast angebracht ist, oder ob ich meine Klasse überdenken sollte.
Was ist denn Eure Meinung dazu?
Schönen Abend,
Rachus
-
gudn tach!
Mein Anliegen ist eine C++-Klasse, die ich zum Wrappen der std::unordered_multimap nutzen wollte. Dabei wollte ich die Schlüssel nicht direkt in der Tabelle speichern, sondern nur einen Pointer.
mit schluessel meinst du iterator, oder? ein iterator ist ja praktisch schon sowas wie ein pointer, sodass du durch die zusatzlichen pointers eigentlich keine speicherersparnis bekommst.
wenn du einfach iterators und const_iterators statt pointers (auf die iterators) verwenden wuerdest, haettest du das problem nicht, oder verstehe ich dich falsch?
prost
seth-
Hallo,
mit schluessel meinst du iterator, oder? ein iterator ist ja praktisch schon sowas wie ein pointer, sodass du durch die zusatzlichen pointers eigentlich keine speicherersparnis bekommst.
Nun das wäre theoretisch tatsächlich so, wenn ich nicht das Problem gehabt hätte, dass ich dann meiner Hasher und Equaler-Funktion einerseits Pointer und andererseits Iteratoren hätte übergeben müssen. Wenn das geht, klärt mich bitte auf, aber ich habe es vorerst so gelöst, dass ich einen Pointer (als Schlüssel) und einen Iterator (mit als Wert) speichere:
std::list<Key> identifiers;
std::unordered_multimap<Key*, std::pair<class std::list<Key>::iterator, Value>, Hasher, Equaler> data;Der operator() meines Hashers und Equalers sieht dabei übrigens so aus:
template<class Key, class Value, class Hash, class Equals>
inline size_t
UM_Wrapper<Key, Value, Hash, Equals>::Hasher::operator()
(const Key* const key) const
{
return hasher(*key);
}template<class Key, class Value, class Hash, class Equals>
inline bool
UM_Wrapper<Key, Value, Hash, Equals>::Equaler::operator()
(const Key* const first, const Key* const second) const
{
return equaler(*first, *second);
}wenn du einfach iterators und const_iterators statt pointers (auf die iterators) verwenden wuerdest, haettest du das problem nicht, oder verstehe ich dich falsch?
Das war allerdings nicht mein Problem. Eigentlich ging es mir darum, dass die Funktion key_exists (und eigentlich auch alle anderen Funktionen, die einen Lookup in der Hashtabelle machen) (siehe mein erster Beitrag) nicht kompiliert, wenn ich nicht den key const_caste. Ist hier mein Konzept kaputt, oder ist const_cast für genau solche Fälle gedacht?
Vielleicht habe ich dich aber hier auch selbst falsch verstanden. Meine Klasse zeigt nämlich Iteratoren gar nicht nach außen hin. Sie verwendet diese eigentlich nur intern, weswegen es nicht in Frage kam, komplett auf Iteratoren umzusteigen.Grüße,
Rachus
-
gudn tach!
Nun das wäre theoretisch tatsächlich so, wenn ich nicht das Problem gehabt hätte, dass ich dann meiner Hasher und Equaler-Funktion einerseits Pointer und andererseits Iteratoren hätte übergeben müssen.
hmm, ich glaube, ich hatte und habe einfach nicht verstanden, was du vorhast, sorry.
prost
seth
-
-
-
Kurz vorweg: ich habe keine C++ Erfahrung.
Mein Anliegen ist eine C++-Klasse, die ich zum Wrappen der std::unordered_multimap nutzen wollte. Dabei wollte ich die Schlüssel nicht direkt in der Tabelle speichern, sondern nur einen Pointer.
Erste Frage, warum?
Der Schlüssel selbst liegt in einer anderen Datenstruktur (einer std::list; damit wird bei mehreren Werten eines Schlüssels der Schlüssel trotzdem garantiert nur einmal gespeichert). Nun sieht eine Funktion beispielsweise so aus (ist hoffentlich selbsterklärend):
template<class Key, class Value, class Hash, class Equals>
inline const bool
UM_Wrapper<Key, Value, Hash, Equals>::key_exists(const Key& key) const
{
return data.find(&key) != data.end();
}Kannst du das vielleicht mal wörtlich beschreiben? Die Syntax finde ich als Java Gewöhnter nicht so intuitiv. Also: was hast du für Datenstrukturen und für Klassen und wer soll was warum womit machen.
Leider liest man aber im Internet viel zu häufig, dass const_cast (genauso, wie reinterpret_cast)
Generell sind casts böse. Nämlich deshalb, weil dadurch Fehler nur noch zur Laufzeit festgestellt werden können; das bedeutet, die Verantwortung verlagert sich vom Compiler auf dich - und das willst du nicht.
-
Hallo,
Erste Frage, warum?
Ich wollte mir eine Klasse schreiben, die mir das Hantieren mit Iteratoren der unordered_multimap versteckt und dabei gleich noch etwas optimieren.
Der Schlüssel selbst liegt in einer anderen Datenstruktur (einer std::list; damit wird bei mehreren Werten eines Schlüssels der Schlüssel trotzdem garantiert nur einmal gespeichert). Nun sieht eine Funktion beispielsweise so aus (ist hoffentlich selbsterklärend):
template<class Key, class Value, class Hash, class Equals>
inline const bool
UM_Wrapper<Key, Value, Hash, Equals>::key_exists(const Key& key) const
{
return data.find(&key) != data.end();
}Kannst du das vielleicht mal wörtlich beschreiben? Die Syntax finde ich als Java Gewöhnter nicht so intuitiv. Also: was hast du für Datenstrukturen und für Klassen und wer soll was warum womit machen.
UM_Wrapper ist meine Klasse, die um die Hashtabelle (std::unordered_multimap) der Standardbibliothek herumgebaut wurde. Zusätzlich verwende ich noch eine std::list, die die Schlüssel speichert. Die Hashtabelle selber nutzt zum Indexen Zeiger auf die, in der Liste liegenden, Schlüssel und als Werte Paare, die einen Iterator auf den Schlüssel und den eigentlich Wert zu speichern. (Den Iterator habe ich da eingebaut, da ich nicht wusste, wie ich meiner Hasher-/Equaler-Funktionsklassen klarmache, dass das fast das gleiche ist).
Nun ist es so, dass bei einem einfachen key_exists eine konstante Referenz (in Java wohl mit final vergleichbar) übergeben wird. Konstant, da das zur sauberen Schnittstelle gehört (und man liest im Internet ja genügend über C++ Const Correctness). Die Methode find von der unordered_multimap erwartet auch eine konstante Referenz auf ein Objekt des Schlüsseltyps (Key*). Nur sichert mir sie nicht mehr zu, dass auch der Bereich, auf den der Zeiger zeigt (durch &key hole ich mir ja einen Zeiger, da dieser Operator die Speicheradresse zurückgibt) auch konstant bleibt. Diese Zusicherung habe ich allerdings dem Aufrufer meiner Methode gegeben. Daher kompiliert sie auch ohne Cast nicht.
(Hier hoffe ich, dass ich die Compilerfehler auch richtig gedeutet habe… Sie sind nicht immer ganz leicht verständlich.)Generell sind casts böse. Nämlich deshalb, weil dadurch Fehler nur noch zur Laufzeit festgestellt werden können; das bedeutet, die Verantwortung verlagert sich vom Compiler auf dich - und das willst du nicht.
Und deswegen wollte ich in diesem Falle erfragen, ob hier eine Situation vorliegt, in der ein Cast sinnvoll ist, oder ob ich die Klasse lieber mal über den Haufen werfen sollte.
Grüße,
Rachus
-
Diese Zusicherung habe ich allerdings dem Aufrufer meiner Methode gegeben. Daher kompiliert sie auch ohne Cast nicht.
Was ist bei dir eine Zusicherung?
Der Compiler dürfte schimfen, weil er eine Referenz erwartet, du ihm aber ein Temporary unterjubeln möchtest?!-
Was ist bei dir eine Zusicherung?
Der Compiler dürfte schimfen, weil er eine Referenz erwartet, du ihm aber ein Temporary unterjubeln möchtest?!Okay, Zusicherung ist in diesem Falle wohl der falsche Begriff. "Typ" würde es wohl besser bezeichnen.
Vielleicht kann ich (meine Gedanken) bildlich etwas darstellen:Aufrufer UM_Wrapper::key_exists std::unordered_multimap::find
Key wird als Nimmt Key als Konstante nimmt konstanten Key* ent-
Konstante über- entgegen und gibt Zeiger gegen. Allerdings ist hier
geben darauf als Konstante (Key*) nicht mehr sichergestellt,
weiter. dass *Key (also die Deref-
erenzierung) immer noch, wie
vom Aufrufer gefordert,
konstant ist.Grüße,
Rachus
-
std::unordered_multimap::find
nimmt konstanten Key* ent-
gegen. Allerdings ist hier
nicht mehr sichergestellt,
dass *Key (also die Deref-
erenzierung) immer noch, wie
vom Aufrufer gefordert,
konstant ist.Wer fordert das? Du?
Suchst du const Key* const?-
std::unordered_multimap::find
nimmt konstanten Key* ent-
gegen. Allerdings ist hier
nicht mehr sichergestellt,
dass *Key (also die Deref-
erenzierung) immer noch, wie
vom Aufrufer gefordert,
konstant ist.Wobei hier gerade die Dereferenzierung konstant ist und der Pointer selbst nicht!
-
std::unordered_multimap::find
nimmt konstanten Key* ent-
gegen. Allerdings ist hier
nicht mehr sichergestellt,
dass *Key (also die Deref-
erenzierung) immer noch, wie
vom Aufrufer gefordert,
konstant ist.
Wobei hier gerade die Dereferenzierung konstant ist und der Pointer selbst nicht!Ach, ..., und genau das wird das problem sein, du hast einen const key* brauchst aber einen key* const.
-
Und das ist es glaube ich auch, was du die ganze Zeit beschrieben hast?!
du hast einen const Key in der Funktion key_exists
brauchst dort aber einen Key* const, weil data.find diesen erwartet
bekommst aber ohne einen const_cast damit nur einen const Key* consthmmm, warum ist dein Key in data denn überhaupt ein Pointer? Ich würde eher das ändern.
Du willst ja auh nicht den Pointer hashen, sondern den Inhalt.-
Und das ist es glaube ich auch, was du die ganze Zeit beschrieben hast?!
du hast einen const Key in der Funktion key_exists
brauchst dort aber einen Key* const, weil data.find diesen erwartet
bekommst aber ohne einen const_cast damit nur einen const Key* consthmmm, warum ist dein Key in data denn überhaupt ein Pointer? Ich würde eher das ändern.
Du willst ja auh nicht den Pointer hashen, sondern den Inhalt.Es könnte sein, dass ich gerade etwas wieder ziemlich verwechsel (also bitte verbessern, wenn ich falsch liege). Aber eigentlich war es doch so, dass man die consts von rechts nach links lesen kann. Dann gäbe es:
1. Key* const
2. Key const* (aka const Key*)Bei 1. ist der Zeiger konstant. Also wird er immer auf die gleiche Speicherstelle zeigen, aber deren Inhalt kann beliebig geändert werden (ist nicht const).
Bei 2. ist die Speicherstelle konstant, aber es kann beliebig geändert werden, welche Speicherstelle.key_exists bekommt nun eine Referenz. Diese ist konstant (also ist die Speicherstelle konstant). find bekommt eine Referenz des Zeigers, also ist in find der Zeiger konstant, die Speicherstelle aber theoretisch nicht mehr, oder? Genau das würde ja durch den const_cast behoben.
Der Key ist ein Pointer, da ich die Schlüssel ja in der std::list<Key> speichern wollte und nur noch Zeiger auf die eigentlichen Schlüssel der Hashmap geben wollte. Daher musste ich ja auch Hasher und Equaler schreiben - damit eben die gespeicherten Zeiger dereferenziert und nicht die Zeiger verglichen werden.
Ist das jetzt soweit richtig, oder habe ich dann irgendetwas übersehen?
Grüße,
Rachus
-
key_exists bekommt nun eine Referenz. Diese ist konstant (also ist die Speicherstelle konstant). find bekommt eine Referenz des Zeigers, also ist in find der Zeiger konstant, die Speicherstelle aber theoretisch nicht mehr, oder? Genau das würde ja durch den const_cast behoben.
Es würde sich übersetzen lassen, ja, behoben wird nichts, wenn die Variable auf die der const Pointer zeigt, wirklich konstant ist (und nicht nur über ein paar Funktionsaufrufe so getan wird, als wäre er es), führt ein schreibender Zugriff zum Laufzeitfehler.
-
Es würde sich übersetzen lassen, ja, behoben wird nichts, wenn die Variable auf die der const Pointer zeigt, wirklich konstant ist (und nicht nur über ein paar Funktionsaufrufe so getan wird, als wäre er es), führt ein schreibender Zugriff zum Laufzeitfehler.
Allerdings dürfte find keinen schreibenden Zugriff auf die Variable ausführen. Somit dürfte es auch zu keinem Laufzeitfehler kommen.
Wie macht man es richtig, dass es hier unter keinen Umständen zu einem Laufzeitfehler kommt?
Grüße,
Rachus
-
Allerdings dürfte find keinen schreibenden Zugriff auf die Variable ausführen. Somit dürfte es auch zu keinem Laufzeitfehler kommen.
Ja, das ist richtig, allerdings dürfte es auch keinen Grund geben in der map einen Pointer als Schlüssel zu nehmen!
Wie macht man es richtig, dass es hier unter keinen Umständen zu einem Laufzeitfehler kommt?
const_cast nicht verwenden und dafür sorgen, dass solch ein cast nicht nötig ist!
Insgesammt ist dein ganzer Wrapper unnötig - soweit ich verstanden habe, was du überhaupt erreichen willst.
-
Ja, das ist richtig, allerdings dürfte es auch keinen Grund geben in der map einen Pointer als Schlüssel zu nehmen!
Das ist die Frage. Ich hatte vor, Platz zu sparen, indem bei mehreren Werten für einen Schlüssel dieser nur einmal gespeichert wird. Wahrscheinlich wäre es ohne besser.
const_cast nicht verwenden und dafür sorgen, dass solch ein cast nicht nötig ist!
Wozu hat man denn dann const_cast eingeführt? Es ist immer unschön, Möglichkeiten zu haben, die man nicht nutzen sollte ;)
Insgesammt ist dein ganzer Wrapper unnötig - soweit ich verstanden habe, was du überhaupt erreichen willst.
Ich empfand meine Schnittstelle als einfacher. Wenn man direkt auf einer std::unordered_multimap arbeitet, muss man zum Einfügen immer std::pairs verwenden und beim Finden diese wieder aufsplitten. Außerdem gibt es keine einfache Methode, um alle Schlüssel zu finden. Aber so, wie es aussieht, ist es wohl doch einfacher direkt darauf zu arbeiten, als noch ein Konstrukt außenherum zu bauen, dass es vereinfachen soll.
Schade.Danke für deine Hilfe!
Grüße,
Rachus
-
Das ist die Frage. Ich hatte vor, Platz zu sparen, indem bei mehreren Werten für einen Schlüssel dieser nur einmal gespeichert wird. Wahrscheinlich wäre es ohne besser.
Und wo soll das bei dir passieren? Das sehe ich nicht wie das gemacht werden soll.
Wenn du viele gleiche Werte mit gleichem Schlüssel hast, könntest du das über eine map von listen machen, bei einer multimap hast du für jeden eingetragenen Wert auch einen Schlüssel.
Du verbrauchst, soweit ich das verstanden habe, wesentlich mehr Speicher als die reine multimap ohne deinen Wrapper, indem du zusätzlich noch eine Liste mit Zeiger auf die Schlüssel speicherst und dann nochmal zusätzlich zu jedem Wert einen iterator in diese Liste.Wozu hat man denn dann const_cast eingeführt? Es ist immer unschön, Möglichkeiten zu haben, die man nicht nutzen sollte ;)
Manchmal kommt man aber nicht umhin solche Ausnahmen zu nutzen, oder hat nicht die Zeit es geradezuziehen.
Jetzt mal auf dein Beispiel bezogen, müsste man sich entscheiden, macht man die Ausssenschnittstelle key_exists unsauber indem man auf das const verzichtet, oder die interne Implementierung indem man den const_cast einsetzt, mit der Gewissheit, das kein schreibender Zugriff erfolgt. Die entscheidung dürfte klar für den Einsatz des const_casts ausfallen.
Aber wenn man den auch noch umgehen kann, ist doch alles bestens.-
Hallo,
Und wo soll das bei dir passieren? Das sehe ich nicht wie das gemacht werden soll.
es sollte so passieren, dass die Schlüssel (vom Typ Key, die meist "größere Objekte", z.B. längere Strings darstellen) nur einmal in der Liste gespeichert werden und in der Hashtabelle nur die Zeiger darauf gespeichert werden müssen.
Wenn du viele gleiche Werte mit gleichem Schlüssel hast, könntest du das über eine map von listen machen, bei einer multimap hast du für jeden eingetragenen Wert auch einen Schlüssel.
So werde ich es wohl das nächste Mal auch besser machen…
Du verbrauchst, soweit ich das verstanden habe, wesentlich mehr Speicher als die reine multimap ohne deinen Wrapper, indem du zusätzlich noch eine Liste mit Zeiger auf die Schlüssel speicherst und dann nochmal zusätzlich zu jedem Wert einen iterator in diese Liste.
Das ist abzuwägen. Als "Grundlast" habe ich sizeof(std::list<Key>) + sizeof(std::unordered_multimap<Key*, std::pair<class std::list<Key>::iterator, Value>, Hasher, Equaler>). Bei nicht doppelten Key-Einträgen, kommt pro Eintrag 2*sizeof(void*) dazu. Sobald nun aber ein Schlüssel mehrfach verwendet wird, und dieser Schlüssel größer als 2*sizeof(void*) ist, würde man etwas einsparen. Allerdings ist das wohl tatsächlich nicht so ganz das Wahre.
Aber wenn man den auch noch umgehen kann, ist doch alles bestens.
Auch wenn das bedeutet, dass ich jetzt wieder direkt mit der multimap arbeite.
Grüße,
Rachus
-
es sollte so passieren, dass die Schlüssel (vom Typ Key, die meist "größere Objekte", z.B. längere Strings darstellen) nur einmal in der Liste gespeichert werden und in der Hashtabelle nur die Zeiger darauf gespeichert werden müssen.
Ja, ich hatte auch nochmal nachgesehen, ich war davon ausgegangen, dass in der multimap der Hash als eigentlicher Key dient und der ursprüngliche Schlüssel also überhaupt nicht jedesmal gespeichert wird. Ist leider nicht so!
Damit würdest du tatsächlich Speicherplatz sparen. Aber wie kommst du vom eigentlichen Schlüssel auf den Zeiger in deiner Liste? Durch lineare Suche?Auch wenn das bedeutet, dass ich jetzt wieder direkt mit der multimap arbeite.
Naja, das ist ja nicht schlimm, bis auf den mehrfachen Speicherverbrauch des Schlüssels.
-
Aber wie kommst du vom eigentlichen Schlüssel auf den Zeiger in deiner Liste? Durch lineare Suche?
Ach so, das ist ja dein key_exists! Das wird nicht funktionieren! Du musst doch erst mal in deiner Liste den eigentlichen Schlüssel suchen, um dort die Adresse zu ermitteln, mit der du in der multimap suchst! Sonst suchst du ja mit dem falschen Zeiger!
-
Hallo,
Ach so, das ist ja dein key_exists! Das wird nicht funktionieren! Du musst doch erst mal in deiner Liste den eigentlichen Schlüssel suchen, um dort die Adresse zu ermitteln, mit der du in der multimap suchst! Sonst suchst du ja mit dem falschen Zeiger!
Nein, eigentlich nicht. Ich speichere ja statt des Schlüssels einen Zeiger zu dem Schlüssel, der zu dem Element innerhalb meiner Liste zeigt. Ein Zugriff darauf findet so schnell statt, wie ein Zeiger zum Dereferenzieren benötigt. (Deswegen ja auch mein eigener Equaler und Hasher) Beim Einfügen habe ich dann nur den Schlüssel in die Liste eingefügt, mir den Zeiger darauf geholt und den in der multimap gespeichert. (Natürlich auch noch einen Iterator, damit das Entfernen auch in O(1) funktioniert)
Wenigstens sind wir uns aber einig, dass meine Wrapperklasse wohl eine Schnapsidee war…
Grüße,
Rachus
-
Nein, eigentlich nicht. Ich speichere ja statt des Schlüssels einen Zeiger zu dem Schlüssel,
Ja, soweit verstanden!
der zu dem Element innerhalb meiner Liste zeigt.
der Zeiger, zeigt auf einen std-String, der ist doch nicht in deiner Liste?
Beim Einfügen habe ich dann nur den Schlüssel in die Liste eingefügt, mir den Zeiger darauf geholt und den in der multimap gespeichert.
Ok, das ist wieder klar. Aber,
- Du fügst mit Key "xyz" etwas ein. Das ist die Variable 1 mit Adresse 1!
- Adresse 1 speicherst du in der Liste und nimmst diese als Key?
- Du suchst mit Key "xyz" etwas mit deinem Wrapper. Das ist die 2. Variable mit Adresse 2
Welchen Zeiger speicherst du denn in der Liste bzw. Map? Den auf Variable 1 oder machst du noch eine Kopie und speicherst diese Adresse? Sonst könnte die Variable 1 im u.U. gelöscht/verändert werden!
Wie kommst du von Variable 2 auf Adresse 1? Du müsstest ja die Liste durchgehen und den Inhalt der gespeicherten Keys mit Variable 2 vergleichen um den Key der multimap zu finden.Wenigstens sind wir uns aber einig, dass meine Wrapperklasse wohl eine Schnapsidee war…
Nicht mehr so ganz, das mit dem Speicherplatz sparen macht durchaus Sinn!
Allerdings dürfte das Suchen der Keys reht lange dauern, so wie du es gelöst hast!-
Hallo,
der Zeiger, zeigt auf einen std-String, der ist doch nicht in deiner Liste?
vielleicht sagt hier Code mehr als 1000 Worte: (allerdings ungetestet - find-Aufrufe benötigen auch hier einen const_cast<Key*>(&key), damit sie funktionieren - habe ich aber nicht bereinigt)
template<class Key, class Value, class Hash, class Equals>
inline void
UM_Wrapper<Key, Value, Hash, Equals>::insert
(const Key& key, const Value& value)
{
identifiers.push_front(key);
std::pair<class std::list<Key>::iterator, Value>
value_content(identifiers.begin(), value);
std::pair<Key*, std::pair<class std::list<Key>::iterator, Value>>
key_value_pair(&*value_content.first, std::move(value_content));
data.insert(std::move(key_value_pair));
}template<class Key, class Value, class Hash, class Equals>
const std::vector<const Value*>
UM_Wrapper<Key, Value, Hash, Equals>::get_values(const Key& key) const
{
std::vector<const Value*> values;
values.reserve(data.count(&key));
std::pair<class std::unordered_multimap<Key, Value, Hasher, Equaler>::const_iterator,
class std::unordered_multimap<Key, Value, Hasher, Equaler>::const_iterator>
range = data.equal_range(&key);
for (; range.first != range.second; ++range.first)
values.push_back(&range.first->second);
return std::move(values);
}template<class Key, class Value, class Hash, class Equals>
const std::vector<Value*>
UM_Wrapper<Key, Value, Hash, Equals>::get_values(const Key& key)
{
std::vector<Value*> values;
values.reserve(data.count(&key));
std::pair<class std::unordered_multimap<Key, Value, Hasher, Equaler>::iterator,
class std::unordered_multimap<Key, Value, Hasher, Equaler>::iterator>
range = data.equal_range(&key);
for (; range.first != range.second; ++range.first)
values.push_back(&range.first->second);
return std::move(values);
}Welchen Zeiger speicherst du denn in der Liste bzw. Map? Den auf Variable 1 oder machst du noch eine Kopie und speicherst diese Adresse? Sonst könnte die Variable 1 im u.U. gelöscht/verändert werden!
In der Liste werden tatsächlich Objekte gespeichert, in der Map werden die Zeiger darauf hinterlegt.
Wie kommst du von Variable 2 auf Adresse 1? Du müsstest ja die Liste durchgehen und den Inhalt der gespeicherten Keys mit Variable 2 vergleichen um den Key der multimap zu finden.
Nein, ich muss der map nur sagen, dass sie dereferenzieren soll. Dafür habe ich ja Hasher und Equaler geschrieben. Diese sorgen dafür, dass nicht die Zeiger, sondern die Werte, die dahinter stehen, betrachtet werden. (siehe auch mein Post mit dem Code) Sollte also prinzipiell eine konstante asymptotische Laufzeit haben.
Wenigstens sind wir uns aber einig, dass meine Wrapperklasse wohl eine Schnapsidee war…
Nicht mehr so ganz, das mit dem Speicherplatz sparen macht durchaus Sinn!
Allerdings dürfte das Suchen der Keys reht lange dauern, so wie du es gelöst hast!Nun, wie gesagt: Ich selbst bin der Meinung, dass alle von mir bis jetzt gezeigten Funktionen im Average Case in O(1) liegen. Ansonsten denke ich, dass die Einsparung von Speicherplatz doch besser durch eine andere Kollisionsauflösung erfolgen könnte. Zum Beispiel, wie von dir bereits vorgeschlagen, durch eine Liste, die man in einer map (ohne multi!) speichert. Das könnte man unter Umständen sogar bedarfsgesteuert machen. Dann hat man auch nicht mehr das Problem, dass man const_casten müsste.
Grüße,
Rachus
-
Nein, ich muss der map nur sagen, dass sie dereferenzieren soll. Dafür habe ich ja Hasher und Equaler geschrieben. Diese sorgen dafür, dass nicht die Zeiger, sondern die Werte, die dahinter stehen, betrachtet werden. (siehe auch mein Post mit dem Code) Sollte also prinzipiell eine konstante asymptotische Laufzeit haben.
ja, daran hatte ich nicht mehr gedacht
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
gudn tach!
Erste Frage, warum?
Ich wollte mir eine Klasse schreiben, die mir das Hantieren mit Iteratoren der unordered_multimap versteckt
die anfordernungen sind mir noch nicht ganz klar. was genau soll diese klasse koennen? geht es einfach nur um einen container, dem man etwas hinzufuegen oder wegnehmen kann und den man fragen kann, ob etwas bestimmtes in ihm ist? und du willst dem user verbieten, ueber den inhalt zu iterieren?
und dabei gleich noch etwas optimieren.
naja, wenn du einen wrapper schreibst, wird der mit grosser wahrscheinlichkeit nicht schneller oder optimaler[1] sein als die gewrappte klasse.
prost
seth[1] ja, ich kann "optimal" steigern und "voll" und "leer" und "ok" auch.
-
-
-
Folgendes
UM_Wrapper<Key, Value, Hash, Equals>::key_exists(const Key& key) const
{
const Key* pKey = &key;
return data.find(pKey) != data.end();
}sollte doch funktionieren?
-
Folgendes
UM_Wrapper<Key, Value, Hash, Equals>::key_exists(const Key& key) const
{
const Key* pKey = &key;
return data.find(pKey) != data.end();
}sollte doch funktionieren?
Oder eher nicht, wie willst du denn den Pointer finden? Oder ist die find-Methode von dir (überschrieben)?
-
Hallo,
Oder eher nicht, wie willst du denn den Pointer finden? Oder ist die find-Methode von dir (überschrieben)?
Nein, die find-Methode ist die aus der Standardbibliothek. Mithilfe der letzten beiden Template-Argumenten von std::unordered_multimap kann ich aber bestimmen, wie der Hash und Vergleich unternommen werden soll. Dazu verwendet ich die beiden Klassen:
template<class Key, class Value, class Hash, class Equals>
inline size_t
UM_Wrapper<Key, Value, Hash, Equals>::Hasher::operator()
(const Key* const key) const
{
return hasher(*key);
}template<class Key, class Value, class Hash, class Equals>
inline bool
UM_Wrapper<Key, Value, Hash, Equals>::Equaler::operator()
(const Key* const first, const Key* const second) const
{
return equaler(*first, *second);
}Und in der Headerdatei ist die Map definiert:
std::list<Key> identifiers;
std::unordered_multimap<Key*, std::pair<class std::list<Key>::iterator, Value>, Hasher, Equaler> data;Da find standarmäßig zum Vergleichen den operator() meines Equaler und zum Hashen den Operator meines Hasher aufruft, kann ich das Verhalten von find (und einigen anderen Methoden auch) beeinflussen.
Grüße,
Rachus
-
Nein, die find-Methode ist die aus der Standardbibliothek. Mithilfe der letzten beiden Template-Argumenten von std::unordered_multimap kann ich aber bestimmen, wie der Hash und Vergleich unternommen werden soll. Dazu verwendet ich die beiden Klassen:
template<class Key, class Value, class Hash, class Equals>
inline size_t
UM_Wrapper<Key, Value, Hash, Equals>::Hasher::operator()
(const Key* const key) const
{
return hasher(*key);
}Also wird doch der Inhalt des Keys zum identifizieren genutzt und nicht die Adresse des Keys im Speicher?
Dann sollte es doch so gehen wie hier vorgeschlagen?Sonst hättest du aber so oder so ein Problem!
-
Hallo,
so funktioniert es (zumindest bei mir) nicht. Ich habe einmal die Klasse auf das nötigste heruntergebrochen:
#include <string>
#include <vector>
#include <list>
#include <unordered_map>template
<
class Key = std::string,
class Value = std::string,
class Hash = std::hash<Key>,
class Equals = std::equal_to<Key>class UM_Wrapper
{
public:
typedef Key key_type;
typedef Value value_type;
typedef Hash hasher_type;
typedef Equals equals_type;inline const bool key\_exists(const Key& key) const; private: class Hasher { public: inline size\_t operator() (const Key\* const key) const; private: Hash hasher; }; class Equaler { public: inline bool operator() (const Key\* const first, const Key\* const second) const; private: Equals equaler; }; std::list<Key> identifiers; std::unordered\_multimap<Key\*, std::pair<class std::list<Key>::iterator, Value>, Hasher, Equaler> data;};
template<class Key, class Value, class Hash, class Equals>
inline const bool
UM_Wrapper<Key, Value, Hash, Equals>::key_exists(const Key& key) const
{
const Key* const_key = &key;
return data.find(const_key) != data.end();
}template<class Key, class Value, class Hash, class Equals>
inline size_t
UM_Wrapper<Key, Value, Hash, Equals>::Hasher::operator()
(const Key* const key) const
{
return hasher(*key);
}template<class Key, class Value, class Hash, class Equals>
inline bool
UM_Wrapper<Key, Value, Hash, Equals>::Equaler::operator()
(const Key* const first, const Key* const second) const
{
return equaler(*first, *second);
}Um zu "testen", habe ich mir dann noch eine kleine main-Funktion geschrieben.
#include "um_wrapper.hpp"
#include <iostream>int main()
{
UM_Wrapper<> w;
w.key_exists("keystring");
return 0;
}Kompiliert wurde es per "g++ -std=c++0x tester.cpp". Dabei fliegt mir folgende Fehlermeldung um die Ohren.
In file included from tester.cpp:1:0:
um_wrapper.hpp: In instantiation of ‘const bool UM_Wrapper<Key, Value, Hash, Equals>::key_exists(const Key&) const [with Key = std::basic_string<char>; Value = std::basic_string<char>; Hash = std::hash<std::basic_string<char> >; Equals = std::equal_to<std::basic_string<char> >]’:
tester.cpp:7:26: required from here
um_wrapper.hpp:51:42: error: passing ‘const std::unordered_multimap<std::basic_string<char>*, std::pair<std::_List_iterator<std::basic_string<char> >, std::basic_string<char> >, UM_Wrapper<>::Hasher, UM_Wrapper<>::Equaler, std::allocator<std::pair<std::basic_string<char>* const, std::pair<std::_List_iterator<std::basic_string<char> >, std::basic_string<char> > > > >’ as ‘this’ argument of ‘std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::iterator std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::find(const key_type&) [with _Key = std::basic_string<char>*; _Value = std::pair<std::basic_string<char>* const, std::pair<std::_List_iterator<std::basic_string<char> >, std::basic_string<char> > >; _Allocator = std::allocator<std::pair<std::basic_string<char>* const, std::pair<std::_List_iterator<std::basic_string<char> >, std::basic_string<char> > > >; _ExtractKey = std::_Select1st<std::pair<std::basic_string<char>* const, std::pair<std::_List_iterator<std::basic_string<char> >, std::basic_string<char> > > >; _Equal = UM_Wrapper<>::Equaler; _H1 = UM_Wrapper<>::Hasher; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; bool __cache_hash_code = true; bool __constant_iterators = false; bool __unique_keys = false; std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::iterator = std::__detail::_Node_iterator<std::pair<std::basic_string<char>* const, std::pair<std::_List_iterator<std::basic_string<char> >, std::basic_string<char> > >, false, true>; std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::key_type = std::basic_string<char>*]’ discards qualifiers [-fpermissive]
um_wrapper.hpp:51:42: error: invalid conversion from ‘const std::basic_string<char>*’ to ‘std::_Hashtable<std::basic_string<char>*, std::pair<std::basic_string<char>* const, std::pair<std::_List_iterator<std::basic_string<char> >, std::basic_string<char> > >, std::allocator<std::pair<std::basic_string<char>* const, std::pair<std::_List_iterator<std::basic_string<char> >, std::basic_string<char> > > >, std::_Select1st<std::pair<std::basic_string<char>* const, std::pair<std::_List_iterator<std::basic_string<char> >, std::basic_string<char> > > >, UM_Wrapper<>::Equaler, UM_Wrapper<>::Hasher, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, true, false, false>::key_type {aka std::basic_string<char>*}’ [-fpermissive]
In file included from /usr/include/c++/4.7/unordered_map:45:0,
from um_wrapper.hpp:5,
from tester.cpp:1:
/usr/include/c++/4.7/bits/hashtable.h:932:5: error: initializing argument 1 of ‘std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::iterator std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::find(const key_type&) [with _Key = std::basic_string<char>*; _Value = std::pair<std::basic_string<char>* const, std::pair<std::_List_iterator<std::basic_string<char> >, std::basic_string<char> > >; _Allocator = std::allocator<std::pair<std::basic_string<char>* const, std::pair<std::_List_iterator<std::basic_string<char> >, std::basic_string<char> > > >; _ExtractKey = std::_Select1st<std::pair<std::basic_string<char>* const, std::pair<std::_List_iterator<std::basic_string<char> >, std::basic_string<char> > > >; _Equal = UM_Wrapper<>::Equaler; _H1 = UM_Wrapper<>::Hasher; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; bool __cache_hash_code = true; bool __constant_iterators = false; bool __unique_keys = false; std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::iterator = std::__detail::_Node_iterator<std::pair<std::basic_string<char>* const, std::pair<std::_List_iterator<std::basic_string<char> >, std::basic_string<char> > >, false, true>; std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::key_type = std::basic_string<char>*]’ [-fpermissive]Wie bereits beschrieben, würde es nunmal mit einem
return data.find(const_cast<Key*>(&key)) != data.end();
funktionieren. Aber da ist eben dieser Cast drin, der theoretisch von einem schlechten Konzept zeugt.Hoffentlich sind jetzt alle Klarheiten beseitigt ;)
Grüße,
Rachus
-
Gibt es in hashtable.h eine Funktion find(const key&) const?
-
Gibt es in hashtable.h eine Funktion find(const key&) const?
Im Header <unordered_map> gibt es diese find-Methoden. Sie übernehmen jeweils eine konstante key-Referenz.
Grüße,
Rachus
-
Im Header <unordered_map> gibt es diese find-Methoden. Sie übernehmen jeweils eine konstante key-Referenz.
Diese Frage hatte sich erledigt, da hatte ich nicht weit genug gedacht.
-
-
-
-
-
-
-
-
Dabei wollte ich die Schlüssel nicht direkt in der Tabelle speichern, sondern nur einen Pointer.
Es wird ja weder der Schlüssel, noch der Pointer gespeichert, sondern ein berechneter Hashwert.
Der Schlüssel selbst liegt in einer anderen Datenstruktur (einer std::list; damit wird bei mehreren Werten eines Schlüssels der Schlüssel trotzdem garantiert nur einmal gespeichert).
Der gleiche Schlüssel ergibt immer den gleichen Hashwert.
Es könnte (theoretisch) vorkommen, das mehrere Schlüssel den gleichen Hashwert ergeben. Das fängst du aber auch nicht ab. -
Hallo Rachus,
habe mir jetzt nicht alle Beiträge durchgelesen aber im Grunde denke ich "spontan" an drei Punkte (oder auch mehr)
1. Ein großer Vorteil von C++ ist die starke Typisierung und die Überprüfbarkeit
von Typen während der Kompilierung und teilweise auch zur Laufzeit. Zeiger brechen dieses
Verhalten/Mechanismus. Manchmal ist das vielleicht erwünscht, aber dann setzt
man voraus, dass der Programmierer weiss was er da macht. Die Stärke von C++
ist, dass man so ziemlich alles machen kann. Der Nachteil von C++ ist, dass man
so ziemlich alles machen kann. Unterm Strich kann man sagen "Vermeide Zeiger
oder Umwandlungen auf selbige, weil es unweigerlich zu Fehler führt".2. "data.find(&key)" => Finde die Adresse von key. Ich halte es für unwahrscheinlich,
dass genau diese Adresse in data gespeichert wurde, und selbst wenn, dann frage
ich mich warum und wie die da überhaupt reingeraten ist oder was genau dort abgelegt wurde.3. "data.find(const_cast<Key*>(&key))" => siehe 1.
Gruß micha
-
Hallo micha2012,
wow, C++ ist einfach nicht mein Gebiet ^^. So einen Müll schreibe ich alle 6 Jahre. Einfach ignorieren, alles falsch ...
LG
-