Locating patterns in strings with std::search and choosing the optimal implementation

Searching for a string in a string is a slightly different problem than finding one object in a range. On the one hand, a string is, of course, an iterable range (of characters) too. On the other hand, finding a string in a string means finding a range in another range. And this comes along with multiple comparisons per potential match position, so we need some other algorithm for that.

std::string already contains a find function, which can do exactly what we are talking about; nevertheless we'll concentrate on std::search in this section. Although std::search might be used on strings mostly, it works on all kinds of containers. The more interesting feature of std::search is that since C++17, it has a slightly different additional interface and allows for simply exchanging the search algorithm itself. These algorithms are optimized and can be freely chosen by the user, depending on what is better in which...