How to get the rank of an element in vector in C++

Question

I need to get the rank (the positional index+1) of an element for containers in C++ like vector or list. Is there a convenient way of doing so? I could have done testing based on nth_element in order to find the rank. Or I could sort and do binary search to find the rank. But all of these do not seem very efficient in the worst-case. I'd like to get O(lgn) complexity, and done with STL algorithms if possible.

Answer 1

If your container has random access iterators (e.g. vector) and is sorted, you can use the std::lower_bound() algorithm to get an elements index in O(log n) complexity. For example:

std::vector<int> v({10,20,30,30,20,10,10,20});
std::sort(v.begin(), v.end());
auto iter = std::lower_bound(v.begin(), v.end(), 20);
std::cout << "index " << int(iter - v.begin()) << std::endl;

(I'm using C++11 syntax to keep the code short, but you should get the idea).

Note that you can insert elements to a vector in a sorted way, so you don't need to sort before finding the index.

Answer 2

It seems very unlikely that you will find something more efficient than linear search here. The worst case must necessarily be that you compare all elements with what you search for - and that is exactly what linear search gives you.