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

Question

我正在尝试解决leetcode 中的Ones 和 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 数组）仅使用与其元素一样多的内存。向量使用一些内存来存储一些内务信息，例如数据的长度和位置。

因为您创建了向量的向量的向量，所以会为所有嵌套向量创建此内务信息，这会占用大量空间。如果您增加“多维”向量的“维度”，情况会变得越来越糟。