Take this
#include <range/v3/view/remove_if.hpp>
#include <range/v3/range/conversion.hpp>
#include <vector>
std::vector<int> foo(std::vector<int> v, bool(*p)(int)) {
return v | ranges::views::remove_if(p) | ranges::to_vector;
}
as compared to this
#include <range/v3/action/remove_if.hpp>
#include <vector>
std::vector<int> bar(std::vector<int> v, bool(*p)(int)) {
return std::move(v) | ranges::actions::remove_if(p);
}
No templates around, just two TUs providing each a pure function with the same signature. Given their implementation, I would expect the two functions to accomplish the same task, from the caller's perspective. And that's what they seem to do.
However, they compile to fairly different code, to the point that GCC (trunk, at least) produces shorter code for the latter, whereas Clang (trunk) produces shorter code for the former.
I don't see any reason for the two functions to compile down to different code, other than "it's too hard for the compiler to come up with the same code for both", but what is making it so difficult? Or, if I'm wrong, why must the two functions compile down to different assembly?
And, other than benchmarking, is there a rationale why I should prefer one over the other implementation?
I'm not sure it's even theoretically possible that the two generate the same code. Let's go through the two approaches.
std::vector<int> bar(std::vector<int> v, bool(*p)(int)) {
return std::move(v) | ranges::actions::remove_if(p);
}
With actions, this is taking v, mutating it in place to remove the elements that satisfy p, and returning the same v back. This is equivalent to having written:
std::vector<int> bar(std::vector<int> v, bool(*p)(int)) {
std::erase_if(v, p);
return v;
}
Or, from before C++20:
std::vector<int> bar(std::vector<int> v, bool(*p)(int)) {
v.erase(std::remove_if(v.begin(), v.end(), p), v.end());
return v;
}
There is definitely no allocation that happens, we're just moving a bunch of ints around and then changing v.size().
std::vector<int> foo(std::vector<int> v, bool(*p)(int)) {
return v | ranges::views::remove_if(p) | ranges::to_vector;
}
views::remove_if is a lazy filter. That gives us a view over the elements of v that do not satisfy p. Then, to_vector is going to construct a new vector, which requires allocation, and copying all the elements of v that do not satisfy p into a new vector. That new vector is returned.
Initially, the expression v | remove_if(p) | to_vector allocates a new vector<int> that is distinct from v. v is alive for the entire length of this expression, so you cannot reuse v's memory here.
The optimization here wouldn't just be to recognize that v is imminently being destroyed and so its allocation can be reused. But also that the new vector is at most the same size as v so reusing its allocation is a viable strategy. But also that the elements of this new vector are populated in a way that allows reusing that allocation.
Fundamentally, the two cases are just different algorithms. Sometimes compilers can figure that out, but this seems like such a huge stretch. If such an optimization existed, it would basically be hand-crafted for this scenario.
And which should I prefer and why?
In general, the answer to this question is going to be to use the most specific tool for the job. If you have a vector<int> and you just want the elements that don't satisfy p and you don't need the original elements at all - that's actions::remove_if (or, depending on context, just a direct call to std::erase_if). That's the job that actions::remove_if is built to solve.
If you don't need a container of all the elements that satisfy p and just need to on-demand pick (some) of them - that's views::remove_if.
Sometimes eager is better. Sometimes lazy is better. It really depends on the problem.