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 16:53:10

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

 Typically, interval trees can be implemented as ranges ordered by the low
 endpoint, but each node is augmented to store an extra annotation holding
 the maximum upper endpoint among all child nodes. An special search
 function is used to find the overlap.

 Without augmentation, I suspect that the equal range search would not
 detect any overlapping range. Is algorithmically guaranteed that with a
 tree ordered by the low endpoint, a lower_bound search using (x._end <=
 y._start) will find the start of the overlapping range?

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