fork download
copy 
  1. // int_set.h 
  2. #ifndef __int_set__
  3. #define __int_set__
  4. #include <bitset>
  5.  
  6. template < int From, int To >
  7. class int_set
  8. {
  9.     static constexpr int N = To - From + 1; 
  10.  
  11.     typedef std::bitset< N > bits_t;
  12.  
  13.     bits_t exists;
  14.  
  15. public:
  16.  
  17.     int_set() {}
  18.  
  19.     int_set operator = ( const int_set &x )
  20.     {
  21.         exists = x.exists; return *this;
  22.     }
  23.  
  24.     int_set ( const int_set &x )
  25.     {
  26.         *this = x;
  27.     }
  28.  
  29.     class iterator
  30.     {
  31.         bits_t *base; int index;
  32.  
  33.         friend class int_set;
  34.  
  35.         iterator next()
  36.         {
  37.             while( index < To && ! (*base)[ index - From ] )
  38.                 index++;
  39.  
  40.             return *this;
  41.         }
  42.  
  43.     public:
  44.  
  45.         iterator( bits_t *b = nullptr, const int i = 0 ) : base( b ), index( i ) {}
  46.  
  47.         iterator( const iterator &it ) : base( it.base ), index( it.index ) {}
  48.  
  49.         iterator begin( bits_t &x )
  50.         {
  51.             base = &x, index = From; return next();
  52.         }
  53.  
  54.         iterator end( bits_t &x )
  55.         {
  56.             base = &x, index = To; return *this;
  57.         }
  58.  
  59.         iterator operator ++ () // prefix increment
  60.         {
  61.             index++; return next();
  62.         }
  63.  
  64.         iterator operator ++ ( const int y ) // postfix increment
  65.         {
  66.             iterator it = *this; ++(*this); return it;
  67.         }
  68.  
  69.         int operator() () const
  70.         {
  71.             return index;
  72.         }
  73.  
  74.         int operator* () const
  75.         {
  76.             return index;	
  77.         }
  78.  
  79.         bool operator != ( const iterator &x )
  80.         {
  81.             return base != x.base || index != x.index;
  82.         }
  83.  
  84.         bool operator == ( const iterator &x )
  85.         {
  86.             return base == x.base && index == x.index;
  87.         }
  88.     };
  89.  
  90.     class reverse_iterator
  91.     {
  92.         bits_t *base; int index;
  93.  
  94.         friend class int_set;
  95.  
  96.         reverse_iterator next()
  97.         {
  98.             while( index >= From && ! (*base)[ index - From ] )
  99.                 index--;
  100.  
  101.             return *this;
  102.         }
  103.  
  104.     public:
  105.  
  106.         reverse_iterator( bits_t *b = nullptr, const int i = 0 ) : base( b ), index( i ) {}
  107.  
  108.         reverse_iterator( const reverse_iterator &it ) : base( it.base ), index( it.index ) {}
  109.  
  110.         reverse_iterator begin( bits_t &x )
  111.         {
  112.             base = &x, index = To - 1; return next();
  113.         }
  114.  
  115.         reverse_iterator end( bits_t &x )
  116.         {
  117.             base = &x, index = From - 1; return *this;
  118.         }
  119.  
  120.         reverse_iterator operator ++ () // prefix increment
  121.         {
  122.             index--; return next();
  123.         }
  124.  
  125.         reverse_iterator operator ++ ( const int y ) // postfix increment
  126.         {
  127.             reverse_iterator it = *this; ++(*this); return it;
  128.         }
  129.  
  130.         int operator() () const
  131.         {
  132.             return index;
  133.         }
  134.  
  135.         int operator* () const
  136.         {
  137.         	return index;
  138.         }
  139.  
  140.         bool operator != ( const reverse_iterator &x )
  141.         {
  142.             return base != x.base || index != x.index;
  143.         }
  144.  
  145.         bool operator == ( const reverse_iterator &x )
  146.         {
  147.             return base == x.base && index == x.index;
  148.         }
  149.     };
  150.  
  151.  
  152.     iterator begin()
  153.     {
  154.         iterator it; return it.begin( exists );
  155.     }
  156.  
  157.     iterator end()
  158.     {
  159.         iterator it; return it.end( exists );
  160.     }
  161.  
  162.     reverse_iterator rbegin()
  163.     {
  164.         reverse_iterator it; return it.begin( exists );
  165.     }
  166.  
  167.     reverse_iterator rend()
  168.     {
  169.         reverse_iterator it; return it.end( exists );
  170.     }
  171.  
  172.     bool operator [] ( const int x ) const
  173.     {
  174.         return exists[ x - From ];
  175.     }
  176.  
  177.     void insert( const int x )
  178.     {
  179.         int i = x - From;
  180.  
  181.         if ( !exists[ i ] )
  182.             exists.set( i );
  183.     }
  184.  
  185.     void insert( iterator first, iterator last )
  186.     {
  187.         int i;
  188.  
  189.         for( iterator it( first ); it != last; it++ )
  190.             if ( !exists[ i = it.index - From ] )
  191.                 exists.set( i );
  192.     }
  193.  
  194.     void erase( const int x )
  195.     {
  196.         int i = x - From;
  197.  
  198.         if ( exists[ i ] )
  199.             exists.reset( i );
  200.     }
  201.  
  202.     void erase( iterator first, iterator last )
  203.     {
  204.         int i;
  205.  
  206.         for( iterator it( first ); it != last; it++ )
  207.             if ( exists[ i = it.index - From ] )
  208.                 exists.reset( i );
  209.     }
  210.  
  211.     void swap( int_set &x )
  212.     {
  213.         int_set y = *this; *this = x, x = y;
  214.     }
  215.  
  216.     void clear()
  217.     {
  218.         exists.clear();
  219.     }
  220.  
  221.     bool empty() const
  222.     {
  223.         return exists.empty();
  224.     }
  225.  
  226.     size_t size() const
  227.     {
  228.         return exists.count();
  229.     }
  230.  
  231.     size_t max_size() const
  232.     {
  233.         return N;
  234.     }
  235.  
  236.     bool none() const
  237.     {
  238.         return empty();
  239.     }
  240.  
  241.     bool any() const
  242.     {
  243.         return size() > 0;
  244.     }
  245.  
  246.     bool all() const
  247.     {
  248.         return size() == N;
  249.     }
  250.  
  251.     int_set operator &= ( int_set &x )
  252.     {
  253.         exists &= x.exists; return  *this;
  254.     }
  255.  
  256.     int_set operator |= ( int_set &x )
  257.     {
  258.         exists |= x.exists; return *this;
  259.     }
  260.  
  261.     int_set operator ^= ( int_set &x )
  262.     {
  263.         exists ^= x.exists; return *this;
  264.     }
  265.  
  266.     int_set operator -= ( int_set &x )
  267.     {
  268.         exists &= ~x.exists; return *this;
  269.     }
  270.  
  271.     int_set operator ~() const
  272.     {
  273.         int_set x( *this ); x.exists = ~x.exists; return x;
  274.     }
  275.  
  276.     void set_intersection( int_set &x )
  277.     {
  278.         *this &= x;
  279.     }
  280.  
  281.     void set_union( int_set &x )
  282.     {
  283.         *this |= x;
  284.     }
  285.  
  286.     void set_difference( int_set &x )
  287.     {
  288.         *this -= x;
  289.     }
  290.  
  291.     void set_symmetric_difference( int_set &x )
  292.     {
  293.         *this ^= x;
  294.     }
  295.  
  296.     bool operator == ( const int_set &x ) const
  297.     {
  298.         return exists == x.exists;
  299.     }
  300.  
  301.     bool operator != ( const int_set &x ) const
  302.     {
  303.         return exists != x.exists;
  304.     }
  305.  
  306.     friend int_set operator & ( const int_set &x, const int_set &y )
  307.     {
  308.         int_set z( x ); z &= y; return z;
  309.     }
  310.  
  311.     friend int_set operator | ( const int_set &x, const int_set &y )
  312.     {
  313.         int_set z( x ); z |= y; return z;
  314.     }
  315.  
  316.     friend int_set operator ^ ( const int_set &x, const int_set &y )
  317.     {
  318.         int_set z( x ); z ^= y; return z;
  319.     }
  320.  
  321.     friend int_set operator - ( const int_set &x, const int_set &y )
  322.     {
  323.         int_set z( x ); z -= y; return z;
  324.     }
  325. };
  326.  
  327. #endif // __int_set__
  328. // int_set.h <EOF>
  329.  
  330. // The following is an example for using the int_set< int From, int To > class
  331.  
  332. #include <bits/stdc++.h>
  333. // #include "int_set.h"
  334.  
  335. using namespace std;
  336.  
  337. typedef int_set< 1, 6 > my_set_t;
  338.  
  339. int main()
  340. {
  341.     ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
  342.  
  343.     my_set_t x;
  344.  
  345.     x.insert( 2 ), x.insert( 5 );
  346.  
  347.     for( auto y: x )
  348.       cout << y << " ";
  349. }
  350.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 5
https://ideone.com/r9mh55
int_set class template and sample program
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!