Possible implementation of std::equal_range

Question

std::equal_range documentation on cppreference.com shows a possible implementation:

template<class ForwardIt, class T>
std::pair<ForwardIt,ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last,
                const T& value)
{
    return std::make_pair(std::lower_bound(first, last, value),
                          std::upper_bound(first, last, value));
}

but this looks more optimal while still pretty simple:

template<class ForwardIt, class T>
std::pair<ForwardIt,ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last,
                const T& value)
{
    first = std::lower_bound(first, last, value);
    return std::make_pair(first,
                          std::upper_bound(first, last, value));
}

as this solution is pretty obvious, is there any reason it is not used?

Answer 1

The implementation given on cppreference is a possible implementation, not necessarily the most optimized implementation. I think it was included for clarity's sake so that a reader could get a better feel for what the algorithm is doing internally rather than as a guide for the fastest of all possible implementations.

As long as you're optimizing the implementation, you might consider having some logic to check if the range is small and, if so, to use a linear search instead of a binary search.

It might be helpful to look at an actual implementation to see how it's structured. Take a look at, say, the libstdc++ implementation, which is exceptionally dense and much harder to read than the clearer but less efficient version given at cppreference. That version - as of the time of this writing - uses a totally different approach:

1. Use an initial binary search to search for any copy of the element.
2. Use secondary binary search on the remaining window to find the first and last copies of the elements in that range.

That approach is likely to be even faster than what you're proposing, since a lot of work from the two binary searches can be shared.