C++ unordered_map sortieren

[Dese]

1. ein array hat nichts mit sortiert zu tun. die daten darin können sortiert sein, müssen aber nicht
2. das du mit einem iterator die schlüssel der map in einer (sortierten) ordnung traversieren kannst bedeutet NICHT, dass die daten sortiert sind!

das ist ganz entscheident bei der verwendung von maps. sind die schlüssel nämlich tatsächlcih sortiet, dann kann man diese in linearer zeit traversieren. ist das nicht der fall, so kann man von dieser laufzeit nicht ausgehen.

bei maps wird nur von einer möglichen traversierung in einer definierbaren ordnung gesprochen. die daten sind aber im allgeminen NICHT sortiert!

map's geben KEINERLEI garantie über die art und weise, wie die daten tatsächlich gehalten werden und damit auch nicht ob diese sortiert sind (in der ordnung, die zur traversierung verwendet werden soll).

meist sind die keys tatsächlcih als binarytree gehalten, wie es auch in dem link oben steht und das als array ist NICHT in der zu traversierenden ordnung sortiert.

was du mit dem hinweis zur MMU mir sagen willst ist mir schleierhaft. die mmu hat mit den maps und wie sie ihre daten vorhält absolut nichts zu tun.

Ergänzung (12. Juni 2013)

Ich glaube, das Problem ist, das du und ich eine verschiedene Vorstellung von "sortiert" haben.

nein, wir haben hier gerade eine unterschiedliche vorstellung was wir sortiert haben.

die daten/keys sind es bei maps nicht! der zugrauf die keys kann aber die keys in einer sortierten reihenfolge durchlaufen.
sind diese aber nicht tatsächlcih sortiert gehalten, ist das im allgemeinen teuer.

es ist einfach falsch und schlecht aus der möglichen "sortierten" traversierung der keys bei einer map eine sortierte folge abzuleiten, da dies im allgemeinen teuerer ist, als eine echte sortierte/sortierende datenstruktur.


EDIT: um es kurz zu machen:
map: die daten sind im allgeminen NICHT sortiert. ABER man kann per iterator diese in einer sortierten reihenfolge durchlaufen.

und der springende punkt:

wie die map ihre daten hält ist ihre sache. aus nutzer sicht, geht das einen nichts an und man darf auch nicht annehmen, intern wären die daten sortiert vorhanden, nur wil manche implementierung dies so machen.

 

[slashmaxx]

Ich weiss nicht, ob das Ziel der Aufgabe richtig verstanden wurde (ich sprech mich davon mal nicht frei). Aber ich meine, dass es hier doch eher darum geht den Sortieralgorithmus selbst zu implementieren und nicht eine Funktionalität zu verwenden, die es für einen tut.
Ich weiss, dass man das Rad nicht neu erfinden muss, aber hier geht es denke ich wirklich um die Grundlagen.

Ja dann ist in deiner Spreche ein Array ja auch nicht sortiert (MMU so mal als Hinweis).
Ich kann mit bei einer map darauf verlassen, dass ich mit dem iterator die Werte sortiert bekomme (und zwar aufsteigend).

Ich glaube, das Problem ist, das du und ich eine verschiedene Vorstellung von "sortiert" haben.

Ich vielleicht auch :-) Vielleicht kannst du mir das mit dem Array nochmal erläutern. Bin der Meinung das wilde Werte in einem Array auch nicht gerade sortiert sind (zumindest nicht zwingend). Es ist mir klar, dass diese in der Regel als MemoryBlock im Speicher liegen und jeder Inkrementation des Index der Speicherort des Wertes sich ebenfalls um die Wertbreite inkrementiert. Aber hier geht es um die Sortierung der Werte selbst. Aber korrigiere mich ruhig.

Ich gebe dir dahingehend Recht ein Sache kann sortiert sein oder auch nur sortiert zurückgegeben werden.
Auf letzteres kommt es an. Ein sortiertes Array kann schnell zugeriffen werden (konstanter Aufwand sofern Index bekannt, sonst Suche nach Wert = linearer Aufwand). Eine sortierte Map, wenn die zugrundeliegende Datenstruktur es nicht sortiert ablegt, wird durch den Suchvorgang länger und somit ineffizienter sein. Wenn diese es sortiert ablegt, dann sieht es natürlich anders aus. Hängt also von der Datenstruktur ab. Und wenn man die nicht kennt, dann sollte man sich nicht über negative Effekte wundern :-)

 

[Hancock]

Du hast ein Array mit sortierten Werten => die liegen sortiert im Speicher.
Stimmt nur solange man den virtuellen Speicher betrachtet (daher der Hinweis auf die MMU).

Ich betrachte es abstrakt und sage, dass das sortiert ist, welches auf irgendeine Weise abgerufen werden kann (ohne Aufwand durch mich mit linearem Aufwand), wobei bei diesem Abruf die Daten in richtiger Reihenfolge kommen. Also in Java Notation

void echoSorted(Enumerable<?> map){
for(Object o:map)
System.out.println(o);
}

irgendeine Weise: std::map::iterator
linearer Aufwand: http://stackoverflow.com/questions/...mplexity-of-iterating-through-a-stdset-stdmap
richtige Reihenfolge: The elements in the container follow a strict order at all times. All inserted elements are given a position in this order.
=> Daten in einer map sind sortiert. Wie, ist mir soweit egal, solange ich keine komplexitätstechnische Nachteile habe
=> Daten in map <=> Daten sortiert

BTW: Sortieren mittels einer map oder set ist laut Wikipedia das effizienteste bekannte Sortierverfahren (bis auf den Speicherverbrauch).

 

[Dese]

das abrufen der daten in sortierter reiehenfolge bei MAPs ist NICHT garanteirt linear!

du ignorierst bei deiner abstrakten sicht einfach die spezifikation der MAPs. maps bieten einen geordnete traversierung aber nicht sortierte daten! wenn du diese beiden eigenschaften durcheinander wirfst, dann ist das keine ansichtssache sondern ein fehler.

MAPs haben lediglich eine erwartete amortisierte konstante laufzeit für EINE iteration. d.h. einmal durch alle elemente zu iterieren dauert im ERWARTUNGSFALL O(n). und das gilt auch nur aufgrund der derzeitigen gewählten implementierung!

hier von sortierung zu reden ist nicht nur falsch, es ist auch gefährlich jeh nachdem, wie die daten tatsächlcih aussehen.

https://groups.google.com/forum/?fromgroups#!topic/comp.lang.c++.moderated/3CDTxV-wbcs


edit: ganz ehrlich... ich weiß nicht was es heir zu diskutieren gibt. in den standardimplementierungen sind die daten in einem binarytree gehalten -> NICHT SORTIERT!
laufzeit für eine vollständige traversierung ist nur erwartet O(n).

da gibt's nichts zu diskutieren. in reihe sortiert ist da nichts, bzw. ob es das ist, ist eine reine interne angelegenheit der maps und keine garantierte eigenschaft der schnittstelle.

edit2: daten in einem array sind auch unter berücksichtigung einer mmu sortiert. sortiert bedeutet, dass jede nachfolgende zelle (im sinne der ordnung) in GARANTIERT konstanter zeit erreicht werden kann (im gegensatz zu maps, wo es nur AMORTISIERT bzw. ERWARTET der fall ist).

 

[Hancock]

Zu edit: Laufzeit ist O(n), siehe Red-Black-Tree und C++ Standard.

Du wirst sie in sortierter Reihenfolge bekommen, das ist garantiert.

Zu deinem Edit2: Und das ist bei einem Array hinter einer MMU grade nicht der Fall (Auslagerungsdatei z.B.), da kannst du locker mal O(log n) für einzelne Elemente haben, in Summe hast du wieder amortisiert O(1) für ein Zugriff und damit O(n) für alle (womit's wieder genauso gut ist wie n set).

 

[Dese]

Zu edit: Laufzeit ist O(n), siehe Red-Black-Tree und C++ Standard.

Du wirst sie in sortierter Reihenfolge bekommen, das ist garantiert.

also langsam zweifle ich an deinen lesefähigkeiten.
wer hat denn angezweifelt, dass ich beim anfragen über eine methode, die genau das garantiert, die daten NICHT in sortierter reihenfolge bekomme?

es geht darum, ob die datenstruktur diese sortiert vorhält. und das müssen MAPs NICHT und tuen es im allgemeinen auch nicht.

binary-tree =/= soprtiert!!!

Zu deinem Edit2: Und das ist bei einem Array hinter einer MMU grade nicht der Fall (Auslagerungsdatei z.B.), da kannst du locker mal O(log n) für einzelne Elemente haben, in Summe hast du wieder amortisiert O(1) für ein Zugriff und damit O(n) für alle (womit's wieder genauso gut ist wie n set).

1. reden wir hier von einer datenstruktur und nicht von der hardware und ihren eigenarten. fügt man daten sortiert in ein array ein, sind diese sortiert in der datenstruktur "array". was die hardware mit mmu etc drunter anstellt hat nichts mit der datenstrukrur zu tun.
bei einer c++ MAP sind die daten im allgemienen NICHT sortiert gehalten.
viel wichtiger: MAP garantiert nichts über den in-order zugriff. es gibt einen lediglich die möglichkeit in einer sorteirten reihenfolge zu traversieren. wie gut oder schlecht ist eine ganz andere frage!

ich verstehe nciht was du da immer noch rum reden willst?

EDIT: MAPs müssen noch nicht einmal effiziente binary-trees wie red-bacl-trees nutzen. das sind implementationsfreiheit!!! die datenstruktur selbst (aus sicht des anwenders) gibt so etwas nicht vor.
du verläßt dich gerade ausschließlich auf wissen über gängie implementationen und nicht auf die garantien der methoden der datenstruktur.

2. zu mmu, das kommt auf den typ an. im allgemeinen kann man bei geigneter wahl von größe etc. bei mmu operation von konstant reden, z.m. für eine der auflösungsrichtungen.
aber das hat so oder so nichts mit unser sinnlosen diskussion zu tun.

Verwendung von MAP als Datenstruktur gibt einem nicht garantiert alle Eigenschaften einer sortierenden datenstruktur. so sind maps nicht spezifiziert! dazu haben wir bei ja schon genügend c++ standard links gepostet.

2.