Re: [boost] Interval Library and comparison operators

From: David Abrahams (dave_at_[hidden])
Date: 2002-09-05 17:13:04

From: "George A. Heintzelman" <georgeh_at_[hidden]>

> > How would you define the mid-point relation for elements having
> > identical midpoints, but varying extension, such as [1, 5] and [2, 4]?
> > Since we want a total ordering, and not be forced (through the
> > "equivalent if incomparable" hypothesis of the STL library) to have
them
> > be equal...
>
> The midpoint relation isn't a total ordering. It *is*, however, a
> strict weak ordering, which satisfies the requirements for defined
> behavior in std::sort. [1,5] and [2,4] are part of the same equivalence
> class for this ordering.
>
> If you wanted to extend this to a total ordering, you could, but I
> don't think it's necessary, and would add overhead to operator<.
> Furthermore, I don't think there is an intuitive definition to choose
> in this case, so it will be one of those things that people are
> continually looking up.

Sure, it meets the requirements, but it doesn't give you useful behavior.
If you try to put (2,4) in a map which contains (3,3), nothing will happen.
I agree with others that from an STL viewpoint, lexicographic ordering or
something like it is the only one that makes sense.

It's not unreasonable to think of using a rel_ops approach for these
things, though the operators won't propagate into generic algorithms:

namespace mine {
    boost::interval f(boost::interval* start, boost::interval* finish)
    {
        using boost::intervals::my_preferred_comparison_ops;

        ... start[0] < start[1] ... ; // ok

        std::sort(start, finish); // error
    };
}

-----------------------------------------------------------
           David Abrahams * Boost Consulting
dave_at_[hidden] * http://www.boost-consulting.com