Установить алгоритм объединения с использованием вектора в C++

Question

В этой проблеме я использую только std::vector, и я не могу гарантировать дублирование в каждом векторе (но в каждом векторе нет никакого порядка). Как объединить векторы, которые у меня есть?

Пример:

Если у меня есть следующие векторы ...

1 
1 
3 2 
5 
5 4 
2 
4 
4 2 

После объединения я должен иметь только два вектора слева:

1 
2 3 4 5 

Опять я только с помощью вектора , std::set не допускается.

Answer 1

Вы можете использовать алгоритм 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 

См: http://www.cplusplus.com/reference/algorithm/set_union/

Answer 2

Сортировка векторов, а затем объединить их, как и в сортировке слиянием, но не вставляйте дубликаты.

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

Вот мой код:

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