为什么在leetcode中相同大小的vector比array占用更多的内存?

Question

我试图从leetcode和相同的代码中解决1和0问题，但使用向量占用比使用相同大小的数组多3倍的内存。下面是我使用三维矢量的代码:

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数组)只使用与其元素相同的内存。vector使用一些内存来存储一些日常信息，如数据的长度和位置。

因为您创建了向量的向量的向量，所以为所有嵌套的向量创建了这个整理信息，这占用了大量的空间。如果你增加"维度"，情况会越来越糟。你的"多维度"向量。