Given a constexpr std::array and an UnaryPredicate pred, how can I filter the array to return a new constexpr std::array which all of its elements meets pred(e)?
struct foo {
int f1;
int f2;
};
static constexpr std::array<foo, 5> arr{ foo{1,1}, {2,2}, {3,3}, {4,4}, {5,5} };
int main() {
// will result in { foo{1,1}, {2,2}, {4,4}, {5,5} }
constexpr auto filterd = filter_array(arr, [](const foo& f) {return f.f1 != 3;})
return 0;
}
it's definitely that, dependent type, the type that depends on a value, is impossible in present-day C++. you can't decide the size M of result type std::array<T, M> by only the function arguments, which means M must be a template argument.
so you have to provide an additional template argument M for the result type, by a constexpr function count_if, and then just decide each element to be which value:
template<size_t I, typename T, typename Pred, std::enable_if_t<I == 0, int> = 0>
constexpr T get_element_helper(T const* arr, Pred&& pred){
return pred(arr[0]) ? arr[0] : get_element_helper<0>(arr + 1, pred);
}
template<size_t I, typename T, typename Pred, std::enable_if_t<I != 0, int> = 0>
constexpr T get_element_helper(T const* arr, Pred&& pred){
return pred(arr[0]) ? get_element_helper<I - 1>(arr + 1, pred) : get_element_helper<I>(arr + 1, pred);
}
template<typename T, size_t N, typename Pred, size_t ...Is>
constexpr std::array<T, sizeof...(Is)> filter_array_helper(std::array<T, N> const& arr, Pred&& pred, std::index_sequence<Is...>*){
return { get_element_helper<Is>(arr.data(), pred)... };
}
template<size_t M, typename T, size_t N, typename Pred>
constexpr std::array<T, M> filter_array(std::array<T, N> const& arr, Pred&& pred){
return filter_array_helper(arr, std::forward<Pred>(pred), (std::make_index_sequence<M>*)nullptr);
}
template<typename T, size_t N, typename Pred, size_t... Is>
constexpr size_t count_if_helper(std::array<T, N> const& arr, Pred&& pred, std::index_sequence<Is...>*){
return ((size_t)(bool)pred(arr[Is]) + ...);
}
template<typename T, size_t N, typename Pred>
constexpr size_t count_if(std::array<T, N> const& arr, Pred&& pred){
return count_if_helper(arr, std::forward<Pred>(pred), (std::make_index_sequence<N>*)nullptr);
};
int main(){
constexpr std::array<int, 5> a = { 0, 1, 2, 3, 4 };
constexpr auto pred = [](int a){ return a % 2 == 0; };
constexpr auto b = filter_array<count_if(a, pred)>(a, pred); // std::array<int, 3>{0, 2, 4}
}
Since a lot of algorithm in <algorithm> is constexpr in C++20, we can just use it in meta-programming in a natural way:
#include <algorithm>
#include <array>
struct foo {
int f1;
int f2;
bool operator==(const foo&) const = default;
};
constexpr static std::array arr{foo{1,1}, foo{2,2}, foo{3,3}, foo{4,4}, foo{5,5}};
constexpr auto filter_array(auto pred) {
constexpr auto p = [=] {
auto res = arr;
auto size = std::distance(res.begin(), std::remove_if(res.begin(), res.end(), pred));
return std::pair{res, size};
}();
constexpr auto res = p.first;
constexpr auto size = p.second;
return [=]<auto... Is>(std::index_sequence<Is...>) {
return std::array{res[Is]...};
}(std::make_index_sequence<size>{});
}
int main() {
// will result in { foo{1,1}, {2,2}, {4,4}, {5,5} }
constexpr auto filterd = filter_array([](const foo& f) { return f.f1 == 3; });
static_assert(filterd == std::array{foo{1,1}, foo{2,2}, foo{4,4}, foo{5,5}});
}