shanto_bangladesh's blog

How to subtract pointers pointing to elements of a set?
By shanto_bangladesh, history, 3 years 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

Comments Comments (3)
| Write comment?
»
3 years 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!

→ Reply
»
3 years 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.

→ Reply
»
3 years 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.

→ Reply