CODEWITHSUNDEEP
c++stlset
Catskul
Catskul

Reputation: 19259

Why is std::set::lower_bound(x) (effectively) defined as the smallest number >= x rather than the largest number <= x?

Perhaps I'm misunderstanding the technical definition of lower bound but I would expect if I had a set a = { 0, 3, 4 } and computed the a.lower_bound(2) that the result would be 0. I.e. I would expect std::set::lower_bound to be close to the mathematical concept of infimum

And yet the standard library defines it as the largest number not less than (effectively >=) x.

What is the reasoning behind this?

Upvotes: 13

Views: 4360

Answers (2)

Tawnos
Tawnos

Reputation: 1887

The "[lower|upper]_bound" functions are meant to return a place in a set where you could insert a key that would not violate the ordering of the set. Because an iterator of an STL set points to before the next element, if lower_bound(2) returned an iterator to 0, then inserting 2 would violate the order of your set, it would now be {2, 0, 3, 4}. Upper bound serves to show the last place you could insert without violating set order.

This is most useful if your set may have duplicate key entries. Consider {0, 3, 3, 4}. lower_bound(3) would return an iterator to here: {0, *, 3, 3, 4}, while upper_bound(3) would return it here: {0, 3, 3, *, 4}.

Upvotes: 29

James McNellis
James McNellis

Reputation: 355079

It may help to consider the behavior of lower_bound and upper_bound together.

In the STL, ranges are always closed-open intervals. The range delimited by two iterators, first and last, includes all of the elements between first and last, including first and excluding last. Using interval notation, we'd represent this as [first, last).

lower_bound and upper_bound are defined such that they find the range of elements that compare equal to the specified value. If you iterate between lower_bound(x) and upper_bound(x), you will iterate over all of the elements that compare equal to x. If no element is equal to x, then it is guaranteed that lower_bound(x) == upper_bound(x).

This feature is less important for std::map, which has at most one element for every key, but is a very useful feature for non-unique associative containers and for the nonmember std::lower_bound that may be used with arbitrary sequences of sorted elements.

[Note that if you want to obtain both the lower and upper bound, you should call equal_range instead, which returns both.]

Upvotes: 6

Related Questions