sortierte maps

Hallo zusammen

ich habe das Problem dass mir meine Map meine key-woerter sortiert. Ich weiss zwar, dass map so implementiert ist, aber kann ich das auch umgehen? Ich glaube gelesen zu haben dass man dann seinen eigenen sort() algorithmus schreiben muss. Wo ist denn der bei dem maps definiert? Bzw wie kann ich meine Daten trotzdem in der Reihenfolge haben, wie ich sie eigentlich will und nicht wie sie die map speichert? Ich hatte mir ueberlegt in der Methode einfach eine feste Liste zu speichern in der Reihenfolge wie ich es gerne moechte und dann dementsprechend meine Daten wieder in einen vector stecke. Ist das zu kompliziert?

Danke fuer eure Hilfe und
Gruesse

.filmor

Vielleicht so:

struct DontSort
{
    template <typename T>
    bool operator () (const T&, const T&)
    {
        return true;
    }
};

std::map<std::string, int, DontSort> m;

Ne Map ist doch ein Baum da gibt es keine Sortierung.

Die Lösung ist recht simpel: std::list< std::pair< key, value > >

Die Lösung da oben ist nicht nur quatsch, sondern ausdrücklich verboten.

peterchen

Ne Map ist doch ein Baum da gibt es keine Sortierung.

Aber wenn du durchiterierst, bekommst du die nicht in einfügeordnung (sondern meist sortiert)

Wenn du wenige Elemente hast, ist eine unsortierte Liste und eine lineare Suche oft besser.

Wenn du den schnellen Zugriff brauchst: parallel Liste oder Vektor (je nach Anwendungsfall) mit den map-Iteratoren halten (in Einfügereihenfolge), das ganze in eine Klasse verpacken.

.filmor

Any schrieb:

Die Lösung ist recht simpel: std::list< std::pair< key, value > >

Die Lösung da oben ist nicht nur quatsch, sondern ausdrücklich verboten.

Das ist nicht gleichwertig mit einer map. Man hat so keinen Zugriff über ein Key-Objekt. Warum ist meins verboten?!

finix

.filmor schrieb:

Any schrieb:

Die Lösung ist recht simpel: std::list< std::pair< key, value > >

Die Lösung da oben ist nicht nur quatsch, sondern ausdrücklich verboten.

Das ist nicht gleichwertig mit einer map. Man hat so keinen Zugriff über ein Key-Objekt.

Ich denke er meint Peterchens Lösung...

.filmor schrieb:

Warum ist meins verboten?!

Strict Weak Ordering? Schon mal gehört?

tntnet

.filmor schrieb:

Any schrieb:

Die Lösung ist recht simpel: std::list< std::pair< key, value > >

Die Lösung da oben ist nicht nur quatsch, sondern ausdrücklich verboten.

Das ist nicht gleichwertig mit einer map. Man hat so keinen Zugriff über ein Key-Objekt. Warum ist meins verboten?!

Das Prädikat-Objekt dient nicht einfach nur zur Sortierung, sondern auch zur ermittlung der Gleichheit der Schlüssel. Wenn Du aus der Map einen Wert z. B. mittels std::find ermittelst, dann bekommst Du mit deinem Prädikat wahrscheinlich keinen Treffer, da find ein Element sucht, bei denen pred(a, b) und pred(b, a) falsch sind. Genau dann ist nämlich Gleichheit gegeben (man denke an "a < b" und "b < a"). Bei Deiner Implementierung ist das nie der Fall, also gibt es keine Treffer.

Wobei Du bei einem Versuch durchaus Treffer bekommen kannst, da ein Fall, wo "pred(a, b)" und "pred(b, a)" wahr ergeben nicht sein darf und daher undefiniert und damit implementierungsabhängig ist.

Tommi