Hacker News Reader

Comment by andyg_blog | Hacker News Reader

This is not a valid drop in replacement for lower_bound. Accessing iterators as front[index] is only for random access iterators like vector has. The author may have realized this if they benchmarked on other containers.A forward iterator must be advanced and then dereferenced.

View on HN

Can you do binary search without random access? I would not expect so. Am I missing a point that someone could explain?

The C++ standard measures the time complexity of lower_bound and binary_search by the number of comparisons performed. So yes, it's possible on e.g., a linked list like std::list (by this definition)

Observe that you can restrict your code to only call std::advance on the iterator. So definitely you could do binary search without random access, and you would actually iterate over all elements, but you just skip the comparison function for the majority of elements.

Good point. I don't think anyone actually uses it for containers that only support forward iteration. But the author did declare the signature with ForwardIterator.

For a proper/sane forward iterator, front[index] is the same thing as *(front + index) and front + index achieves the same as std::advance(front, index) (just not in place).

Or are you pointing out how first[length] and first += length + rem would technically result in advancing a forward iterator through to first + length twice? (Trivially fixed with a middle = first + length temporary variable btw).

Reply on news.ycombinator.com