Was für nen Algo hat map?
-
hi!
map <string, string> my_map;was für nen algorithmus hat map intern`?
wenn ich schreibemy_map["abc"] = "d";wird intern aus dem "abc" eine nummer (hashkey) berechnet?
-
Nein,
std::maphat normalerweise eine Baumstruktur und unterstützt somit logarithmische Zeitkomplexität fürs Suchen.
-
Ich glaube, mal gelesen zu haben, daß es ein red-black tree ist.
-
Ich habwe mal gelesen, daß es ein AVL-Baum ist.
-
Ich habe mal gelesen dass es implementationsabhängig ist.
-
Ich glaube, mal gelesen zu haben, daß es baumartig implementiert ist.
-
mapp0r schrieb:
...wird intern aus dem "abc" eine nummer (hashkey) berechnet?
Nö.
-
Ich glaube nicht dass die Baum-Art vorgeschrieben ist, aber Red-Black Trees sind recht üblich.
-
Man könnte auch eine randomized skip list nehmen.
-
Tachyon schrieb:
mapp0r schrieb:
...wird intern aus dem "abc" eine nummer (hashkey) berechnet?
Nö.
oje, dann wirds ja richtig lahmarschig, bei einigen mega einträgen.
muss ich mir wohl selber was coden.
-
mapp0r schrieb:
Tachyon schrieb:
mapp0r schrieb:
...wird intern aus dem "abc" eine nummer (hashkey) berechnet?
Nö.
oje, dann wirds ja richtig lahmarschig, bei einigen mega einträgen.
muss ich mir wohl selber was coden.Wie wärs mit
std::tr1::unordered_map?
-
wäre eventuell gut, kenne ich mich leider nicht mit aus.
wie ist es bei zwei oder mehreren elementen mit dem gleichen hashkey, ich nehme an dafür brauche ich die multimap und die kollisionsbehandlung brauche ich nicht selbst zu machen ?
-
Abgesehen davon: Bevor man selber das Rad neu erfindet, sollte man schauen, ob die bestehenden Möglichkeiten tatsächlich so langsam sind oder ob man sich einfach verschätzt hat. Letzteres passiert nämlich ab und zu...
-
aaah, sieht so aus, zu sehen an der 'Adding elements sektion',
habe nämlich hier gerade ne interessante seite gefunden
http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c15303__2/ok, vielen dank erstmal!
gruß,
mapp0r
-
Nexus schrieb:
Abgesehen davon: Bevor man selber das Rad neu erfindet, sollte man schauen, ob die bestehenden Möglichkeiten tatsächlich so langsam sind oder ob man sich einfach verschätzt hat. Letzteres passiert nämlich ab und zu...
sorry, hab deinen post übersprungen. ja, ich gebe dir recht, aber ich wollte eh mal wissen, ob c++ die möglichkeit einer hastable bietet.
gruß,
m.
-
mapp0r schrieb:
oje, dann wirds ja richtig lahmarschig, bei einigen mega einträgen.muss ich mir wohl selber was coden.
Ach, und hast du nachgemessen? Auch sollte der Aufwand einer Hashfunktion nicht unterschaetzt werden. Desweiteren ist std::map kein Algorithmus, sondern eine Datenstruktur.
-
knivil schrieb:
Desweiteren ist std::map kein Algorithmus, sondern eine Datenstruktur.
std::mapbasiert vielleicht auf einer Datenstruktur, aber es ist keine Datenstruktur sondern ein Container. Da gehört dann auch Algorithmik dazu.
-
knivil schrieb:
mapp0r schrieb:
oje, dann wirds ja richtig lahmarschig, bei einigen mega einträgen.muss ich mir wohl selber was coden.
Ach, und hast du nachgemessen? Auch sollte der Aufwand einer Hashfunktion nicht unterschaetzt werden. Desweiteren ist std::map kein Algorithmus, sondern eine Datenstruktur.
Nein, ich habe noch nicht nachgemessen. Und ich habe auch nicht geschrieben, das std::map ein Algorithmus ist.
-
Tachyon schrieb:
std::mapbasiert vielleicht auf einer Datenstruktur, aber es ist keine Datenstruktur sondern ein Container. Da gehört dann auch Algorithmik dazu.Für den Begriff "Datenstruktur" gibt es keine allgemeingültige Definition. Eine so detailierte Diskussion ist daher sinnlos.
Je nach Definition enthalten Datenstrukturen auch Algorithmen. Ich würde sogar sagen, dass das die am weitesten verbreitete Definition von "Datenstruktur" ist. Also, kann map auch bedenkenlos als Datenstruktur bezeichnet werden.
-
Mitleid schrieb:
Je nach Definition enthalten Datenstrukturen auch Algorithmen. Ich würde sogar sagen, dass das die am weitesten verbreitete Definition von "Datenstruktur" ist. Also, kann map auch bedenkenlos als Datenstruktur bezeichnet werden.
Eigentlich gibt es da schon gängige Definitionen. Siehe z.B. "The Art of Computer Programming" oder "Algorithms and Data Structures".
Eine Struktur ist auch erstmal eine Struktur. Das hat mit Algorithmen wenig zu tun. Es gibt allerdings Algorithmen, mit denen man bestimmte Datenstrukturen idealerweise gewährleisten kann.
