Schnittmenge von Vektoren berechnen

Hallo,

kann ich auch einfach selber machen, aber wollte mal horchen, ob es da nicht vllt einen schicken standardalgorithmus gibt:

Ich würde gerne aus einer Menge von Vektoren gleichen Typs die Schnittmenge bilden also einen Vektor bauen der die Elemente enthält die in allen Vektoren enthalten sind.
Gibt es das was?

volkard

Namenloser324 schrieb:

Gibt es das was?

Nicht ganz.

Kannst aber wiederholt http://www.cplusplus.com/reference/algorithm/set_intersection/ anwenden, am besten in einer hübschen baumartigen Reihenfolge, wie bei Merge-Sort.

volkard schrieb:

Kannst aber wiederholt http://www.cplusplus.com/reference/algorithm/set_intersection/ anwenden, am besten in einer hübschen baumartigen Reihenfolge, wie bei Merge-Sort.

Nö, hier ist baumartig nicht so gut. Er nimmt sich den kleinsten der Vektoren und nimmt den als Ausgangslage. Dann wendet er wiederholt set_intersection auf diesen und alle anderen Vektoren an (braucht einen Hilfsvektor dafür.)

Angenommen, alle Vektoren sind schon sortiert so ist die Laufzeit (x+n_1)+(x+n_2)+... < 2n.

Schau mal hier:

camper schrieb:

#include <initializer_list>
#include <iterator>
#include <vector>
#include <iostream>
 
template <typename OutputIterator, typename Size, typename... InputIterator>
OutputIterator zip_merge_n(OutputIterator out, Size n, InputIterator... in)
{
    for ( ; n--; )
        (void)std::initializer_list<bool>{ ( ( *out++ = *in++ ), false )... };
    return out;
}
 
int main()
{
    std::vector<int> a = { 1, 5, 10 }, b = { 23, 42, 87 };
    std::vector<int> result;
    zip_merge_n( std::back_inserter(result), a.size(), begin( a ), begin( b ) );
}

volkard

fasdf schrieb:

Nö, hier ist baumartig nicht so gut.

Jup.

out schrieb:

...

Was hat der Code mit der Aufgabe zu tun?

Super, danke, das ist genau das was ich suche