Subject: Re: [Boost-bugs] [Boost C++ Libraries] #11701: Regression in boost::intrusive::set::equal_range
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2015-10-03 11:02:48
#11701: Regression in boost::intrusive::set::equal_range
Reporter: nyh@â¦ | Owner: igaztanaga
Type: Bugs | Status: new
Milestone: To Be Determined | Component: intrusive
Version: Boost 1.57.0 | Severity: Regression
Resolution: | Keywords:
Comment (by igaztanaga):
Boost.Intrusive's custom comparators were designed before heterogeneous
comparisons were proposed. Intrusive's "advanced lookup" functions
were designed to use a search function without the need of constructing a
whole "value_type". That is, if your value_type is ordered by a
std::string, these functions offer a way to search the set with a
std::string or a "const char *" key. But the idea was that the comparison
object had to be strictly compatible (same strict weak order) with the
predicate used to define the container. With that precondition, a lower
bound (in a set, not a multiset) can only return a single value (because
there are no two "equivalent" objects in the set).
This precondition was only documented in some functions, like
and was missing in lower/upper/equal_bound family.
Heterogeneous lookups are more flexible. The requirement for the supplied
comparison object is that it must be "compatible" with the set's predicate
only in the sense that the container must be also "partitioned" with
respect to the supplied comparison object. E.g.: This allows sorting a
container by surname first and by name if the surname was equivalent, and
then do a search to find a range of surnames (as the container is ordered
with a predicate that also fulfills the requirements of a container sorted
In your case, I don't see how a set ordered by x._start is also
partitioned with respect to the custom comparison "(x._end <= y._start)".
E.g: [0, 1), [2, 6), [3, 5), [6, 7) is ordered by the "_start" member but
I fail to see how is also partitioned with respecto to "(x._end <=
y._start)", so I can do a binary search.
In any case, it might be interesting to update Boost.Intrusive "advanced
lookup" functions to support heterogeneous lookups. This requires changing
"Requires: comp must be a comparison function that induces the same strict
weak ordering as key_compare. The difference is that comp compares an
arbitrary key with the contained values."
to something like:
"Requires: key is a value such that this container is partitioned with
respect to comp(node, key)"
and change the implementation assuming the new requirement.
-- Ticket URL: <https://svn.boost.org/trac/boost/ticket/11701#comment:6> 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:19 UTC