Geek asks and answers

Algorithm for removing elements at 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 the elements that are present in another container (intersection of sets).

something like that:

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 template that will do this, or do I need to roll my own?

thank

+5
source share
6 answers

Try:

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) , , . , , , . erase, .

: , - ++, . , -, , .

+6

( ).

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);
}

erase_if

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

:

erase_if(items, in(items_to_remove));

:)

+3

:

set_difference, . . .

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.
+2

std::erase std::remove . ++, Erase - Remove idiom, .

+1

, , A B, B, , I, (A,B), , I = A^B, : A ( )
B' = B-I

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

.

  • A B
  • , I
  • B I
  • a_j of A, j, I a_j; I,

, :
stl- ?

:
, std::vector?

!

+1

"" , :

#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 multiset ), you can actually replace j--;line c break;for better performance.

0
source

More articles:


All Articles