Remove the common entities from two vector?

问题:

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

回答1:

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.

回答2:

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

回答3:

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

回答4:

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.

回答5:

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.

回答6:

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.