Remove the common entities from two vector?

Question

say I have vector<class1a>,vector<class1b> how to remove the common entities from both of them I have defined ==operator for the class1 objects class1a,class1b

Answer 1

Sort the 2 vectors, then walk through them in parallel doing a common merge operation. That will tell you which items are identical.

Answer 2

The naive way is to do an n^2 iteration comparing each element in the first vector against each element in the second array and adding any matches to a third vector. When you finish the n^2 iteration, you walk the third vector and remove those objects from the first two.

Not the best solution, but depending on how big you expect the vectors to be it may be among the simplest.

Answer 3

For each pair of items in class1a and class1b, add them to an output set, if they are not equal. Else, add only one such instance. Repeat for the minimum of the length of the arrays. If one is longer, you will be left with some more -- try to add all these to the set.

Answer 4

Start adding the value of vector in Set. Override the equals method of class1 and class2 to decide how you want the object to be equal. If you dont override equals by default == will be used to compare and since the objects are of different class == will always return false. So you need to override equals method.

Answer 5

In the stl header algorithm is a function called "set_symmetric_difference" that will put all of the elements of one, but not both source ranges into a single destination range.

Bear in mind that both of the ranges must start sorted.

msdn documentation

Answer 6

The stl algorithms provide several functions to perform set operations, notably calculating the set symmetric difference, which is what you need.

Here's an example of use:

#include <algorithm>
#include <vector>

int main(int argc, char **argv) {

    std::vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    v1.push_back(6);

    std::vector<int> v2;
    v2.push_back(2);
    v2.push_back(4);
    v2.push_back(6);
    v2.push_back(8);

    // Ranges must be sorted!
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    std::vector<int> res; // Will contain the symmetric difference
    std::set_symmetric_difference(v1.begin(), v1.end(), 
                                  v2.begin(), v2.end(), 
                                  std::back_inserter(res));

    // Copy result to the output
    std::copy(res.begin(), res.end(), std::ostream_iterator<int>(cout, " "));
    // Prints "1 3 5"

    return 0;
}

std::set_symmetric_difference takes two range (i.e. two pairs of OutputIterators) and an InputIterator where it will put the result. It also returns an iterator to the end of the result range.

---

EDIT

I just read your comments on your question. If you want the two original vectors to be modified, you can use std::set_difference:

vector<int>::iterator endRange;
endRange = set_difference(v1.begin(), v1.end(), 
                          v2.begin(), v2.end(), 
                          v1.begin());
v1.erase(endRange, v1.end());

Here, we put the result of the set difference v1 - v2 into v1. However, we can't do the vice-versa since v1 is now modified. The solution is to calculate the intersection of v1 and v2, and then the difference with this intersection:

vector<int> inter;
set_intersection(v1.begin(), v1.end(),
                 v2.begin(), v2.end(),
                 back_inserter(inter));
// inter is "2 4 6"

v1.erase(set_difference(v1.begin(), v1.end(),
                        inter.begin(), inter.end(),
                        v1.begin())
         v1.end());
// v1 is "1 3 5"

v2.erase(set_difference(v2.begin(), v2.end(),
                        inter.begin(), inter.end(),
                        v2.begin())
         v2.end());
// v2 is "8"

I guess there are much more performant solutions, but this one is clear, and really convey your intents by using widely known stl algorithms.