Alle Keys einer map aus einer anderen Map entfernen



  • Hallo zusammen,

    wenn ich 2 maps vom selben Typ habe und aus der einen Map alle Einträge die einen Key haben, der auch in der anderen map enthalten ist, wie geht das dann am besten?
    Gibts da vll irgendnen algorithmus, den man verwenden kann oder so?

    Mein naiver Ansatz wäre:

    #include <map>
    #include <string>
    using namespace std;
    
    void foo()
    {
       typedef map<int, string> MyMap;
       MyMap m1,m2;
       fillWithValues(m1);
       fillWithOtherValues(m2);
       for(MyMap::iterator i = m1.begin(); i!= m1.end(); ++i)
       {
          m2.erase(i->first);
       }
    }
    

    Geht das vll noch kürzer/besser?



  • Deine jetzige Implementierung hat Komplexität O(m * log n), wobei m die Größe von m1 und n die Größe von m2 ist. Es geht auch in linearer Zeit O(m + n), wenn du die Sortierung berücksichtigst. Das geht in etwa so:

    auto i = m1.begin();
    auto j = m2.begin();
    while(i != m1.end() && j != m2.end())
    {
        if(i->first == j->first)
        {
            m2.erase(j++);
            ++i;
        }
        else
            ++j;
    }
    

    Es kommt auf die Größenverhältnisse zwischen den beiden Maps an, welche Komplexität als besser zu betrachten ist.



  • Michael E. schrieb:

    Deine jetzige Implementierung hat Komplexität O(n* log n). Es geht auch in linearer Zeit, wenn du die Sortierung berücksichtigst. Das geht in etwa so:

    auto i = m1.begin();
    auto j = m2.begin();
    while(i != m1.end() && j != m2.end())
    {
        if(i->first == j->first)
        {
            m2.erase(j++);
            ++i;
        }
        else
            ++j;
    }
    

    Ohne es groß durchzuprobieren, ahbe ich meine Zweifel, dass ein == reicht, um zu entscheiden, ob es ++i oder ++j sein muss.



  • Ok, sofern es funktioniert, wirds wirklich etwas schneller sein.
    Mir gings aber eigentlich hauptsächlich um die einfachheit/kürze/verständlichkeit, deswegen hatte ich auf nen algorithmus gehofft der da funktioniert.
    Mehr Schnelligkeit ist natürlich auch nich verkehrt, aber nicht das hauptanliegen.
    Für set gibts ja einiges
    set_difference
    set_intersection
    set_symmetric_difference
    set_union

    Ich muss aber zugeben, dass ich ohne nachzuschaun nicht genau weiß, wie die funktionieren.
    Aber für map wird das vermutlich nicht funktionieren.

    Zu dem keyword

    auto
    

    : Das funktioniert aber nur mit C++0x, oder?
    Ich benutz MSVC 2010 und hab bisher noch nichts mit 0x versucht, aber eigentlich siehts ganz praktisch aus.



  • Mir fällt so spontan set_difference ein, wobei der Kram dann in eine dritte Map kopiert wird:

    #include <algorithm>
    #include <iostream>
    #include <iterator>
    #include <map>
    #include <string>
    
    struct pair_key_compare {
      template<typename T, typename U>
      bool operator()(std::pair<T, U> const &lhs,
                      std::pair<T, U> const &rhs) {
        return lhs.first < rhs.first;
      }
    };
    
    int main() {
      std::map<int, std::string> m1, m2, m3;
    
      m1[1] = "foo";
      m1[2] = "bar";
      m1[3] = "baz";
    
      m2[1] = "qux";
      m2[3] = "quux";
      m2[5] = "xyzzy";
    
      std::set_difference(m2.begin(), m2.end(),
                          m1.begin(), m1.end(),
                          std::inserter(m3, m3.begin()),
                          pair_key_compare());
    
      for(std::map<int, std::string>::const_iterator i = m3.begin(); i != m3.end(); ++i) {
        std::cout << i->first << " -> " << i->second << '\n';
      }
    }
    

    Was den Algorithmus angeht, da reicht == in der Tat nicht, zumal der Schlüssel einer Map diesen Operator gar nicht zwingend braucht. So sollte es gehen:

    auto i = m1.begin();
    auto j = m2.begin();
    
    while(i != m1.end() && j != m2.end()) {
      if(i->first < j->first) {
        ++i;
      } else if(j->first < i->first) {
        ++j;
      } else {
        m2.erase(j++);
        ++i;
      }
    }
    


  • HighendCoder schrieb:

    Ohne es groß durchzuprobieren, ahbe ich meine Zweifel, dass ein == reicht, um zu entscheiden, ob es ++i oder ++j sein muss.

    Wie meinst du das? Edit: Jetzt seh ichs auch.

    BTW: Man kann die Performance noch steigern, indem man zwei verschachtelte Schleifen macht, sodass nciht nach jedem Inkrementieren von j geprüft werden muss, ob i == m1.end() ist.


  • Mod

    if (!m1.empty() && !m2.empty() && &m1 != &m2) {
        auto i = m1.begin();
        auto j = m2.begin();
        auto comp = m1.value_comp();
        for ( ;; ) {
            if(m1.comp()(*i, *j) {
                if (++i == m1.end())
                    break;
            } else if(comp()(*j, *i) {
                if (++j == m2.end())
                    break;
            } else {
                m2.erase(j++);
                if (j == m2.end() || ++i == m1.end())
                    break;
            }
        }
    }
    


  • Michael E. schrieb:

    Deine jetzige Implementierung hat Komplexität O(m * log n), wobei m die Größe von m1 und n die Größe von m2 ist. Es geht auch in linearer Zeit O(m + n), wenn du die Sortierung berücksichtigst. Das geht in etwa so:

    auto i = m1.begin();
    auto j = m2.begin();
    while(i != m1.end() && j != m2.end())
    {
        if(i->first == j->first)
        {
            m2.erase(j++);
            ++i;
        }
        else
            ++j;
    }
    

    Es kommt auf die Größenverhältnisse zwischen den beiden Maps an, welche Komplexität als besser zu betrachten ist.

    Du geht davon aus, daß erase() O(1) ist?



  • volkard schrieb:

    Du geht davon aus, daß erase() O(1) ist?

    Ja:

    Complexity
    For the first version ( erase(position) ), amortized constant.

    http://www.cplusplus.com/reference/stl/map/erase/



  • Hmmm...Vorsicht, das ist amortisiert konstant, nicht einfach konstant. Wenn der Baum sich beim Löschen immer das kleinste Element des rechten Unterbaumes herholt, kann man sich damit fiese Worst-Case-Szenarien einhandeln, wenn lange, zusammenhängende Bereiche des Baums gelöscht werden sollen.

    Unter gewissen Umständen könnte es wesentlich schneller sein, zusammenhängende Bereiche per range-erase abzuhandeln. Das verkompliziert allerdings den Algorithmus - Q, mit welchen Datenmengen wirfst du hier um dich? Lohnt sich der Aufwand?



  • seldon schrieb:

    Lohnt sich der Aufwand?

    Nein.

    Ich benutze dann doch einfach, das, was ich im ersten Post geschrieben hab.
    Die Datenmengen sind nicht besonders groß, ich hatte eigentlich nur auf einen algorithmus aus <algorithm> gehofft, den es schon gibt und das ganze einfacht macht.



  • Q schrieb:

    [...] ich hatte eigentlich nur auf einen algorithmus aus <algorithm> gehofft, den es schon gibt und das ganze einfacht macht.

    Den gibt's doch.

    Um die Vorzüge von seldons Code (set_difference) und campers Code (value_comp) zu kombinieren:

    #include <algorithm>
    #include <iostream>
    #include <iterator>
    #include <map>
    #include <string>
    
    int main() {
      std::map<int, std::string> m1, m2;
    
      m1[1] = "foo";
      m1[2] = "bar";
      m1[3] = "baz";
    
      m2[1] = "qux";
      m2[3] = "quux";
      m2[5] = "xyzzy";
    
      // "m1 aus m2 entfernen" ...
      {
        std::map<int, std::string> mt;
        std::set_difference(m2.begin(), m2.end(),
                            m1.begin(), m1.end(),
                            std::inserter(mt, mt.begin()),
                            m2.value_comp());
        m2.swap(mt);
      }
    
      for(auto i = m2.begin(); i != m2.end(); ++i) {
        std::cout << i->first << " -> " << i->second << '\n';
      }
    }
    

    kk


Log in to reply