4

Does any one know why they where given these names? Comming from a maths backgound they always left my mind in tangles since they are both mathematical lower bounds i.e. minimums in the finite world. Also the natural language definition given in the stl is a bad mental model imo.

Does anyone use mental synonyms to be able to work with them, or do they just remember the naïve implementations?

lower_bound(rng, x) = get_iter_to(mathematical_lower_bound(rng | filter([](auto y) {return x<=y;})) upper_bound(rng, x) = get_iter_to(mathematical_lower_bound(rng | filter([](auto y) {return x<y;})))

Improve this question
3
  • 4
    lower_bound returns the leftmost position in a sorted sequence where a given value can be inserted while preserving the order. upper_bound returns the rightmost such position. The two may be different when the sequence contains equivalent elements; or at least, one element equivalent to the value. Another way to think about it - they are two bounds around the (possibly empty) range of elements equivalent to a given value (see also: equal_range) Commented Apr 27, 2022 at 3:22
  • @IgorTandetnik thanks I get it now. You could post that as an answer Commented Apr 27, 2022 at 7:02
  • Great answers. also check this and this questions. Commented Jan 23, 2024 at 0:00

3 Answers 3

Reset to default
2

Igor Tandetnik answered this in the comments.

The set in question is the the elements which the given value can be inserted before while preserving the order.

For example if we want to insert 2 in to the range [0,1,2,2,3,4] then we could insert it at index 2, 3 or 4. lower_bound gives the iterator to the start of the range. upper_bound gives the last element in this range.

I suppose this is a name for library implementers writing pivots, rather than me trying to look up keys/indices of a vector of numerics.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

This example from std::ranges::lower_bound (link) is more helpful

std::vector data = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 }; auto lower = ranges::lower_bound(data, 4); auto upper = ranges::upper_bound(data, 4); ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; // 4 4 4 4
Improve this answer

Comments

1

My (perhaps wrong) understanding of these APIs is that std::lower_bound(first, last, value) and std::upper_bound(first, last, value) are meant to return lower and upper bounds of set

{ x \in [first, last) : equiv(x, value) }

where equiv relation is defined as

equiv(x, y) == !(x < y) && !(y < x) }

std::upper_bound returns iterator pointing to after the actual upper bound so that we could use it to create STL-style half-open interval for our set:

[ std::lower_bound(...), std::upper_bound(...) )
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.