Folding over two parameter packs

[stone idol]

I am trying to implement a multi dimensional array for educational(personal, this is not an assignment) purposes and am trying to implement the underlying data as a single dimensional array. I know that in order to translate a index I need to use either row major or column major formula but I cannot figure out how to do this using template folding (looks impossible via online) so I was wondering how I could go about trying this.

for reference:

struct array_impl<T, std::index_sequence<dimensions...>> {
        template <typename Type, auto>
        using id = Type;

        T& operator[](id<std::size_t, dimensions>... idx) {
                  // How do I compare each value in idx to the appropriate value in dimensions?
                }
}

Row Major formula:
// (i1 to in): Array[i1][i2]...[in] = (i1 * s2 * ... * s(n - 1) * sn + i2 * ... * s(n - 1) * sn + ... + i(n - 1) * sn + in)
Where i is an index to grab within a dimension and s is the maximum size of that dimensions

[worn patio]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For more information use !howto ask.

[tulip tartan]

using a constexpr function would be a lot simpler tbh

[stone idol]

How would that work?

[tulip tartan]

you can fairly easily create an array with the integer values of the packs, then index into the arrays to get the desired value out

template <typename T, std::size_t ... dimensions>
struct nd_array
{
  static constexpr std::size_t to_flat_index(id<std::size_t, dimensions>... indices)
  {
    constexpr std::size_t easy_dimensions[] = { dimensions..., 1 };
    const std::size_t easy_indices[] = { indices... };

    std::size_t result = 0;
    for (std::size_t i = 0; i < sizeof...(dimensions); ++i)
      result += easy_indices[i] * easy_dimensions[i+1];
    return result;
  }
};

or something

[stone idol]

Alrighty, thanks, just out of curiosity would the constexpr array be saved in memory?

Not really concerned just curious if would be moved to its constant values or not

[tulip tartan]

probably depends

for few enough dimensions, there are good odds that the values will get hard-coded into whatever operation is done on the indices

and that the loop gets unrolled

[craggy glacier]

ime, you wanna do this recursively

[mint sleet]

BTW you can have two packs in the same function, as long as they are of equal length.

[tulip tartan]

in terms of codegen?

haven't really looked at it tbh

[craggy glacier]

well, also in terms of readability ^^

sec

[stone idol]

Yeah I saw that but to my incredibly limited knowledge it didnt like the fold expression involving it

[craggy glacier]

we had someone ask exactly this here not too long ago

[stone idol]

Can you?

[craggy glacier]

ofc

[stone idol]

I didnt think you could have 2 packs in one function template

[tulip tartan]

you mean the whole array thing would be recursive?

or just the conversion of indices

[craggy glacier]

an n-dimensional array can be flattened into an n-1-dimensional array can be flattened into…1-d array…

[tulip tartan]

cause for the whole thing, that'd probably be a lot shorter and simpler

[craggy glacier]

also, since you're using C++23 anyways, didn't mdspan get in?

[stone idol]

Yeah that was what I intended to do but I dont know how you can do that with 2 template packs (dimension size and index)

[craggy glacier]

recursively peel off the dimensions 🤷‍♂️

[stone idol]

Probably but im just trying to tinker around and try it

[craggy glacier]

think about what kind of expression you want to generate

[stone idol]

So would you just merge the two packs into one then use that?

[craggy glacier]

you can't do it in a single fold expression i think

but you can do it recursively

i mean it's certainly possible because i've done it many times ^^

[stone idol]

Do you have time to show me how it can be done recursively?

I don't think I quite see how

[craggy glacier]

think about what you want to end up with. basically, you want to generate

((D_3 * i_3) + i_2) * D_2 + i_1) * D_0 + i_0

the recurring pattern there is

(index_1..N) * D_0 + i_0

[tulip tartan]

with this I'm "more" sure that I've understood where you wanted the recursion, and that my codegen test is somewhat relevant

haven't really noticed much of a codegen diff on gcc, and I crashed clang in one version I tested, but for the others the codegen looked equivalent

[tulip tartan]

for completeness of my comparisons, I thought I'd implement the exact principle of the formula you gave, but that's actually really annoying
the original post wanted to use row-major, but guessing based on the notation, you gave the column-major formula

to implement row-major recursively with the recursion you suggested, you'd have to start by using values from the end of the pack

[stone idol]

Yeah I implemented Sly's solution and got it working, I still dont see how I could do this recursively unless there is some helper function to reverse a pack

But im going to mark it as solved

Thanks to both of you

!solved

[worn patio]

Thank you and let us know if you have any more questions!

[SOLVED] Folding over two parameter packs

[worn patio]

@stone idol

This question thread is being automatically marked as solved.