主页 / coding / 问题 / 79447006
Accepted
Ashcoll Ash
Asked: 2025-02-18 10:47:52 +0800 CST

可变函数循环遍历多个跨度的笛卡尔积

  • 772

Span 指一段连续的内存，例如一个数组；

template <typename T>
class Span {
public:
    Span(T first, size_t s) ...;
    Span(T first, T lasst) ...;
public:
    // iterating underlying continuous memory;
    begin() ...
    end() ...
    T & operator[](idx) ...
private:
    T first;
    T last;
};

loop 函数可以迭代所有通过的 span，就像嵌套的冒泡循环一样；

template <typename Func, typename ...Spans>
void loop(Func func, Spans &&...spans) {
    // question: how to implements ?
}

例子

int main() {
    int arr[] {1, 2, 3};
    float arr2[] {1.1, 2.2};
    int arr3[] {-1, -2, -3};
    
    loop(func, Span(arr, 3), Span(arr2, 2));
    /*
        we can get:
        func(1, 1.1);
        func(1, 2.2);
        func(2, 1.1);
        func(2, 2.2);
        func(3, 1.1);
        func(3, 2.2);
    */

    loop(func, Span(arr, 3), Span(arr2, 2), Span(arr3, 3));
    /*
        we can get:
        func(1, 1.1, -1);
        func(1, 1.1, -2);
        func(1, 1.1, -3);
        func(1, 2.2, -1);
        func(1, 2.2, -2);
        func(1, 2.2, -3);
        func(2, 1.1, -1);
        func(2, 1.1, -2);
        ...
    */
}

如何实现循环函数，使用c++语言特性到c++20都可以，但是没有标准库或者第三方库，只能手动实现；

没有递归函数调用，最好使用 for 循环；因为递归容易导致堆栈溢出；

使用向量和元组，结构绑定就可以了；

c++

4 个回答

  1. 使用 C++23 后，这一点变得容易得多，因为std::views::cartesian_product()：

    戈德博尔

    template<class Fn, class... Spans>
void loop(Fn&& fn, Spans... spans) {
    for(auto tuple : std::views::cartesian_product(spans...)) {
        std::apply(std::forward<Fn>(fn), tuple);
    }
}

    如果您仅限于 C++20，那么您必须自己做笛卡尔积 - 例如通过使用递归并将每个跨度的当前值绑定到函数：

    戈德博尔

    template<class Fn, class FirstSpan, class... OtherSpans>
requires std::ranges::range<FirstSpan> && (std::ranges::range<OtherSpans> && ...)
void loop(Fn&& fn, FirstSpan first, OtherSpans... otherSpans) {
    for(auto& el: first) {
        if constexpr(sizeof...(OtherSpans) > 0) {
            loop(std::bind_front(fn, el), otherSpans...);
        } else {
            fn(el);
        }
    }
}

    没有标准库实现：（如评论中所要求）
    godbolt

    template<class Fn, class Span, class... OtherSpans>
void loop(Fn&& fn, Span firstSpan, OtherSpans... otherSpans) {
    if constexpr(sizeof...(OtherSpans) > 0) {
        for(auto& el : firstSpan) {
            loop(
                [&](auto&... values) {
                    fn(el, values...);
                },
                otherSpans...
            );
        }
    } else {
        for(auto& el : firstSpan) {
           fn(el);
        }
    }
}
    • 8

  2. 您可以ranges::for_each与 C++23结合使用views::cartesian_product，例如：

    template <typename Func, typename ...Spans>
void loop(Func func, Spans &&...spans) {
  std::ranges::for_each(
    std::views::cartesian_product(spans...),
    [&](auto&& elem) { std::apply(func, elem); }
  );
}
    • 1

  3. 这是对该帖子答案的简化，允许在编译时生成多个数组的笛卡尔积。

    #include <tuple>
#include <array>
#include <type_traits>
#include <iostream>

////////////////////////////////////////////////////////////////////////////////
template<typename FCT, typename...ARRAYS>
constexpr auto cartesian_product_loop (FCT fct, ARRAYS...arrays)
{
    // we define the number of entries
    constexpr std::size_t N = (1 * ... * arrays.size());

    // we compute the dimensions of the successive parts of the tensor
    std::array<std::size_t,sizeof...(arrays)> dims { arrays.size()... };
    for (std::size_t i=1; i<dims.size(); ++i)  { dims[i] *= dims[i-1]; }
        
    // we iterate each possible entry
    for (std::size_t i=0; i<N; ++i)
    {
        [&]<std::size_t... Is>(std::index_sequence<Is...>) 
        {
           // we demultiplex the current index for each array from the global index 'i'
           auto idx = std::make_tuple ( ( (i*std::get<Is>(dims)) / N) % arrays.size() ...);

           // we call the function with the current entry.
           fct (arrays[std::get<Is>(idx)]...);
            
        }(std::make_index_sequence<sizeof...(arrays)>{});
    }
}

////////////////////////////////////////////////////////////////////////////////

int main() 
{
    std::array<int,   3> a1  {1, 2, 3}; 
    std::array<char,  2> a2  {'a','b'}; 
    std::array<double,4> a3  {2.0, 4.0, 6.0, 8.0}; 

    auto fct = [] (auto...args)
    {
        ((std::cout << args << ' '), ...) << "\n";
    };
    
    cartesian_product_loop (fct, a1,a2,a3);
}

    演示

    主要思想是迭代一个i从 0 到 N-1 的整数（N 是笛卡尔积的可能条目数），然后从这个“全局”整数中检索idx构成当前条目的每个数组的索引作为元组。然后，只需调用提供的函数fct，参数是此索引上的折叠表达式idx。

    它主要使用折叠表达式和std::make_index_sequence/ std::index_sequence。它还假定提供的数组支持operator[]和size方法。

    它适用于 c++17 及更高版本。

    • 1
  4. Best Answer

    这里有一个替代方案，它使用一个数组来跟踪每个跨度的索引。索引数组被声明为具有nSpans+1元素，其中第一个元素用作标记。数组spanSizes被声明为相同的大小，并且也有一个标记。变量carryIndex跟踪应该增加哪个索引。这里的“进位”一词指的是索引以类似于加法中的进位的方式增加的事实。

    template<class Fn, class... Spans>
void loop(Fn&& fn, Spans... spans) {
    constexpr std::size_t nSpans = sizeof...(spans);
    // Array containing the sizes of each span, with a sentinel in front
    std::size_t spanSizes[]{0, spans.size()...};
    // Array containing the loop indexes, also with a sentinel in front
    std::size_t indexes[nSpans+1]{};
    // Points to the index that should be incremented, after considering carries from less significant indexes
    std::size_t carryIndex = nSpans;
    // While the sentinel (most significant index) is not reached
    while(indexes[0] == 0){
        // Call `fn` with perfect forwarding, passing in elements picked from each span according to the corresponding index.
        // The +1 accounts for the sentinel.
        [&]<std::size_t... Is>(std::index_sequence<Is...>){
            std::forward<Fn>(fn)(spans[indexes[Is+1]]...);
        }(std::make_index_sequence<nSpans>());
        // Increment the current index.
        ++indexes[nSpans];
        // Loop while there's need to carry to a more significant index
        while(indexes[carryIndex] == spanSizes[carryIndex]){
            // Reset the index.
            indexes[carryIndex] = 0;
            // Update `carryIndex` to point to the next more significant index and increment it.
            ++indexes[--carryIndex];

            // The next increment should start over from the least significant index.
            if(indexes[carryIndex] != spanSizes[carryIndex]){
                carryIndex = nSpans;
            }
        }
    }
}

    演示：https://godbolt.org/z/ejzhe7e5G（main()取自@Turtlefight 回答中的演示）

    • 1

相关问题