0

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.

Jeff
  • 97
  • 4
  • 4
    `std::stack` is a wrapper around another container. By default, it uses `std::deque`, but you could change it to `std::vector` if you prefer. – Yksisarvinen Mar 30 '22 at 10:27
  • 2
    Possibly related issue: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=77524. Also: https://stackoverflow.com/questions/40203494/why-does-stddeque-allocate-memory-for-its-elements-in-the-default-constructor. – Daniel Langr Mar 30 '22 at 10:32
  • 1
    what online judge did you use? It would help if others can reproduce your measurements – 463035818_is_not_an_ai Mar 30 '22 at 10:34
  • Comparing `std::vector` to `std::deque` would be more appropriate since they exist at the same level of abstraction. – JaMiT Mar 30 '22 at 10:34
  • 5
    The bigger question is why you want to allocate a vector of 300005 stacks!!!?? – paddy Mar 30 '22 at 10:55
  • apparently size_of stack is larger than size_of vector – ttemple Mar 30 '22 at 11:01
  • @ttemple It is, but not 18 times (if by size_of you mean `sizeof`). The core of the problem is somewhere else. – Daniel Langr Mar 30 '22 at 11:10

1 Answers1

2

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.

pptaszni
  • 5,591
  • 5
  • 27
  • 43