Michael Michael - 24 days ago 8
C++ Question

C++ offers std::sort, but does it also offer something to search efficiently?

I have a vector of objects which implement

operator<
and
operator==
. C++ offers std::sort to sort that vector efficiently.

Is there also a function in std to efficiently search a vector repeatedly?

I will have many searches on that sorted vector, so std::find does not seem to be a good option, since it just walks through the iterator until it finds a match.

Answer

Of course, there are.

For example, have a look at lower_bound and upper_bound functions.

Also binary_search may be useful.

All these functions work on the sorted input and have logarithmic complexity.