Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Is there any library supporting set operation.

Reply
Thread Tools

Is there any library supporting set operation.

 
 
kuangye
Guest
Posts: n/a
 
      10-11-2008
Hi, all.

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




 
Reply With Quote
 
 
 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      10-11-2008
kuangye wrote:

> 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
 
Reply With Quote
 
 
 
 
James Kanze
Guest
Posts: n/a
 
      10-11-2008
On Oct 11, 7:23*am, kuangye <(E-Mail Removed)> wrote:

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

--
James Kanze (GABI Software) email:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
 
Reply With Quote
 
Erik Wikström
Guest
Posts: n/a
 
      10-11-2008
On 2008-10-11 07:23, kuangye wrote:
> 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.

--
Erik Wikström
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
difflib-like library supporting moved blocks detection? Vlastimil Brom Python 2 07-15-2011 09:49 PM
How to set docstrings for extensions supporting PyNumberMethods? Nick Alexander Python 2 03-05-2007 12:22 AM
501 PIX "deny any any" "allow any any" Any Anybody? Networking Student Cisco 4 11-16-2006 10:40 PM
Is there a way to write a memory leak detector supporting new(nothrow)? Lighter C++ 1 08-18-2006 06:11 AM
Firewall supporting MIDCOM or any API for management Josip Gracin Cisco 0 10-06-2004 08:12 AM



Advertisments