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::iterator
s 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
InputIterator
meets the requirements of random access iterator, returns(last - first)
; otherwise, returns the number of increments needed to get fromfirst
tolast
.
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.