Set a join algorithm using a vector in C ++

Question

I use only std::vector in this problem, and I cannot guarantee duplication in every vector (but there is no order in each vector). How to combine vectors that I have?

Example:

If I have the following vectors ...

 1 1 3 2 5 5 4 2 4 4 2 

After combining, I only have two vectors left:

 1 2 3 4 5 

Again I use only vector, std::set not allowed.

Answer 1

You can use the std :: set_union algorithm.

 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 

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

Answer 2

Sort the vectors, then merge them as in mergesort, but do not insert duplicates.

 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

Here is my code:

 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; }