These are the search algorithms we have used in this recipe:
| Algorithm | Purpose |
| std::find | Accepts a search range and a comparison value as arguments. Returns an iterator that points to the first item equal to the comparison value. Searches linearly. |
| std::find_if | Works like std::find but uses a predicate function instead of a comparison value. |
| std::binary_search | Accepts a search range and a comparison value as arguments. Performs a binary search and returns true if the range contains that value. |
| std::lower_bound | Accepts a search range and a comparison value, and then performs a binary search for the first item that is not smaller than the comparison value. Returns an iterator pointing to that item. |
| std::upper_bound | Works like std::lower_bound but returns an iterator to the first item that is larger than the comparison value. |
| std::equal_range | Accepts a search range and a comparison value and, then, returns a pair of iterators. The first iterator is the result of std::lower_bound and the second iterator is the result of std::upper_bound. |
All these functions accept custom comparison functions as an optional additional argument. This way, the search can be customized, as we did in the recipe.
Let's have a closer look at how std::equal_range works. Imagine that we have a vector, v = {0, 1, 2, 3, 4, 5, 6, 7, 7, 7, 8}, and call equal_range(begin(v), end(v), 7); in order to perform a binary search for the value 7. As equal_range returns us a pair of lower bound and upper bound iterators, these should afterward denote the range {7, 7, 7}, as there are so many values of 7 in the sorted vector. Check out the following diagram for more clarity:
At first, equal_range uses the typical binary search approach until it trips into the range of values not smaller than the search value. Then, it splits up to a lower_bound call and an upper_bound call in order to bundle their return values in a pair as the return value.
In order to get a binary search function, which just returns the first item that fits the requirements, we could implement the following:
template <typename Iterator, typename T>
Iterator standard_binary_search(Iterator it, Iterator end_it, T value)
{
const auto potential_match (lower_bound(it, end_it, value));
if (potential_match != end_it && value == *potential_match) {
return potential_match;
}
return end_it;
}
This function uses std::lower_bound in order to find the first item not smaller than value. The resulting potential_match can then have three different cases it points to:
- No item is not smaller than value. In this case, it is identical to end_it.
- The first item that is not smaller than value is also larger than value. Therefore we must signal that we did not find it by returning end_it.
- The item that potential_match points to is equal to value. So, it is not only a potential match, but it is an actual match. Therefore we can return it.
If our type T does not support the == operator, it must at least support the < operator for the binary search. Then, we can rewrite the comparison to !(value < *potential_match) && !(*potential_match < value). If it is neither smaller, nor larger, then it must be equal.
One potential reason why the STL does not provide such a function out of the box is the missing knowledge about the possibility that there are multiple hits, as in the diagram where we have multiple values of 7.