set,bitset 的一个应用实例——数据结构和比较算法

set <bitset<180>, CompBitSet>  a;

// --------------------------------------
//  对两个 bitset 进行数值比较
template < size_t _N >
bool   operator   <  ( const  bitset < _N >   &  a,  const  bitset < _N >   &  b){
    size_t i;
     for (i  =   0 ; i  <=  (_N  -   1 )  /   32  ;i ++ ){
         if (a._W(i)  !=  b._W(i)) return  (a._W(i)  <  b._W(i));
    }
     return   false ;
}

// --------------------------------------
//  用于 set 的比较类
struct  CompBitSet{
     bool   operator  ()( const  itemset  & a,  const  itemset  & b) const {
        return (a[0] ? ~a : a) < (b[0] ? ~b : b);
    }
};

/*
 * vector<vector<int>> 压缩
  */
#pragma  warning(disable:4786)
#include  < time.h >

#include  < iostream >
#include  < bitset >
#include  < set >

#define  BITLEN 180

using  std::bitset;
using  std:: set ;
using  std::cout;
using  std::endl;

// --------------------------------------
struct  CompBitSet;

typedef bitset < BITLEN >  itemset;
typedef  set < itemset,CompBitSet >  dataset;

// --------------------------------------
template < size_t _N >
bool   operator   <  ( const  bitset < _N >   &  a,  const  bitset < _N >   &  b){
    size_t i;
     for (i  =   0 ; i  <=  (_N  -   1 )  /   32  ;i ++ ){
         if (a._W(i)  !=  b._W(i)) return  (a._W(i)  <  b._W(i));
    }
     return   false ;
}

// --------------------------------------
struct  CompBitSet{
     bool   operator  ()( const  itemset  & a,  const  itemset  & b) const {
        return (a[0] ? ~a : a) < (b[0] ? ~b : b);
    }
};

// --------------------------------------
void  listset( const  dataset  & data){
    dataset::const_iterator citer;
     for (citer  =  data.begin();citer  !=  data.end();citer ++ ){
         for ( int  i  =   0 ;i  <  BITLEN;i ++ ){
             if (( * citer)[i])cout << i << ' , ' ;
        }
        cout << endl;
    }
}

// --------------------------------------
void  main( void ){
    dataset data;
    itemset item;

    srand((unsigned  int )time(NULL));

    cout << " Start init data " << endl;
    system( " pause " );
     int  i,j;
    time_t begtime,usetime;
    begtime =  time(NULL);
     for (i  =   0 ;i  <   1000000 ;i ++ ){
        item.reset();
         for (j  =   0 ;j  <  BITLEN;j ++ )
            item. set (rand()  %  BITLEN);
        data.insert(item);
        data.insert(item);
        data.insert( ~ item);
         if ( 0   ==  i  %   123 )cout << ' ' << i;
    }
    cout << " Times :  " << i << endl << " End of Init " << endl;
    cout << " Total items :  " << data.size() << endl;
    usetime  =  time(NULL)  -  begtime;
    cout << " Use time :  " << usetime  /   60 << " : " << usetime  %   60 << " ( " << usetime << " s) " << endl;

    item.reset();
    data.insert(item);
    data.insert( ~ item);
    cout << " Insert empty set and full set " << endl;
    cout << " Total items :  " << data.size() << endl;

    data.erase(item);
    cout << " Remove empty set " << endl;
    cout << " Total items :  " << data.size() << endl;

//     listset(data);
}