algorithm to remove elements in the intersection of two sets

Question

I have a Visual Studio 2008 C++03 application where I have two standard containers. I would like to remove from one container all of the items that are present in the other container (the intersection of the sets).

something like this:

std::vector< int > items = /* 1, 2, 3, 4, 5, 6, 7 */;
std::set< int > items_to_remove = /* 2, 4, 5*/;

std::some_algorithm( items.begin, items.end(), items_to_remove.begin(), items_to_remove.end() );

assert( items == /* 1, 3, 6, 7 */ )

Is there an existing algorithm or pattern that will do this or do I need to roll my own?

Thanks

Is there a reason for the downvote? Is there some way I can improve how I phrased the question? Or is this just a drive-by de-repping? — PaulH, May 17 '12 at 17:44

K-ballo · Accepted Answer · 2012-05-15T15:11:02.903

6

Try with:

items.erase(
    std::remove_if(
        items.begin(), items.end()
      , std::bind1st(
            std::mem_fun( &std::set< int >::count )
          , items_to_remove
        )
    )
  , items.end()
);

std::remove(_if) doesn't actually remove anything, since it works with iterators and not containers. What it does is reorder the elements to be removed at the end of the range, and returns an iterator to the new end of the container. You then call erase to actually remove from the container all of the elements past the new end.

Update: If I recall correctly, binding to a member function of a component of the standard library is not standard C++, as implementations are allowed to add default parameters to the function. You'd be safer by creating your own function or function-object predicate that checks whether the element is contained in the set of items to remove.

edited May 15 '12 at 15:11

answered May 15 '12 at 14:59

K-ballo

80,396
20
159
169

Or in C++11, you could use a lambda: `[&](int i) { return items_to_remove.count(i); }` – Steve Jessop May 15 '12 at 15:12
@Steve Jessop: In **_C++11_** that is, but the OP is working with _C++03_ – K-ballo May 15 '12 at 15:13
5

that's why it's not an answer :-) – Steve Jessop May 15 '12 at 15:14

score 3 · Answer 2 · answered May 15 '12 at 15:14

3

Personally, I prefer to create small helpers for this (that I reuse heavily).

template <typename Container>
class InPredicate {
public:
    InPredicate(Container const& c): _c(c) {}

    template <typename U>
    bool operator()(U const& u) {
        return std::find(_c.begin(), _c.end(), u) != _c.end();
    }

private:
    Container const& _c;
};

// Typical builder for automatic type deduction
template <typename Container>
InPredicate<Container> in(Container const& c) {
    return InPredicate<Container>(c);
}

This also helps to have a true erase_if algorithm

template <typename Container, typename Predicate>
void erase_if(Container& c, Predicate p) {
    c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
}

And then:

erase_if(items, in(items_to_remove));

which is pretty readable :)

answered May 15 '12 at 15:14

Matthieu M.

287,565
48
449
722

And you probably want to partially specialize `InPredicate` for `set` (in this example) and `map` to be less slow. – Steve Jessop May 15 '12 at 15:18
@SteveJessop: probably, but that is an optimization :) – Matthieu M. May 15 '12 at 15:25
True. Come to think of it, you could overload `erase_if` to work on non-sequences too. – Steve Jessop May 15 '12 at 15:27

score 2 · Answer 3 · answered May 15 '12 at 15:56

One more solution:

There is standard provided algorithm set_difference which can be used for this. But it requires extra container to hold the result. I personally prefer to do it in-place.

std::vector< int > items;
//say items = [1,2,3,4,5,6,7,8,9]

std::set<int>items_to_remove;
//say items_to_remove = <2,4,5>

std::vector<int>result(items.size()); //as this algorithm uses output 
                           //iterator not inserter iterator for result.

std::vector<int>::iterator new_end = std::set_difference(items.begin(), 
 items.end(),items_to_remove.begin(),items_to_remove.end(),result.begin());

result.erase(new_end,result.end()); // to erase unwanted elements at the 
                                    // end.

You can use `back_insert_iterator` for the last argument to `set_difference()`. It'll automatically push back the elements to `result`. — jrok, May 15 '12 at 16:06

score 1 · Answer 4 · answered May 15 '12 at 14:59

1

You can use std::erase in combination with std::remove for this. There is a C++ idiom called the Erase - Remove idiom, which is going to help you accomplish this.

answered May 15 '12 at 14:59

Tony The Lion

61,704
67
242
415

score 1 · Answer 5 · edited May 23 '17 at 12:30

Assuming you have two sets, A and B, and you want to remove from B, the intersection, I, of (A,B) such that I = A^B, your final results will be: A (left intact)
B' = B-I

Full theory:
http://math.comsci.us/sets/difference.html

This is quite simple.

Create and populate A and B
Create a third intermediate vector, I
Copy the contents of B into I
For each element a_j of A, which contains j elements, search I for the element a_j; If the element is found in I, remove it

Finally, the code to remove an individual element can be found here:
How do I remove an item from a stl vector with a certain value?

And the code to search for an item is here:
How to find if an item is present in a std::vector?

Good luck!

score -1 · Answer 6 · answered May 24 '15 at 11:53

Here's a more "hands-on" in-place method that doesn't require fancy functions nor do the vectors need to be sorted:

#include <vector>

template <class TYPE>
void remove_intersection(std::vector<TYPE> &items, const std::vector<TYPE> &items_to_remove)
{
    for (int i = 0; i < (int)items_to_remove.size(); i++) {
        for (int j = 0; j < (int)items.size(); j++) {
            if (items_to_remove[i] == items[j]) {
                items.erase(items.begin() + j);
                j--;//Roll back the iterator to prevent skipping over
            }
        }
    }
}

If you know that the multiplicity in each set is 1 (not a multiset), then you can actually replace the j--; line with a break; for better performance.

algorithm to remove elements in the intersection of two sets

6 Answers6