Is there any library supporting set operation.

K

kuangye

Hi, all.

Is there any library supporting set operation such as union,
intersection, difference on sets of integer numbers.
 
K

Kai-Uwe Bux

kuangye said:
Hi, all.

Is there any library supporting set operation such as union,
intersection, difference on sets of integer numbers.

Using operator abuse and std::set:

/*
A, B : sets
a, b : elements

union: A + B A + b A += B A += b
intersection: A * B A * b A *= B A *= b
difference: A - B A - b A -= B A -= b
symmetric difference: A ^ B A ^ b A ^= B A ^= b
*/

#include <set>
#include <algorithm>
#include <iterator>


// union:
// ======

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> operator+ ( std::set<T,Alloc,Compare> const & a,
std::set<T,Alloc,Compare> const & b ) {
std::set<T,Alloc,Compare> result;
std::set_union( a.begin(), a.end(),
b.begin(), b.end(),
std::inserter( result, result.begin() ) );
return( result );
}

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> operator+ ( std::set<T,Alloc,Compare> const & a,
T const & t ) {
std::set<T,Alloc,Compare> result ( a );
result.insert( t );
return( result );
}

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> & operator+= ( std::set<T,Alloc,Compare> & me, T
const & other ) {
me.insert( other );
return ( me );
}

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> & operator+= ( std::set<T,Alloc,Compare> & me,
std::set<T,Alloc,Compare> const & other ) {
std::copy( other.begin(), other.end(),
std::inserter( me, me.begin() ) );
return( me );
}


// intersection:
// =============

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> operator* ( std::set<T,Alloc,Compare> const & a,
std::set<T,Alloc,Compare> const & b ) {
std::set<T,Alloc,Compare> result;
std::set_intersection( a.begin(), a.end(),
b.begin(), b.end(),
std::inserter( result, result.begin() ) );
return( result );
}

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> operator* ( std::set<T,Alloc,Compare> const & a,
T const & t ) {
std::set<T,Alloc,Compare> result;
result.insert( t );
result = result * a;
return( result );
}


template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> & operator*= ( std::set<T,Alloc,Compare> & me, T
const & other ) {
me = me * other;
return ( me );
}

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> & operator*= ( std::set<T,Alloc,Compare> & me,
std::set<T,Alloc,Compare> const & other ) {
me = me * other;
return( me );
}


// difference:
// ===========

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> operator- ( std::set<T,Alloc,Compare> const & a,
std::set<T,Alloc,Compare> const & b ) {
std::set<T,Alloc,Compare> result;;
std::set_difference( a.begin(), a.end(),
b.begin(), b.end(),
std::inserter( result, result.begin() ) );
return( result );
}

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> operator- ( std::set<T,Alloc,Compare> const & a,
T const & t ) {
std::set<T,Alloc,Compare> result ( a );
result.erase( t );
return( result );
}

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> & operator-= ( std::set<T,Alloc,Compare> & me,
std::set<T,Alloc,Compare> const & other ) {
for ( typename std::set<T,Alloc,Compare>::const_iterator iter =
other.begin();
iter != other.end(); ++ iter ) {
me.erase( *iter );
}
return( me );
}

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> & operator-= ( std::set<T,Alloc,Compare> & me,
T const & t ) {
me.erase( t );
return ( me );
}


// symmetric difference:
// =====================

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> operator^ ( std::set<T,Alloc,Compare> const & a,
std::set<T,Alloc,Compare> const & b ) {
std::set<T,Alloc,Compare> result;
std::set_symmetric_difference( a.begin(), a.end(),
b.begin(), b.end(),
std::inserter( result, result.begin() ) );
return( result );
}

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> operator^ ( std::set<T,Alloc,Compare> const & a,
T const & t ) {
return( a ^ ( std::set<T,Alloc,Compare>() + t ) );
}

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> & operator^= ( std::set<T,Alloc,Compare> & me,
std::set<T,Alloc,Compare> const & other ) {
me = me ^ other;
return( me );
}

template < typename T, typename Alloc, typename Compare >
std::set<T,Alloc,Compare> & operator^= ( std::set<T,Alloc,Compare> & me,
T const & t ) {
me = me ^ t;
return( me );
}


Best

Kai-Uwe Bux
 
J

James Kanze

Is there any library supporting set operation such as union,
intersection, difference on sets of integer numbers.

There's a BitVector class at my site
(http://kanze.james.neuf.fr/code-en.html), which handles
integer values in a range of [0...N] (where N is a template
argument). It supports the operators you're looking for.

Of course, if you're sets typically contain only one or two
values, over the range [INT_MIN...INT_MAX], the implementation
won't be very space efficient, but it works effectively for
small sets of integers.

There's also a DynBitVector, which automatically grows, so
effectively does handle [0...INT_MAX]. Except that it is still
only space effective if the sets are reasonably dense.

Both are in the Basic component.
 
E

Erik Wikström

Hi, all.

Is there any library supporting set operation such as union,
intersection, difference on sets of integer numbers.

std::set_union(), std::set_intersection(), std::set_difference(), and
std::set_symmetric_difference()

Works on sorted containers.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,906
Latest member
SkinfixSkintag

Latest Threads

Top