EXT C++ Library - range_set

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

---

Details:

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.

Interface:

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

    public:
        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;

    public:
        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 &);

    public:
        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;
};


• typename T
  ext::range_set::value_type
  The type of values that represent the boundaries of each ext::range element.
• typename T_comp
  ext::range_set::key_compare
  The comparison function for ext::range <T> objects. Defaults to std::less. This calls by default the operator <. This template parameter is forwarded to underlying std::set.
• typename T_alloc
  The allocator for ext::range <T> objects. Defaults to std::allocator. This template parameter is forwarded to underlying std::set.
• ext::range_set::insert
  The name insert is overloaded by two functions and one function template that resemble those of std::set. After completion of an insert operation, the ext::range_set is guaranteed to contain all passed ext::ranges, either as copies or as part of different, broader, ext::range.
• ext::range_set::erase
  The erase member function is overloaded for an iterator, range of iterators and a ext::range parameter. After completion, the ext::range_set is guaranteed not to contain any arbitrary value that any of the provided ext::ranges contain.
• ext::range_set::count
  Returns true if there is a range in the set that contain the parameter (a value or a range). A value of false is returned otherwise.
• ext::range_set::swap
  The swap function swaps the contents of the ext::range_set with a different one.

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.

Examples:

#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;
        default:
        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.

Remarks

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.

---

[index]