**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

**Next message:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #2984: Cannot serialize protected and private base classes"**Previous message:**Boost C++ Libraries: "[Boost-bugs] [Boost C++ Libraries] #11703: test_exec_monitor.so couldn't be built correctly for lockfree test on Solaris 11.2"**In reply to:**Boost C++ Libraries: "[Boost-bugs] [Boost C++ Libraries] #11701: Regression in boost::intrusive::set::equal_range"**Next in thread:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #11701: Regression in boost::intrusive::set::equal_range"

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

**Next message:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #2984: Cannot serialize protected and private base classes"**Previous message:**Boost C++ Libraries: "[Boost-bugs] [Boost C++ Libraries] #11703: test_exec_monitor.so couldn't be built correctly for lockfree test on Solaris 11.2"**In reply to:**Boost C++ Libraries: "[Boost-bugs] [Boost C++ Libraries] #11701: Regression in boost::intrusive::set::equal_range"**Next in thread:**Boost C++ Libraries: "Re: [Boost-bugs] [Boost C++ Libraries] #11701: Regression in boost::intrusive::set::equal_range"

*
This archive was generated by hypermail 2.1.7
: 2017-02-16 18:50:19 UTC
*