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 15:33:16

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

 In your example, "comp" does not induce a strict weak order because both x
 < y and y < x are true for two ranges x = (2, 2) and y = (2, 2).

 And the comparison passed as argument shall induce the same strict weak
 ordering as key_compare (this precondition is missing in equal_range but
 it's the same as required by "erase", "insert_", etc...

 In a set, two elements can't be equivalent according to the predicate, so
 with any comparison function that leads to the same strict ordering,
 equal_range must return the only element equivalent to "key" as pair.first
 and an iterator to the next element as pair.second. The tree is ordered
 using the predicate so using any ordering function that does not lead to
 the same order will be broken by definition, even using lower-bound() and
 upper_bound might return false replies.

 I guess the problem appeared when set::equal_range was optimized assuming
 those preconditions. I think your use case is invalid, and missing "comp"
 preconditions should be added to all functions that take it as argument.

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