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.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:15 UTC