如何在编译时在 C++ 中将 n 维矩阵中的位置映射到 1D？

Question

我必须在编译期间计算元素在一维数组内的 n 维矩阵中的位置。简而言之，一个 array[i][j][k]....[n] -> array[...] 的映射，其中 i,j,k,...,n 在 {1,2,3} 中，每个索引的维度是 DIM = 3。也就是说，每一行和每一列都有 3 个元素。

我的主要问题是编写 n 索引（参数包）的总和作为模板，并使用 constexpr 在编译时计算总和。

我在其他堆栈中的研究 post 得出以下 3 维公式：

    a[i][j][k] -> a[(i*DIM*DIM) + (j*DIM) + k]

如果我们将其扩展到 n 个维度，则得到以下公式：

    a[i][j][k]....[n] -> a[(n*DIM ^ (indexAmount-1)] +... + (i*DIM*DIM) + (j*DIM) + k].

此外，i 编写了使用模板和 constexpr 生成和的加数的代码，如下面的代码所示。

    /**
    * calculates DIM3^(indexPos)
    */
    template<auto count>
    int constexpr multiple_dim(){
        if constexpr (count == 0){
            return 1;
        }else{
            return DIM3 * multiple_dim<count-1>();
        }
    }

    /**
    *
    *calculates addends for the end summation
    * e.g if we have 3 indices i,j,k. j would be at position 2
    * and j = 1. The parameters would be IndexPos = 2, index = 1.

    */
    template<auto indexPos, auto index>
    int constexpr calculate_flattened_index(){
        if constexpr (indexPos == 0){
            return (index-1);
        }else{
            return (index-1) * multiple_dim<indexPos>();
        }
    }

    /**
     * calculates the position of an element inside a
     * nD matrix and maps it to a position in 1D
     * A[i][j]..[n] -> ???? not implemented yet
     * @tparam Args
     * @return
     */
    template<auto ...Args>
    [[maybe_unused]] auto constexpr pos_nd_to_1d(){
     /* maybe iterate over all indices inside the parameter pack?
        const int count = 1;
        for(int x : {Args...}){

        }
        return count;
    */
    }

3D 矩阵中元素的示例输出 A。 A111、A121、A131。 3 个元素的总和将是 1D 中的位置。例如 A121 -> 0 + 3 + 0 = 3。 A111 将被放置在一维数组中 array[3]。

    std::cout << "Matrix A111" << std::endl;
    //A111
    std::cout << calculate_flattened_index<0 , 1>() << std::endl;
    std::cout << calculate_flattened_index<1 , 1>() << std::endl;
    std::cout << calculate_flattened_index<2 , 1>() << std::endl;
    std::cout << "Matrix A121" << std::endl;
    //A121
    std::cout << calculate_flattened_index<0 , 1>() << std::endl;
    std::cout << calculate_flattened_index<1 , 2>() << std::endl;
    std::cout << calculate_flattened_index<2 , 1>() << std::endl;
    std::cout << "Matrix A131" << std::endl;
    //A131
    std::cout << calculate_flattened_index<0 , 1>() << std::endl;
    std::cout << calculate_flattened_index<1 , 3>() << std::endl;
    std::cout << calculate_flattened_index<2 , 1>() << std::endl;

    Output:
    Matrix A111
    0
    0
    0
    Matrix A121
    0
    3
    0
    Matrix A131
    0
    6
    0

所需的输出可能类似于以下代码：

函数调用

    pos_nd_to_1d<1,1,1>() //A111 
    pos_nd_to_1d<1,2,1>() //A121 
    pos_nd_to_1d<1,3,1>() //A131

输出：

    0 //0+0+0
    3 //0+3+0
    6 //0+6+0

Answer 1

如果我没理解错的话...你看起来是这样的

template <auto ... as>
auto constexpr pos_nd_to_1d ()
 { 
   std::size_t  i { 0u };

   ((i *= DIM, i += as - 1u), ...);

   return i;
 }

或者您可以使用 std::common_type，用于 i，

std::common_type_t<decltype(as)...>  i {};

但对于索引，我建议使用 std::size_t（也 std::size_t ... as）。

下面是一个完整的编译示例

#include <iostream>

constexpr auto DIM = 3u;

template <auto ... as>
auto constexpr pos_nd_to_1d ()
 { 
   std::size_t  i { 0u };

   ((i *= DIM, i += as - 1u), ...);

   return i;
 }


int main ()
 {
   std::cout << pos_nd_to_1d<1u, 1u, 1u>() << std::endl;
   std::cout << pos_nd_to_1d<1u, 2u, 1u>() << std::endl;
   std::cout << pos_nd_to_1d<1u, 3u, 1u>() << std::endl;
 }

-- 编辑 --

OP 问

could you explain how this code works?I am a bit new to c++.

无论如何，我更擅长编码，更擅长解释...

我在这里使用了什么

   ((i *= DIM, i += as - 1u), ...);
//...^^^^^^^^^^^^^^^^^^^^^^   repeated part

称为“fold expression”（或 "folding" 或 "template folding"），是一个新的 C++17 功能（您也可以在 C+ 中获得相同的结果+14（也是 C++11 但不是 constexpr），但以一种不太简单和优雅的方式），包括使用运算符扩展可变参数模板包。

举个例子，如果你想对索引求和，你可以简单地写

(as + ...);

表达式变为

(a0 + (a1 + (a2 + (/* etc */))));

在这种情况下，我使用逗号作为运算符这一事实，因此表达式

   ((i *= DIM, i += as - 1u), ...);

成为

   ((i *= DIM, i += a0 - 1u), 
     ((i *= DIM, i += a1 - 1u),
        ((i *= DIM, i += a2 - 1u),
           /* etc. */ )))))

观察，这样，第一个i *= DIM是没有用的（因为i初始化为零）但是后面的i *= DIM乘以as - 1u正确的数次

因此，当 as... 为 1, 2, 1 时，例如，您得到

  (1 - 1)*DIM*DIM + (2 - 1)*DIM + (1 - 1)

如何在编译时在 C++ 中将 n 维矩阵中的位置映射到 1D？

How do I map a position in a n dimensional matrix to 1D, in C++ at compile time?

templates

matrix

template-meta-programming

variadic-templates

c++17