hessam94's blog

GNU C++17 gives me memory Limit but MS C++ 17 accepted it, any idea ?

By hessam94, history, 15 months ago, In English

Hello guys,

please take a look at this two submissions, developed on Visual Studio 2019 C++, both code are exactly same:
1- GNU 17 2- MSC++ 17

So I have two questions:
1- what is the difference between these two compilers in terms of memory, at least here.
2- why this amount of memory? I checked inside my code to see how much is taken , it is not that much shown on my submissions. for test case #13 which i get MemLimit, there is only 1 * 1000000 vector. ok, so my vector<queue< int >> is nothing but 4M byte, it should never reach to 256MB ?? I always submitted to GNU because of faster time, never had memory issue.

Could you help me to learn this part.

Thanks
Hessam

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
15 months ago, # |
  Vote: I like it +14 Vote: I do not like it

In C++, a queue<int> is actually just a deque<int>, and its push/pop operations simply call the push/pop functions of the deque inside. You can change which container a queue contains, for example queue<int, list<int>> is a queue that uses a linked list inside instead of a deque.

A deque in libstdc++ (GCC's C++ library) is implemented as a sequence of allocated constant-sized blocks containing its elements. A deque block in libstdc++ is 512 bytes, which means that a queue<int> containing only one element uses at least 512 bytes. (Trivia: it is 4096 bytes if you choose clang.)

Therefore, if you use GCC and create a million non-empty queue<int>s, they will use at least 512MB of memory in total. On the other hand, MSVC's library uses a much smaller block size so a million queues fit inside the memory limit.

Tip: Don't create a lot of queues. In this problem, it's possible to just use vectors. If you must use a lot of queues, you can use queue<int, list<int>> or write your own queue class.

→ Reply