CODEWITHSUNDEEP
c++memoryvectorstack
Jeff
Jeff

Reputation: 99

Why is std::stack using 18 times more memory than std::vector when used as an element of a vector?

The following code occupies 7000 kb:

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

While this occupies more than 131 000 kb:

vector<stack<int>> st(300005)

I also tested for deque and queue, which took more than 131 000 kb as well.

The memory usage measurements come from submitting my programs to an online competitive programming judge, since this is where I ran into this issue. Is it a known fact that stack takes more memory than vector or is this a weird thing related to the online judge? I also checked for the memory usage when declaring individual stacks and vectors, and in that case it is the same.

Upvotes: 0

Views: 674

Answers (1)

pptaszni
pptaszni

Reputation: 8217

Simple comparison of sizes of default-constructed containers: 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;
}

yields 24, 80, 80 with gcc 11. If you peek into STL vector implementation it is composed of 3 pointers, in 64-bit architecture normally 8 bytes each - hence 24 bytes the size of vector. Then the implementation of deque (and stack is just deque wrapped in additional features) is slightly different. The class consists of: map pointer, size_t, and 2 iterators. Each iterator is composed of 4 pointers, so in the end std::deque itself takes 80 bytes.

Considering that, your vector of stacks should in theory take a bit more than 3 times more memory than vector of vectors. I am not very familiar with memory layouts, but I guess that on some machines it might take significantly more due to fragmentation or single memory page size limits (vector must use a contiguous memory). Maybe that's why your online judge shows 18 times more.

Upvotes: 2

Related Questions