interval_set uses std::set with non strict weak ordering

[Tamás Kenéz <tamas.kenez@…>]

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);

}

[Ivan Romanenko <viva.cpp@…>]

Also found the same problem. When ICL use boost::container::flat_set instead of std::set.

Because implementation of insertion algorithm in boost::container::flat_set differs with std::set and boost::container::set.

PS. Same problem with interval_map and std::map

[tvk.boost@…]

I can reproduce the problem with clang/libc++.

A temporary workaround is to

#define ICL_USE_BOOST_MOVE_IMPLEMENTATION

before including ICL headers. This will make it use the boost implementation std::set.

[Joachim Faulhaber]

Fixed with 1.56.0