lower_bound returns the first position whose element is greater than or equal to a queried value. Map, set, and multiset provide member functions; std::lower_bound also works with ordered elements such as a sorted vector. section 7.2.2
Use the result to:
- Test whether a value exists by comparing lower_bound with upper_bound: matching positions mean the value is absent. section 7.2.2
- Work through all values for a multimap key by using the iterator range returned by equal_range. section 7.2.3
- Find an insertion position without checking every earlier element in a sorted sequence. section 7.2.2
Searching a sorted vector
For {1, 2, 4, 5, 6, 7}, querying 3 makes lower_bound point to 4, the first element not less than 3. equal_range returns both bounds together.
Listing 7.8 Finding an overlapping word more efficiently
std::pair<std::string, int> find_overlapping_word(std::string word,
const std::map<std::string, std::string>& dictionary)
{
size_t offset = 1;
while (offset < word.size())
{
auto stem = word.substr(offset);
auto [lb, ub] = dictionary.equal_range(stem); #1
if (lb != dictionary.end() &&
stem == lb->first.substr(0, stem.size())) #2
{
return {lb->first, offset}; #3
}
++offset;
}
return {"", -1};
}
A word-overlap function uses equal_range on a dictionary to locate a matching stem while avoiding potentially checking every key. section 7.2.2
