Is there any library supporting set operation.

Discussion in 'C++' started by kuangye, Oct 11, 2008.

  1. kuangye

    kuangye Guest

    Hi, all.

    Is there any library supporting set operation such as union,
    intersection, difference on sets of integer numbers.
    kuangye, Oct 11, 2008
    #1
    1. Advertising

  2. kuangye

    Kai-Uwe Bux Guest

    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
    Kai-Uwe Bux, Oct 11, 2008
    #2
    1. Advertising

  3. kuangye

    James Kanze Guest

    On Oct 11, 7:23 am, kuangye <> 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:
    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
    James Kanze, Oct 11, 2008
    #3
  4. 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
    Erik Wikström, Oct 11, 2008
    #4
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Eilsa
    Replies:
    0
    Views:
    554
    Eilsa
    Nov 23, 2004
  2. Yuraukar
    Replies:
    0
    Views:
    336
    Yuraukar
    Dec 18, 2003
  3. F. GEIGER
    Replies:
    3
    Views:
    281
    Ziga Seilnacht
    Jan 22, 2006
  4. Lighter
    Replies:
    1
    Views:
    339
    Alan Johnson
    Aug 18, 2006
  5. Eilsa
    Replies:
    0
    Views:
    123
    Eilsa
    Nov 23, 2004
Loading...

Share This Page