STL: vector + vector + duplikate rauswerfen

peterchen

Mal wieder eine von meinen "geht das auch besser" Fragen:

Ich habe zwei Vektoren die evtl. Duplikate beinhalten. Die zwei Vektoren muß ich zusammenschmeißen, duplikate rauswerfen udn das ganze wieder in einem vektor zurückgeben. Reihenfolge der ausgegebenen werte ist egal

mein Ansatz (pseudocode):

copy.reserve(v1.size() + v2.size());
copy = v1;
copy.insert(v1.end(), v2);
sort(copy);
it = unique(copy);
vector result(copy.begin(), it);

nun die angedrohte Frage: geht das (mit Bordmitteln) auch einfacher / effektiver?

LordJaxom

Als jemand, der auch gerade erst anfängt exzessiver die STL zu benutzen, versuche ich's mal:

sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());

vector result;
set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result));

EDIT:
set_union wäre wahrscheinlich besser, da intersection nur die Elemente beibehält, die in beiden Vektoren vorhanden waren, Rest wie oben..

peterchen

sieht schon mal vie besser aus

Noch 'ne Frage: wie schlecht ist std::sort für bereits sortierte Daten? Gibt es da irgendwelche Garantien?

(Ist leider ein Implementationsdetail, daß ich nicht explizit ausnutzen kann)

Jester

peterchen schrieb:

nun die angedrohte Frage: geht das (mit Bordmitteln) auch einfacher / effektiver?

Effektiver wohl kaum, vielleicht etwas effizienter. :p
Merge kann zwei sortierte Sequenzen sortiert zusammenfügen.

vector result;
result.reserve(v1.size()+v2.size());
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(result));
result.erase(unique(result.begin(), result.end()), result.end());

Auf jeden Fall würde ich die Daten danach nicht nochmal kopieren, sondern einfach die überflüssigen Einträge rauslöschen.
Merge darfst Du allerdings nur verwenden, wenn die Daten sortiert sind. Sonst doch eher die Copy-Methode.

MfG Jester