Yesterday, a contributor to one of my open source projects (Robert) pointed out to me that std::find_if(f, l, pred) != l is just std::any_of(f, l, pred). I totally missed this while refactoring even though it is implicitly covered in my STL Algorithm Cheatsheet:
So thank you Robert for pointing it out! And because of this I decided to write up a short blog about the following:
Always choose the most specialized algorithm.
Below is a diagram that captures the specializations / relationships between std::find_if, std::any_of and all of the std::mismatch algorithms.
I assert that you should always choose the most specialized algorithm, aka the algorithm that is furthest from mismatch that works for your problem. Here are a couple of C++ snippets that show how you can implement these in terms of each other. The implementations also double as examples of code that should just be replaced by the more specialized / better named algorithm.
auto adjacent_find(auto f, auto l, auto pred) {
return std::mismatch(f, std::prev(l), std::next(f), pred).first;
}
auto is_sorted_until(auto f, auto l, auto comp = std::less_equal{}) {
return std::adjacent_find(f, l, std::not_fn(comp));
}
auto is_sorted(auto f, auto l, auto comp = std::less_equal{}) {
return std::is_sorted_until(f, l, comp) == l;
}
auto equal(auto f, auto l, auto f2) {
return std::mismatch(f, l, f2, std::not_equal_to{}).first == l;
}
auto find_if(auto f, auto l, auto pred) {
return std::mismatch(f, l, f, [&](auto a, auto b) {
return pred(a);
}).first;
}
auto any_of(auto f, auto l, auto pred) {
return std::find_if(f, l, pred) != l;
}
auto find(auto f, auto l, auto val) {
return std::find_if(f, l, [&](auto e) { return e == val; });
}
Update
Stephan T. Lavavej (aka STL, one of the MSVC Standard Library implementers) pointed out that is_partitioned_until and is_partitioned could be added to the diagram.
is_partitioned_until and is_partitioned could be added to the diagram, as they can be thought of as weaker versions of is_sorted.
— Stephan T. Lavavej (@StephanTLavavej) March 7, 2021
So I updated my diagram. Note that is_partitioned_until isn’t actually in the C++ Standard Library which is why it is in grey. The code snippets have been provided as well.
auto is_partitioned_until(auto f, auto l, auto pred) {
return std::next(std::adjacent_find(f, l, [&](auto a, auto b) {
return not pred(a) and pred(b);
}));
}
auto is_partitioned(auto f, auto l, auto pred) {
return is_partitioned_until(f, l, pred) != l;
}
Finally, I have received a couple comments on Reddit and Twitter asking “Why?” or stating that I did not provide any reasoning. That was an oversight on my part.
The motivation for choosing the most specialized algorithm is that it leads to simpler and more readable code.
The more specialized algorithms contain more meaning and therefore communicates more information to future readers of the code. For example, is_sorted is much more meaningful than adjacent_find with the greater function object or the less_equal function object + not_fn. Furthermore, code using more specialized algorithms is simpler. An example of this is that using many of the specialized algorithms avoids having to write != container.end().
That’s all. Happy coding!
Feel free to leave a comment on the reddit thread or tweet.