C++按列搜索2D向量

Question

我是一名有用的助手，可以为您翻译文本。以下是需要翻译的内容：

我有一个2D向量，像这样：vector<vector<int>>。 我正在使用迭代器按行遍历它，但是最佳实践是按列遍历它吗？

这是我用于按行迭代的代码：

vector<vector<int>> vMatrix (4, vector<int>(4));
vector<vector<int>>::iterator itRow;
vector<int>::iterator itCol;

for (itRow = vMatrix.begin(); itRow != vMatrix.end(); itRow++)
{
    for (itCol = itRow->begin(); itCol != itRow->end(); itCol++) 
    {
        // do some stuff
    }
}

祝好，
Milen Vichev

- milen.vichev

Answer 1

在这种情况下可能的解决方案是：

for (int col = 0; col < 4; col++)
{
    for (int row = 0; row < 4; row++) 
    {
        // do some stuff
    }
}

- Ilya

---

谢谢您的回复。我正在寻找一个使用迭代器的解决方案，因为它应该更快。 - milen.vichev

好的，我明白了。但是向量的向量对于在正交方向上快速访问元素来说是一个不好的结构。我认为，对于这种结构没有更好的解决方案。而且在你的情况下（小的4x4矩阵），使用其他东西也不会有效。 - Ilya

实际上，矩阵中的元素不是 INT 类型，而是对象类型，但为了方便起见，我使用了 INT 类型。我需要以矩阵形式存储对象，因此选择了向量以快速访问元素。您是否更喜欢其他存储方式？ - milen.vichev

有时使用std::valarray进行此类操作非常有效。但我不知道您的任务，所以无法确定它是否完全适合您。 - Ilya

我需要遍历矩阵，并根据当前单元格的值进行下一个单元格的检查，可能会更改其值。 - milen.vichev

听起来这是std::valarray的好任务，因为它是非常强大的容器。看看std::slice_array、std::mask_array、std::indirect_array和其他方法吧！ - Ilya

Answer 2

我认为实现这一点的方法是通过矩阵的转置：

std::vector<std::vector<int>> transpose(const std::vector<std::vector<int>> &m)
{
  using std::vector;

  vector<vector<int>> result(m[0].size(), vector<int>(m.size()));

  for (vector<int>::size_type i(0); i < m[0].size(); ++i)
    for (vector<int>::size_type j(0); j < m.size(); ++j)
      result[i][j] = m[j][i];

  return result;
}

并且

std::vector<std::vector<int>>::iterator itCol;
std::vector<int>::iterator itRow;
std::vector<std::vector<int>> t(transpose(vMatrix));

for (itRow = t.begin(); itRow != t.end(); itRow++)
  for (itCol = itRow->begin(); itCol != itRow->end(); itCol++)
  {
    // ...
  }

循环体内部不需要进行任何更改，但速度较慢。

您可以通过修改transpose来获得一些速度，以返回矩阵转置的“视图”：

std::vector<std::vector<int *>> transpose(const std::vector<std::vector<int>> &)

无论如何，即使这种解决方案比通过operator[]访问元素要慢。

可能，如果代码重构是一个选项，一个好的解决方案是从向量的向量改变为一维向量，以获得更好的代码局部性（类似于https://dev59.com/02Uo5IYBdhLWcg3wxBwe#15799557）。

- manlio

---

太棒了！非常感谢你！ - milen.vichev