为什么相同大小的向量比leetcode中的数组占用更多内存

Question

我正在尝试解决来自 leetcode 和相同代码的 Ones and Zeros 问题，但使用向量占用的内存比使用相同大小的数组多 3 倍。这是我使用 3-D 矢量的代码：

int findMaxForm(vector<string>& strs, int m, int n) {
    int S = strs.size();
    vector<vector<vector<int>>> dp(S+1, vector<vector<int>>(m+1, vector<int>(n+1, 0)));

    // int dp[S+1][m+1][n+1];
    // memset(dp, 0, sizeof dp);
    
    for(int i = 0; i < S; i++) {
        for(int j = 0; j <= m; j++) {
            for(int k = 0; k <= n; k++) {
                if(i == 0) {
                    int zeros = count(strs[i].begin(), strs[i].end(), '0');
                    int ones = strs[i].length() - zeros;

                    if(zeros <= j && ones <= k) dp[i][j][k] = 1;
                    else dp[i][j][k] = 0;
                    continue;
                }
                int skip = dp[i - 1][j][k];
    
                int take = INT_MIN;
                int zeros = count(strs[i].begin(), strs[i].end(), '0');
                int ones = strs[i].length() - zeros;
                if(zeros <= j && ones <= k)
                    take = 1 + dp[i - 1][j - zeros][k - ones];

                dp[i][j][k] = max(skip, take);
            }
        }
    }
    
    return dp[S-1][m][n];
}

提交详情：

使用vector：运行时间（~500ms）；内存 （102.6 MB）
使用array：运行时间（~500ms）；内存 (32.5 MB)

Answer 1

一个数组（我假设你使用的是纯 C 数组）只使用与其元素一样多的内存。矢量使用一些内存来存储一些内部管理信息，例如数据的长度和位置。

因为您创建了一个向量的向量向量，所以会为所有嵌套向量创建此管家信息，这会占用很多 space。如果增加“多维”向量的“维数”，情况会变得越来越糟。

为什么相同大小的向量比leetcode中的数组占用更多内存

Why does vector of same size takes more memory than array in leetcode

c++

arrays

vector

dynamic-programming