c++ - 更高效地访问 std::vector

Question

在我的项目中，我定义了一个类 Matrix我使用的数据结构是 std::vector<std::vector<T> > matrix;

现在我的问题是:如何更有效地访问它？如果我没记错的话，按索引访问(例如矩阵[i][j])是一个效率 killer ，而建议的方法是通过迭代器。这样对吗？

假设是，那么我有另一个问题:有时我需要知道我正在操作的行或列的索引。例如，考虑与另一个矩阵逐元素相加:我怎么能这样说呢

C[i][j] = A[i][j] + B[i][j]

不使用两个索引i和 j ？然后我有其他操作，比如乘以 Vector (我正在定义的另一个类)，但我想如果我正确理解访问元素的最有效方式，那么我可以复制相同的模式。

Answer 1

how can I access it more efficiently? If I remember correctly, accessing by index (e.g. matrix[i][j]) is an efficiency killer, while the advised way is via iterators. Is this right?

不要猜测，仔细阅读:

Complexity

Constant.

http://en.cppreference.com/w/cpp/container/vector/operator_at

正如 harold 所指出的，这并不意味着它是高效的，但知道这个运算符(总是？)实现类似于...

// data member
T * underlying_array;
// in operator[]
return *(underlying_array + position); // underlying_array[position]

... 这将相对较好，性能明智。请注意，我还听说过向 operator[] 添加边界检查的 STL 实现，这会添加一个分支，因此可能会对性能产生负面影响。

也就是说，您当然可以更改代码以使用迭代器而不是 operator[]，例如:

std::vector<std::vector<T>> A,B,C;
// Check for correct sizes first!
auto a_row = std::begin(A);
auto c_row = std::begin(C);
auto b_row = std::begin(B);
for (; a_row != std::end(A); ++a_row, ++b_row, ++c_row) {
  // Check correct sizes!
  auto a_col = std::begin(*a_row);
  auto b_col = std::begin(*b_row);
  auto c_col = std::begin(*c_row);
  for (; a_col != std::end(*a_row); ++a_col, ++b_col, ++c_col) {
    *c_col = *a_col + *b_col;
  }
}

这可以更有效率……但是否值得……

真正的性能 killer 将是如果您的数据不是全部连续存储的。 std::vector 将它的元素存储在连续的内存中，但是连续存储 std::vector(就像你的“外部” vector 所做的那样)对你没有帮助，因为“内部” vector 可以将它们的数据存储在不同的地方。因此，要将矩阵的所有数据保存在连续的内存中，您应该使用单个 std::vector 并自己进行正确的列 - 行索引(您的矩阵可以提供 operator[] 返回对辅助类实例的引用，该辅助类又实现其 operator[] 以访问矩阵，进行类似 matrix[1][2] 的调用可能)。