multimap: Wertereihenfolge bei identischen Schlüsseln
-
Ein vector kommt leider nicht in Frage, obwohl es natürlich sauberer wäre und ich die multimap ein wenig vergewaltige. Allerdings ist die value-Klasse (die int's waren nur für's Beispiel) semantisch nicht kopierbar (trotzdem wurden für "STL-Kompatibilität" ein sinnloser Copy-Konstruktor und Zuweisungsoperator reingefrickelt
). Da der Code nicht von mir ist und zu kompliziert anzupassen, habe ich mich erstmal für die Multimap entschieden.
-
Ja, Templates sind schon was feines!
-
7H3 N4C3R schrieb:
Ein vector kommt leider nicht in Frage, obwohl es natürlich sauberer wäre und ich die multimap ein wenig vergewaltige. Allerdings ist die value-Klasse (die int's waren nur für's Beispiel) semantisch nicht kopierbar (trotzdem wurden für "STL-Kompatibilität" ein sinnloser Copy-Konstruktor und Zuweisungsoperator reingefrickelt
). Da der Code nicht von mir ist und zu kompliziert anzupassen, habe ich mich erstmal für die Multimap entschieden.fuktioniert dann vielleicht ne liste? Obwohl...dürfte es dann nicht auch bei der mulimap probleme geben, wenn die objekte so komisch sind?
-
C++98 hat schon die möglichkeit gegeben, einen "hint" anzugeben (siehe tabelle 69 im standard) mit
insert (hint, pair<key,value>), der aber nicht wirklich beachtet werden muss. der Standard garantiert dir das nicht. die von Dinkumware, gcc < 4, Metrowerks CodeWarrior, STLport machen es z.B. anders als Rogue Wave und gcc > 4.
für C++0x siehe dazu zunächst lwg-issue 371 - was aber keine lösung für die reihenfolge darstellt.lwg-issue 233 ändert dass, in dem
mm.insert (mm.end(), make_pair(an_int, a_string)den string immer an das ende des equal_range einfügt. damit wird ein equal_rang quasi zu einem sub-container in einer multimap. 233 ist beeinflusst vom diesem proposal, das das problem zehnmal besser auf den punkt bringt, als ich hier.als lösung: verwende nicht den insert mit dem hint vor C++0x, weil der auf verschiedenen implementationen verschieden inserted. bei allen implementationen ist insert ohne hint ein insert-at-upper-bound (also das verhalten, dass du brauchst), wird aber nicht garantiert, wird aber garantiert werden. zusätzlich: verwende nicht find, sondern equal_range/lower_bound um die elemente in dieser reihenfolge zu bekommen. die stabilität der reihenfogle ist dank der implementation sowieso garantiert (es wäre ineffizient, die reihenfolge der elemente nach einem erase/insert noch zusätzlich zu verändern - deshalb macht es niemand. lwg-issue 371 ist also ebenfalls nur standardisierung einer bereits bestehenden tatsache, ebenso wie lwg-issue 233), die zukunft wird also theoretisch alles ändern und praktisch nur das verhalten von insert-with-hint.
-
Die Klasse enthält Referenzmember... deshalb ist das Einfügen über Copykonstruktor okay... den Zuweisungsoperator habe ich über ein abort() lahmgelegt und der wird auch nie gerufen. Ist schon ziemlich gruselig. Ich glaub ich stell das auf vector<pair<int,T*>> um und mach die stable_sort Variante.
Trotzdem würde es mich interessieren, wenn die eigentliche Frage noch ein Standard-Guru beantworten könnte. (Edit: Aaah da war jemand schneller - dankeschön)
-
was hast du vor? Warum brauchst du sowas komisches?
-
Speichere doch pointer in Deiner map, vector, was auch immer.
Dann wird dein value bestimmt nicht kopiert und du hast alle freiheiten
-
sagmal schrieb:
was hast du vor? Warum brauchst du sowas komisches?
Ich passe bestehenden Fremdcode an. Der Spielraum für Änderungen wie ich will ist leider verdammt klein.
-
Wenn diese Objekte scheinbar keine Wert-Semantik haben pack einfach boost::shared_ptr<Foo> in den Container. Dann brauchst du auch keine sinnlosen Copy-C'toren zu faken.
-
Boost kann (==darf) ich leider nicht verwenden.
-
7H3 N4C3R schrieb:
Boost kann (==darf) ich leider nicht verwenden.
Dann nimm die Implementierung und kopier sie in ne eigene Headerdatei. Oder such Dir ne billigere Implementierung eines shared_ptr - in wxFlatNotebook gammelt m.W. eine rum, die nur aus einem Header besteht.
Ich verstehe echt nicht warum Arbeitgeber grundsätzlich fremde Bibliotheken ablehnen, insbesondere wenn sie nichtmal binäre Abhängigkeiten verursachen. Glauben die immernoch dass ihre eigenen Leute das Rad schneller und besser erfinden als Boost und die Standard-Leute?
-
ich nehme an, deshalb:
7H3 N4C3R schrieb:
Ich passe bestehenden Fremdcode an. Der Spielraum für Änderungen wie ich will ist leider verdammt klein.
wir können da nur spekulieren und unsere antworten dementsprechend anpassen. aber in diesem fall ist es für ihn es sicher (genug), die multimap zu nehmen.
-
LordJaxom schrieb:
Ich verstehe echt nicht warum Arbeitgeber grundsätzlich fremde Bibliotheken ablehnen, insbesondere wenn sie nichtmal binäre Abhängigkeiten verursachen. Glauben die immernoch dass ihre eigenen Leute das Rad schneller und besser erfinden als Boost und die Standard-Leute?
So einfach ist das leider nicht, da leider nicht alle Compiler auf den Einsatzplattformen den Template-intensiven Code gut verkraften bzw. überhaupt übersetzen. Auch wenn shared_ptr allein nicht wahnsinnig kompliziert ist. Nur die Überlegung war entweder ganz und für alle Plattformen boost, oder garnicht.
@queer_boy:
Das Problem ist, Ergebnisse von verschiedenen Threads so zu ordnen, dass sie die selbe Reihenfolge wie in der Singlethreaded Variante haben. Jeder Key wird immer nur von einem Thread produziert, die Values sind chronologisch richtig.