I_lOVE_ROMAN's blog

How much map STL in C++ leads to MLE?
By I_lOVE_ROMAN, history, 4 months ago, In English

Today I used two maps like that 

map<pair<char,int>,int>mp1;

map<pair<char,int>,int>mp2;

It leaded to MLE-Memory Limit exceeded.

I guess some solutions with like this below got accepted-

map<int,vector<int>>mp1

map<int,vector<int>>mp2;

Then a question comes to my mind is there some anticpated benchmarks for using maps.How less complex it should be to avoid MLE?Is there some suggestions?

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by I_lOVE_ROMAN (previous revision, new revision, compare).

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by I_lOVE_ROMAN (previous revision, new revision, compare).

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by I_lOVE_ROMAN (previous revision, new revision, compare).

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You may assume map<T, F> has a size of (sizeof(T) + sizeof(F)) * number of keys. To avoid MLEs, use other data structures, which are most likely to be more efficient, since using map<int, vector<int>> is very impractical.

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

    The data structure map is using is red black tree. There's also the left and right child,the parent pointers and the colour of the node.

    → Reply