c++ - Implement the stack that pops the most frequently added item -

i asked implement stack pops added item in interview. gave him below answer not happy solution.

class stack  {   // map of value , count    map<int,int> cntmap;     public:    void push(int val)    {      // find val in map       // if found increment map count       // else insert pair (val,1)    }     int pop( )    {      // find key in cntmap max value       // using std::max_element       // decrement cntmap count popped val    }  } 

can me correct approach?

it's interesting question, because in push, using key, , in pop, using mapped value. std::map supports first immediately: have is:

++ cntmap[ val ]; 

the [] operator insert entry if key isn't present, initializing mapped type default constructor, int results in 0. don't need if.

the second more difficult. comments, however, give solution: need custom compare, takes 2 std::pair<int, int>, , compares second element. std::max_element return iterator entry you're interested in, can use directly. far (and simple), have consider error conditions: happens if cntmap empty. , might want remove element if count goes down 0 (again, simple, since have iterator designating entry, both key , value).

finally, if interview question, definitly point out pop operation o(n), , might worthwhile (although more complicated) maintain secondary index, find maximum element more quickly. (if interviewing, next question. advanced programmers, however.)