ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1306. Sequence Median

multiset VS priority_queue
Posted by JackVoo 6 Dec 2010 15:15
I use the multiset initially with the similar method. However, I had a memory limit exist. After, I saw the discussion, then I change the container to priority_queue.
Then I am able to solve the quetion. I just wonder, why with the similar algorithm, the memory usage is different? 1 396 KB vs 972 KB.

The memory usage of multiset is more than simple array is used then sorted. 1 084 KB
Re: multiset VS priority_queue
Posted by Ruslan Nigmatullin [Ural FU] 19 Dec 2010 18:11
multiset uses Red-Black Tree data structure, so it stores for every element not only it's value (4 bytes), but also addresses of it's parent (4 bytes more), both children (8 bytes) and color (enum, 4 bytes). So, as you can see, it spends 28 bytes for every element versus 4 bytes at priority_queue