使用奇怪的循环模板模式 (CRTP) 计算多维数组的线性索引
Computing the linear index of a multi-dimensional array when using the curiously recurring template pattern (CRTP)
我正在用 C++ 编写一个多维数组 class 并且想要它的静态和动态内存版本。根据我的 之一的回答,我使用 CRTP 定义了一个基础 class,然后它可以访问具有连续内存的相应数据容器(std::array 和 std::vector)在派生的 classes.
我希望在基础 class 本身中实现多维下标运算符(例如,访问 4x3 矩阵的 (1, 2) 条目,该矩阵的 12 个条目连续存储在内存中),以便以避免代码重复。请注意,我只是选择了下标运算符,因为它是最简单的 class 方法,可以说明我希望实现的目标。我试图将@Jarod42 给出的 的多维下标线性化解决方案应用到我的 CRTP 案例中。但是,我不确定如何在派生的 classes 中存储数组维度,以便在计算线性化索引时在基础 class 中推断它们。我希望下面的代码能清楚地说明我的问题(我正在使用 C++20 进行编译):
#include <array>
#include <cassert>
#include <vector>
/** Multi-dimensional Array Base Class with CRTP. */
template <class derived, class T>
class MultiDimArray
{
private:
constexpr derived& Derived() noexcept { return static_cast<derived&>(*this); }
constexpr const derived& Derived() const noexcept { return static_cast<const derived&>(*this); }
protected:
constexpr MultiDimArray() {}
public:
// I've butchered the syntax in the following subscript operators, but I hope it captures what I intend to do.
constexpr const T& operator()(HookTypeToPack<Derived().Dimensions, std::size_t> ...Is) const {
return *(this->Derived()[ComputeIndex<Derived().Dimensions...>(Is...)]);
}
constexpr T& operator()(HookTypeToPack<Derived().Dimensions, std::size_t> ...Is) {
return *(this->Derived()[ComputeIndex<Derived().Dimensions...>(Is...)]);
}
};
/** Static Multi-dimensional Array Class */
template <class T, std::size_t ...Dims>
class StaticMultiDimArray : public std::array<T, (Dims * ...)>,
public MultiDimArray<StaticMultiDimArray<T, (Dims * ...)>, T>
{
private:
constexpr static std::size_t nEntries = (Dims * ...);
constexpr static std::tuple<HookTypeToPack<Dims, std::size_t>...> Dimensions = std::make_tuple(Dims...);
friend MultiDimArray<StaticMultiDimArray<T, (Dims * ...)>, T>;
public:
constexpr StaticMultiDimArray() : std::array<T, nEntries>(InitStaticArray<T, nEntries>(0.0)) {}
};
/** Dynamic Multi-dimensional Array Class */
template <class T>
class DynamicMultiDimArray : public std::vector<T>, public MultiDimArray<DynamicMultiDimArray<T>, T>
{
private:
std::size_t nEntries;
std::tuple<...> Dimensions; // Not sure what to use here considering a tuple is immutable
friend MultiDimArray<DynamicMultiDimArray<T>, T>;
public:
DynamicMultiDimArray() : std::vector<T>() {}
template <typename ...Dims>
DynamicMultiDimArray(Dims ...dimensions) : std::vector<T>((dimensions * ...), 0.0) { Resize(dimensions...); }
template <typename ...Dims>
void Resize(Dims ...dimensions)
{
nEntries = (dimensions * ...);
this->resize(nEntries);
// store dimensions in Dimensions...
}
};
上面用到的支持函数InitStaticArray
、HookTypeToPack
、ComputeIndex
定义如下:
template <class T, std::size_t size>
constexpr auto InitStaticArray(const T& value)
{
std::array<T, size> arr;
std::fill(arr.begin(), arr.end(), value);
return arr;
}
template <std::size_t, typename T>
using HookTypeToPack = T;
template <std::size_t ...Dims>
constexpr std::size_t ComputeIndex(HookTypeToPack<Dims, std::size_t> ...multi_index)
{
constexpr std::size_t dims_arr[] = {Dims...};
std::size_t multi_index_arr[] = {multi_index...};
std::size_t index(0), factor(1);
for(int i = 0; i < sizeof...(Dims); i++)
{
assert(0 <= multi_index_arr[i] && multi_index_arr[i] < dims_arr[i]);
index += factor * multi_index_arr[i];
factor *= dims_arr[i];
}
assert(0 <= index && index < (Dims * ...));
return index;
}
任何人都可以给我一些关于如何在 StaticMultiDimArray
和 DynamicMultiDimArray
中存储数组维度的建议,以便可以在 MultiDimArray
中的 operator()
重载中适当地调用它们?
有几个选项。您已经暗示的一个:将维度存储在派生 class 中。但是,不要使用 std::tuple
;这允许每个元素具有不同的类型,而我们只希望每个维度的大小为 std::size_t
。对静态数组使用 std::array
,对动态数组使用 std::vector
:
template <class T, std::size_t ...Dims>
class StaticMultiDimArray :
public std::array<T, ...>,
public MultiDimArray<...>
{
constexpr static std::array dimensions{Dims...};
...
};
template <class T>
class DynamicMultiDimArray :
public std::vector<T>,
public MultiDimArray<...>
{
std::vector<std::size_t> dimensions;
...
};
您也不需要将 DynamicMultiDimArray
的构造函数设为模板,而是可以让它以 std:initializer_list
作为参数,如下所示:
DynamicMultiDimArray(std::initializer_list<std::size_t> dimensions) :
std::vector<T>(std::accumulate(dimensions.begin(), dimensions.end(), std::size_t{1}, std::multiplies<std::size_t>())),
Dimensions(dimensions) {}
是的,实际元素向量的初始化现在看起来很难看。我建议不要为此使用继承,而是使用组合。那么可以先初始化维度,再初始化数据的array/vector,并且可以在MultiDimArray
中创建一个成员变量来计算条目数:
template <class derived, class T>
class MultiDimArray {
...
constexpr std::size_t nEntries() const {
const auto &dimensions = Derived().dimensions;
return std::accumulate(dimensions.begin(), dimensions.end(), std::size_t{1}, std::multiplies<std::size_t>());
}
...
};
template <class T>
class DynamicMultiDimArray :
public MultiDimArray<...>
{
std::vector<std::size_t> dimensions;
std::vector<T> data;
...
public:
DynamicMultiDimArray(std::initializer_list<std::size_t> dimensions) :
Dimensions(dimensions),
data(nEntries()) {}
};
同样,您可以让 operator()
为索引取一个 std::initializer_list<std::size_t>
。使用它的代码如下所示:
DynamicMultiDimArray dimarr({3, 5, 7}); // create new array
...
std::cout << dimarr({1, 2, 3}) << '\n'; // print element at index 1, 2, 3
这避免了很多模板麻烦。您甚至可以考虑创建自定义多维索引类型而不是 std::initializer_list<std::size_t>
,这样可以更轻松地将索引存储在变量中并传递它们。
我正在用 C++ 编写一个多维数组 class 并且想要它的静态和动态内存版本。根据我的
我希望在基础 class 本身中实现多维下标运算符(例如,访问 4x3 矩阵的 (1, 2) 条目,该矩阵的 12 个条目连续存储在内存中),以便以避免代码重复。请注意,我只是选择了下标运算符,因为它是最简单的 class 方法,可以说明我希望实现的目标。我试图将@Jarod42 给出的
#include <array>
#include <cassert>
#include <vector>
/** Multi-dimensional Array Base Class with CRTP. */
template <class derived, class T>
class MultiDimArray
{
private:
constexpr derived& Derived() noexcept { return static_cast<derived&>(*this); }
constexpr const derived& Derived() const noexcept { return static_cast<const derived&>(*this); }
protected:
constexpr MultiDimArray() {}
public:
// I've butchered the syntax in the following subscript operators, but I hope it captures what I intend to do.
constexpr const T& operator()(HookTypeToPack<Derived().Dimensions, std::size_t> ...Is) const {
return *(this->Derived()[ComputeIndex<Derived().Dimensions...>(Is...)]);
}
constexpr T& operator()(HookTypeToPack<Derived().Dimensions, std::size_t> ...Is) {
return *(this->Derived()[ComputeIndex<Derived().Dimensions...>(Is...)]);
}
};
/** Static Multi-dimensional Array Class */
template <class T, std::size_t ...Dims>
class StaticMultiDimArray : public std::array<T, (Dims * ...)>,
public MultiDimArray<StaticMultiDimArray<T, (Dims * ...)>, T>
{
private:
constexpr static std::size_t nEntries = (Dims * ...);
constexpr static std::tuple<HookTypeToPack<Dims, std::size_t>...> Dimensions = std::make_tuple(Dims...);
friend MultiDimArray<StaticMultiDimArray<T, (Dims * ...)>, T>;
public:
constexpr StaticMultiDimArray() : std::array<T, nEntries>(InitStaticArray<T, nEntries>(0.0)) {}
};
/** Dynamic Multi-dimensional Array Class */
template <class T>
class DynamicMultiDimArray : public std::vector<T>, public MultiDimArray<DynamicMultiDimArray<T>, T>
{
private:
std::size_t nEntries;
std::tuple<...> Dimensions; // Not sure what to use here considering a tuple is immutable
friend MultiDimArray<DynamicMultiDimArray<T>, T>;
public:
DynamicMultiDimArray() : std::vector<T>() {}
template <typename ...Dims>
DynamicMultiDimArray(Dims ...dimensions) : std::vector<T>((dimensions * ...), 0.0) { Resize(dimensions...); }
template <typename ...Dims>
void Resize(Dims ...dimensions)
{
nEntries = (dimensions * ...);
this->resize(nEntries);
// store dimensions in Dimensions...
}
};
上面用到的支持函数InitStaticArray
、HookTypeToPack
、ComputeIndex
定义如下:
template <class T, std::size_t size>
constexpr auto InitStaticArray(const T& value)
{
std::array<T, size> arr;
std::fill(arr.begin(), arr.end(), value);
return arr;
}
template <std::size_t, typename T>
using HookTypeToPack = T;
template <std::size_t ...Dims>
constexpr std::size_t ComputeIndex(HookTypeToPack<Dims, std::size_t> ...multi_index)
{
constexpr std::size_t dims_arr[] = {Dims...};
std::size_t multi_index_arr[] = {multi_index...};
std::size_t index(0), factor(1);
for(int i = 0; i < sizeof...(Dims); i++)
{
assert(0 <= multi_index_arr[i] && multi_index_arr[i] < dims_arr[i]);
index += factor * multi_index_arr[i];
factor *= dims_arr[i];
}
assert(0 <= index && index < (Dims * ...));
return index;
}
任何人都可以给我一些关于如何在 StaticMultiDimArray
和 DynamicMultiDimArray
中存储数组维度的建议,以便可以在 MultiDimArray
中的 operator()
重载中适当地调用它们?
有几个选项。您已经暗示的一个:将维度存储在派生 class 中。但是,不要使用 std::tuple
;这允许每个元素具有不同的类型,而我们只希望每个维度的大小为 std::size_t
。对静态数组使用 std::array
,对动态数组使用 std::vector
:
template <class T, std::size_t ...Dims>
class StaticMultiDimArray :
public std::array<T, ...>,
public MultiDimArray<...>
{
constexpr static std::array dimensions{Dims...};
...
};
template <class T>
class DynamicMultiDimArray :
public std::vector<T>,
public MultiDimArray<...>
{
std::vector<std::size_t> dimensions;
...
};
您也不需要将 DynamicMultiDimArray
的构造函数设为模板,而是可以让它以 std:initializer_list
作为参数,如下所示:
DynamicMultiDimArray(std::initializer_list<std::size_t> dimensions) :
std::vector<T>(std::accumulate(dimensions.begin(), dimensions.end(), std::size_t{1}, std::multiplies<std::size_t>())),
Dimensions(dimensions) {}
是的,实际元素向量的初始化现在看起来很难看。我建议不要为此使用继承,而是使用组合。那么可以先初始化维度,再初始化数据的array/vector,并且可以在MultiDimArray
中创建一个成员变量来计算条目数:
template <class derived, class T>
class MultiDimArray {
...
constexpr std::size_t nEntries() const {
const auto &dimensions = Derived().dimensions;
return std::accumulate(dimensions.begin(), dimensions.end(), std::size_t{1}, std::multiplies<std::size_t>());
}
...
};
template <class T>
class DynamicMultiDimArray :
public MultiDimArray<...>
{
std::vector<std::size_t> dimensions;
std::vector<T> data;
...
public:
DynamicMultiDimArray(std::initializer_list<std::size_t> dimensions) :
Dimensions(dimensions),
data(nEntries()) {}
};
同样,您可以让 operator()
为索引取一个 std::initializer_list<std::size_t>
。使用它的代码如下所示:
DynamicMultiDimArray dimarr({3, 5, 7}); // create new array
...
std::cout << dimarr({1, 2, 3}) << '\n'; // print element at index 1, 2, 3
这避免了很多模板麻烦。您甚至可以考虑创建自定义多维索引类型而不是 std::initializer_list<std::size_t>
,这样可以更轻松地将索引存储在变量中并传递它们。