shanto_bangladesh's blog

By shanto_bangladesh, history, 6 months ago, In English

I tried to find the index of the upper_bound of an integer in a set.

set<int> s = {1,2,3,4,5};
int ind = s.upper_bound(2) - s.begin();
cout << ind << "\n";

But it's showing error. I did similar thing with vectors previously. Code looks like the following:

vector<int> v = {1,2,3,4,5};
int ind = upper_bound(v.begin(), v.end(), 2) - v.begin();
cout << ind << "\n;

The above code nicely executes the desired task. Why it's not working for set and multiset and what to do if we want to do the same task with a set or multiset without traversing the whole set?

Thanks for your patience!

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +6 Vote: I do not like it

std::set (or multiset, doesn't matter) doesn't allow you to do it fast. To calculate the index you should think of easier solution for the problem that doesn't involve it; it's too difficult use some more advanced data structures, for example ordered_set (see here). But actually, pay attention to the striked text!

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

What you are using are are containers. Set, vector, map etc. There are linear containers and there are non-linear containers. Vector is a linear container and so you can subtract the iterators whereas set is non-linear container and you cannot do that.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

STL set is implemented by binary search tree. That's why you can not subtract the iterators to find the position. You can use Policy Base Data structures or Ordered set for that. Link

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Pointers in std::set are only bidirectional iterators: this means that a std::set "pointer" can only go one step forward or one step backward in the set, no random jumps allowed and this also means no pointer addition/subtraction.