nicht angemeldet
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
seth