std::set::equal_range for a container of std::pair

Question

I'm trying to find all the ranges [a,b] enclosing int values i, where a <= i <= b. I'm using set<std:pair<int,int>> for the set of ranges.

In the following, using equal range on a vector<int> yields the start and one past the end of the range.

When I do the same for a set<pair<int,int>>, the result starts and ends at one past the end of the range and therefore doesn't include the range enclosing the value.

#include <set>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int ia[] = {1,2,3,4,5,6,7,8,9,10};
    set<int> s1(begin(ia),end(ia));
    auto range1 = s1.equal_range(5);

    cout << *range1.first << " " << *range1.second << endl; //prints 5 6

    pair<int,int> p[] = {make_pair(1,10), 
                         make_pair(11,20),  
                         make_pair(21,30), 
                         make_pair(31,40)}; 
    set<pair<int,int>> s(begin(p), end(p));    

    auto range = s.equal_range(make_pair(12,12));

    cout << range.first->first << " " << range.first->second << endl; //prints 21 30, why?
    cout << range.second->first << " " << range.second->second << endl; //prints 21 30

}

prints
5 6
21 30
21 30
Why does equal_range on the set<pair<int,int>> not include the range that encloses the value (12), namely [11.20]

score 4 · Accepted Answer · edited Nov 12 '12 at 19:33

equal_range is behaving completely correctly:

assert( std::make_pair(11, 20) < std::make_pair(12, 12) );
assert( std::make_pair(12, 12) < std::make_pair(21, 30) );

[11,20] is not a range, it's a pair. The pair [12,12] is not "within" another pair, that makes no sense to even say.

[12,12] is not "within" [11,20], it's greater than it. The less-than operator for std::pair compares the first elements first, and only if they're equal does it look at the second elements, so make_pair(11,x) is less than make_pair(12, y) for any x and y

So equal_range tells you that [12,12] would be inserted after [11,20] and before [21,30], which is correct.

If you want to treat pairs as ranges of values you need to write code to do that, not assume the built-in comparisons for pairs does that. You're actually trying to find an int 12 in a range of pairs of ints, but have written code to find a pair [12,12] in a range of pairs of ints. That's not the same thing.

score 3 · Answer 2 · edited Nov 12 '12 at 00:06

3

It does not include [11, 20] in the range, because it doesn't include anything in the range. There are no equal elements to [12, 12], so it returns an empty range (represented by the half-open interval [x, x)).

BTW dereferencing the upper bound of the range may invoke undefined behavior, since that may be equal to s.end().

edited Nov 12 '12 at 00:06

Jesse Good

50,901
14
124
166

answered Nov 11 '12 at 23:05

jpalecek

47,058
7
102
144

Shouldn't equal range use the same `less>` default comparator as used to define the the set? In this case, the range including the 12 returns `true` because [11,20] < [12,12] – hhbilly Nov 11 '12 at 23:12
I want to find all ranges in a large set that enclose a value. Instead of using the set member, I could use find_if algorithm with a lambda that tests for enclosure but doesn't that mean I need to test all elements in the set (numbering in the millions)? – hhbilly Nov 11 '12 at 23:27
Is it possible to find all ranges with O(log(n)) by using a set member function instead? – hhbilly Nov 11 '12 at 23:30
@user1626720: If your intervals overlap (and there may be more than one covering a particular point) you want an interval tree, not `std::set`. In case the intervals don't overlap (as is the case in your example), what you do is almost right. You just look immediately below and at the lower bound. – jpalecek Nov 11 '12 at 23:53
Thanks @jpalecek: The example wasn't brilliant as the intervals do overlap (and duplicate). The reason for using a `std::set` is I'm hoping to use the stdlib red-black tree implementation rather than roll my own interval tree. Am I barking up the wrong tree? :P – hhbilly Nov 11 '12 at 23:58

score 1 · Answer 3 · answered Nov 11 '12 at 23:15

1

The pair [12, 12] is sorted after [11, 20] and before [21, 30].

std::set::equal_range() includes a range of equal elements. There is no equal element in your set (especially not [11, 20]), so equal_range() returns [21, 30], [21, 30].

answered Nov 11 '12 at 23:15

Olaf Dietsche

72,253
8
102
198

score 1 · Answer 4 · answered Nov 11 '12 at 23:22

equal_range is implemented as to call lower_bound first then call upper_bound to search the rest data set.

template <class ForwardIterator, class T>
  pair<ForwardIterator,ForwardIterator>
    equal_range ( ForwardIterator first, ForwardIterator last, const T& value )
{
  ForwardIterator it = lower_bound (first,last,value);
  return make_pair ( it, upper_bound(it,last,value) );
}

Look at your sample: It calls lower_bound to locate the lower bound of value(which is pair(12,12), which arrives at

pair<int,int> p[] = {make_pair(1,10), 
                     make_pair(11,20), 
                     make_pair(21,30),   // <--- lower_bound() points to here
                     make_pair(31,40)};

Then it calls upper_bound() to search on (21,30),(31,40) and it cound't find it, it returns (21,30)

http://www.cplusplus.com/reference/algorithm/upper_bound/

score 1 · Answer 5 · answered Nov 11 '12 at 23:24

I don't think your std::set<std::pair<int, int> > won't help you much in intersecting it with your integer: You can find the s.lower_bound(std::make_pair(i + 1, i + 1) to cut off the search but all ranges starting at an index lower than i + 1 can potentially include the value i if the second boundary is large enough. What might help is if you know the maximum size of the ranges in which case you can bound the search towards the front by s.lower_bound(std::make_pair(i - max_range_size, i - max_range_size)). You'll need to inspect each of the ranges in turn to identify if your i falls into them:

auto it    = s.lower_bound(std::make_pair(i - max_range_size, i - max_range_size));
auto upper = s.lower_bound(std::make_pair(i + 1, i + 1));
for (; it != upper; ++it) {
    if (i < it->second) {
        std::cout << "range includes " << i << ": "
                  << [" << it.first << ", " << it->second << "]\n";
}

(or something like this...)

These ranges can overlap so even if I know the maximum range by checking first this won't lead to an improvement over O(n). For example if ranges are like `[a [c [e... ...f] d] b]` and `e < i < f`. — hhbilly, Nov 11 '12 at 23:45
Yes, that is correct. If you want something better than O(n) you need a different algorithm, e.g., using [range trees](http://en.wikipedia.org/wiki/Range_tree). — Dietmar Kühl, Nov 11 '12 at 23:50

std::set::equal_range for a container of std::pair

5 Answers5

Linked