Span referred to a continuous memory, for example an array;
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 function can iterating all passing spans, like a nested bubbling loop;
template <typename Func, typename ...Spans>
void loop(Func func, Spans &&...spans) {
// question: how to implements ?
}
example
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);
...
*/
}
how to implements the loop function, using c++ language features up to c++20 is ok, but no standard library or 3rd-part library, just implements manually;
no recursion function call, better for loop; cause recursion easily get stack overflow;
using vector and tuple, structure binding is ok;
Span referred to a continuous memory, for example an array;
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 function can iterating all passing spans, like a nested bubbling loop;
template <typename Func, typename ...Spans>
void loop(Func func, Spans &&...spans) {
// question: how to implements ?
}
example
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);
...
*/
}
how to implements the loop function, using c++ language features up to c++20 is ok, but no standard library or 3rd-part library, just implements manually;
no recursion function call, better for loop; cause recursion easily get stack overflow;
using vector and tuple, structure binding is ok;
Share Improve this question edited 2 days ago Ashcoll Ash asked Feb 18 at 2:47 Ashcoll AshAshcoll Ash 435 bronze badges New contributor Ashcoll Ash is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct. 8 | Show 3 more comments4 Answers
Reset to default 8With C++23 this is much easier thanks to std::views::cartesian_product():
godbolt
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);
}
}
If you're limited to C++20 then you'll have to do the cartesian product yourself - for example by using recursion and binding the current value for each span to the function:
godbolt
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);
}
}
}
No Standard Library Implementation: (as requested in the comments)
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);
}
}
}
Here is an alternative that uses an array to keep track of the indices for each of the spans. The index array is declared to have nSpans+1 elements where the first element serves as a sentinel. The array spanSizes is declared to be the same size and also have a sentinel. The variable carryIndex keeps track of which index should be incremented. The word "carry" here refers to the fact that the indices are incremented in a manner similar to carries in additions.
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;
}
}
}
}
Demo: https://godbolt./z/ejzhe7e5G (The main() is taken from demo in the answer by @Turtlefight)
You can combine ranges::for_each with C++23 views::cartesian_product like:
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); }
);
}
Here is a simplification of an answer of this post that allows to generate at compile time the Cartesian product of several arrays.
#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);
}
Demo
The main idea is to iterate an integer i from 0 to N-1 (with N the number of possible entries of the Cartesian product) and from this 'global' integer, one retrieves as a tuple the index idx of each array that make the current entry. Then one has just to call the provided function fct with arguments being a fold expression on this index idx.
It mainly uses fold expressions and std::make_index_sequence / std::index_sequence. It also supposes that the provided arrays support operator[] and size methods.
It works with c++17 and above.
std::views::cartesian_productthat returnsstd::tuple. Then you would need some template metaprogramming to unpack the tuple into individual function args. But you wanted C++20. – Eugene Commented Feb 18 at 4:06requiresclause, which you can drop if you want. – Weijun Zhou Commented 2 days ago