[Boost-bugs] [Boost C++ Libraries] #9501: interval_set uses std::set with non strict weak ordering

Subject: [Boost-bugs] [Boost C++ Libraries] #9501: interval_set uses std::set with non strict weak ordering
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-12-17 11:02:30

#9501: interval_set uses std::set with non strict weak ordering
-------------------------------------------------+-------------------------
 Reporter:  Tamás Kenéz <tamas.kenez@…>          |      Owner:  jofaber
     Type:  Bugs                                 |     Status:  new
Milestone:  To Be Determined                     |  Component:  ICL
  Version:  Boost 1.55.0                         |   Severity:  Problem
 Keywords:  icl interval_set insert clang llvm   |
  set ordering                                   |
-------------------------------------------------+-------------------------
 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);

  }

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/9501>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.