大型嵌套向量的高效内存分配

最好只使用一个一维向量,并在某些函数/类中封装行、列索引。这样就保证了整个矩阵的存储器是连续的。

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

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

我将从明显的优化开始。 如果在开始填充值(或可用上限)之前就知道行数,那么只需事先保留空间即可。在推送大量值时花费的大部分时间是通过重新分配内存和复制已包含的值。

Matrix matrix(rows);
for(unsigned i = 0; i < rows; i++) {
    vector<pair<unsigned int, char>> row(cols);
    for(unsigned j; j < cols; j++) {
        row[j] = // value
    }
    matrix[i] = row;
}

使用VS 2010编译器,以下操作效果最佳:

Matrix matrix;
matrix.reserve(rows);

vector<pair<unsigned int, char>> row;
row.reserve(cols);

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

只创建一个用于构建所有行的向量比创建一个每次为“列”条目分配内存的新向量消耗的内存要少得多。但不太清楚为什么会这样。

然而,我接受Andreas的回答,因为这只是我特定案例的解决方案,而他的回答提供了此类优化所需的一般信息。

问题是当外部向量增长时,会有大量数据复制。考虑将typedef更改为

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

和做 matrix.reserve(rows) 在你开始把它与价值观联系起来之前。