Union unsortierter vectoren



  • Hallo Forum,

    folgende Aufgabe: ich möchte alle Elemente aus einem vector einem anderen hinzufügen, sofern sie dort noch nicht enthalten sind (Prüfung nicht über Gleichheit, sondern über eine Objekteigenschaft).

    std::set_union schien mir zwar geeignet, allerdings verlangt der Algorithmus zum einen sortierte Eingangsdaten, zum anderen müsste ich einen temporären Ergebnis-vector erzeugen und diesen dann wieder meinem Ziel-vector zuweisen. Das scheint mir aus Performance-Gründen nicht ideal.

    Ich habe jetzt folgenden Ansatz gewählt, bin mir aber bezüglich des Anhängens an "dest" mittels des back_inserters ein wenig unsicher, weil ich ja dabei den vector verändere, auf den ich find_if anwende. Ist das ok so, oder gibt es deutlich bessere Wege?

    std::vector<Mytype> source;
    std::vector<Mytype> dest;
    
    // Anzahl der Element in source deutlich kleiner als in dest
    
    dest.reserve(dest.size() + source.size());
    std::copy_if(source.begin(), source.end(), std::back_inserter(dest), [&dest] (const MyType& lhs)
    {
        auto it = std::find_if(dest.begin(), dest.end(), [&lhs] (const MyType& rhs)
        {
            return lhs.SomeProperty() == rhs.SomeProperty();
        });
    
        return it == dest.end();
    });
    


  • Ich sehe da kein Problem mit dem Verändern von data .
    Die Lösung braucht N * M Zeit, aber keinen zusätzlichen Platz. Wenn das schnell genug ist, warum nicht?
    Man kann das auf N + M verkürzen, wenn man ein Hashset der SomeProperty s statt find_if verwendet. Das braucht dann aber zusätzlichen Platz.



  • Vielen Dank für den Hinweis.
    Vielleicht schaue ich mir das unordered_set mal an, auch wenn das in meinem Fall vielleicht ein wenig mit Kanonen auf Spatzen geschossen ist :-).


Log in to reply