std::map::insert() - pair an bestimmter Stelle einfügen

[-insane- 0]

Gibt es eine Möglichkeit ein pair an eine bestimmte Stelle einzufügen? Ich habe ein pair, welches ganz oben stehen soll und der Rest ist egal, aber soll auf jeden Fall darunter.

bla_pair = std::make_pair (text, 1);
	it = bla_map.begin();
	it++;
	bla_map.insert (it, bla_pair);

Damit geht es nicht, weil die Funktion sich ja selber die richtige Stelle raussucht und der iterator nur ein Hinweis ist.

Eine letzte Alternative wäre noch den obersten Eintrag rauszunehmen und selbst zu handlen, aber das wäre sehr lästig und ich wollte vorher erstmal nachfragen ob es eine bessere Möglichkeit gibt.

[otze]

Eine map sortiert nach dem Schlüssel des Elements. Wenn das Element nicht den kleinsten Schlüssel hat(btw: du meintest sicher make_pair(1,text) bei der Erstellung, oder?), wird es nicht als erstes eingefügt. Auch, wenn du es mit dem Iterator sagst.

Bei einer normalen Map sagst du mit dem Iterator nur: "Hier ist das Element, und ich kenne bereits die Position wo es hin soll". Dann schaut sich die Map den Iterator an und entscheidet, ob das wirklich die richtige Position für die interne Sortierung ist. Wenn ja, dann sparst du Zeit beim einfügen....wenn nicht, dann nicht ;).

Bei einer Multimap, wenn mehrere Elemente den selben Schlüssel haben, wird man eventuell was mit dem Iterator drehen können, damit das Element vor den anderen mit gleichem Schlüssel eingefügt wird. Ich würde aber meinen Hut verwetten, dass dies nicht vom Standard garantiert ist. Eine Map hat nicht die Aufgabe, irgendeine bestimmte Reihenfolge zu forcieren. Wenn das Dinge, dann könnte die Map ihre eigentliche Aufgabe nicht erfüllen: Ein Element anhand seines Schlüssels schnell wieder zu finden.

[DStefan]

Du könntest deinen eigenen Vergleichsoperator schreiben. std::map erlaubt die Übergabe eines solchen als dritten Parameter.

struct MyCmp: public std::binary_function<Key, Key, bool> {

   bool operator()(const Key &lhs, const Key &rhs) const {
       return // <<< Tja...
   }
};

typedef std::map<Key, Value, MyCmp> MyMap;

Stefan.

[-insane- 0]

Ob erst der String kommt und dann der Integer ist doch egal. Ich weiß grad nicht mehr genau warum ich das so gemacht habe, aber ich hatte einen Grund dafür. Und ja es wird nach dem Alphabet geordnet, dadurch, dass der String der Key ist.

Eine Multimap würde für mich auch gar nicht in Frage kommen.

Die automatische Sortierung lässt sich auch nicht umgehen oder?

Das 2. Element ist übrigens zum Mitzählen, nicht für den Index.

EDIT @ DStefan: Danke, das hört sich schonmal gut an.

[Simon2]

Hi,

also ehrlich gesagt: Ich halte es für keine gute Idee, einen Container mal selbst die Sortierung überlassen zu wollen und es mal selbst machen zu wollen.

Entweder gibst Du die Sortierung ab, nimmst std::map und nimmst in Kauf, dass ab&an mal eine "Einsortierung" stattfindet, die evtl. nicht notwendig wäre.

Oder Du übernimmst die Sortierung komplett selbst und legst Deine Daten in vector<pair<int, string> > > ab.

Mal andersherum gesprochen: Wie soll denn eine std::map effizient sortieren können UND Dich gleichzeitig an ihren Sortiermechanismen vorbei irgendwo reinschießen lassen? Das passt einfach nicht.

Gruß,

Simon2.

[otze]

Ob erst der String kommt und dann der Integer ist doch egal. Ich weiß grad nicht mehr genau warum ich das so gemacht habe, aber ich hatte einen Grund dafür. Und ja es wird nach dem Alphabet geordnet, dadurch, dass der String der Key ist.

Ist ja schon gut. Ich dachte halt, du wüsstest wie eine Map funktioniert und das sah deswegen ziemlich komisch aus. Der Hinweis auf Multimap war übrigens auch nur ein Hinweis. Auch hier aus der Verwirrung heraus, das ich eigentlich dachte dass du weißt wie die Map funktioniert.

Die automatische Sortierung lässt sich auch nicht umgehen oder?

Nein. Wie gesagt, ist die Sortierung der Grund, dass die Map überhaupt schnell Elemente anhand ihres Schlüssels finden kann. Denn dafür wurde sie designed. Ich bin aber grade verwundert, warum du überhaupt ein Element ganz vorne bei den Iteratoren haben willst. Iterator-Operationen sind nicht wirklich das, wofür eine Map gemacht ist. Bist du sicher, dass du eine Map brauchst?

Achja: Für DStefans Vorschlag musst du bereits im Voraus wissen, wie das Element heißt, das ganz vorne liegen soll.

[-insane- 0]

Simon2 schrieb:

Entweder gibst Du die Sortierung ab, nimmst std::map und nimmst in Kauf, dass ab&an mal eine "Einsortierung" stattfindet, die evtl. nicht notwendig wäre.

Naja ab und an mal ist gut, es gibt ca. 3500 Strings, die eventuell der Map hinzugefügt werden könnten. ^^

Simon2 schrieb:

Oder Du übernimmst die Sortierung komplett selbst und legst Deine Daten in vector<pair<int, string> > > ab.

Gute Idee, das werde ich jetzt auch tun, danke.

otze schrieb:

Ist ja schon gut. Ich dachte halt, du wüsstest wie eine Map funktioniert und das sah deswegen ziemlich komisch aus. Der Hinweis auf Multimap war übrigens auch nur ein Hinweis. Auch hier aus der Verwirrung heraus, das ich eigentlich dachte dass du weißt wie die Map funktioniert.

Ich wollte mich nicht verteidigen, ich wollte nur drauf hinweisen, weil ich dachte es wäre relevant dafür eine Lösung zu finden. Und ich weiß generell wie Maps funktionieren, nur dachte ich, dass vielleicht irgendjemand was in seiner Trickkiste hat

[DStefan]

-insane- schrieb:

Naja ab und an mal ist gut, es gibt ca. 3500 Strings, die eventuell der Map hinzugefügt werden könnten. ^^

Simon2 schrieb:

Oder Du übernimmst die Sortierung komplett selbst und legst Deine Daten in vector<pair<int, string> > > ab.

Gute Idee, das werde ich jetzt auch tun, danke.

Wirklich eine gute Idee? Bei bis zu 3500 Strings?

Stefan.

[otze]

Was willst du überhaupt machen? Warum brauchst du die Reihenfolge?

btw: Ich bezweifle inzwischen, dass du weißt wie eine Map funktioniert. Sonst würdest du nicht fragen, wie man die sortierung abschalten kann. Das Ding implementiert einen Binärbaum. Wenn du da die Sortierung abschaltest, findest du gar nichts wieder. Das Ding muss strukturbedingt sortieren.

[-insane- 0]

@ DStefan: Es muss ja nur ein Eintrag an 1. Stelle sein, der Rest ist egal.
@ otze: Okay, dann dachte ich halt ich wüsste es genauer. ^^

[DStefan]

-insane- schrieb:

@ DStefan: Es muss ja nur ein Eintrag an 1. Stelle sein, der Rest ist egal.

Ja, und wenn du weißt, welchen Wert der Key dieses Eintrags hat, kannst du das prima mit einer std::map und einem eigenen Vergleichs-Operator erledigen. Vorausgesetzt, der Key kommt nicht auch bei anderen Einträgen vor.

Stefan.