Combining arrays without repeating elements

The condition can be interpreted in two ways. If the task is for all the elements to be unique, it is convenient to use std::set or std::unordered_set :

 #include <algorithm> // copy() #include <iostream> // cout #include <iterator> // ostream_iterator<> #include <set> #define SIZE(array) (sizeof(array) / sizeof(*array)) int main() { typedef int Value; Value a[] = {3,2,1,1,2,3}, b[] = {3,3,3,4,5,5}; std::set<Value> c(a, a + SIZE(a)); c.insert(b, b + SIZE(b)); std::copy(c.begin(), c.end(), std::ostream_iterator<Value>(std::cout, " ")); } 

The complexity of the creation is linear-logarithmic: O(n*log n + m*log m) , where n , m dimensions a and b . You can make the creation time linear using unordered_set , if the Value type allows.

Example:

 $ g++ merge_all_unique.cc && ./a.out 1 2 3 4 5 

You can see that the result is sorted and there are no duplicate items.

If inside a and b elements can be repeated, but you cannot just add elements from b that already exist in a :

 #include <algorithm> // copy() #include <iostream> // cout #include <iterator> // ostream_iterator<>, begin(), end() #include <unordered_set> #include <vector> int main() { using std::begin; using std::end; typedef int Value; Value a[] = {3,2,1,1,2,3}, b[] = {3,3,3,4,5,5}; std::vector<Value> c(begin(a), end(a)); std::unordered_set<Value> a_set(begin(c), end(c)); std::copy_if(begin(b), end(b), std::back_inserter(c), [&a_set] (Value item) { return a_set.find(item) == a_set.end(); // item not in a }); std::copy(begin(c), end(c), std::ostream_iterator<Value>(std::cout, " ")); } 

The complexity of creating c linear: O(n + m) .

Example:

 $ g++ -std=c++11 merge_not_in_a.cc && ./a.out 3 2 1 1 2 3 4 5 5 

It can be seen that the elements are not sorted and can be repeated (how many times they are present in separate input arrays). 3 not copied from b , because this number is already in a .

To taste, instead of algorithms, you can use explicit loops:

 #include <iostream> // cout #include <iterator> // begin() #include <unordered_set> #include <vector> int main() { typedef int Value; Value a[] = {3,2,1,1,2,3}, b[] = {3,3,3,4,5,5}; std::vector<Value> c(std::begin(a), std::end(a)); std::unordered_set<Value> a_set(c.begin(), c.end()); for (auto item : b) { if (a_set.find(item) == a_set.end()) { // if not in `a` c.push_back(item); // copy from `b` } } for (auto item : c) { std::cout << item << ' '; } } 

The result and execution time are the same.

Will work with many containers and even with regular arrays.

 #include <windows.h> #include <array> #include <algorithm> int main() { std::array<int, 10> arr1 = { 1,2,3,4,5 }; std::array<int, 5> arr2 = { 1,7,8,9,5 }; std::copy_if(arr2.begin(), arr2.end(), arr1.begin() + 5, [&](const int& _1) {for (auto it : arr1) { if (it == _1)return false; }return true; }); for (auto it : arr1) { printf_s("%d\n", it); } while (true) { Sleep(1); } return 0; }