id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
9501,interval_set uses std::set with non strict weak ordering,Tamás Kenéz <tamas.kenez@…>,Joachim Faulhaber,"This program fails with clang's own LLVM STL implementation (libc++)

#include <boost/icl/interval_set.hpp>
void t1()
{
    //correct output:
    //[15 43)
    
    //invalid output (mac, xcode 5.0.2, w/standard lib: ""libc++ (LLVM)"")
    //[15 31)
    //[30 43)
    
    typedef boost::icl::interval_set<int> IVS;
    typedef boost::icl::discrete_interval<int> IV;

    IVS ivs;
    ivs.insert(IV(20, 21));
    ivs.insert(IV(30, 43));
    ivs.insert(IV(15, 31));
    
    for(auto it = ivs.begin(); it != ivs.end(); ++it)
        printf(""[%d %d)\n"", it->lower(), it->upper());
}

Reason:

interval_set's underlying std::set container requires a strict weak ordering. interval_set uses an ""overlap-free less"" (icl/detail/exclusive_less_than.hpp) which is not strict weak (that is, !(a<b)&&!(b<a) is not transitive).
Therefore, behaviour of std::set::insert becomes undefined. With clang's libc++, it is different than the one excepted by the icl.

std::set test case mimicking what's happening under the hood in interval_set::insert:

struct MIV
{
    MIV(int a, int b)
    :lo(a), hi(b) {}
    
    int lo, hi;
    
    //equivalent to the intervalset's overlap-free less
    //in boost::icl::exclusive_less_than
    bool operator<(const MIV& y) const
    {
        return hi <= y.lo;
    }
};

#include <set>
void t2()
{
    //output when icl works:
    //it: [30-43), bool: 0

    //output when icl fails (mac, xcode 5.0.2, w/standard lib: ""libc++ (LLVM)"")
    //it: [20-21), bool: 0

    typedef std::set<MIV> MSET;
    MSET ms;
    
    ms.insert(MIV(20, 21));
    ms.insert(MIV(30, 43));
    
    auto itb = ms.insert(MIV(15, 31));
    
    printf(""it: [%d-%d), bool: %d\n"", itb.first->lo, itb.first->hi, itb.second);
    
 }",Bugs,closed,To Be Determined,ICL,Boost 1.55.0,Showstopper,fixed,icl interval_set insert clang llvm set ordering,tamas.kenez@…