Iúri Chaer wrote:

>> But in the case of std::list since C++11 we have constant-time
>> size(), which std::lower_bound() doesn't exploit.
>
> Well, std::lower_bound() takes a pair of iterators, so we can't really rely
> on size().

Here's an idea, how about a std::lower_bound overload that takes
an iterator and a size?

> The classic way of merging ordered sequences is to simply
> iterate over both linearly, moving forward the one which compares less so
> we can find all matches, achieving the minimal worst-case complexity of 2*n
> comparisons. But if you think about it, that's really wasteful: both
> sequences are sorted, why can't we use binary search to fast-forward the
> iterator which is behind, and perform O(log(n)) comparisons on the
> best-case scenario? By narrowing down the iterator range as we move
> forward, with one-sided binary search we can preserve the worst-case
> scenario complexity while improving the best-case scenario.

Right, a worthwhile improvement is possible for set_intersection for
random-access iterators.

As for std::set...

> You may be asking yourself "why not use std::set::lower_bound() instead?",
> and the answer is that std::set::lower_bound() doesn't take two iterators
> as its input, it will start at the root of the tree and work its way down,
> so that the worst-case complexity of using it to iterate over both trees
> would be O(n*log(n)). The magic of worst-case linear traversal can only
> happen with the standalone std::lower_bound(), so that we decrease n as we
> move forward, while at the same time exploiting the fact that the number of
> steps required by one-sided binary search depends on the distance of the
> match, rather than the size of the range.

Ugh, I feel a bit queasy with the idea of doing a binary search through a
std::set without using its (private) left/right/parent pointers to do so.
Slightly more queasy than finding the size of a std::list without using its
size() member. Here's an idea, add a std::set::lower_bound overload that
takes an iterator pair (or a single begin iterator); maybe call it a hint,
like std::set::insert?


Regards, Phil.