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
4
As mentioned in the comments, you can simply use std::lower_bound with your std::vector to get a RandomAccessIterator.
std::lower_bound calls its iterator template parameter ForwardIt because first and last iterators should be at least forward ones (and in that case a forward iterator is returned).
But the type of the returned iterator matches the type of first and last (as internally it is a result of manupulating them to search the range).
For std::vector they would be of type std::vector::iterator which is a RandomAccessIterator and the returned value would be as well.
Both RandomAccessIterator and ForwardIterator are concepts, 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 iterators of a particular type, and returns an iterator of the same type. It requires the iterator type 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
[algorithms.general]
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.
[iterator.operations]
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.