为什么 std::stack 在用作矢量元素时使用的内存是 std::vector 的 18 倍?

Question

以下代码占用 7000 kb：

vector<vector<int>> v(300005);

虽然这占用超过 131 000 kb：

vector<stack<int>> st(300005)

我还测试了 deque 和队列，这也花费了超过 131 000 kb。

内存使用测量来自将我的程序提交给在线竞争编程评委，因为这是我遇到这个问题的地方。堆栈比矢量占用更多的内存是一个已知的事实，还是与在线法官有关的奇怪事情？在声明单个堆栈和向量时，我还检查了内存使用情况，在这种情况下是相同的。

Answer 1

默认构造容器大小的简单比较：std::vector、std::deque、std::stack：

int main()
{
std::vector<int> v1;
std::deque<int> v2;
std::stack<int> v3;
std::cout << sizeof(v1) << std::endl;
std::cout << sizeof(v2) << std::endl;
std::cout << sizeof(v3) << std::endl;
}

使用 GCC 11 时产量24, 80, 80。如果你偷看一下 STL 向量实现，它由 3 个指针组成，在 64 位架构中，通常每个指针 8 个字节 - 因此矢量的大小为 24 个字节。然后 deque 的实现(和堆栈只是包含在附加功能中的 deque)略有不同。该类由：映射指针、size_t和 2 个迭代器组成。每个迭代器由 4 个指针组成，因此最终std::deque本身需要 80 个字节。

考虑到这一点，理论上你的堆栈向量应该比向量向量占用的内存多 3 倍多一点。我对内存布局不是很熟悉，但我想在某些机器上，由于碎片或单个内存页面大小限制(矢量必须使用连续内存)，它可能需要更多时间。也许这就是为什么你的在线评委显示的次数要多 18 倍。