c++ - ユニークな要素のスタックのコンテナ

Question

私がやろうとしているのは、ユニークな要素を含むスタックを構築することです。

また、すでにスタックにある要素がプッシュされた場合、要素はプッシュされませんが、既存の要素はスタックの一番上に移動する必要があります。つまり、ABCD + B > ACDB です。

この機能を実現するには、どのコンテナが最適なのか、ここでお知らせしたいと思います。

リスト上のユーザースタックアダプターを使用することにしました。

1. リストは要素の移動に一定の時間を提供します
2. list は、スタックでネイティブにサポートされているコンテナーの 1 つです。

私の選択の欠点は、重複する要素を手動でチェックする必要があることです。

PS私のコンパイラはそれほど最近ではないので、unordered_setを提案しないでください。

Answer 1

基本的には一定時間移動＋長時間探索か、一定時間探索＋長時間移動かのどちらかを選択する必要があります。

どちらがより時間がかかるかはわかりませんが、次のことを考慮してください。

• 要素を追加しようとするたびに、要素が存在するかどうかを検索する必要があります
• コンテナーに「新しい」要素を追加する場合があることは明らかなので、毎回要素を移動する必要はありません。

要素とそのスタック位置を別のコンテナーに保存することをお勧めします。高速検索を提供する方法で要素を格納し、高速移動を提供する方法でスタック位置を格納します。両方をポインターで接続すると (つまり、どの要素がどの位置にあり、どの位置がどの要素を保持しているかがわかります <-- 厄介なフレーズ、私はそれを知っています!)、かなり高速に処理を実行できます。

Answer 2

あなたの要件から、必要な構造はMax Heapから派生できるように思えます。

アイテムだけを保存する代わりに、単調に増加するカウンターから生成されるペア (世代、アイテム) を保存する場合、ヒープの「ルート」は常に最後に見られた要素です (そして、他の要素は実際には重要ではありません)。 、彼らは?)。

• ポップ: ヒープに対する典型的なポップ操作 ( delete-maxoperation)
• プッシュ: 構造内の「アイテム」の一意性を考慮して操作を変更
  • 「アイテム」を探し、見つかった場合はその世代を更新します (increase-key操作)
  • そうでない場合は、挿入します（insert操作）

要素の数 (20) を考えると、上にヒープを構築するのvectorは自然な選択に思えます。