Provided that you do not mind losing the original order of two arrays:
std::sort(first_array, first_array + N); std::sort(second_array, second_array + M); std::set_union( first_array, first_array+N, second_array, second_array+M, target_array );
N and M are the numbers of elements in arrays. You need to either define operator< or specialize std::less for your class: instead, write a comparator function and set it to sort and set_union .
The time complexity is O(N log N + M log M) - sort is the slower part, and then set_union is linear.
If first_array or second_array may already contain errors within themselves (not only between them), then you need an additional step to remove them, which loses not only order, but also deception in the original arrays:
std::sort(first_array, first_array + N); MyClass *first_end = std::unique(first_array, first_array + N); std::sort(second_array, second_array + M); MyClass *second_end = std::unique(second_array, second_array + M); std::set_union( first_array, first_end, second_array, second_end, target_array );
Alternatively, you can write a modified version of set_union , which combines and dedupes in a single pass.
[Edit: sorry, in writing, I missed that the result ended up being returned in first_array , and not in a separate target_array . set_union does not work with the output as one of the inputs, so it also requires additional memory for the target array, which can then be copied back to the original array, assuming, of course, that the source is large enough.]
If you want to keep the order of the original arrays, then you can create a container and check how you go:
container<MyClass> items(first_array, first_array + N); MyClass *dst = first_array + N; for (MyClass *it = second_array; it != second_array + M; ++it) { if (items.count(*it) == 0) { items.insert(*it); *dst++ = *it; } }
If arrays can contain duplicates within themselves, then start with items empty and dst = first_array , then go to both input arrays.
container can be std::set (in this case, O(N log N + M log(N + M)) , which is actually O(N log N + M log M) , and you still need an order comparator ), or std::unordered_set in C ++ 11 (in this case, the expected time is O(N + M) with pathological worst cases, and you need to specialize std::hash or write a hash function otherwise, and provide an equal function instead order comparator). Prior to C ++ 11, other hash containers are available only not in the standard.
If you do not mind additional memory and do not mind losing the original order:
container<MyClass> items(first_array, first_array + N); items.insert(second_array, second_array + M); std::copy(items.begin(), items.end(), first_array);
If you do not want to use (large) extra memory and have space in the original array for M additional elements, and not just have a place for the result:
std::copy(second_array, second_array + M, first_array + N); std::sort(first_array, first_array + N + M); MyClass *dst = std::unique(first_array, first_array + N + M);