I_lOVE_ROMAN's blog

How much map STL in C++ leads to MLE?
By I_lOVE_ROMAN, history, 21 month(s) 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

Comments Comments (2)
| Write comment?
»
21 month(s) ago, hide # |
← 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
  • »
    »
    21 month(s) ago, hide # ^ |
     
    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