CODEWITHSUNDEEP
c++algorithm
PaulH
PaulH

Reputation: 7863

algorithm to remove elements in the intersection of two sets

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

Upvotes: 7

Views: 5842

Answers (6)

MasterHD
MasterHD

Reputation: 2384

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.

Upvotes: -1

pravs
pravs

Reputation: 1081

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.

Upvotes: 2

Matthieu M.
Matthieu M.

Reputation: 299890

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 :)

Upvotes: 3

K-ballo
K-ballo

Reputation: 81349

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.

Upvotes: 6

Cloud
Cloud

Reputation: 19333

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.

  1. Create and populate A and B
  2. Create a third intermediate vector, I
  3. Copy the contents of B into I
  4. 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!

Upvotes: 1

Tony The Lion
Tony The Lion

Reputation: 63200

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.

Upvotes: 1

Related Questions