Was für nen Algo hat 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 ?

Nexus

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.

knivil

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.

Tachyon

knivil schrieb:

Desweiteren ist std::map kein Algorithmus, sondern eine Datenstruktur.

std::map basiert 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::map basiert 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.

Tachyon

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.

EOP

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.

hustbaer

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.

Nexus

Mitleid schrieb:

Das ist irrelevant bzw. erkläre mal was du genau damit meinst.

Wahrscheinlich meint er, dass die konkrete Datenstruktur, die std::map verwendet, implementierungsabhängig ist.

Nexus schrieb:

Wahrscheinlich meint er, dass die konkrete Datenstruktur, die std::map verwendet, 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.

Jester

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.

Tachyon

Jester schrieb:

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.

Ja, die Aussage ist falsch.
"Container" ist ein wohl definierter Begriff aus der Typen-Theorie in der Informatik. Einem Container liegt zwar immer eine bestimmte Datenstruktur zugrunde, aber ein Container ist keine Datenstruktur.

Tachyon

Mitleid schrieb:

Nexus schrieb:

Wahrscheinlich meint er, dass die konkrete Datenstruktur, die std::map verwendet, 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.

Komisch. Ein Stack oder eine Queue haben auch eine bestimmte Schnittstelle, und trotzdem ist die Datenstruktur dahinter relativ wahlfrei.

Nochmal, du machst Aussagen über einen Begriff der sehr unterschiedlich verwendet wird. Schreib einfach dazu, was du unter "Datenstruktur" verstehst, bzw. gib eine Definition an.

Ich beziehe mich z.B. auf die Definition im Duden Informatik, die ich auch in verschiedenen anderen Werken angetroffen habe. Danach ist map eine Datenstruktur.

Deswegen, kannst du auch nicht unbedingt sagen eine Aussage sei falsch. Vielleicht ist sie falsch, wenn man deine Definition von Datenstruktur als Grundlage nimmt. Das solltest du aber dazusagen, denn nicht jeder redet bei "Datenstruktur" über das, was du meinst.

volkard

Jester schrieb:

Typischerweise würde ich eine Datenstruktur über die angebotenen Operationen und deren Semantik definieren. Gegebenenfalls könnte man noch Performance-Garantien dazunehmen.

Und das ist dann eine abstrakte Datanstruktur.

Manchmal sehe ich auch, daß man Implemetierung verrät. Neulich las ich ein Paper über einen Algorithmus, da stand, wenn man eine verkettete Liste nimmt, kann man eine bestimmte Zeitkomplexität O() zu erreichen. Weder die Schnittstelle noch Performance-Garantien wurden verraten, die Konkretisierung auf "verkettete Liste" sagte alles.