EXT C++ Library - range_set

The ext::range_set is a container template for ext::range elements with optimized storage algorithm.


The main difference between normal std::set of ext::range elements and ext::range_set is that ext::range_set automaticaly re-organizes the contained data. This means that it actually inserts a new range only when neccessary, otherwise it extends or joins one or more existing ranges. Thus the size of ext::range_set (number of contained ext::ranges) can actually be lower after an insert operation.

Roughly the same apply when removing (using erase member function) elements from the ext::range_set. One or more contained ext::ranges can be removed and none, one or two of them can be changed to carry out the operation.


template <typename T,
          typename T_comp = std::less <range <T> >,
          typename T_alloc = std::allocator <ext::range <T> > > {
class ext::range_set {
        typedef ::std::set <ext::range <T>, T_comp, T_alloc> underlying_type;

        typedef typename underlying_type::value_type        value_type;
        typedef typename underlying_type::key_type          key_type;
        typedef typename underlying_type::key_compare       key_compare;
        typedef typename underlying_type::value_compare     value_compare;
        typedef typename underlying_type::pointer           pointer;
        typedef typename underlying_type::reference         reference;
        typedef typename underlying_type::const_reference   const_reference;
        typedef typename underlying_type::size_type         size_type;
        typedef typename underlying_type::difference_type   difference_type;
        typedef typename underlying_type::iterator          iterator;
        typedef typename underlying_type::const_iterator    const_iterator;
        typedef typename underlying_type::reverse_iterator  reverse_iterator;
        typedef typename underlying_type::const_reverse_iterator const_reverse_iterator;

        std::pair <iterator, bool> insert (const value_type &);
        iterator                   insert (iterator, const value_type &);

        template <class InputIterator>
        void insert (InputIterator, InputIterator);

        void erase (iterator);
        void erase (iterator, iterator);
        void erase (const key_type &);

        bool count (const T &) const;
        bool count (const key_type &) const;

        void swap (range_set &);

        using underlying_type::begin;
        using underlying_type::end;
        using underlying_type::rbegin;
        using underlying_type::rend;
        using underlying_type::size;
        using underlying_type::max_size;
        using underlying_type::empty;
        using underlying_type::key_comp;
        using underlying_type::value_comp;
        using underlying_type::clear;
        using underlying_type::find;
        using underlying_type::lower_bound;
        using underlying_type::upper_bound;

Note that all other standard (C++03) member functions of std::set are exposed and all member typedefs are brought visible from the underlying set. See your favorite STL book for details.


#include <ext/c++>

bool populate (const ext::range_set <int> & d) {
    int v1 = 0;
    int v2 = 0;

    std::printf ("Enter a value, range, or none to quit: ");
    switch (std::scanf ("%i .. %i", &v1, &v2)) {
        case 1:
            d.insert (ext::range <int> (v1, v1));
            return true;
        case 2:
            d.insert (ext::range <int> (v1, v2));
            return true;
        case 0:
            return false;

int main () {
    ext::range_set <int> data;

    while (populate (data))

    for each (ext::range_set <int> ::const_iterator, ri, data)
        for (int v = ri->first; v <= ri->last; ++v)
            /* work (v); */;

    return 0;

See EXT C++ Library testsuite for more detailed example.


The private typedef underlying_type is exposed here to allow better understanding of how is the ext::range_set implemented and which member functions are directly forwarded to their std::set counterparts.