CODEWITHSUNDEEP
c++stl
Qiang Li
Qiang Li

Reputation: 10855

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

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.

Upvotes: 5

Views: 4675

Answers (3)

Angel Koh
Angel Koh

Reputation: 13485

this might be abit untidy.

you can use the fact that elements in vectors are contiguous within memory.

so what you have to do is

1) get the iterator address of the element of interest

2) subtract with the vector.begin() to get the total memory

3) divide by the size of one element

this should give you the position (or rank).

this is assuming that the elements are fixed size.

Upvotes: 0

drrlvn
drrlvn

Reputation: 8437

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.

Upvotes: 5

Johan Kotlinski
Johan Kotlinski

Reputation: 25729

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.

Upvotes: 2

Related Questions