### CodingKnight's blog

By CodingKnight, 9 days ago, ,

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

•
• -28
•