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-01 21:02:03

#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 anonymous):

 Hi igaztanaga, thanks for the detailed response, although I have to admit
 I'm a little confused about all the "preconditions" on the given
 comparator which you mention. Can you please point me to some
 documentation which lays them out explicitly?

 But I have to admit I'm surprised by your statements about the various
 "preconditions" and "compatibility" of the two comparators and the fact
 that the second one also needs to define a set. To explain why I'm
 surprised, let's step back for a moment and ask ourselves - why am I using
 lower_bound (or upper_bound or equal_range) at all? Why am I not just
 doing a simple iteration on the set to compare the items in the set with
 the given item, using the given comparator?

 The answer is complexity: Simple iteration has linear complexity (O(N)),
 while upper_bound and friends are supposed to have logarithmic complexity
 O(ln N). BUT, there is one snag: while std::upper_bound
 (http://en.cppreference.com/w/cpp/algorithm/upper_bound) indeed does a
 logarithmic number of *comparisons*, it still needs to do a linear number
 of increments of the iterator when the iterator is not random-access,
 because it cannot skip half the list at once. Other than this snag (linear
 number of increments), std::upper_bound does exactly what I want, and does
 not have any of the "preconditions" you mention on the comparator - all
 you need a guarantee that the comparator in fact divides (partitions) the
 given iteratable list into "smaller than the given item" (according to the
 comparactor in the parameter) and "higher than the given item". That's it.
 And in my example, this condition definitely holds.

 Now, what I expected in boost::intrusive::set::upper_bound and friends, is
 to implement std::upper_bound with one added benefit: Because the set is
 not just a sorted list, but actually a tree, we can skip big parts of the
 list and get ourselves a logarithmic number of iterator updates instead of
 linear, as we hoped. In other words, I expected
 boost::intrusive::set::upper_bound to not be more limited - just better
 performing - than std::upper_bound.

 What most surprised me in your answer is that you seem to say that because
 the given list is known to be a set (according to its intrinsic
 comparator), with non-equal values, then the result of equal_range with a
 '''different''' comparator should always be a single value - no matter
 what the second comparator is (and in particular we're not allowed to
 choose a comparator which declares several items in the set to be equal
 under this comparator). This is really surprising, because
 std::equal_range was designed exactly for the purpose of choosing a
 comparator which does declare multiple items to be equal, and the idea is
 to find all the equal items.

 By the way, interestingly, std::set's upper_bound and friends do not let
 you specify the comparator at all. They always use the set's intrinsic
 comparator. I guess that while boost::intrusive::set's implementation does
 let you specify the comparator, it's really unsafe to do so unless you
 really know what you're doing. Perhaps http://www.open-

 std.org/jtc1/sc22/wg21/docs/papers/2012/n3465.pdf is relevant here. But it
 is apparently not useful to invent your own comparator and belive it would
 work - even if it would have worked just fine in std::upper_bound. The
 rules for a comparator for std::upper_bound and for
 boost::intrusive::set::upper_bound are apparently very different in
 surprising ways.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/11701#comment:5>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.