3 ms·
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
by andyg_blog 3y ago
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.
- fn-mote 3y agoCan you do binary search without random access? I would not expect so. Am I missing a point that someone could explain?
- andyg_blog 3y agoThe 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)
- kccqzy 3y agoObserve 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.
- commonlisp94 3y agoGood 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.
- mhdm 3y agoFor 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).