How to check if a set has an element in a specific range in C ++

Question

I need to check if the std::set element contains the element / elements in a range. For example, if a set is set<int> {1, 2, 4, 7, 8} and an int interval [3, 5] specified (inclusive with both endpoints), I need to know if there are elements in it. In this case, return true. But if the interval is [5, 6] , return false. The interval can be [4, 4] , but not [5, 3] .

It looks like I can use set::lower_bound , but I'm not sure if this is the right approach. I also want the difficulty as low as possible. I believe using lower_bound logarithmic, right?

Answer 1

You can use lower_bound and upper_bound together. Your example of testing elements from 3 to 5 inclusive can be written as follows:

 bool contains_elements_in_range = s.lower_bound(3) != s.upper_bound(5); 

You can make the range inclusive or exclusive from either end by switching the function you use ( upper_bound or lower_bound ):

 s.upper_bound(2) != s.upper_bound(5); // Tests (2, 5] s.lower_bound(3) != s.lower_bound(6); // Tests [3, 6) s.upper_bound(2) != s.lower_bound(6); // Tests (2, 6) 

Logarithmic time is the best you can achieve for this, since the set is sorted, and you need to find the element in a sorted range that requires a dichotomous search.

Answer 2

If you are sure you are going to use std::set , I agree that the lower_bound method is the way to go. As you say, it will have a logarithmic temporal complexity.

But depending on what you are trying to do, the overall performance of your program may be better if you use the sorted std::vector and standalone std::lower_bound algorithm ( std::lower_bound(v.begin(), v.end(), 3) ). It is also logarithmic, but with a smaller constant. (Of course, the disadvantage is that inserting elements into std::vector and preserving their sorting is usually much more expensive than inserting elements into std::set .)