CodingKnight's blog

By CodingKnight, 9 days ago, In English,

The following is a C++ class template int_set that uses bitset STL to compute operations on sets of integers using bitset STL bitwise operators. int_set<From,To> is a class of objects that represent subsets of universal domain U = [From,To]. Each object stores the membership function of the corresponding subset using a private bitset<N> member exists, where N = To - From + 1, and can be updated using set insertion/deletion operations.

The main advantage of the int_set is that the set insertion/deletion operations as well as the fundamental set union, intersection, complement, difference, and symmetric difference operations are implemented using the bitset STL bitwise operators, unlike the corresponding set STL operations that require adding/deleting elements to/from the binary tree representation of the set.

#ifndef __int_set__
#define __int_set__
#include <bitset>

template < int From, int To >
class int_set
{
    static constexpr int N = To - From + 1; typedef std::bitset< N > bits_t;

    bits_t exists;

public:

    int_set() {}

    int_set operator = ( const int_set &x )
    {
        exists = x.exists; return *this;
    }

    int_set ( const int_set &x )
    {
        *this = x;
    }

    class iterator
    {
        bits_t *base; int index;

        friend class int_set;

        iterator next()
        {
            while( index < To && ! (*base)[ index - From ] )
                index++;

            return *this;
        }

    public:

        iterator( bits_t *b = nullptr, const int i = 0 ) : base( b ), index( i ) {}

        iterator( const iterator &it ) : base( it.base ), index( it.index ) {}

        iterator begin( bits_t &x )
        {
            base = &x, index = From; return next();
        }

        iterator end( bits_t &x )
        {
            base = &x, index = To; return *this;
        }

        iterator operator ++ () // prefix increment
        {
            index++; return next();
        }

        iterator operator ++ ( const int y ) // postfix increment
        {
            iterator it = *this; ++(*this); return it;
        }

        int operator() () const
        {
            return index;
        }

        bool operator != ( const iterator &x )
        {
            return base != x.base || index != x.index;
        }

        bool operator == ( const iterator &x )
        {
            return base == x.base && index == x.index;
        }
    };

    class reverse_iterator
    {
        bits_t *base; int index;

        friend class int_set;

        reverse_iterator next()
        {
            while( index >= From && ! (*base)[ index - From ] )
                index--;

            return *this;
        }

    public:

        reverse_iterator( bits_t *b = nullptr, const int i = 0 ) : base( b ), index( i ) {}

        reverse_iterator( const reverse_iterator &it ) : base( it.base ), index( it.index ) {}

        reverse_iterator begin( bits_t &x )
        {
            base = &x, index = To - 1; return next();
        }

        reverse_iterator end( bits_t &x )
        {
            base = &x, index = From - 1; return *this;
        }

        reverse_iterator operator ++ () // prefix increment
        {
            index--; return next();
        }

        reverse_iterator operator ++ ( const int y ) // postfix increment
        {
            reverse_iterator it = *this; ++(*this); return it;
        }

        int operator() () const
        {
            return index;
        }

        bool operator != ( const reverse_iterator &x )
        {
            return base != x.base || index != x.index;
        }

        bool operator == ( const reverse_iterator &x )
        {
            return base == x.base && index == x.index;
        }
    };


    iterator begin()
    {
        iterator it; return it.begin( exists );
    }

    iterator end()
    {
        iterator it; return it.end( exists );
    }

    reverse_iterator rbegin()
    {
        reverse_iterator it; return it.begin( exists );
    }

    reverse_iterator rend()
    {
        reverse_iterator it; return it.end( exists );
    }

    bool operator [] ( const int x ) const
    {
        return exists[ x - From ];
    }

    void insert( const int x )
    {
        int i = x - From;

        if ( !exists[ i ] )
            exists.set( i );
    }

    void insert( iterator first, iterator last )
    {
        int i;

        for( iterator it( first ); it != last; it++ )
            if ( !exists[ i = it.index - From ] )
                exists.set( i );
    }

    void erase( const int x )
    {
        int i = x - From;

        if ( exists[ i ] )
            exists.reset( i );
    }

    void erase( iterator first, iterator last )
    {
        int i;

        for( iterator it( first ); it != last; it++ )
            if ( exists[ i = it.index - From ] )
                exists.reset( i );
    }

    void swap( int_set &x )
    {
        int_set y = *this; *this = x, x = y;
    }

    void clear()
    {
        exists.clear();
    }

    bool empty() const
    {
        return exists.empty();
    }

    size_t size() const
    {
        return exists.count();
    }

    size_t max_size() const
    {
        return N;
    }

    bool none() const
    {
        return empty();
    }

    bool any() const
    {
        return size() > 0;
    }

    bool all() const
    {
        return size() == N;
    }

    int_set operator &= ( int_set &x )
    {
        exists &= x.exists; return  *this;
    }

    int_set operator |= ( int_set &x )
    {
        exists |= x.exists; return *this;
    }

    int_set operator ^= ( int_set &x )
    {
        exists ^= x.exists; return *this;
    }

    int_set operator -= ( int_set &x )
    {
        exists &= ~x.exists; return *this;
    }

    int_set operator ~() const
    {
        int_set x( *this ); x.exists = ~x.exists; return x;
    }

    void set_intersection( int_set &x )
    {
        *this &= x;
    }

    void set_union( int_set &x )
    {
        *this |= x;
    }

    void set_difference( int_set &x )
    {
        *this -= x;
    }

    void set_symmetric_difference( int_set &x )
    {
        *this ^= x;
    }

    bool operator == ( const int_set &x ) const
    {
        return exists == x.exists;
    }

    bool operator != ( const int_set &x ) const
    {
        return exists != x.exists;
    }

    friend int_set operator & ( const int_set &x, const int_set &y )
    {
        int_set z( x ); z &= y; return z;
    }

    friend int_set operator | ( const int_set &x, const int_set &y )
    {
        int_set z( x ); z |= y; return z;
    }

    friend int_set operator ^ ( const int_set &x, const int_set &y )
    {
        int_set z( x ); z ^= y; return z;
    }

    friend int_set operator - ( const int_set &x, const int_set &y )
    {
        int_set z( x ); z -= y; return z;
    }
};

#endif // __int_set__

The following is an example for using the int_set class

#include <cstdio>
#include "int_set.h"

typedef int_set< 1, 6 > my_set_t;

int main()
{
    my_set_t x;

    x.insert( 2 ), x.insert( 5 );

    for( my_set_t::iterator it = x.begin(), ie = x.end(); it != ie; it++ )
        std::printf( "%i ", it() );
}
 
 
 
 
  • Vote: I like it  
  • -28
  • Vote: I do not like it