I'm looking for a log2(N) way of searching a std::vector and receive a RandomAccessIterator. I want it to work exactly as std::lower_bound() but return a RandomAccessIterator instead of a ForwardIterator.
I need the result from the first std::vector search, to define a a subrange of a larger second std::vector. I want to use the index from the first search to describe the subrange in the second vector.
I don't want to do any slow linear manipulations like std::distance at al. Performance is of the essence.
What is the best way to achieve this?
Thanks in advance
Both RandomAccessIterator and ForwardIterator are named requirements, not types. RandomAccessIterator subsumes ForwardIterator, i.e. it has all the requirements of ForwardIterator, plus some extra ones.
Because of that, every type that satisfies RandomAccessIterator also satisfies ForwardIterator.
std::lower_bound is a template function. It takes a pair of iterators of a particular type, and returns an iterator of the same type. It requires the iterator type to satisfy at least ForwardIterator. The standard names the type parameter ForwardIterator because it defines the requirements of algorithms by the names of the parameters.
If an algorithm's template parameter is named
ForwardIterator,ForwardIterator1, orForwardIterator2, the template argument shall satisfy the requirements of a forward iterator
The iterator type you get out of std::vector, std::vector::iterator, is required to satisfy RandomAccessIterator, and therefore it satisfies ForwardIterator.
Thus, you can pass a pair of std::vector::iterators to std::lower_bound and get a std::vector::iterator as the result.
N.b. std::distance is not a linear manipulation when you pass it a type that satisfies RandomAccessIterator:
Effects: If
InputIteratormeets the requirements of random access iterator, returns(last - first); otherwise, returns the number of increments needed to get fromfirsttolast.
What is the best way to achieve this?
std::lower_bound. Technically, the standard does not require implementations move between elements efficiently, but all the major ones do when given RandomAccessIterators.