元素级多维数组迭代，无论存储顺序如何 [英] Element-wise multidimensional array iteration regardless of storage order
本文介绍了元素级多维数组迭代，无论存储顺序如何的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我有一个n维数组类，我想能够以特定的顺序迭代元素，让我们说，首先，因此不管存储顺序（行或列专业）。
数组类的签名是 template< typename T，StorageOrder T_storageOrder，std :: size_t ... T_dimensions> class Array ，我有一个 storageIndex（）函数，将索引列表转换为1-D索引以检索内部数据，是一个 ElementWiseIterator 类的迭代逻辑。
一切都很好，但对于end-major案件。结束迭代器背后的想法是使用 storageIndex（）函数从超出由定义的数组形状的范围的索引列表中检索1-D索引 T_dimensions 模板参数。换句话说，如果我有一个 2×3 数组，然后我试图检索位于 {2,0}的索引， ，但这（合理地）返回我使用列主要顺序数组的第三个元素，而不是返回第七个（非现有）元素，因为我需要代表结束迭代器。
这让我相信我的方法有缺陷，但我目前没有其他想法，我正在寻找一点灵感，想出一个干净和通用的方法。我看了一下 numpy.nditer ，但无法理解任何实现。
我也想知道如果 ElementWiseIterator 无法简化一点，因为它目前需要保存一些数据。
#include< array>
#include< cstddef>
#include< iostream>
#include
template< typename T>
constexpr T product（T unique）
{return unique; }
template< typename T，typename ... T_Others>
constexpr T product（T first，T second，T_Others ... others）
{return product（first * second，others ...）; }
枚举类StorageOrder {
rowMajor，
columnMajor
};
template< StorageOrder> struct StorageOrderTag {};
使用RowMajorStorageOrderTag = StorageOrderTag< StorageOrder :: rowMajor> ;;
使用ColumnMajorStorageOrderTag = StorageOrderTag< StorageOrder :: columnMajor> ;;
// - 将特定形状数组的索引列表转换为1-D索引。
template< typename T_Shape>
std :: size_t storageIndex（const T_Shape& indices，const T_Shape& shape，RowMajorStorageOrderTag）
{
std :: size_t i = 0;
std :: size_t out = indices [i];
while（i ++< indices.size（） - 1）{
out = indices [i] + shape [i] * out;
}
return out;
}
template< typename T_Shape>
std :: size_t storageIndex（const T_Shape& indices，const T_Shape& shape，ColumnMajorStorageOrderTag）
{
std :: size_t i = indices.size（）
std :: size_t out = indices [i];
while（i--> 0）{
out = indices [i] + shape [i] * out;
}
return out;
}
// - 元素迭代器。
template<
typename T，
typename T_Data，
StorageOrder T_storageOrder，
std :: size_t T_dimensionality
>
class ElementWiseIterator
：public std :: iterator< std :: bidirectional_iterator_tag，T>
{
private：
使用Shape = std :: array< std :: size_t，T_dimensionality> ;;
public：
T& operator *（）const
{return * _currentElement; }
ElementWiseIterator& operator ++（）
{
std :: size_t i = _shape.size（）;
while（i--> 0）{
if（_currentIndices [i] <_shape [i] - 1 || i == 0）{
++ _ currentIndices [i] ;
break;
}
}
for（++ i; i <_currentIndices.size（）; ++ i）{
_currentIndices [i] = 0;
}
setCurrentElement（）;
return * this;
}
friend bool operator ==（const ElementWiseIterator& iterator1，const ElementWiseIterator& iterator2）
{return iterator1._currentElement == iterator2._currentElement; }
friend bool operator！=（const ElementWiseIterator& iterator1，const ElementWiseIterator& iterator2）
{return！（iterator1 == iterator2）; }
private：
ElementWiseIterator（T_Data * data，const Shape& indices，const Shape& shape）
：_currentElement（nullptr），
_data ），
_currentIndices（indices），
_shape（shape）
{
setCurrentElement（）;
}
void setCurrentElement（）
{
std :: size_t index = storageIndex（
_currentIndices，
_shape，
StorageOrderTag< T_storageOrder>（）
）;
_currentElement =&（* _ data）[index];
}
T * _currentElement;
T_Data * _data;
Shape _currentIndices;
Shape _shape;
template< typename，StorageOrder，std :: size_t ...>朋友类Array;
};
// - 数组类。
template< typename T，StorageOrder T_storageOrder，std :: size_t ... T_dimensions>
class Array
{
public：
static constexpr std :: size_t size（）
{return product（T_dimensions ...）; }
使用Shape = std :: array< std :: size_t，sizeof ...（T_dimensions）> ;;
static constexpr形状shape（）
{return {T_dimensions ...}; }
protected：
using Storage = std :: array< T，size（）>
public：
使用Iterator = typename Storage :: iterator;
使用ElementWiseIterator = ElementWiseIterator<
T，
Storage，
T_storageOrder，
sizeof ...（T_dimensions）
> ;;
Iterator begin（）
{return _data.begin（）; }
迭代器结束（）
{return _data.end（）; }
ElementWiseIterator elementWiseBegin（）
{return ElementWiseIterator（& _data，{0}，shape（））; }
ElementWiseIterator elementWiseEnd（）
{
//将当前迭代器索引设置为第一个超出范围元素。
// Ie：对于一个2x3数组，它将是{2,0}。
Shape shape = this-> shape（）;
return ElementWiseIterator（& _data，{shape [0]}，shape）;
}
T& operator []（std :: size_t index）
{return _data [index]; }
const T& operator []（std :: size_t index）const
{return _data [index]; }
private：
Storage _data;
};
template< typename T，StorageOrder T_storageOrder，std :: size_t ... T_dimensions>
void printDebug（Array< T，T_storageOrder，T_dimensions ...& array）
{
std :: size_t i = 0;
auto it = array.elementWiseBegin（）;
for（; i< array.size（）; ++ i，++ it）{
std :: cout< * it< ;
}
std :: cout<< std :: endl;
}
int main（int argc，char ** argv）
{
Array< int，StorageOrder :: rowMajor，2,3& rowArray2d;
Array< int，StorageOrder :: columnMajor，2，3> colArray2d;
Array< int，StorageOrder :: rowMajor，4,2,3> rowArray3d;
Array< int，StorageOrder :: columnMajor，4,2,3> colArray3d;
{
std :: cout<< \\\
Test case 1 \\\
<< ----------- \\\
<< 两个数组表示相同的2×3矩阵：\\\
< 0 1 2 \\\
<< 3 4 5
<< std :: endl;
rowArray2d [0] = 0; rowArray2d [1] = 1; rowArray2d [2] = 2;
rowArray2d [3] = 3; rowArray2d [4] = 4; rowArray2d [5] = 5;
colArray2d [0] = 0; colArray2d [2] = 1; colArray2d [4] = 2;
colArray2d [1] = 3; colArray2d [3] = 4; colArray2d [5] = 5;
//下面返回0 1 2 3 4 5如预期。
std :: cout<< row-wise iteration over rowArray2d：\\\
;
for（auto it = rowArray2d.elementWiseBegin（）; it！= rowArray2d.elementWiseEnd（）; ++ it）{
std :: cout< * it< ;
}
std :: cout<< \ n 0 1 2 3 4 5（预期）< std :: endl;
//下面只返回0而不是0 1 2 3 4 5.
std :: cout<< element-wise iteration over colArray2d：\\\
;
for（auto it = colArray2d.elementWiseBegin（）; it！= colArray2d.elementWiseEnd（）; ++ it）{
std :: cout< * it< ;
}
std :: cout<< \ n 0 1 2 3 4 5（预期）< std :: endl;
//但是如果我们使用`elementWiseBegin`迭代器递增，并使用
//索引号作为停止条件，那么它运行良好。
std :: cout<< 调试元素方式迭代colArray2d：\\\
;
printDebug（colArray2d）;
std :: cout<< internal 1-D data iteration over rowArray2d：\\\
;
for（auto it = rowArray2d.begin（）; it！= rowArray2d.end（）; ++ it）{
std :: cout < * it< ;
}
std :: cout<< \ n 0 1 2 3 4 5（预期）< std :: endl;
std :: cout<< 内部1-D数据迭代colArray2d：\\\
;
for（auto it = colArray2d.begin（）; it！= colArray2d.end（）; ++ it）{
std :: cout< * it< ;
}
std :: cout<< \ n 0 3 1 4 2 5（预期）< std :: endl;
}
{
std :: cout<< \\\
Test case 2 \\\
<< ----------- \\\
<< 两个数组共享相同的内部1-D表示：\\\
<< 0 1 2 3 4 5
<< std :: endl;
rowArray2d [0] = 0; rowArray2d [1] = 1; rowArray2d [2] = 2;
rowArray2d [3] = 3; rowArray2d [4] = 4; rowArray2d [5] = 5;
colArray2d [0] = 0; colArray2d [2] = 2; colArray2d [4] = 4;
colArray2d [1] = 1; colArray2d [3] = 3; colArray2d [5] = 5;
//下面返回0 1 2 3 4 5如预期。
std :: cout<< row-wise iteration over rowArray2d：\\\
;
for（auto it = rowArray2d.elementWiseBegin（）; it！= rowArray2d.elementWiseEnd（）; ++ it）{
std :: cout < * it< ;
}
std :: cout<< \ n 0 1 2 3 4 5（预期）< std :: endl;
//下面只返回0而不是0 2 4 1 3 5.
std :: cout<< element-wise iteration over colArray2d：\\\
;
for（auto it = colArray2d.elementWiseBegin（）; it！= colArray2d.elementWiseEnd（）; ++ it）{
std :: cout< * it< ;
}
std :: cout<< \ n 0 2 4 1 3 5（预期）< std :: endl;
//但是如果我们使用`elementWiseBegin`迭代器递增，并使用
//索引号作为停止条件，那么它运行良好。
std :: cout<< 调试元素方式迭代colArray2d：\\\
;
printDebug（colArray2d）;
std :: cout<< internal 1-D data iteration over rowArray2d：\\\
;
for（auto it = rowArray2d.begin（）; it！= rowArray2d.end（）; ++ it）{
std :: cout< * it< ;
}
std :: cout<< \ n 0 1 2 3 4 5（预期）< std :: endl;
std :: cout<< 内部1-D数据迭代colArray2d：\\\
;
for（auto it = colArray2d.begin（）; it！= colArray2d.end（）; ++ it）{
std :: cout< * it< ;
}
std :: cout<< \ n 0 1 2 3 4 5（预期）< std :: endl;
}
{
//这是因为结束迭代器，指向索引（2，0）是
//（足够的）转换为索引2由`storageIndex`函数，
//而不是超过最后一个元素的索引。
// std :: cout<< \\\
column-major storage index at（2,0）：\\\
//< storageIndex（{colArray2d.shape（）[0]}，colArray2d.shape（），ColumnMajorStorageOrderTag（））
//< std :: endl;
}
{
std :: cout<< \\\
Test case 3 \\\
<< ----------- \\\
<< 两个数组表示相同的4x2x3矩阵：\\\
<< 0 1 2 6 7 8 12 13 14 18 19 20 \\\
<< 3 4 5 9 10 11 15 16 17 21 22 23 \\\
<< std :: endl;
rowArray3d [0] = 0; rowArray3d [1] = 1; rowArray3d [2] = 2;
rowArray3d [3] = 3; rowArray3d [4] = 4; rowArray3d [5] = 5;
rowArray3d [6] = 6; rowArray3d [7] = 7; rowArray3d [8] = 8;
rowArray3d [9] = 9; rowArray3d [10] = 10; rowArray3d [11] = 11;
rowArray3d [12] = 12; rowArray3d [13] = 13; rowArray3d [14] = 14;
rowArray3d [15] = 15; rowArray3d [16] = 16; rowArray3d [17] = 17;
rowArray3d [18] = 18; rowArray3d [19] = 19; rowArray3d [20] = 20;
rowArray3d [21] = 21; rowArray3d [22] = 22; rowArray3d [23] = 23;
colArray3d [0] = 0; colArray3d [8] = 1; colArray3d [16] = 2;
colArray3d [4] = 3; colArray3d [12] = 4; colArray3d [20] = 5;
colArray3D [1] = 6; colArray3d [9] = 7; colArray3d [17] = 8;
colArray3d [5] = 9; colArray3d [13] = 10; colArray3d [21] = 11;
colArray3d [2] = 12; colArray3d [10] = 13; colArray3d [18] = 14;
colArray3d [6] = 15; colArray3d [14] = 16; colArray3d [22] = 17;
colArray3d [3] = 18; colArray3d [11] = 19; colArray3d [19] = 20;
colArray3d [7] = 21; colArray3d [15] = 22; colArray3d [23] = 23;
//下面返回0 1 2 3 4 5如预期。
std :: cout<< row-wise iteration over rowArray3d：\\\
;
for（auto it = rowArray3d.elementWiseBegin（）; it！= rowArray3d.elementWiseEnd（）; ++ it）{
std :: cout< * it< ;
}
std :: cout<< \ n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23（预期）< std :: endl;
//下面只返回0而不是0 1 2 3 4 5.
std :: cout<< element-wise iteration over colArray3d：\\\
;
for（auto it = colArray3d.elementWiseBegin（）; it！= colArray3d.elementWiseEnd（）; ++ it）{
std :: cout< * it< ;
}
std :: cout<< \ n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23（预期）< std :: endl;
//但是如果我们使用`elementWiseBegin`迭代器递增，并使用
//索引号作为停止条件，那么它运行良好。
std :: cout<< debug element-wise iteration over colArray3d：\\\
;
printDebug（colArray3d）;
std :: cout<< 内部1-D数据迭代在rowArray3d：\\\
;
for（auto it = rowArray3d.begin（）; it！= rowArray3d.end（）; ++ it）{
std :: cout< * it< ;
}
std :: cout<< \ n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23（预期）< std :: endl;
std :: cout<< 内部1-D数据迭代colArray3d：\\\
;
for（auto it = colArray3d.begin（）; it！= colArray3d.end（）; ++ it）{
std :: cout< * it< ;
}
std :: cout<< \ n 0 6 12 18 3 9 15 21 1 7 13 19 4 10 16 22 2 8 14 20 5 11 17 23（预期）< std :: endl;
}
return 0;
}
代码输出：
<测试用例1
-----------
两个数组代表相同的2x3矩阵：
0 1 2
3 4 5
在rowArray2d的元素迭代：
0 1 2 3 4 5
0 1 2 3 4 5（预期）
元素层迭代colArray2d：
0
0 1 2 3 4 5（预期）
在colArray2d上调试元素方面的迭代：
0 1 2 3 4 5
在rowArray2d上的内部1-D数据迭代：
0 1 2 3 4 5
0 1 2 3 4 5（预期）
在colArray2d上的内部1-D数据迭代：
0 3 1 4 2 5
0 3 1 4 2 5（预期）
测试用例2
-----------
Both数组共享相同的内部1-D表示：
0 1 2 3 4 5
在rowArray2d的元素方面迭代：
0 1 2 3 4 5
0 1 2 3 4 5（预期）
通过colArray2d的元素迭代：
0
0 2 4 1 3 5（预期）
在colArray2d上调试元素方面的迭代：
0 2 4 1 3 5
rowArray2d的内部1-D数据迭代：
0 1 2 3 4 5
0 1 2 3 4 5（预期）
内部1-D数据对colArray2d的迭代：
0 1 2 3 4 5
0 1 2 3 4 5（预期）
测试用例3
-------- ---
这两个数组代表相同的4x2x3矩阵：
0 1 2 6 7 8 12 13 14 18 19 20
3 4 5 9 10 11 15 16 17 21 22 23
在rowArray3d上的元素迭代：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23（预期）
对colArray3d的元素迭代：
0 1 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23（预期）
在colArray3d上调试元素迭代：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
rowArray3d上的内部1-D数据迭代：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23（预期）
colArray3d上的内部1-D数据迭代：
0 6 12 18 3 9 15 21 1 7 13 19 4 10 16 22 2 8 14 20 5 11 17 23
0 6 12 18 3 9 15 21 1 7 13 19 4 10 16 22 2 8 14 20 5 11 17 23（预期）
编辑 b $ b
这个迭代器的目的是在具有不同存储顺序的数组之间进行元素操作，例如比较元素的相等性。
，迭代器应该以预定义的顺序（这里是row-major）遍历数组元素。也就是说，当使用 elementWiseBegin（）方法初始化 2 x 3 数组的迭代器时，在（0，0）处的元素。当增加它时，它应该指向（0，1），然后（0，2） c $ c>（1,0），等等。
这确保在迭代过程中，可以将位于索引（0,2）处的数组与位于相同索引（0,2），因此无论其存储顺序如何。
编辑2
$ b b
似乎在行/列主存储顺序的定义上有一些混乱。当我谈到存储顺序时，我指的是内存中的布局，如维基百科，而不是向量导向。
不同的存储顺序不应该改变向用户呈现数组的方式。事实上， 2 x 3 数组将始终如下所示，其中元素表示它们的索引。
+ ---- + ---- + ---- +
| 00 | 01 | 02 |
+ ---- + ---- + ---- +
| 10 | 11 | 12 |
+ ---- + ---- + ---- +
不同的存储顺序不同，存储器中的内部表示中的元素是不同的，即：
//行主存储顺序。
00 01 02 10 11 12
//列主存储顺序。
00 10 01 11 02 12
当直接设置内部数据 0 1 2 3 4 5 在我的代码片段内，根据刚才说的，这是我期望的数组看起来像：
//行主存储顺序。
+ --- + --- + --- +
| 0 | 1 | 2 |
+ --- + --- + --- +
| 3 | 4 | 5 |
+ --- + --- + --- +
//列主存储顺序。
+ --- + --- + --- +
| 0 | 2 | 4 |
+ --- + --- + --- +
| 1 | 3 | 5 |
+ --- + --- + --- +
元素级迭代器总是以 00 的顺序返回元素，而不考虑存储顺序。这就是为什么当直接设置内部数据与 0 1 2 3 4 5 ，我期望这个元素级迭代器返回的元素的顺序 0 1 2 3 4 5 当使用行主存储顺序时， 0 2 4 1 3 5 主存储顺序。
解决方案
存储值 0,1,2,3,4,5， / code>转换为1-D数组，其表示当存储器访问是行主要时的行主要2-D数组（2行，3列）：
存储顺序：
[
0，1，2，
3，4，5
]
ie，[0，1，2，3，4，5]
$ b b
将值 0,1,2,3,4,5，存储到1-D阵列中，其表示列主2-D阵列（2行， 3列）内存访问是行主：
存储顺序：
[
0，2，4，
1，3，5
]
ie，[0，2，4，1，3，5]
您注明：
这个迭代器的目的是在具有不同存储顺序的数组之间进行元素操作，例如比较元素的相等性。
$ b $我认为这意味着行主数组应当以不同于列主数组存储其数据，并且应当可用特殊迭代器，使得每个数组可以以相同的逻辑顺序 em>（例如，比较它们是否等效）。假设我理解你的问题，那么行/列主要数组将在内存中如上所示。但是，使用特殊迭代器强制执行行主要排序会导致每个数组以相同的逻辑顺序访问它的值（即 [0，1 ，2，3，4，5] 。
代码输出（我添加了注释）：
//这表示存储顺序如上所述
存储顺序：{0，1，2，3，4，5}
存储顺序：{0，2，4，1，3，5}
//这表明两者可以以相同的逻辑顺序迭代
r主顺序：{0， 1，2，3，4，5}
r主要订单：{0，1，2，3，4，5}
/ *********** **********************
*用于任意ND数组*
************* ******************** /
// 3-D
存储顺序：{0，1，2，3， 4，5，6，7}
存储顺序：{0,4,2,6,1,5,3,7}
r主序：{0,1,2,3,4， 5，6，7}
r主要订单：{0，1，2，3，4，5，6，7}
// 4-D
存储顺序： {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
存储顺序：{0，8，4，12，2 ，10，6，14，1，9，5，13，3，11，7，15}
r主要订单：{0,1,2,3,4,5,6,7,8,9 ，10，11，12，13，14，15}
r主要顺序：{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14 ，15}
测试用例1
-----------
这两个数组表示相同的2x3矩阵：
0 1 2
3 4 5
row main迭代在rowArray：
0 1 2 3 4 5
0 1 2 3 4 5（预期）
在colArray的行重复迭代：
0 1 2 3 4 5
0 1 2 3 4 5（预期）
在rowArray的内部1-D数据迭代：
0 1 2 3 4 5
0 1 2 3 4 5（预期）
colArray的内部1-D数据迭代：
0 3 1 4 2 5
0 3 1 4 2 5（预期）
col主迭代over rowArray：
0 3 1 4 2 5
0 3 1 4 2 5（预期）
col colArray上的主要迭代：
0 3 1 4 2 5
0 3 1 4 2 5（预期）
测试用例2
-----------
两个数组共享相同的内部1-D表示：
0 1 2 3 4 5
row重复迭代rowArray：
0 1 2 3 4 5
0 1 2 3 4 5（预期）
行主要迭代over colArray：
0 2 4 1 3 5
0 2 4 1 3 5（预期）
在rowArray的内部1-D数据迭代：
0 1 2 3 4 5
0 1 2 3 4 5（预期）
colArray的内部1-D数据迭代：
0 1 2 3 4 5
0 1 2 3 4 5（预期）
col main迭代在rowArray：
0 3 1 4 2 5
0 3 1 4 2 5（预期）
col重复迭代colArray：
0 1 2 3 4 5
0 1 2 3 4 5（预期）
代码：
支持任意维度的行主要或列主要迭代。
#include<数组>
#include< cstdint>
#include< fstream>
#include< iostream>
#include< string>
#include< vector>
枚举类StorageOrder
{
rowMajor，
columnMajor
};
template< typename T>
constexpr T product（T t1，T t2）
{
return t1 * t2;
}
template< typename T，typename ... Ts>
constexpr T product（T t，Ts ... ts）
{
return t * product（ts ...）;
}
template< StorageOrder T_iterOrder，std :: size_t ... T_dimensions>
class ArrayIndexer
{
public：
using Indices = const std :: array< std :: size_t，sizeof ...（T_dimensions）>
static std :: size_t computeIndex（const Indices& indices）
{
const std :: array< std :: size_t，sizeof ...（T_dimensions）> indexSizes = {T_dimensions ...};
std :: size_t index = 0;
for（std :: size_t i = 0; i< sizeof ...（T_dimensions）; ++ i）
{
std :: size_t result = 1;
for（std :: size_t j = i + 1; j< sizeof ...（T_dimensions）; ++ j）
{
result * = indexSizes [j]
}
result * = indices [i];
index + = result;
}
return index;
}
};
template< std :: size_t ... T_dimensions>
class ArrayIndexer< StorageOrder :: columnMajor，T_dimensions ...>
{
public：
using Indices = std :: array< std :: size_t，sizeof ...（T_dimensions）> ;;
static std :: size_t computeIndex（const Indices& indices）
{
const std :: array< std :: size_t，sizeof ...（T_dimensions）> indexSizes = {T_dimensions ...};
std :: size_t index = indices [0];
for（std :: size_t i = 1; i< sizeof ...（T_dimensions）; ++ i）
{
std :: size_t result = 1;
for（std :: size_t j = 0; j< i; ++ j）
{
result * = indexSizes [j]
}
result * = indices [i];
index + = result;
}
return index;
}
};
template< typename T，StorageOrder T_storageOrder，StorageOrder T_iterOrder，std :: size_t ... T_dimensions>
class ArrayIterator
{
public：
using Storage = std :: array< T，product（T_dimensions ...）&
using IndexSizes = std :: array< std :: size_t，sizeof ...（T_dimensions）> ;;
using Indices = std :: array< std :: size_t，sizeof ...（T_dimensions）> ;;
ArrayIterator（存储和数组，const指数和索引）：
mArray（array）
{
IndexSizes indexSizes = {T_dimensions ...};
if（indices == indexSizes）
{
mIndex = mArray.size（）;
}
else
{
mIndex = ArrayIndexer< T_iterOrder，T_dimensions ...> :: computeIndex
}
}
constexpr bool operator ==（const ArrayIterator& other）const
{
return& mArray ==& other.mArray &&& mIndex == other.mIndex;
}
constexpr bool operator！=（const ArrayIterator& other）const
{
return！operator ==（other）;
}
T& operator *（）
{
return mArray [mIndex];
}
ArrayIterator& operator ++（）
{
++ mIndex;
return * this;
}
private：
std :: size_t mIndex;
Storage& mArray;
};
template< typename T，std :: size_t ... T_dimensions>
class ArrayIterator< T，StorageOrder :: rowMajor，StorageOrder :: columnMajor，T_dimensions ...>
{
public：
using Storage = std :: array< T，product（T_dimensions ...）> ;;
using IndexSizes = std :: array< std :: size_t，sizeof ...（T_dimensions）> ;;
using Indices = std :: array< std :: size_t，sizeof ...（T_dimensions）> ;;
ArrayIterator（存储和数组，const指数和索引）：
mIndexSizes（{T_dimensions ...}），
mIndices（indices），
mArray ）
{
if（mIndices == mIndexSizes）
{
for（std :: size_t i = 0; i< mIndices.size（） - 1; ++ i ）
{
mIndices [i] = 0;
}
}
}
constexpr bool operator ==（const ArrayIterator& other）const
{
return& mArray == & other.mArray&& mIndices == other.mIndices;
}
constexpr bool operator！=（const ArrayIterator& other）const
{
return！operator ==（other）;
}
T& operator *（）
{
return mArray [ArrayIndexer< StorageOrder :: rowMajor，T_dimensions ...> :: computeIndex（mIndices）];
}
ArrayIterator& operator ++（）
{
advance（0）;
return * this;
}
private：
void advance（std :: size_t incrementIndex）
{
if（++ mIndices [incrementIndex] == mIndexSizes [incrementIndex ]
{
if（incrementIndex< sizeof ...（T_dimensions） - 1）
{
mIndices [incrementIndex] = 0;
advance（incrementIndex + 1）;
}
}
}
private：
IndexSizes mIndexSizes;
指数mIndices;
Storage& mArray;
};
template< typename T，std :: size_t ... T_dimensions>
class ArrayIterator< T，StorageOrder :: columnMajor，StorageOrder :: rowMajor，T_dimensions ...>
{
public：
using Storage = std :: array< T，product（T_dimensions ...）> ;;
using IndexSizes = std :: array< std :: size_t，sizeof ...（T_dimensions）> ;;
using Indices = std :: array< std :: size_t，sizeof ...（T_dimensions）> ;;
ArrayIterator（存储和数组，const指数和索引）：
mIndexSizes（{T_dimensions ...}），
mIndices（indices），
mArray ）
{
if（mIndices == mIndexSizes）
{
for（std :: size_t i = 1; i< mIndices.size（）; ++ i）
{
mIndices [i] = 0;
}
}
}
constexpr bool operator ==（const ArrayIterator& other）const
{
return& mArray == & other.mArray&& mIndices == other.mIndices;
}
constexpr bool operator！=（const ArrayIterator& other）const
{
return！operator ==（other）;
}
T& operator*()
{
return mArray[ArrayIndexer<StorageOrder::columnMajor, T_dimensions...>::computeIndex(mIndices)];
}
ArrayIterator& operator++()
{
advance(sizeof... (T_dimensions) - 1);
return * this;
}
private:
void advance(std::size_t incrementIndex)
{
if (++mIndices[incrementIndex] == mIndexSizes[incrementIndex])
{
if (incrementIndex > 0)
{
mIndices[incrementIndex] = 0;
advance(incrementIndex - 1);
}
}
}
private:
IndexSizes mIndexSizes;
Indices mIndices;
Storage &mArray;
};
template<typename T, StorageOrder T_storageOrder, std::size_t... T_dimensions>
class Array
{
public:
static constexpr std::size_t StorageSize = product(T_dimensions...);
using Storage = std::array<T, StorageSize>;
using iterator = typename Storage::iterator;
using iterator_row = ArrayIterator<T, T_storageOrder, StorageOrder::rowMajor, T_dimensions...>;
using iterator_col = ArrayIterator<T, T_storageOrder, StorageOrder::columnMajor, T_dimensions...>;
constexpr bool empty() const
{
return mArray.empty();
}
constexpr std::size_t size() const
{
return mArray.size();
}
iterator begin()
{
return mArray.begin();
}
iterator end()
{
return mArray.end();
}
iterator_row beginRowMajor()
{
return iterator_row(mArray, { 0, 0 });
}
iterator_row endRowMajor()
{
return iterator_row(mArray, { T_dimensions... });
}
iterator_col beginColMajor()
{
return iterator_col(mArray, { 0, 0 });
}
iterator_col endColMajor()
{
return iterator_col(mArray, { T_dimensions... });
}
T& operator[](std::size_t index)
{
return mArray[index];
}
const T& operator[](std::size_t index) const
{
return mArray[index];
}
private:
Storage mArray;
};
template<typename T, StorageOrder S, std::size_t... D>
std :: ostream& operator<<(std::ostream& stream, Array<T, S, D...>& array)
{
stream << {;
if (!array.empty())
{
std::size_t index = 0;
stream<< < array[index];
while (++index < array.size())
{
stream << ，< array[index];
}
}
stream<< };
return stream;
}
template<typename T, StorageOrder S, std::size_t... D>
void printRowMajor(Array<T, S, D...>& array)
{
std::cout << {;
auto itr = array.beginRowMajor();
if (itr != array.endRowMajor())
{
std::cout << < *itr;
while (++itr != array.endRowMajor())
{
std::cout << ，< *itr;
}
}
std::cout << };
}
int main()
{
{
Array<int, StorageOrder::rowMajor, 2, 3> rowMajorArray;
int i = -1;
// Store the data directly to the array
for (auto& v : rowMajorArray)
{
v = ++i;
}
Array<int, StorageOrder::columnMajor, 2, 3> colMajorArray;
i = -1;
// Store the data directly to the array
for (auto& v : colMajorArray)
{
v = ++i;
}
std :: cout<< \"storage order: \" << rowMajorArray << \\\
;
std :: cout<< \"storage order: \" << colMajorArray << \\\
;
std :: cout<< \"r major order: \"; printRowMajor(rowMajorArray); std :: cout<< \\\
;
std :: cout<< \"r major order: \"; printRowMajor(colMajorArray); std :: cout<< \\\
;
}
{
Array<int, StorageOrder::rowMajor, 2, 2, 2> rowMajorArray;
int i = -1;
// Store the data directly to the array
for (auto& v : rowMajorArray)
{
v = ++i;
}
Array<int, StorageOrder::columnMajor, 2, 2, 2> colMajorArray;
i = -1;
// Store the data directly to the array
for (auto& v : colMajorArray)
{
v = ++i;
}
std :: cout<< \"storage order: \" << rowMajorArray << \\\
;
std :: cout<< \"storage order: \" << colMajorArray << \\\
;
std :: cout<< \"r major order: \"; printRowMajor(rowMajorArray); std :: cout<< \\\
;
std :: cout<< \"r major order: \"; printRowMajor(colMajorArray); std :: cout<< \\\
;
}
{
Array<int, StorageOrder::rowMajor, 2, 2, 2, 2> rowMajorArray;
int i = -1;
// Store the data directly to the array
for (auto& v : rowMajorArray)
{
v = ++i;
}
Array<int, StorageOrder::columnMajor, 2, 2, 2, 2> colMajorArray;
i = -1;
// Store the data directly to the array
for (auto& v : colMajorArray)
{
v = ++i;
}
std :: cout<< \"storage order: \" << rowMajorArray << \\\
;
std :: cout<< \"storage order: \" << colMajorArray << \\\
;
std :: cout<< \"r major order: \"; printRowMajor(rowMajorArray); std :: cout<< \\\
;
std :: cout<< \"r major order: \"; printRowMajor(colMajorArray); std :: cout<< \\\
;
}
{
Array<int, StorageOrder::rowMajor, 2, 3> rowArray;
Array<int, StorageOrder::columnMajor, 2, 3> colArray;
rowArray[0] = 0; rowArray[1] = 1; rowArray[2] = 2;
rowArray[3] = 3; rowArray[4] = 4; rowArray[5] = 5;
colArray[0] = 0; colArray[2] = 1; colArray[4] = 2;
colArray[1] = 3; colArray[3] = 4; colArray[5] = 5;
std::cout
<< \"\nTest case 1\n\"
<< \"-----------\n\"
<< \"Both arrays represent the same 2x3 matrix:\n\"
<< \" 0 1 2\n\"
<< \" 3 4 5\n\";
std :: cout<< \"row major iteration over rowArray:\n \";
for (auto itr = rowArray.beginRowMajor(); itr != rowArray.endRowMajor(); ++itr)
{
std::cout << *itr << ;
}
std :: cout<< \"\n 0 1 2 3 4 5 (expected)\n\";
std :: cout<< \"row major iteration over colArray:\n \";
for (auto itr = colArray.beginRowMajor(); itr != colArray.endRowMajor(); ++itr)
{
std::cout << *itr << ;
}
std :: cout<< \"\n 0 1 2 3 4 5 (expected)\n\";
std :: cout<< \"internal 1-D data iteration over rowArray:\n \";
for (auto itr = rowArray.begin(); itr != rowArray.end(); ++itr)
{
std::cout << *itr << ;
}
std :: cout<< \"\n 0 1 2 3 4 5 (expected)\" << std :: endl;
std :: cout<< \"internal 1-D data iteration over colArray:\n \";
for (auto itr = colArray.begin(); itr != colArray.end(); ++itr)
{
std::cout << *itr << ;
}
std :: cout<< \"\n 0 3 1 4 2 5 (expected)\" << std :: endl;
std :: cout<< \"col major iteration over rowArray:\n \";
for (auto itr = rowArray.beginColMajor(); itr != rowArray.endColMajor(); ++itr)
{
std::cout << *itr << ;
}
std :: cout<< \"\n 0 3 1 4 2 5 (expected)\n\";
std :: cout<< \"col major iteration over colArray:\n \";
for (auto itr = colArray.beginColMajor(); itr != colArray.endColMajor(); ++itr)
{
std::cout << *itr << ;
}
std :: cout<< \"\n 0 3 1 4 2 5 (expected)\n\";
}
{
Array<int, StorageOrder::rowMajor, 2, 3> rowArray;
Array<int, StorageOrder::columnMajor, 2, 3> colArray;
rowArray[0] = 0; rowArray[1] = 1; rowArray[2] = 2;
rowArray[3] = 3; rowArray[4] = 4; rowArray[5] = 5;
colArray[0] = 0; colArray[2] = 2; colArray[4] = 4;
colArray[1] = 1; colArray[3] = 3; colArray[5] = 5;
std::cout
<< \"\nTest case 2\n\"
<< \"-----------\n\"
<< \"Both arrays share the same internal 1-D representation:\n\"
<< \" 0 1 2 3 4 5\n\";
std :: cout<< \"row major iteration over rowArray:\n \";
for (auto itr = rowArray.beginRowMajor(); itr != rowArray.endRowMajor(); ++itr)
{
std::cout << *itr << ;
}
std :: cout<< \"\n 0 1 2 3 4 5 (expected)\n\";
std :: cout<< \"row major iteration over colArray:\n \";
for (auto itr = colArray.beginRowMajor(); itr != colArray.endRowMajor(); ++itr)
{
std::cout << *itr << ;
}
std :: cout<< \"\n 0 2 4 1 3 5 (expected)\n\";
std :: cout<< \"internal 1-D data iteration over rowArray:\n \";
for (auto itr = rowArray.begin(); itr != rowArray.end(); ++itr)
{
std::cout << *itr << ;
}
std :: cout<< \"\n 0 1 2 3 4 5 (expected)\" << std :: endl;
std :: cout<< \"internal 1-D data iteration over colArray:\n \";
for (auto itr = colArray.begin(); itr != colArray.end(); ++itr)
{
std::cout << *itr << ;
}
std :: cout<< \"\n 0 1 2 3 4 5 (expected)\" << std :: endl;
std :: cout<< \"col major iteration over rowArray:\n \";
for (auto itr = rowArray.beginColMajor(); itr != rowArray.endColMajor(); ++itr)
{
std::cout << *itr << ;
}
std :: cout<< \"\n 0 3 1 4 2 5 (expected)\n\";
std :: cout<< \"col major iteration over colArray:\n \";
for (auto itr = colArray.beginColMajor(); itr != colArray.endColMajor(); ++itr)
{
std::cout << *itr << ;
}
std :: cout<< \"\n 0 1 2 3 4 5 (expected)\n\";
}
return 0;
}
I have a n-dimensional array class and I would like to be able to iterate though the elements in a specific order, let's say rows first, and thus regardless of the storage order (row or column major).
The signature of the array class is template<typename T, StorageOrder T_storageOrder, std::size_t ... T_dimensions> class Array, I have a storageIndex() function that converts a list of indices into a 1-D index to retrieve the internal data, and there is an ElementWiseIterator class for the iteration logic.
Everything works well but for the end iterator in the column-major case. The idea behind the end iterator is to use the storageIndex() function to retrieve a 1-D index from a list of indices that is out of range of the array shape defined by the T_dimensions template parameter. In other words, if I have a 2 × 3 array, then I'm trying to retrieve an index that is located at {2, 0}, but this (rightfully) returns me the 3rd element when using a column-major order array, instead of returning the 7th (non existing) element as I'd need to represent the end iterator.
This leads me to believe that my approach is flawed but I have no other idea at the moment and am looking for a bit of inspiration to come up with a clean and generic approach. I had a look at numpy.nditer but couldn't understand anything of the implementation.
I was also wondering if the ElementWiseIterator couldn't be simplified a bit because it currently requires to hold quite some data.
Please find below a reduction of the code.
#include <array>
#include <cstddef>
#include <iostream>
#include <iterator>
template<typename T>
constexpr T product(T unique)
{ return unique; }
template<typename T, typename ... T_Others>
constexpr T product(T first, T second, T_Others ... others)
{ return product(first * second, others ...); }
enum class StorageOrder {
rowMajor,
columnMajor
};
template<StorageOrder> struct StorageOrderTag {};
using RowMajorStorageOrderTag = StorageOrderTag<StorageOrder::rowMajor>;
using ColumnMajorStorageOrderTag = StorageOrderTag<StorageOrder::columnMajor>;
// - Converts a list of indices for a specific shape array into a 1-D index.
template<typename T_Shape>
std::size_t storageIndex(const T_Shape &indices, const T_Shape &shape, RowMajorStorageOrderTag)
{
std::size_t i = 0;
std::size_t out = indices[i];
while (i++ < indices.size() - 1) {
out = indices[i] + shape[i] * out;
}
return out;
}
template<typename T_Shape>
std::size_t storageIndex(const T_Shape &indices, const T_Shape &shape, ColumnMajorStorageOrderTag)
{
std::size_t i = indices.size() - 1;
std::size_t out = indices[i];
while (i-- > 0) {
out = indices[i] + shape[i] * out;
}
return out;
}
//- Element-wise iterator.
template<
typename T,
typename T_Data,
StorageOrder T_storageOrder,
std::size_t T_dimensionality
>
class ElementWiseIterator
: public std::iterator<std::bidirectional_iterator_tag, T>
{
private:
using Shape = std::array<std::size_t, T_dimensionality>;
public:
T & operator*() const
{ return *_currentElement; }
ElementWiseIterator & operator++()
{
std::size_t i = _shape.size();
while (i-- > 0) {
if (_currentIndices[i] < _shape[i] - 1 || i == 0) {
++_currentIndices[i];
break;
}
}
for (++i; i < _currentIndices.size(); ++i) {
_currentIndices[i] = 0;
}
setCurrentElement();
return *this;
}
friend bool operator==(const ElementWiseIterator &iterator1, const ElementWiseIterator &iterator2)
{ return iterator1._currentElement == iterator2._currentElement; }
friend bool operator!=(const ElementWiseIterator &iterator1, const ElementWiseIterator &iterator2)
{ return !(iterator1 == iterator2); }
private:
ElementWiseIterator(T_Data *data, const Shape &indices, const Shape &shape)
: _currentElement(nullptr),
_data(data),
_currentIndices(indices),
_shape(shape)
{
setCurrentElement();
}
void setCurrentElement()
{
std::size_t index = storageIndex(
_currentIndices,
_shape,
StorageOrderTag<T_storageOrder>()
);
_currentElement = &(*_data)[index];
}
T *_currentElement;
T_Data *_data;
Shape _currentIndices;
Shape _shape;
template<typename, StorageOrder, std::size_t ...> friend class Array;
};
//- Array class.
template<typename T, StorageOrder T_storageOrder, std::size_t ... T_dimensions>
class Array
{
public:
static constexpr std::size_t size()
{ return product(T_dimensions ...); }
using Shape = std::array<std::size_t, sizeof ... (T_dimensions)>;
static constexpr Shape shape()
{ return {T_dimensions ...}; }
protected:
using Storage = std::array<T, size()>;
public:
using Iterator = typename Storage::iterator;
using ElementWiseIterator = ElementWiseIterator<
T,
Storage,
T_storageOrder,
sizeof ... (T_dimensions)
>;
Iterator begin()
{ return _data.begin(); }
Iterator end()
{ return _data.end(); }
ElementWiseIterator elementWiseBegin()
{ return ElementWiseIterator(&_data, {0}, shape()); }
ElementWiseIterator elementWiseEnd()
{
// Set the current iterator indices to the first out of range element.
// Ie: for an a 2x3 array, that would be {2, 0}.
Shape shape = this->shape();
return ElementWiseIterator(&_data, {shape[0]}, shape);
}
T & operator[](std::size_t index)
{ return _data[index]; }
const T & operator[](std::size_t index) const
{ return _data[index]; }
private:
Storage _data;
};
template<typename T, StorageOrder T_storageOrder, std::size_t ... T_dimensions>
void printDebug(Array<T, T_storageOrder, T_dimensions ...> &array)
{
std::size_t i = 0;
auto it = array.elementWiseBegin();
for (; i < array.size(); ++i, ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
}
int main(int argc, char **argv)
{
Array<int, StorageOrder::rowMajor, 2, 3> rowArray2d;
Array<int, StorageOrder::columnMajor, 2, 3> colArray2d;
Array<int, StorageOrder::rowMajor, 4, 2, 3> rowArray3d;
Array<int, StorageOrder::columnMajor, 4, 2, 3> colArray3d;
{
std::cout << "\nTest case 1\n"
<< "-----------\n"
<< "Both arrays represent the same 2x3 matrix:\n"
<< " 0 1 2\n"
<< " 3 4 5"
<< std::endl;
rowArray2d[0] = 0; rowArray2d[1] = 1; rowArray2d[2] = 2;
rowArray2d[3] = 3; rowArray2d[4] = 4; rowArray2d[5] = 5;
colArray2d[0] = 0; colArray2d[2] = 1; colArray2d[4] = 2;
colArray2d[1] = 3; colArray2d[3] = 4; colArray2d[5] = 5;
// Below returns 0 1 2 3 4 5 as expected.
std::cout << "element-wise iteration over rowArray2d:\n ";
for (auto it = rowArray2d.elementWiseBegin(); it != rowArray2d.elementWiseEnd(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n 0 1 2 3 4 5 (expected)" << std::endl;
// Below returns only 0 instead of 0 1 2 3 4 5.
std::cout << "element-wise iteration over colArray2d:\n ";
for (auto it = colArray2d.elementWiseBegin(); it != colArray2d.elementWiseEnd(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n 0 1 2 3 4 5 (expected)" << std::endl;
// But if we increment using the `elementWiseBegin` iterator and use the
// index number as a stop condition, then it works well.
std::cout << "debug element-wise iteration over colArray2d:\n ";
printDebug(colArray2d);
std::cout << "internal 1-D data iteration over rowArray2d:\n ";
for (auto it = rowArray2d.begin(); it != rowArray2d.end(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n 0 1 2 3 4 5 (expected)" << std::endl;
std::cout << "internal 1-D data iteration over colArray2d:\n ";
for (auto it = colArray2d.begin(); it != colArray2d.end(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n 0 3 1 4 2 5 (expected)" << std::endl;
}
{
std::cout << "\nTest case 2\n"
<< "-----------\n"
<< "Both arrays share the same internal 1-D representation:\n"
<< " 0 1 2 3 4 5"
<< std::endl;
rowArray2d[0] = 0; rowArray2d[1] = 1; rowArray2d[2] = 2;
rowArray2d[3] = 3; rowArray2d[4] = 4; rowArray2d[5] = 5;
colArray2d[0] = 0; colArray2d[2] = 2; colArray2d[4] = 4;
colArray2d[1] = 1; colArray2d[3] = 3; colArray2d[5] = 5;
// Below returns 0 1 2 3 4 5 as expected.
std::cout << "element-wise iteration over rowArray2d:\n ";
for (auto it = rowArray2d.elementWiseBegin(); it != rowArray2d.elementWiseEnd(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n 0 1 2 3 4 5 (expected)" << std::endl;
// Below returns only 0 instead of 0 2 4 1 3 5.
std::cout << "element-wise iteration over colArray2d:\n ";
for (auto it = colArray2d.elementWiseBegin(); it != colArray2d.elementWiseEnd(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n 0 2 4 1 3 5 (expected)" << std::endl;
// But if we increment using the `elementWiseBegin` iterator and use the
// index number as a stop condition, then it works well.
std::cout << "debug element-wise iteration over colArray2d:\n ";
printDebug(colArray2d);
std::cout << "internal 1-D data iteration over rowArray2d:\n ";
for (auto it = rowArray2d.begin(); it != rowArray2d.end(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n 0 1 2 3 4 5 (expected)" << std::endl;
std::cout << "internal 1-D data iteration over colArray2d:\n ";
for (auto it = colArray2d.begin(); it != colArray2d.end(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n 0 1 2 3 4 5 (expected)" << std::endl;
}
{
// This is because the end iterator, pointing to the indices (2, 0) is
// (fairly enough) converted into the index 2 by the `storageIndex` function,
// instead of an index beyond the last element.
// std::cout << "\ncolumn-major storage index at (2, 0):\n "
// << storageIndex({colArray2d.shape()[0]}, colArray2d.shape(), ColumnMajorStorageOrderTag())
// << std::endl;
}
{
std::cout << "\nTest case 3\n"
<< "-----------\n"
<< "Both arrays represent the same 4x2x3 matrix:\n"
<< " 0 1 2 6 7 8 12 13 14 18 19 20\n"
<< " 3 4 5 9 10 11 15 16 17 21 22 23\n"
<< std::endl;
rowArray3d[ 0] = 0; rowArray3d[ 1] = 1; rowArray3d[ 2] = 2;
rowArray3d[ 3] = 3; rowArray3d[ 4] = 4; rowArray3d[ 5] = 5;
rowArray3d[ 6] = 6; rowArray3d[ 7] = 7; rowArray3d[ 8] = 8;
rowArray3d[ 9] = 9; rowArray3d[10] = 10; rowArray3d[11] = 11;
rowArray3d[12] = 12; rowArray3d[13] = 13; rowArray3d[14] = 14;
rowArray3d[15] = 15; rowArray3d[16] = 16; rowArray3d[17] = 17;
rowArray3d[18] = 18; rowArray3d[19] = 19; rowArray3d[20] = 20;
rowArray3d[21] = 21; rowArray3d[22] = 22; rowArray3d[23] = 23;
colArray3d[ 0] = 0; colArray3d[ 8] = 1; colArray3d[16] = 2;
colArray3d[ 4] = 3; colArray3d[12] = 4; colArray3d[20] = 5;
colArray3d[ 1] = 6; colArray3d[ 9] = 7; colArray3d[17] = 8;
colArray3d[ 5] = 9; colArray3d[13] = 10; colArray3d[21] = 11;
colArray3d[ 2] = 12; colArray3d[10] = 13; colArray3d[18] = 14;
colArray3d[ 6] = 15; colArray3d[14] = 16; colArray3d[22] = 17;
colArray3d[ 3] = 18; colArray3d[11] = 19; colArray3d[19] = 20;
colArray3d[ 7] = 21; colArray3d[15] = 22; colArray3d[23] = 23;
// Below returns 0 1 2 3 4 5 as expected.
std::cout << "element-wise iteration over rowArray3d:\n ";
for (auto it = rowArray3d.elementWiseBegin(); it != rowArray3d.elementWiseEnd(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 (expected)" << std::endl;
// Below returns only 0 instead of 0 1 2 3 4 5.
std::cout << "element-wise iteration over colArray3d:\n ";
for (auto it = colArray3d.elementWiseBegin(); it != colArray3d.elementWiseEnd(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 (expected)" << std::endl;
// But if we increment using the `elementWiseBegin` iterator and use the
// index number as a stop condition, then it works well.
std::cout << "debug element-wise iteration over colArray3d:\n ";
printDebug(colArray3d);
std::cout << "internal 1-D data iteration over rowArray3d:\n ";
for (auto it = rowArray3d.begin(); it != rowArray3d.end(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 (expected)" << std::endl;
std::cout << "internal 1-D data iteration over colArray3d:\n ";
for (auto it = colArray3d.begin(); it != colArray3d.end(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n 0 6 12 18 3 9 15 21 1 7 13 19 4 10 16 22 2 8 14 20 5 11 17 23 (expected)" << std::endl;
}
return 0;
}
Code output:
Test case 1
-----------
Both arrays represent the same 2x3 matrix:
0 1 2
3 4 5
element-wise iteration over rowArray2d:
0 1 2 3 4 5
0 1 2 3 4 5 (expected)
element-wise iteration over colArray2d:
0
0 1 2 3 4 5 (expected)
debug element-wise iteration over colArray2d:
0 1 2 3 4 5
internal 1-D data iteration over rowArray2d:
0 1 2 3 4 5
0 1 2 3 4 5 (expected)
internal 1-D data iteration over colArray2d:
0 3 1 4 2 5
0 3 1 4 2 5 (expected)
Test case 2
-----------
Both arrays share the same internal 1-D representation:
0 1 2 3 4 5
element-wise iteration over rowArray2d:
0 1 2 3 4 5
0 1 2 3 4 5 (expected)
element-wise iteration over colArray2d:
0
0 2 4 1 3 5 (expected)
debug element-wise iteration over colArray2d:
0 2 4 1 3 5
internal 1-D data iteration over rowArray2d:
0 1 2 3 4 5
0 1 2 3 4 5 (expected)
internal 1-D data iteration over colArray2d:
0 1 2 3 4 5
0 1 2 3 4 5 (expected)
Test case 3
-----------
Both arrays represent the same 4x2x3 matrix:
0 1 2 6 7 8 12 13 14 18 19 20
3 4 5 9 10 11 15 16 17 21 22 23
element-wise iteration over rowArray3d:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 (expected)
element-wise iteration over colArray3d:
0 1 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 (expected)
debug element-wise iteration over colArray3d:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
internal 1-D data iteration over rowArray3d:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 (expected)
internal 1-D data iteration over colArray3d:
0 6 12 18 3 9 15 21 1 7 13 19 4 10 16 22 2 8 14 20 5 11 17 23
0 6 12 18 3 9 15 21 1 7 13 19 4 10 16 22 2 8 14 20 5 11 17 23 (expected)
Edit
The purpose of this iterator is to do element-wise operations between arrays having different storage orders, such as comparing the elements for equality.
As such, the iterator should traverse the array elements in a predefined order (row-major here). That is, when initializing the iterator for a 2 x 3 array with the elementWiseBegin() method, it should point to the element at the index (0, 0). When incrementing it, it should point to (0, 1), then (0, 2), then (1, 0), and so on.
This ensures that, during an iteration process, an element from a first array located at the index (0, 2) can be compared to the element of a second array located at the same index (0, 2), and thus regardless of their storage order.
Edit 2
It seems that there is some confusion around the definition of row/column major storage orders. When I'm talking of storage order, I'm referring to the layout in memory as per the definition on Wikipedia, not to the vector orientation.
A different storage order shouldn't change the way the array is presented to the user. Indeed, a 2 x 3 array will always be noted as below, with the elements representing their indices.
+----+----+----+
| 00 | 01 | 02 |
+----+----+----+
| 10 | 11 | 12 |
+----+----+----+
What a different storage order does though, is aligning differently the elements within the internal representation in memory, ie:
// Row-major storage order.
00 01 02 10 11 12
// Column-major storage order.
00 10 01 11 02 12
When setting directly the internal data with 0 1 2 3 4 5 as done within my snippet, and according to what was said just before, this is how I expect the arrays to look like:
// Row-major storage order.
+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 3 | 4 | 5 |
+---+---+---+
// Column-major storage order.
+---+---+---+
| 0 | 2 | 4 |
+---+---+---+
| 1 | 3 | 5 |
+---+---+---+
The goal of the element-wise iterator is to always return the elements in the order 00 01 02 10 11 12, regardless of the storage order. That's why when setting directly the internal data with 0 1 2 3 4 5, I'm expecting this element-wise iterator to return the elements in the order 0 1 2 3 4 5 when using the row-major storage order, and 0 2 4 1 3 5 in the case of a column-major storage order.
解决方案
Storing values 0, 1, 2, 3, 4, 5, into a 1-D array which represents a row major 2-D array (2 rows, 3 columns) when memory access is row major:
Storage order:
[
0, 1, 2,
3, 4, 5
]
i.e., [0, 1, 2, 3, 4, 5]
Storing values 0, 1, 2, 3, 4, 5, into a 1-D array which represents a column major 2-D array (2 rows, 3 columns) when memory access is row major:
Storage order:
[
0, 2, 4,
1, 3, 5
]
i.e., [0, 2, 4, 1, 3, 5]
You state:
The purpose of this iterator is to do element-wise operations between arrays having different storage orders, such as comparing the elements for equality.
I take this to mean the row major array should store its data differently than the column major array and a special iterator should be available such that each array can be iterated in the same logical order (e.g., to compare if they are equivalent). Assuming I understand your question then the row/column major arrays will be in memory as shown above. However, using a special iterator enforcing a row major ordering causes each array to visit its values in the same logical order (i.e., [0, 1, 2, 3, 4, 5].
Code output (I added the comments):
// This shows the storage order is as describe above
storage order: { 0, 1, 2, 3, 4, 5 }
storage order: { 0, 2, 4, 1, 3, 5 }
// This shows that both can be iterated in the same 'logical order'
r major order: { 0, 1, 2, 3, 4, 5 }
r major order: { 0, 1, 2, 3, 4, 5 }
/*********************************
* Works for arbitrary N-D array *
*********************************/
// 3-D
storage order: { 0, 1, 2, 3, 4, 5, 6, 7 }
storage order: { 0, 4, 2, 6, 1, 5, 3, 7 }
r major order: { 0, 1, 2, 3, 4, 5, 6, 7 }
r major order: { 0, 1, 2, 3, 4, 5, 6, 7 }
// 4-D
storage order: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }
storage order: { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }
r major order: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }
r major order: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }
Test case 1
-----------
Both arrays represent the same 2x3 matrix:
0 1 2
3 4 5
row major iteration over rowArray:
0 1 2 3 4 5
0 1 2 3 4 5 (expected)
row major iteration over colArray:
0 1 2 3 4 5
0 1 2 3 4 5 (expected)
internal 1-D data iteration over rowArray:
0 1 2 3 4 5
0 1 2 3 4 5 (expected)
internal 1-D data iteration over colArray:
0 3 1 4 2 5
0 3 1 4 2 5 (expected)
col major iteration over rowArray:
0 3 1 4 2 5
0 3 1 4 2 5 (expected)
col major iteration over colArray:
0 3 1 4 2 5
0 3 1 4 2 5 (expected)
Test case 2
-----------
Both arrays share the same internal 1-D representation:
0 1 2 3 4 5
row major iteration over rowArray:
0 1 2 3 4 5
0 1 2 3 4 5 (expected)
row major iteration over colArray:
0 2 4 1 3 5
0 2 4 1 3 5 (expected)
internal 1-D data iteration over rowArray:
0 1 2 3 4 5
0 1 2 3 4 5 (expected)
internal 1-D data iteration over colArray:
0 1 2 3 4 5
0 1 2 3 4 5 (expected)
col major iteration over rowArray:
0 3 1 4 2 5
0 3 1 4 2 5 (expected)
col major iteration over colArray:
0 1 2 3 4 5
0 1 2 3 4 5 (expected)
The code:
Supports row major or column major iteration for arbitrary dimensionality.
#include <array>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
enum class StorageOrder
{
rowMajor,
columnMajor
};
template<typename T>
constexpr T product(T t1, T t2)
{
return t1 * t2;
}
template<typename T, typename... Ts>
constexpr T product(T t, Ts... ts)
{
return t * product(ts...);
}
template<StorageOrder T_iterOrder, std::size_t... T_dimensions>
class ArrayIndexer
{
public:
using Indices = const std::array<std::size_t, sizeof... (T_dimensions)>;
static std::size_t computeIndex(const Indices& indices)
{
const std::array<std::size_t, sizeof... (T_dimensions)> indexSizes = { T_dimensions... };
std::size_t index = 0;
for (std::size_t i = 0; i < sizeof... (T_dimensions); ++i)
{
std::size_t result = 1;
for (std::size_t j = i + 1; j < sizeof... (T_dimensions); ++j)
{
result *= indexSizes[j];
}
result *= indices[i];
index += result;
}
return index;
}
};
template<std::size_t... T_dimensions>
class ArrayIndexer<StorageOrder::columnMajor, T_dimensions...>
{
public:
using Indices = std::array<std::size_t, sizeof... (T_dimensions)>;
static std::size_t computeIndex(const Indices& indices)
{
const std::array<std::size_t, sizeof... (T_dimensions)> indexSizes = { T_dimensions... };
std::size_t index = indices[0];
for (std::size_t i = 1; i < sizeof... (T_dimensions); ++i)
{
std::size_t result = 1;
for (std::size_t j = 0; j < i; ++j)
{
result *= indexSizes[j];
}
result *= indices[i];
index += result;
}
return index;
}
};
template<typename T, StorageOrder T_storageOrder, StorageOrder T_iterOrder, std::size_t... T_dimensions>
class ArrayIterator
{
public:
using Storage = std::array<T, product(T_dimensions...)>;
using IndexSizes = std::array<std::size_t, sizeof... (T_dimensions)>;
using Indices = std::array<std::size_t, sizeof... (T_dimensions)>;
ArrayIterator(Storage& array, const Indices& indices) :
mArray(array)
{
IndexSizes indexSizes = { T_dimensions... };
if (indices == indexSizes)
{
mIndex = mArray.size();
}
else
{
mIndex = ArrayIndexer<T_iterOrder, T_dimensions...>::computeIndex(indices);
}
}
constexpr bool operator==(const ArrayIterator& other) const
{
return &mArray == &other.mArray && mIndex == other.mIndex;
}
constexpr bool operator!=(const ArrayIterator& other) const
{
return !operator==(other);
}
T& operator*()
{
return mArray[mIndex];
}
ArrayIterator& operator++()
{
++mIndex;
return *this;
}
private:
std::size_t mIndex;
Storage &mArray;
};
template<typename T, std::size_t... T_dimensions>
class ArrayIterator<T, StorageOrder::rowMajor, StorageOrder::columnMajor, T_dimensions...>
{
public:
using Storage = std::array<T, product(T_dimensions...)>;
using IndexSizes = std::array<std::size_t, sizeof... (T_dimensions)>;
using Indices = std::array<std::size_t, sizeof... (T_dimensions)>;
ArrayIterator(Storage& array, const Indices& indices) :
mIndexSizes({ T_dimensions... }),
mIndices(indices),
mArray(array)
{
if (mIndices == mIndexSizes)
{
for (std::size_t i = 0; i < mIndices.size() - 1; ++i)
{
mIndices[i] = 0;
}
}
}
constexpr bool operator==(const ArrayIterator& other) const
{
return &mArray == &other.mArray && mIndices == other.mIndices;
}
constexpr bool operator!=(const ArrayIterator& other) const
{
return !operator==(other);
}
T& operator*()
{
return mArray[ArrayIndexer<StorageOrder::rowMajor, T_dimensions...>::computeIndex(mIndices)];
}
ArrayIterator& operator++()
{
advance(0);
return *this;
}
private:
void advance(std::size_t incrementIndex)
{
if (++mIndices[incrementIndex] == mIndexSizes[incrementIndex])
{
if (incrementIndex < sizeof... (T_dimensions) - 1)
{
mIndices[incrementIndex] = 0;
advance(incrementIndex + 1);
}
}
}
private:
IndexSizes mIndexSizes;
Indices mIndices;
Storage &mArray;
};
template<typename T, std::size_t... T_dimensions>
class ArrayIterator<T, StorageOrder::columnMajor, StorageOrder::rowMajor, T_dimensions...>
{
public:
using Storage = std::array<T, product(T_dimensions...)>;
using IndexSizes = std::array<std::size_t, sizeof... (T_dimensions)>;
using Indices = std::array<std::size_t, sizeof... (T_dimensions)>;
ArrayIterator(Storage& array, const Indices& indices) :
mIndexSizes({ T_dimensions... }),
mIndices(indices),
mArray(array)
{
if (mIndices == mIndexSizes)
{
for (std::size_t i = 1; i < mIndices.size(); ++i)
{
mIndices[i] = 0;
}
}
}
constexpr bool operator==(const ArrayIterator& other) const
{
return &mArray == &other.mArray && mIndices == other.mIndices;
}
constexpr bool operator!=(const ArrayIterator& other) const
{
return !operator==(other);
}
T& operator*()
{
return mArray[ArrayIndexer<StorageOrder::columnMajor, T_dimensions...>::computeIndex(mIndices)];
}
ArrayIterator& operator++()
{
advance(sizeof... (T_dimensions) - 1);
return *this;
}
private:
void advance(std::size_t incrementIndex)
{
if (++mIndices[incrementIndex] == mIndexSizes[incrementIndex])
{
if (incrementIndex > 0)
{
mIndices[incrementIndex] = 0;
advance(incrementIndex - 1);
}
}
}
private:
IndexSizes mIndexSizes;
Indices mIndices;
Storage &mArray;
};
template<typename T, StorageOrder T_storageOrder, std::size_t... T_dimensions>
class Array
{
public:
static constexpr std::size_t StorageSize = product(T_dimensions...);
using Storage = std::array<T, StorageSize>;
using iterator = typename Storage::iterator;
using iterator_row = ArrayIterator<T, T_storageOrder, StorageOrder::rowMajor, T_dimensions...>;
using iterator_col = ArrayIterator<T, T_storageOrder, StorageOrder::columnMajor, T_dimensions...>;
constexpr bool empty() const
{
return mArray.empty();
}
constexpr std::size_t size() const
{
return mArray.size();
}
iterator begin()
{
return mArray.begin();
}
iterator end()
{
return mArray.end();
}
iterator_row beginRowMajor()
{
return iterator_row(mArray, { 0, 0 });
}
iterator_row endRowMajor()
{
return iterator_row(mArray, { T_dimensions... });
}
iterator_col beginColMajor()
{
return iterator_col(mArray, { 0, 0 });
}
iterator_col endColMajor()
{
return iterator_col(mArray, { T_dimensions... });
}
T& operator[](std::size_t index)
{
return mArray[index];
}
const T& operator[](std::size_t index) const
{
return mArray[index];
}
private:
Storage mArray;
};
template<typename T, StorageOrder S, std::size_t... D>
std::ostream& operator<<(std::ostream& stream, Array<T, S, D...>& array)
{
stream << "{";
if (!array.empty())
{
std::size_t index = 0;
stream << " " << array[index];
while (++index < array.size())
{
stream << ", " << array[index];
}
}
stream << " }";
return stream;
}
template<typename T, StorageOrder S, std::size_t... D>
void printRowMajor(Array<T, S, D...>& array)
{
std::cout << "{";
auto itr = array.beginRowMajor();
if (itr != array.endRowMajor())
{
std::cout << " " << *itr;
while (++itr != array.endRowMajor())
{
std::cout << ", " << *itr;
}
}
std::cout << " }";
}
int main()
{
{
Array<int, StorageOrder::rowMajor, 2, 3> rowMajorArray;
int i = -1;
// Store the data directly to the array
for (auto& v : rowMajorArray)
{
v = ++i;
}
Array<int, StorageOrder::columnMajor, 2, 3> colMajorArray;
i = -1;
// Store the data directly to the array
for (auto& v : colMajorArray)
{
v = ++i;
}
std::cout << "storage order: " << rowMajorArray << "\n";
std::cout << "storage order: " << colMajorArray << "\n";
std::cout << "r major order: "; printRowMajor(rowMajorArray); std::cout << "\n";
std::cout << "r major order: "; printRowMajor(colMajorArray); std::cout << "\n";
}
{
Array<int, StorageOrder::rowMajor, 2, 2, 2> rowMajorArray;
int i = -1;
// Store the data directly to the array
for (auto& v : rowMajorArray)
{
v = ++i;
}
Array<int, StorageOrder::columnMajor, 2, 2, 2> colMajorArray;
i = -1;
// Store the data directly to the array
for (auto& v : colMajorArray)
{
v = ++i;
}
std::cout << "storage order: " << rowMajorArray << "\n";
std::cout << "storage order: " << colMajorArray << "\n";
std::cout << "r major order: "; printRowMajor(rowMajorArray); std::cout << "\n";
std::cout << "r major order: "; printRowMajor(colMajorArray); std::cout << "\n";
}
{
Array<int, StorageOrder::rowMajor, 2, 2, 2, 2> rowMajorArray;
int i = -1;
// Store the data directly to the array
for (auto& v : rowMajorArray)
{
v = ++i;
}
Array<int, StorageOrder::columnMajor, 2, 2, 2, 2> colMajorArray;
i = -1;
// Store the data directly to the array
for (auto& v : colMajorArray)
{
v = ++i;
}
std::cout << "storage order: " << rowMajorArray << "\n";
std::cout << "storage order: " << colMajorArray << "\n";
std::cout << "r major order: "; printRowMajor(rowMajorArray); std::cout << "\n";
std::cout << "r major order: "; printRowMajor(colMajorArray); std::cout << "\n";
}
{
Array<int, StorageOrder::rowMajor, 2, 3> rowArray;
Array<int, StorageOrder::columnMajor, 2, 3> colArray;
rowArray[0] = 0; rowArray[1] = 1; rowArray[2] = 2;
rowArray[3] = 3; rowArray[4] = 4; rowArray[5] = 5;
colArray[0] = 0; colArray[2] = 1; colArray[4] = 2;
colArray[1] = 3; colArray[3] = 4; colArray[5] = 5;
std::cout
<< "\nTest case 1\n"
<< "-----------\n"
<< "Both arrays represent the same 2x3 matrix:\n"
<< " 0 1 2\n"
<< " 3 4 5\n";
std::cout << "row major iteration over rowArray:\n ";
for (auto itr = rowArray.beginRowMajor(); itr != rowArray.endRowMajor(); ++itr)
{
std::cout << *itr << " ";
}
std::cout << "\n 0 1 2 3 4 5 (expected)\n";
std::cout << "row major iteration over colArray:\n ";
for (auto itr = colArray.beginRowMajor(); itr != colArray.endRowMajor(); ++itr)
{
std::cout << *itr << " ";
}
std::cout << "\n 0 1 2 3 4 5 (expected)\n";
std::cout << "internal 1-D data iteration over rowArray:\n ";
for (auto itr = rowArray.begin(); itr != rowArray.end(); ++itr)
{
std::cout << *itr << " ";
}
std::cout << "\n 0 1 2 3 4 5 (expected)" << std::endl;
std::cout << "internal 1-D data iteration over colArray:\n ";
for (auto itr = colArray.begin(); itr != colArray.end(); ++itr)
{
std::cout << *itr << " ";
}
std::cout << "\n 0 3 1 4 2 5 (expected)" << std::endl;
std::cout << "col major iteration over rowArray:\n ";
for (auto itr = rowArray.beginColMajor(); itr != rowArray.endColMajor(); ++itr)
{
std::cout << *itr << " ";
}
std::cout << "\n 0 3 1 4 2 5 (expected)\n";
std::cout << "col major iteration over colArray:\n ";
for (auto itr = colArray.beginColMajor(); itr != colArray.endColMajor(); ++itr)
{
std::cout << *itr << " ";
}
std::cout << "\n 0 3 1 4 2 5 (expected)\n";
}
{
Array<int, StorageOrder::rowMajor, 2, 3> rowArray;
Array<int, StorageOrder::columnMajor, 2, 3> colArray;
rowArray[0] = 0; rowArray[1] = 1; rowArray[2] = 2;
rowArray[3] = 3; rowArray[4] = 4; rowArray[5] = 5;
colArray[0] = 0; colArray[2] = 2; colArray[4] = 4;
colArray[1] = 1; colArray[3] = 3; colArray[5] = 5;
std::cout
<< "\nTest case 2\n"
<< "-----------\n"
<< "Both arrays share the same internal 1-D representation:\n"
<< " 0 1 2 3 4 5\n";
std::cout << "row major iteration over rowArray:\n ";
for (auto itr = rowArray.beginRowMajor(); itr != rowArray.endRowMajor(); ++itr)
{
std::cout << *itr << " ";
}
std::cout << "\n 0 1 2 3 4 5 (expected)\n";
std::cout << "row major iteration over colArray:\n ";
for (auto itr = colArray.beginRowMajor(); itr != colArray.endRowMajor(); ++itr)
{
std::cout << *itr << " ";
}
std::cout << "\n 0 2 4 1 3 5 (expected)\n";
std::cout << "internal 1-D data iteration over rowArray:\n ";
for (auto itr = rowArray.begin(); itr != rowArray.end(); ++itr)
{
std::cout << *itr << " ";
}
std::cout << "\n 0 1 2 3 4 5 (expected)" << std::endl;
std::cout << "internal 1-D data iteration over colArray:\n ";
for (auto itr = colArray.begin(); itr != colArray.end(); ++itr)
{
std::cout << *itr << " ";
}
std::cout << "\n 0 1 2 3 4 5 (expected)" << std::endl;
std::cout << "col major iteration over rowArray:\n ";
for (auto itr = rowArray.beginColMajor(); itr != rowArray.endColMajor(); ++itr)
{
std::cout << *itr << " ";
}
std::cout << "\n 0 3 1 4 2 5 (expected)\n";
std::cout << "col major iteration over colArray:\n ";
for (auto itr = colArray.beginColMajor(); itr != colArray.endColMajor(); ++itr)
{
std::cout << *itr << " ";
}
std::cout << "\n 0 1 2 3 4 5 (expected)\n";
}
return 0;
}
这篇关于元素级多维数组迭代，无论存储顺序如何的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
