Search code examples
c++stlbinary-searchstdset

How to use lower_bound/upper_bound to get index number from std::set?

I am trying to use Binary search function provided by STL which requires a vector to be sorted first. So that's why I am trying to directly use Set so i don't have to sort first.

But when used set in the following way,

`

#include <bits/stdc++.h>
using namespace std;
int main(){
set <int> mn = {11, 33, 44, 66, 80,90};
auto it= mn.lower_bound(55);
cout<<it-mn.begin();
    return 0;
}

`

an error occurs saying:

error: no match for ‘operator-’ (operand types are ‘std::_Rb_tree_const_iterator’ and ‘std::set::iterator’

How to use set to get index number of returned iterator here?

PS: I have also tried using set::lower_bound, but shows the same error.

Solution

  • The iterators for set are bidirectional iterators, which means that you can't subtract two of them.

    You can calculate the distance thus: std::distance(mn.begin(), it) but you need to be aware that for bidirectional iterators, this is an O(N) operation - not constant time.