Was für nen Algo hat map?
-
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.
-
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.
-
Mitleid schrieb:
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.
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.
-
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.
-
volkard schrieb:
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.
Ja, weil eine "verkettete Liste" eine absolute Standard-Datenstruktur ist, die typischerweise bestimmte Operationen mit typischen Performance-Garantien anbietet.
-
Tachyon schrieb:
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.Komischwerweise ist bei Wikipedia der Container im Bereich Datenstruktur eingeordnet. Demnach ist also jeder Container eine Datenstruktur. Nach der Länge des Wikipedia-Artikels zu urteilen, scheint es sich wohl nicht gerade um ein allzu zentrales Konzept zu handeln. Zudem ist es mir wie gesagt noch nie begegnet.
Der Begriff Container mag in C++ eine wichtige Rolle spielen, weil es eine sehr zentrale Abstraktion in der STL ist, aber in der Informatik an sich eher nicht. Da spricht man eben doch häufiger über Datenstrukturen. Wo hast Du diese lustigen Ideen eigentlich her?
-
hustbaer schrieb:
Ein Red-Black-Tree ist eine Datenstruktur.
Ein AVL-Baum ist eine Datenstruktur.
Eine std::map ist keine Datenstruktur, sondern eine Black-Box.Du meinst vermutlich
http://de.wikipedia.org/wiki/Abstrakter_Datentyp
im Gegensatz zu
http://de.wikipedia.org/wiki/DatenstrukturLeider nimmt Wikipedia sofort die Luft aus den Segeln
Der Übergang von der Datenstruktur zu einem Abstrakten Datentyp ist dabei nicht klar definiert, sondern hängt einzig von der Betrachtungsweise ab.