A container for integer intervals, such as RangeSet, for C++

If you encode ranges as a sequence of endpoints and step direction, instead of start/end pairs, then finding union should become much easier, just a simple mergesort.

(0, +) (5, -)

(0, +) (5, -) (10, +) (15, -)

(0, +) (5, +) (5, -) (7, -) (10, +) (15, -)

Look, the overlapping range appears as nested ranges. Just preserve only the outermost ones.

(0, +) (5, +) (5, -) (7, -) (10, +) (15, -)
   1      2      2     1       1       1       <= depth
(0, +) (7, -) (10, +) (15, -)

(0, +) (7, -) (10, +) (12, +) (15, -) (17, -)
   1      1      1       2       2       1
(0, +) (7, -) (10, +) (17, -)


(0, +) (6, +) (7, -) (10, +) (13, -) (17, -)
   1      2      2      2       2       1
(0, +) (17, -)

I think that finding intersections becomes simple also, now you preserve only endpoints with a nesting level of 2, instead of deleting them.

Credit to Arne Vogel for noting that a set of pairs indexed on their first element is really a map.

Hence pretty close to my initial thoughts and to Useless' answer (except simple on comparing bounds); we get this:

typedef std::pair<int, int> Range;

class RangeSet : public std::map<int, int> {
public:

std::pair<RangeSet::iterator, bool> insert(const Range& range) {
    assert(range.first <= range.second);

    RangeSet::iterator after = upper_bound(range.first), insert_range;

    if (after == begin() or std::prev(after)->second < range.first) {
        insert_range = std::map<int, int>::insert(after, range);
    }   
    else {
        insert_range = std::prev(after);
        if (insert_range->second >= range.second) {
            return std::pair<RangeSet::iterator, bool>(insert_range, false);
        }   
        else {
            insert_range->second = range.second;
        }   
    }   

    while (after != end() and range.second >= after->first) {
        insert_range->second = std::max(after->second, insert_range->second);
        after = erase(after);
    }   

    return std::pair<RangeSet::iterator, bool>(insert_range, true);
}   

};

With the boolean returned being true iff there is at least one element added to the total set.

Boost has the Interval Container Library (ICL). If you want to do computations on intervals, e.g. represent sin(I) for an interval I, there is also a Interval Arithmetic Library in boost.