GlydonNeedsDedication's blog

C++ Map Memory Limit Exceeded!
By GlydonNeedsDedication, history, 3 years ago, In English

For a practice problem of bitmask in Topic Stream Mashup: Bitwise Operations
( If not opening , click HERE )
I wrote 2 solutions ( Solution1 , Solution2 )
Solution1 is accepted
But Solution2 is showing Memory Limit Exceeded even for testcase1

Can Anyone explain why this happening?

The only change between the two codes is shown here ->
main difference

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Even if mask is not in the map, the operator[] will insert it and default initialize the value with 0.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes, but for the first test case n is 3, which is very small, even if I consider 26 unique cases for each of the 3 masked values it should not be too much for a map to handle right? I am not getting that point.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The problem is that you are iterating over cnt while also adding additional entries to it. This could lead to RTE but in your case it seems to end up in a cascade of inserts...

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But you change the outer loop's mask value to any constant value instead of x.ff , the overall thing works fine without any problem, how is this happening?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          suppose initially cnt only contains the entry for 1. then in the first iteration, you will insert 0,2,4,8,... in the next iteration, you may take the entry 2 and will insert the values 3,0,6,10,... in the end, you could end up with 2^26 entries in the map. (Note that this is just an example. We don't really know in which order you will iterate over the entries in the map)

          → Reply