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 brauchtN * M
Zeit, aber keinen zusätzlichen Platz. Wenn das schnell genug ist, warum nicht?
Man kann das aufN + M
verkürzen, wenn man ein Hashset derSomeProperty
s stattfind_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 :-).