std::multimap alle Werte aber nur jeweils einmal den Schlüssel ausgeben
-
Hallo @all
Ich möchte aus einer std::multimap alle Werte ausgeben bzw. verwerten aber ich benötige nur jeweils einmal den Schlüssel.
Die Werte für einen bestimmten Schlüssel bekomme ich so:
std::multimap<Key,Value> mmap; for( auto werte = mmap.equal_range(mykey); werte.first != werte.second; werte++) { // ... }
Möchte ich alle Werte ausgeben:
for( auto eintrag : mmap) { // ... }
Jetzt habe ich aber das Problem, dass ich bei der zweiten Variante mir immer merken muss, welchen Schlüssel ich schon verwendet habe und in jedem Schritt überprüfen muss, ob sich der Schlüssel geändert hat.
Und Deshalb meine Frage, ob es dafür eine elegantere Möglichkeit gibt, als immer zu überprüfen, ob sich der Schlüsselwert verändert hat.
MfG
Hlymur
-
Machs doch genauso wie schon gezeigt:
auto iter = mmap.begin(), end = mmap.end(); while (iter != end) { auto& key = iter->first; // Falls erwünscht auto pair = mmap.equal_range(key); for (iter = pair.first; iter != pair.second; ++iter) // … }
-
Arcoth schrieb:
Machs doch genauso wie schon gezeigt:
auto iter = mmap.begin(), end = mmap.end(); while (iter != end) { auto& key = iter->first; // Falls erwünscht auto pair = mmap.equal_range(key); for (iter = pair.first; iter != pair.second; ++iter) // … }
Das ist O(n log n), nicht?
auto iter = mmap.begin(), end = mmap.end(); while (iter != end) { auto& key = iter->first; do { // … } while (++iter != end && iter->key == key); }
O(n) und sollte damit schneller sein.
-
AFAICS, wenn die Anzahl der Elemente und die Anzahl der unterschiedlichen Keys angibt, benötigt dein Code Vergleiche und meiner (nicht mehr als um genau(er) zu sein). I.e. meiner wird mit vergleichsweise niedrig werdender Key-Anzahl besser.
Die Vorgehensweise mit
equal_range
kann im Übrigen mittelsstd::upper_bound
deutlich verbessert werden.auto iter = mmap.begin(), end = mmap.end(); while (iter != end) { auto last = std::upper_bound(iter, end, *iter, mmap.value_comp()); for (; iter != last; ++iter) // … }
-
Arcoth schrieb:
AFAICS, wenn die Anzahl der Elemente und die Anzahl der unterschiedlichen Keys angibt, benötigt dein Code Vergleiche und meiner [...]. I.e. meiner wird mit vergleichsweise niedrig werdender Key-Anzahl besser.
Richtig, aber der OP will sowieso durch alle Elemente durchiterieren, von daher fällt alles unter O(n) nicht uns Gewicht und nur deine Variante ist potentiell schädlich (ausser es ist garantiert, dass die Schlüssel durchschnittlich O(log n) mal vorkommen).
(nicht mehr als um genau(er) zu sein)
Durchaus möglich, kannst du mir eine Quelle geben, dass der Baum höchstens Tiefe 2 hat?
-
Mein Code ist potenziell aber auch besser als deiner, der definitiv ins Gewicht fällt, während meiner, sublineares Vorkommen unterschiedlicher Keys vorausgesetzt, nicht.
eqr schrieb:
(nicht mehr als um genau(er) zu sein)
Durchaus möglich, kannst du mir eine Quelle geben, dass der Baum höchstens Tiefe 2 hat?
Was soll denn die Tiefe des Baums mit der Anzahl der Vergleiche zu tun haben?
Aber nein, ich habe mich vertan; Der Standard redet in [associative.reqmts] tatsächlich nicht von konkreten oberen Schranken, nur in [equal.range]. Daher nehme ich die genaue(re) Aussage zurück.
-
Ah, ok so werde ich das dann machen
Danke euch