Re: [Boost-bugs] [Boost C++ Libraries] #11701: Regression in boost::intrusive::set::equal_range

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
 (http://www.boost.org/doc/libs/1_59_0/doc/html/intrusive/advanced_lookups_insertions.html)
 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
 "insert_check"
 (http://www.boost.org/doc/libs/1_59_0/doc/html/boost/intrusive/set.html#idp50496544-bb)
 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
 by surname).

 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
 the precondition

 "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.