vector<T> vereinen

[dfdsfdf]

Ich habe einen vector<vector<T>> vv; und will in einen vector<T> die vv[i] reinkopieren, wobei alles sortiert und Duplikate entfernt werden sollen.

Wie mache ich das am besten?

[fasdf]

std::vector<int> w;
for (auto const& v : vv)
    w.insert(w.end(), v.begin(), v.end());
std::sort(w.begin(), w.end());
w.erase(std::unique(w.begin(), w.end()), w.end());

[volkard]

dfdsfdf schrieb:

Ich habe einen vector<vector<T>> vv; und will in einen vector<T> die vv[i] reinkopieren, wobei alles sortiert und Duplikate entfernt werden sollen.
Wie mache ich das am besten?

Mir fällt spontan ein, jeden vector erstmal mit
sort http://www.cplusplus.com/reference/algorithm/sort/
zu sortieren, mit
unique http://www.cplusplus.com/reference/algorithm/unique/
die Duplikate zu entfernen, und dann immer zwei zu vectoren zu nehmen und mit
set_uinion http://www.cplusplus.com/reference/algorithm/set_union/
zusammenzuführen, bis nur noch einer übrig ist.

[fasdf]

volkard schrieb:

und mit
set_uinion http://www.cplusplus.com/reference/algorithm/set_union/
zusammenzuführen, bis nur noch einer übrig ist.

Das ist entweder wie meine Variante oder wie ein schlechtes Merge-Sort.

[volkard]

fasdf schrieb:

volkard schrieb:

und mit
set_uinion http://www.cplusplus.com/reference/algorithm/set_union/
zusammenzuführen, bis nur noch einer übrig ist.

Das ist entweder wie meine Variante oder wie ein schlechtes Merge-Sort.

Nicht ganz. Ich ziele auf größere Arrays und das Vorhandensein von reichlichen Duplikaten.

Warum *schlechtes* Merge-Sort? Die Happen mit einem Sort vorzusortieren, was für kleinere Menge ausgelegt ist, tut Merge-Sort doch gut.

Ich haue die Duplikate halt während des Sortierens so früh wie möglich weg, denn falls es viele Duplikate gibt, wozu sie bis zum Ende behalten und dann erst wegwerfen?

[fasdf]

volkard schrieb:

Nicht ganz. Ich ziele auf größere Arrays und das Vorhandensein von reichlichen Duplikaten.

Ja, es gibt Konstellationen, da ist wahrscheinlich deines besser. Ich schätze mal
viele Duplikate -> std::set
wenige Arrays mit vielen Duplikaten -> deine Variante
Wenig Duplikate -> meine Variante

Warum *schlechtes* Merge-Sort?

Weil O(n^2).

[volkard]

fasdf schrieb:

Warum *schlechtes* Merge-Sort?

Weil O(n^2).

*lach*
Da muss man aber herzlich unberufen sein, um stets das nächste Array mit dem Ziel-Array zu vereinen. Nee, man kann sich schon immer zwei kleine Arrays nehmen und draus ein größeres machen.