如何实现可变参数的cartesian_product_with_filter函数？

我正尝试实现一个计算范围笛卡尔积的函数，已经知道有views::zip和views::cartesian_product可用，但想用for_each和yield_if来实现，以此加深对Range库的理解。

固定数量范围的版本很容易实现（如下方代码），但我没法把它改成支持任意数量范围的函数。我查过相关文档，里面的find_tuples_satisfying和我的代码思路类似，但它返回的是容器而不是视图。

我期望的函数签名是：

template <typename Pred, std::ranges::viewable_range... Ranges>
  requires std::predicate<Pred&, std::ranges::range_reference_t<Ranges>...>
[[nodiscard]] constexpr auto cartesian_product_with_filter(Pred pred,
                                                           Ranges&&... ranges)
    -> std::ranges::view auto;

当前固定3个范围的实现代码 #

#include <concepts>
#include <ranges>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

#include <fmt/core.h>
#include <fmt/ranges.h>
#include <range/v3/all.hpp>

inline constexpr auto for_each{[] [[nodiscard]] (auto&& function) {
  return std::views::transform(std::forward<decltype(function)>(function))
         | std::views::join;
}};

inline constexpr auto yield_if{
    [] [[nodiscard]] (bool should_yield, auto&& value) {
      return ranges::views::repeat_n(std::forward<decltype(value)>(value),
                                     should_yield ? 1 : 0);
    }};

[[nodiscard]] constexpr auto cartesian_product_with_filter(auto pred,
                                                           auto&& range1,
                                                           auto&& range2,
                                                           auto&& range3)
    -> std::ranges::view auto{
  return range1 | for_each([&pred, &range2, &range3](auto&& value) {
           return range2 | for_each([&pred, &range3, value](auto&& value2) {
                    return range3
                           | for_each([&pred, value, value2](auto&& value3) {
                               return yield_if(
                                   pred(value, value2, value3),
                                   std::tuple{value, value2, value3});
                             });
                  });
         });
}

auto main() -> int {
  std::vector<int> const vec1{1, 2, 3};
  std::vector<std::string> const vec2{"hello", "world"};
  std::vector<double> const vec3{1.2, 3.4, 8.7};
  fmt::print(
      "{}\n",
      fmt::join(cartesian_product_with_filter(
                    [](int value, auto&&, auto&&) { return value % 2 == 1; },
                    vec1, vec2, vec3),
                "\n"));
}

解决方案 #

要实现支持任意数量范围的版本，我们可以用递归模板展开结合Range的视图组合来实现，核心思路是逐步构建元组，最后对完整的元组应用过滤条件：

#include <concepts>
#include <ranges>
#include <tuple>
#include <utility>
#include <vector>

#include <fmt/core.h>
#include <fmt/ranges.h>
#include <range/v3/all.hpp>

inline constexpr auto for_each{[] [[nodiscard]] (auto&& function) {
  return std::views::transform(std::forward<decltype(function)>(function))
         | std::views::join;
}};

inline constexpr auto yield_if{
    [] [[nodiscard]] (bool should_yield, auto&& value) {
      return ranges::views::repeat_n(std::forward<decltype(value)>(value),
                                     should_yield ? 1 : 0);
    }};

// 递归终止：处理最后一个范围，将累积的元组与当前元素组合后过滤
template <typename Pred, typename AccumulatedTuple, std::ranges::viewable_range LastRange>
[[nodiscard]] constexpr auto cartesian_filter_impl(Pred pred, AccumulatedTuple&& acc, LastRange&& last_range)
    -> std::ranges::view auto {
  return last_range | for_each([pred = std::move(pred), acc = std::forward<AccumulatedTuple>(acc)](auto&& elem) {
    auto full_tuple = std::tuple_cat(std::move(acc), std::tuple{std::forward<decltype(elem)>(elem)});
    // 用std::apply将元组元素展开传入谓词
    return yield_if(std::apply(pred, full_tuple), std::move(full_tuple));
  });
}

// 递归步骤：处理当前范围，将当前元素加入累积元组，继续递归处理剩余范围
template <typename Pred, typename AccumulatedTuple, std::ranges::viewable_range FirstRange, std::ranges::viewable_range... RestRanges>
[[nodiscard]] constexpr auto cartesian_filter_impl(Pred pred, AccumulatedTuple&& acc, FirstRange&& first_range, RestRanges&&... rest_ranges)
    -> std::ranges::view auto {
  return first_range | for_each([pred = std::move(pred), acc = std::forward<AccumulatedTuple>(acc), &rest_ranges...](auto&& elem) {
    auto new_acc = std::tuple_cat(std::move(acc), std::tuple{std::forward<decltype(elem)>(elem)});
    return cartesian_filter_impl(std::move(pred), std::move(new_acc), std::forward<RestRanges>(rest_ranges)...);
  });
}

// 对外接口：初始化累积元组为空元组，启动递归
template <typename Pred, std::ranges::viewable_range... Ranges>
  requires std::predicate<Pred&, std::ranges::range_reference_t<Ranges>...>
[[nodiscard]] constexpr auto cartesian_product_with_filter(Pred pred, Ranges&&... ranges)
    -> std::ranges::view auto {
  static_assert(sizeof...(Ranges) > 0, "At least one range is required");
  return cartesian_filter_impl(std::move(pred), std::tuple{}, std::forward<Ranges>(ranges)...);
}

auto main() -> int {
  std::vector<int> const vec1{1, 2, 3};
  std::vector<std::string> const vec2{"hello", "world"};
  std::vector<double> const vec3{1.2, 3.4, 8.7};
  std::vector<char> const vec4{'a', 'b'};

  // 测试3个范围的情况
  fmt::print("3 ranges:\n{}\n\n",
      fmt::join(cartesian_product_with_filter(
                    [](int value, auto&&, auto&&) { return value % 2 == 1; },
                    vec1, vec2, vec3),
                "\n"));

  // 测试4个范围的情况
  fmt::print("4 ranges:\n{}\n",
      fmt::join(cartesian_product_with_filter(
                    [](int v1, auto&&, double v3, char v4) { return v1 %2 ==1 && v3 >2 && v4 == 'a'; },
                    vec1, vec2, vec3, vec4),
                "\n"));
}

实现说明 #

• 递归模板：通过两个重载的cartesian_filter_impl函数实现递归展开：
  • 终止版本处理最后一个范围，将累积的元组与当前元素拼接，用std::apply把元组元素展开传入谓词，满足条件则返回该元组的单元素视图。
  • 递归版本处理当前范围，将当前元素加入累积元组，继续递归处理剩余范围。
• 对外接口：cartesian_product_with_filter初始化空元组作为累积起点，调用递归函数，同时添加了至少一个范围的静态断言。
• 视图特性：整个实现完全基于视图组合，不会提前生成所有笛卡尔积元素，符合Range库的惰性求值特性。

内容的提问来源于stack exchange，提问作者FeignClaims