c++ - 最も頻繁に追加されるアイテムをポップするスタックを実装する

Question

インタビューで最も頻繁に追加されたアイテムをポップするスタックを実装するように依頼されました。私は彼に以下の答えを与えましたが、彼は解決策に満足していませんでした.

class stack 
{
  // Map of value and count 
  map<int,int> Cntmap; 

  public: 
  void push(int val) 
  { 
    // Find val in map 

    // if found then increment map count 

    // else insert a pair (val,1) 
  } 

  int pop( ) 
  { 
    // Find the Key in Cntmap with max value 

    // using std::max_element 

    // Decrement the Cntmap count for the popped val 
  } 
}

誰でも正しいアプローチで私を助けることができますか?

Answer 1

解決策は、 Boost.Bimapをラップすることです(組織は boost を使用していますか?)。これにより、一方向に順序付けられたアクセスを提供し、反対方向にハッシュされるコンテナを作成できます。プッシュとポップの実装では、bimap の置換機能を使用します。