Extract element from 2 vectors?

Question

I have 2 vector of with one has vec1{e1,e2,e3,e4} and the other one with vec2 {e2,e4,e5,e7}

How to effectively get three vector from above vectors such that 1.has elements that is available only in vec1 similarly 2 has only vec2 elements and 3.with common elements

Answer 1

std::set_intersection should do the trick, if both vectors are sorted: http://msdn.microsoft.com/en-us/library/zfd331yx.aspx

std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(vec3));

A custom predicate can be used for the comparison too:

std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(vec3), my_equal_functor());

If they are not sorted, you may of course sort them first, or alternatively, you can iterate through vec1, and for each element, use std::find to see if it exists in vec2.

Answer 2

If the element count is low, you can use the naive approach which is easy to implement and has O(n²) running time.

If you have a large number of elements, you can build a hash table from one of them and look up other vector's elements in it. Alternatively, you could sort one of them and binary search through it.

Answer 3

The problem you describe is vector intersection. This depends on the size of the input vectors.

If the sizes of both vectors are close to each other a merge (like in merge-sort) is best. If one vector is much smaller than the other do the following: For each element of the smaller vector search for that element in the larger vector using binary search.

This is a common problem in information retrieval, where you have to intersect inverted indices. There are some research papers on this.

Answer 4

What you're asking for is that vec3 be the intersection of the other two. Jalf demonstrates how to populate vec3 using the std::set_intersection function from the <algorithm> header. But remember that for the set functions to work, the vectors must be sorted.

Then you want vec1 and vec2 to be the difference between themselves and vec3. In set notation:

vec1 := vec1 \ vec3;
vec2 := vec2 \ vec3;

You can use the std::set_difference function for that, but you can't use it to modify the vectors in-place. You'd have to compute another vector to hold the difference:

std::vector<foo> temp;
std::set_difference(vec1.begin(), vec1.end(),
                    vec3.begin(), vec3.end(),
                    std::back_inserter(temp));
vec1 = temp;
temp.clear();
std::set_difference(vec2.begin(), vec2.end(),
                    vec3.begin(), vec3.end(),
                    std::back_inserter(temp));
vec2 = temp;