intset

There is std::vector specialization known as bit_vector. In the same way there may exist set of integers by using pages of bits accessed through std::map.

#include <map>
#include <bitset>
#include <iostream>

#include <cstdlib>
#include <cassert>

template<typename IntType = long>
class intset {
public:
    typedef IntType key_type;
    typedef intset<key_type> self_type;
private:
    enum { group_bits = sizeof(long)*8 };
    typedef std::map<key_type, std::bitset<group_bits> > map_type;
    map_type groups;

public:
    bool contains(const key_type k) const {
        const size_t bit = k % group_bits;
        const size_t n = k / group_bits;
        const typename map_type::const_iterator it = groups.find(n);
        if (it == groups.end()) return false;
        else return it->second.test(bit);
    }

    self_type &add(const key_type k) {
        const size_t bit = k % group_bits;
        const size_t n = k / group_bits;
        groups[n].set(bit);
        return (*this);
    }

    self_type &remove(const key_type k) {
        const size_t bit = k % group_bits;
        const size_t n = k / group_bits;
        const typename map_type::iterator it = groups.find(n);
        if (it != groups.end()) {
            it->second.reset(bit);
            if (it->second.none()) {
                groups.erase(it);
            }
        }
        return (*this);
    }

    class iterator {
    private:
        const map_type &m;
        typedef typename map_type::const_iterator map_iterator;
        map_iterator i;
        size_t n;

        iterator(const map_type &ref, const map_iterator &iter, size_t bit) : m(ref), i(iter), n(bit) {}
        iterator(const map_type &ref) : m(ref), i(m.end()) {}

    public:

        const key_type operator*() const {
            assert( i->second.test(n) );
            return (i->first * group_bits + n);
        }

        iterator &operator++() {
            while(1) {
                if ( ++n >= group_bits ) {
                    n = 0;
                    ++i;
                    if (i == m.end()) return (*this);
                }
                if (i->second.test(n)) return (*this);
            }
            return (*this);
        }

        bool operator==(const iterator &iter) {
            if (i == m.end()) return (iter.i == m.end());
            return ((i == iter.i) && (n == iter.n));
        }
        bool operator!=(const iterator &iter) { return !(*this == iter); }

        friend class intset<key_type>;
    };

    iterator begin() const {
        iterator it(groups, groups.begin(), 0);
        if (! it.i->second.test(0)) ++it;
        return it;
    }
    iterator end() const { return iterator(groups); }
};


int main() {

    intset<long> s;
    s.add(32).add(33);
    s.add(10000);

    for(intset<long>::iterator i = s.begin(); i != s.end(); ++i) {
        std::cout << *i << std::endl;
    }

    return 0;
}