una - vector de vectores c++

Establecer algoritmo de unión usando vector en C++

Question

Solo estoy usando std::vector en este problema, y ​​puedo garantizar que no habrá duplicados en cada vector (pero no hay ningún orden en cada vector). ¿Cómo puedo unir los vectores que tengo?

Ejemplo:

Si tengo los siguientes vectores ...

1
1
3 2
5
5 4
2
4
4 2

Después de la unión, debería tener solo dos vectores:

1
2 3 4 5

De nuevo, solo estoy usando vector, std::set no está permitido.

Answer 1

Aquí está mi código:

template<class T> bool vectorExist (vector<T> c, T item)
{
return (std::find(c.begin(), c.end(), item) != c.end());
}
template<class T> vector<T> vectorUnion (vector<T> a, vector<T> b)
{
vector<T> c;
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
auto i = a.begin();
auto j = b.begin();
while (i != a.end() || j != b.end())
{
if (j == b.end() || *i < *j)
{
if(!exist(c,*i)) c.insert(*i);
i++;
}
else
{
if(!exist(c,*j)) c.insert(*j)
j++;
}
}
return c;
}

Answer 2

Ordene los vectores, luego combínelos como en mergesort, pero no inserte duplicados.

vector<int> a, b, c;
sort( a.begin(), a.end());
sort( b.begin(), b.end());
int i = 0, j = 0;
while( i < a.size() && j < b.size())
if( a[ i ] == b[ j ] )
{
c.push_back( a[ i ] );
++i, ++j;
}
else if( a[ i ] < b[ j ] )
c.push_back( a[ i++ ] );
else
c.push_back( b[ j++ ] );
while( i < a.size()) c.push_back( a[ i++ ] );
while( j < b.size()) c.push_back( b[ j++ ] );

Answer 3

Puede usar el algoritmo std :: set_union.

int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
std::vector<int> v(10); // 0 0 0 0 0 0 0 0 0 0
std::vector<int>::iterator it;
std::sort (first,first+5); // 5 10 15 20 25
std::sort (second,second+5); // 10 20 30 40 50
it=std::set_union (first, first+5, second, second+5, v.begin());
// 5 10 15 20 25 30 40 50 0 0
v.resize(it-v.begin()); // 5 10 15 20 25 30 40 50

Consulte: http://www.cplusplus.com/reference/algorithm/set_union/