按特定顺序迭代数组元素

Question

我想以特定顺序迭代一个整数一维数组/向量，但我无法理解如何设置循环条件。输入数据是一个整数一维向量：

{1, 5, 9, 13, 17, 21, 2, 6, 10, 14, 18, 22, 3, 7, 11, 15, 19, 23, 4, 8, 12, 16, 20, 24, 25, 29, 33, 37, 41, 45, 26, 30, 34, 38, 42, 46, 27, 31, 35, 39, 43, 47, 28, 32, 36, 40, 44, 48}

这个输入数据实际上是一个带有子组的二维数组/网格的一维表示：

+----+----+----+----+----+----+
| 1  | 5  | 9  | 13 | 17 | 21 |
+----+----+----+----+----+----+
| 2  | 6  | 10 | 14 | 18 | 22 |
+----+----+----+----+----+----+
| 3  | 7  | 11 | 15 | 19 | 23 |
+----+----+----+----+----+----+
| 4  | 8  | 12 | 16 | 20 | 24 |
+----+----+----+----+----+----+
| 25 | 29 | 33 | 37 | 41 | 45 |
+----+----+----+----+----+----+
| 26 | 30 | 34 | 38 | 42 | 46 |
+----+----+----+----+----+----+
| 27 | 31 | 35 | 39 | 43 | 47 |
+----+----+----+----+----+----+
| 28 | 32 | 36 | 40 | 44 | 48 |
+----+----+----+----+----+----+

这个表格被分成了多个2x4的子组：

我想按照数字指示的顺序迭代这个一维输入向量/数组。（从头到尾依次遍历每个2x4的子组）。 在循环中，我想把当前处理的子组的8个元素装入一个向量/整数进行进一步处理。 最终，我应该处理6个子组，第一个子组包含1到8的数字，第二个子组包含9到16，以此类推... 子组应从左到右处理。

注意: 输入数据中的数字仅用作示例，以明确应处理数据的顺序。输入数据可以包含完全随机的值。应保留每个组中值的顺序。组内不应排序/重新排序。重要的是子组/数组维度等约束条件。

除了一维数组/向量之外，我还知道网格的尺寸和子组的大小：

int grid_width = 6; // Variable, but will always be a multiple of 2, to match subgroup width
int grid_height = 8;  // Variable, but will always be a multiple of 4, to match subgroup height
const int group_width = 2; // Constant, subgroup width is always 2.
const int group_height = 4; // Constant, subgroup height is always 4.

我的想法是使用一个循环迭代整个数据集，然后再用两个循环来分别处理子组。但我在循环条件和元素索引上感到很困难。我的思考过程大致如下：

// Iterate over entire data
for (int i = 0; i < grid_width * grid_height; i += (group_width * group_height))
{
    int block[8];
    // Iterate groups in correct order
    for (int j = 0; j < group_height; j++)
    {
        for (int k = 0; k < group_width; k++)
        {
            // Grab current element in group
            int value = input_array[i * grid_width + j]; // ?? This ain't right

            // Add element to group array/vector
            block[??] = ??;
        }
    }

    // Do further processing with the group array
}

有人能帮我正确地循环这个吗？希望问题已经足够清楚了，如果不清楚，请告诉我。

- Kyu96

---

你可以创建另一个包含按照你想要的顺序排列的索引的数组（或向量）。例如，如果可以像{ 0, 6, 12, ... etc }一样开始。通过这种方式，你也应该很快开始看到出现的模式，这意味着你可以根据你对矩阵和子矩阵的信息在运行时创建此索引向量。 - Some programmer dude

如果您可以为每个组添加要处理的值的示例，那么问题将更清晰明了。 - alani

@alaniwi 提到了。第一组将包含值1到8，第二组将是9到16，第三组将是17到24，第四组将是25到32等等... - Kyu96

@Kyu96 是的，但我的意思是你所说的“值从1到8”的示例。显然，一个程序在第一次迭代时输出值1, 2, 3, 4, 5, 6, 7, 8，在第二次迭代时输出数字9, 10, 11, 12, 13, 14, 15, 16等等，这是微不足道的。 - alani

@alaniwi 这些数字只是为了清晰地表明我想要处理数据的顺序。这些数字本身可以有任何值，并且不应该与迭代过程相关。我已经更新了问题，希望现在更加清晰明了。 - Kyu96

Answer 1

到目前为止，我还没有看到一个易懂的答案，因此我将添加一个非常易懂的、逐步解释的代码。

没有注释和解释的代码基本上没有意义。

这个问题可以通过使用整数和模除法来解决，可能是一个训练任务。重要的是要理解，我们当然需要计算索引。因此，作为第一个抽象，我展示了一个示例图片，但主要使用索引。请注意：在C++中，索引从0开始。

你想要的是左侧所示索引的分组。右侧仅显示给定源数据的索引。在绘制所有水平组之后，我们只需添加新行或新行。

重要属性包括：

- 组宽度， - 组高度， - 水平方向上的组数 - 垂直方向上的组数

从这些基本的源属性中，我们可以简单地计算出以下内容：

- 每个组的元素数量 -> 组宽度 * 组高度 - 总元素数量 -> 组宽度 * 组高度 * 水平方向上的组数 * 垂直方向上的组数

还有更多重要且易于计算的值：例如

- 下一行的偏移量 -> 组宽度 * 水平方向上的组数 - 下一个垂直组的偏移量 -> 下一行的偏移量 * 组高度 - 结果组的数量 -> 水平方向上的组数 * 垂直方向上的组数

这里的一切都很简单易懂。现在让我们看一个例子。

如果一个组的宽度为2，高度为4，则每个组有8个元素。

在水平方向上有3个组，我们观察到下一行中元素的索引始终比上一行大: 组宽 * 水平方向组数 = 2 * 3 = 6。

如果我们想知道任何一行的行偏移量（高度为4的一组），无论是哪个组，我们可以先计算索引 % 组高度，即索引 % 4。这将得出一个编号序列：0,1,2,3,0,1,2,3,0,1,2,3......

如果我们将此乘以上面的6，就会得到：0,6,12,18,0,6,12,18,0,6,12,18......

请看图片。如果我们在一个组中向下移动一行，我们就会向下移动6个索引。让我们把这称为行偏移量。

接下来我们需要检查列。如果我们看一下列，那么我们会发现目标的前4个元素在第0列，接下来的4个元素在第1列，以此类推。因此，我们可以通过整数除法简单地计算出列：索引/组高度。我们得到一个序列：0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8，...。

这个偏移量需要限制在每行的最大列数内，我们再次通过先前计算的行宽进行模除运算，例如在我们的示例中为6。结果是0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0,0,0,0,1,1,1,1,2,2,2,2，...

这就是我们所说的列偏移量。

如果我们将列偏移量与行偏移量相加（上面乘以6个值），那么我们已经得到了0、6、12、18、1、7、13、19、2、8、14、20、3、9、15、21等。所以，这已经适用于第一组水平数据。

垂直组偏移很简单。基本上，偏移量是：索引-下一个垂直组的偏移量=索引-下一行的偏移量*组高度=6*4=24。

而且，如果我们想要有组-行偏移量，那么我们只需通过上述计算出的值进行整数除法（index/24），然后再将其乘以24即可。这会产生一个序列：0....0,24....24,48....48,72....72,96....96,... 让我们称之为垂直组偏移。

如果我们将所有偏移量相加，那么我们可以通过一个简单的计算得到源数据中的索引。请注意：为了便于理解，在下面显示的软件中，我将其分成了三个部分。

接下来是目标偏移量。我们需要计算组号：它只是索引/每组元素数量，易于理解。对于一个运行源索引，这是0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,.....

而组内的目标索引也很简单。它是索引%每组元素数量，因此：0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0,1,2,.....

---

现在，我们将一个大问题分割成了许多更容易解决的小问题。

基本上，整个复制循环可以用一行代码完成，如果我们将所有计算出来的值直接放在赋值语句中并省略临时常量。

请查看完整、易于理解和详细注释的代码示例。

#include <iostream>
#include <vector>
#include <array>

int main() {

    // This you may change --------------------------------------------------------------------------------------

    // Source data
    std::vector values{1, 5, 9, 13, 17, 21, 2, 6, 10, 14, 18, 22, 3, 7, 11, 15, 19, 23, 4, 8, 12, 16, 20, 24, 25, 29, 33, 37, 41, 45, 26, 30, 34, 38, 42, 46, 27, 31, 35, 39, 43, 47, 28, 32, 36, 40, 44, 48};

    // Define the dimension of one group
    constexpr unsigned int GroupWidth =  2;
    constexpr unsigned int GroupHeight = 4;

    // Define, how many groups we have in horizontal and vertical direction
    constexpr unsigned int NumberOfGroupsHorizontal = 3;
    constexpr unsigned int NumberOfGroupsVertical   = 2;

    // Calculated values ---------------------------------------------------------------------------

    // Resulting capacity values
    constexpr unsigned int NumberOfElementsPerGroup = GroupWidth * GroupHeight;
    constexpr unsigned int NumberOfOverallElements = GroupWidth * GroupHeight * NumberOfGroupsHorizontal * NumberOfGroupsVertical;

    // Resulting offset values for indices
    constexpr unsigned int IndexOffsetToNextRow = GroupWidth * NumberOfGroupsHorizontal;
    constexpr unsigned int IndexOffsetToNextVerticalGroup = IndexOffsetToNextRow * GroupHeight;

    // How many groups do we have overall
    constexpr unsigned int NumberOfResultingGroups = NumberOfGroupsHorizontal * NumberOfGroupsVertical;

    // First make a sanity check, if parameters are ok. Handles also 0-values
    if (values.size() == NumberOfOverallElements) {

        // Copy algorithm ------------------------------------------------------------------------------

        // Here, we will store the result
        std::array<std::array<int, NumberOfElementsPerGroup>, NumberOfResultingGroups> result{};

        // Iterate over all source data
        for (unsigned int index = 0; index < NumberOfOverallElements; ++index) {


            // Calculate index in array of source data -------------------------------------------------
            // Row offset per group
            const unsigned int  o1 = (index % GroupHeight) * IndexOffsetToNextRow; 
            // Column offset
            const unsigned int  o2 = (index / GroupHeight) % IndexOffsetToNextRow; 
            // Vertical group offset
            const unsigned int  o3 = (index / IndexOffsetToNextVerticalGroup) * IndexOffsetToNextVerticalGroup; 

            // Overall calculated index / offset. (Above three lines could be put here as a one liner)
            const unsigned int sourceDataIndex = o1 + o2 + o3;

            // The target group index ------------------------------------------------------------------
            const unsigned int targetGroupIndex = index / NumberOfElementsPerGroup;

            // The index in the target group
            const unsigned int indexInTargetGroup = index % NumberOfElementsPerGroup;


            // Copy resulting value --------------------------------------------------------------------
            result[targetGroupIndex][indexInTargetGroup] = values[sourceDataIndex];
        }

        // Show result to the user
        for (const auto& a : result) {
            for (const int i : a) std::cout << i << ' ';
            std::cout << '\n';
        }
    }
    else {
        // Some problem occured
        std::cerr << "\n*** Error: Wrong source data size or parameters\n";
    }
    return 0;
}

---

有了上述的知识，现在您可以构建一个简单的函数：

std::vector<std::vector<int>> split(const std::vector<int>& v, const size_t ngh, const size_t ngv, const size_t gw=2U, const size_t gh=4U) {

    // Define resulting 2d vector
    std::vector<std::vector<int>> result(ngh * ngv, std::vector<int>(gw * gh,0));

    // Sanity check. Will also handle parameters being 0
    if (v.size() == gw*gh*ngv*ngh)
        // Copy values in simple for loop
        for (size_t i = 0U; i < v.size(); ++i)
            result[i/(gw*gh)][i%(gw*gh)] = v[((i%gh)*gw*ngh) + ((i/gh)%(gw*ngh)) + ((i/(gh*gw*ngh))*(gh*gw*ngh))] ;

    return result;
}

- A M

Answer 2

我想这个应该可以完成工作：

编辑：我添加了这个解释，因为一些人到目前为止仍然无法理解这个解决方案，尽管它只包含一些简单的线性索引计算，并且由于我没有看到任何非TL; DR但完整的解决方案 : 我们从前往后迭代输入数据。 我们始终计算所读取值所属位置的索引。 我们将该值存储到相应的索引中。 组是二次块。 我们使用group_position_x来存储每个组内的水平位置。 类似地，我们使用group_position_y表示组内的垂直位置，从左上角开始。 我们使用col表示我们在一行中处于第col个组中。 类似地，我们使用row表示我们在一列中处于第row个组中。 然后我们可以轻松计算从输入读取的值必须存储的位置。 该组是所有组中的第col + [col-size] * row个组。 以类似的方式，我们使用组内的x和y坐标来确定刚刚读取的值在组内的哪个索引处存储。 请注意，索引从0开始。 此外，请参见下面代码中的注释。 col，row和组内坐标的新值在每个步骤中都会被“递增”。 当然，我们讨论的是在每种情况下对某个整数取模的增量。 在某些情况下，如果满足其他索引的溢出条件，则出现“+1”。

using data_type = int // change type to correctly group data not being integers
using group = std::vector<data_type>; // reprensents the values of one group
const data_type DEFAULT{ -1 };

/**
@param data_begin begin iterator of the input data
@param data_end end iterator of the input data
@return a vector of all groups from top to bottom, from left to right.
*/
template<class _Const_Iterator>
std::vector<group> grouping(int grid_width, int grid_height, int group_width, int group_height, _Const_Iterator data_begin, _Const_Iterator data_end){
 const int GROUPS_PER_ROW{ grid_width / group_width };
 const int GROUPS_PER_COL{ grid_height / group_height };
 const int NUMBER_GROUPS{ GROUPS_PER_ROW * GROUPS_PER_COL };
 const int GROUP_SIZE{ group_width * group_height };
 std::vector<group> result(NUMBER_GROUPS, group(GROUP_SIZE, DEFAULT)); // create empty result vector with correct size.
 std::size_t group_index{ 0 }; // id of the current group
 std::size_t group_position_y{ 0 }; // currrent vertical position inside a group block
 std::size_t group_position_x{ 0 }; // current horizontal position inside a group block
 std::size_t row{ 0 }; // current row with respect to the groups
 std::size_t col{ 0 }; // current column with respect to the groups

 // iterate through all input data, copy data cell to target structur (result), calculate the correct indices for the next input data cell
 for (_Const_Iterator it{data_begin}; it != data_end; ++it){
  result[group_index][group_position_y + group_height * group_position_x] = *it;

  group_position_x = (group_position_x + 1) % group_width; // new horizontal position inside group
  auto old_col{ col };
  col = (col + (group_position_x == 0)) % GROUPS_PER_ROW; // new column with respect to the groups
  auto old_group_position_y{ group_position_y };
  group_position_y = (group_position_y  + (col == 0 && col != old_col)) % group_height; // new vertical position inside group
  row = (row + (group_position_y == 0 && group_position_y != old_group_position_y)) % GROUPS_PER_COL ; // new row with respect to the groups
  group_index = col + GROUPS_PER_ROW * row; 
 }
 return result;
}

在我个人看法中，最好不要使用太多嵌套循环，而应该使用索引计算。

- Necktschnagge

---

你能否检查一下，这个解决方案在你的环境中是否可行？我只是把它放在这里，没有进行任何编译/测试。 - Necktschnagge

解决方案似乎完美地运作。我将进行更多的测试，使用更大的输入等。不过我必须说，由于所有的模板和迭代器，它相当难以阅读。 - Kyu96

@Kyu96 我不确定你是否真的想要正确排序整数，还是这只是你用来解释问题的最小示例，所以我以稍微更一般的方式编写了代码。也许你可以在行、列、..x、..y等方面添加一些说明，以使它更清晰易懂。 - Necktschnagge

请不要只写代码而没有解释它的作用，如何解决问题，为什么原始代码无法正常工作而你的可以。请参见如何编写好答案。此外，这样的回答往往会促进模拟程序开发，这是不好的。 - Some programmer dude

@Necktschnagge：不幸的是，你的答案仍然缺乏必要的信息。我仍然无法阅读代码，也无法理解你的解决方案背后的算法。因此，我添加了一个完全解释清楚、有良好文档和易于阅读的源代码的答案。也许这可以帮助到你…… - A M

Answer 3

这个解决方案够简单吗？你可以在这里找到一个可工作的演示： https://wandbox.org/permlink/5Qv9HKzpaU9ec6gF

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

constexpr int rowSize        = 8;
constexpr int columnSize     = 6;
constexpr int subGroupWidth  = 2;
constexpr int subGroupHeigth = 4;

void calculate(const vector<vector<int>>& arr, vector<vector<int>>& res)
{
    int index = 0;
    for (int i = 0; i < rowSize; i+=subGroupHeigth)
    {
        for (int j = 0; j < columnSize; j+=subGroupWidth)
        {
            // This represents a sub-group!
            res[index].push_back(arr[i][j]);
            res[index].push_back(arr[i+1][j]);
            res[index].push_back(arr[i+2][j]);
            res[index].push_back(arr[i+3][j]);
            res[index].push_back(arr[i][j+1]);
            res[index].push_back(arr[i+1][j+1]);
            res[index].push_back(arr[i+2][j+1]);
            res[index].push_back(arr[i+3][j+1]);
            ++index;
        }
    }
}

int main()
{
    vector<int> vec {1, 5, 9, 13, 17, 21, 2, 6, 10, 14, 18, 22, 3, 7, 11, 15, 19, 23, 4, 8, 12, 16, 20, 24, 25, 29, 33, 37, 41, 45, 26, 30, 34, 38, 42, 46, 27, 31, 35, 39, 43, 47, 28, 32, 36, 40, 44, 48};

    // Convert the vector to 2D array
    vector<vector<int>> arr (rowSize, std::vector<int>(columnSize));
    int row = -1;
    for (size_t i = 0; i < vec.size(); ++i)
    {
        if (i%columnSize == 0) ++row;
        arr[row][i%columnSize] = vec[i];
    }

    vector<vector<int>> result (columnSize);   // reserve the space for 6 arrays
    calculate(arr, result);                    // extract the 6 sub-groups in terms of arrays

    // Print the results
    for_each (begin(result), end(result), [](vector<int> &row){
        for (auto e : row) cout << e << " ";
        cout << endl;
    });
    return 0;
}

- Kasper

---

vector<vector<int>> result (columnSize); 是一个错误。应该是 vector<vector<int>> result ((rowSize * columnSize) / (subGroupWidth * subGroupHeigth));。只适用于 subGroupWidth == 2 和 subGroupHeigth == 4，这是可以的，因为 OP 表示这些是常量值。 - A M

问题的作者可以轻松更改此代码（实际上，我希望任何人都能这样做，使用从StackOverflow获取的所有代码进行适应、测试和使其更加健壮）。这里的目标是向他展示一种替代方案。 - Kasper