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


  • Mod

    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.


  • Mod

    AFAICS, wenn nn die Anzahl der Elemente und kk die Anzahl der unterschiedlichen Keys angibt, benötigt dein Code nn Vergleiche und meiner Θ(klogn)\Theta(k \log n) (nicht mehr als k(2log2n+O(1))k ( 2\log_2 n + O(1)) um genau(er) zu sein). I.e. meiner wird mit vergleichsweise niedrig werdender Key-Anzahl besser.

    Die Vorgehensweise mit equal_range kann im Übrigen mittels std::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 nn die Anzahl der Elemente und kk die Anzahl der unterschiedlichen Keys angibt, benötigt dein Code nn Vergleiche und meiner Θ(klogn)\Theta(k \log n) [...]. 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 k(2log2n+O(1))k ( 2\log_2 n + O(1)) um genau(er) zu sein)

    Durchaus möglich, kannst du mir eine Quelle geben, dass der Baum höchstens Tiefe 2 hat?


  • Mod

    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 k(2log2n+O(1))k ( 2\log_2 n + O(1)) 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 👍


Log in to reply