[Boost-users] [icl] Icl broken for c++11's hint semantics. Fix provided.

Subject: [Boost-users] [icl] Icl broken for c++11's hint semantics. Fix provided.
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2014-02-25 05:40:39

Dear Icl users,

due to a subtle effect of the changed hint semantics for
associative containers, the icl library is broken in
versions <= 1.55.0 when used with new STL-libraries that
implement the new c++11 standard.

This bug is fixed in the upcoming Boost 1.56.0. (see regression tests at
http://www.boost.org/development/tests/master/developer/icl.html).
Since the release of boost 1.56.0 seems to take longer than
planned due to restructuring efforts for modular-boost, users of
Boost.Icl affected by the problem may choose to pull the fixed
Boost.Icl directly from the git repository and replace
your_boost_1_55_0/boost/icl
with the new code. The libs/icl part does not need an update.

Another possibility is to apply the patch-file
diff_icl_1_55_0_and_master.patch that is attached to this post
to your local boost library 1.55.0:

1. cd to your_boost_1_55_0 root directory.
your_boost_1_55_0>

2. From the command line type
your_boost_1_55_0> patch -p2 < diff_icl_1_55_0_and_master.patch

You may check the patched library by moving to
your_boost_1_55_0/libs/icl/test

and run
your_boost_1_55_0/libs/icl/test> bjam

Sorry for the inconvenience.

Best regards,
Joachim

P.S.:
For those interested in details of the issue here is a report:

The semantics of insertion with hint in associative containers
changed in c++11 form

insert-after-hint  (c++98/03) to
insert-before-hint (c++11)

see e.g. proposal N1780:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html

so for an associative container c of type C, a value x and
an iterator hint
c.insert(hint, x); //tries to insert x right after hint in c++98
c.insert(hint, x); //tries to insert x before hint in c++11

In accordance with this behavior, if using the insert function

std::pair<bool, iterator> C::insert(value_type const& x);

(success, hint) = c.insert(x);

the iterator hint of unsuccessful insertion is the matching hint,
pointing to

[c++98] the last element y in c that is not greater x, so x can
be inserted *after* that hint.

[c++11] the first element z in c that is greater than x,
so x can be inserted *before* that hint.

In Boost.Icl I used the returned hint-iterator of the insert
function, that always returned the last overlapping interval y
for an inserted interval x given the interval's exclusive-less
ordering under c++98.

With the changed hint semantics, this returned hint-iterator
did not point to the last interval y overlapping x anymore
but to the first interval z not overlapping x.

Therefore the code was broken and returned false results.

-- 
Interval Container Library [Boost.Icl]
http://www.joachim-faulhaber.de