upper_bound returns an iterator to the first element whose key is greater than a queried key. It works with ordered associative containers and ordered ranges. section 7.2.2
Use the returned position to:
- Locate the end of all elements matching a key. section 7.2.3
- Pair it with lower_bound to test whether a key exists: matching iterators mean no exact element was found. section 7.2.2
- Use it with equal_range to obtain the complete iterator range for duplicate keys. section 7.2.2 section 7.2.3
const std::vector<int> data{ 1, 2, 4, 5, 6, 7 };
auto lower = std::lower_bound(data.begin(), data.end(), 3);
auto upper = std::upper_bound(data.begin(), data.end(), 3);
A sorted vector demonstrates the general upper_bound algorithm alongside lower_bound. section 7.2.2
Finding a range in a multimap
For a multimap, dictionary.equal_range(key) supplies iterators spanning every value with that key. For a word stem, an upper-bound key beyond the possible stem values provides the range’s endpoint. section 7.2.3
