Was für nen Algo hat map?
-
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.
-
Tachyon schrieb:
Eine Struktur ist auch erstmal eine Struktur.
Wer könnte da widersprechen?
-
Tachyon schrieb:
Eigentlich gibt es da schon gängige Definitionen. Siehe z.B. "The Art of Computer Programming" oder "Algorithms and Data Structures".
Hab mal im Buch vom alten Knuth nachgesehen, aber keine explizite Definition für den Begriff gefunden. "Struct" würde ich auch nicht als Datenstruktur übersetzen. Den zweiten Buchtitel kenne ich nicht, vielleicht müsstest du noch den Autor angeben.
Aber, als "gängig" würde ich z.B. die Definition im Duden Informatik bezeichnen, denn die findet sich bei den meisten (aktuellen) Autoren wieder. Deshalb glaube ich kaum, dass du die Aussage map sei keine Datenstruktur aufrechterhalten kannst.
-
std::map ist keine Datenstruktur, da keine Aussagen darüber getroffen werden, wie so eine std::map denn auszusehen hat.
Ein Red-Black-Tree ist eine Datenstruktur.
Ein AVL-Baum ist eine Datenstruktur.
Eine std::map ist keine Datenstruktur, sondern eine Black-Box.
-
hustbaer schrieb:
std::map ist keine Datenstruktur, da keine Aussagen darüber getroffen werden, wie so eine std::map denn auszusehen hat.
Das ist irrelevant bzw. erkläre mal was du genau damit meinst.
-
Mitleid schrieb:
Das ist irrelevant bzw. erkläre mal was du genau damit meinst.
Wahrscheinlich meint er, dass die konkrete Datenstruktur, die
std::mapverwendet, implementierungsabhängig ist.
-
Nexus schrieb:
Wahrscheinlich meint er, dass die konkrete Datenstruktur, die
std::mapverwendet, implementierungsabhängig ist.Weiß nicht, ob er das meint. Wenn ja, dann würde ich sagen er liegt falsch, denn die Schnittstelle definiert ja bereits die Datenstruktur.
-
hustbaer schrieb:
std::map ist keine Datenstruktur, da keine Aussagen darüber getroffen werden, wie so eine std::map denn auszusehen hat.
Du würdest also sagen, die folgende Aussage ist falsch? "std::map ist eine assoziative Datenstruktur, die Schlüssel zu Werten zuordnet und logarithmische Zeit für Einfüge-,Lösch- und Suchoperationen benötigt."
Schon lustig. Ich würde sowas bedenkenlos jederzeit als Datenstruktur bezeichnen. Das Konzept eines "Containers" ist mir hingegen in der theoretischen Informatik noch nie über den Weg gelaufen.
btw stimmt die entsprechende Wikipedia-Seite Dir nicht zu. Dort wird als Datenstruktur auch ein Graph genannt -- ohne konkrete Implementierung.
Typischerweise würde ich eine Datenstruktur über die angebotenen Operationen und deren Semantik definieren. Gegebenenfalls könnte man noch Performance-Garantien dazunehmen.
