c++ - 大型嵌套 vector 的高效内存分配

Question

我正在创建一个存储在嵌套 vector 中的巨大矩阵:

typedef vector<vector<pair<unsigned int, char>>> Matrix;

外部 vector 最终将包含约 400.000 个 vector ，每个 vector 最多包含约 220 对(大多数包含较少)。这需要大约 1GB 的 RAM，并且是这样完成的:

Matrix matrix;
for (unsigned int i = 0; i < rows; i++) {
    vector<pair<unsigned int, char>> row;
    for (unsigned int j = 0; j < cols; j++) {
        // ...calculations...
        row.push_back( pair<unsigned int, char>(x, y) );
    }
    matrix.push_back(row);
}

前 20% 进行得相当快，但外部 vector 增长越大，整个过程就越慢。我很确定可以进行一些优化，但我不是该领域的专家。有什么简单的技巧可以加快速度吗？还是我的尝试存在重大错误？

Answer 1

最好只使用一个一维 vector 并在某些函数/类中包含行、列索引。这样整个矩阵的内存保证是连续的。

而不是使用 push_back 预先分配整个矩阵:

std::vector<pair<unsigned int, char>> matrix(rows * cols);