検索可能なスタック

Question

私はコンテンツの効率的な検索を可能にするスタックのようなデータ構造を探しています。効果的には、要素が挿入される順序を維持する構造体が必要ですが、要素の値によってO（n）より速く検索することもできます（重複を防ぐため）。

要素が小さい（ポインタ）であり、私の最大の関心事は、メモリ効率なので、単純に二つの相補的なデータ構造（検索するためと1を維持するために、1）を使用することは絶対に理想的ではありません。

Answer 1

2つのデータ構造のメモリ効率を過小評価しないでください。まず、単純なブーストマルチインデックスコンテナライブラリを試して、そのメモリフットプリントで十分かどうかを確認する必要があります。

私が答えとして考えていた最初のあまりデータ構造は、スキップリストでした。ただし、注文しているキーとは異なるキーを検索しているため、このリストは使用できません。同じアイデアを持っている人たちのために注意してください。

Answer 2

あなたの主な関心事は、本当に、あなたがより良いプリミティブリンクリストデータ構造を使用するためにメモリ効率である場合。線形探索の複雑さは、あなたが逆数を証明していない限りそれほど悪くありません。

または、2つの小さなアップグレードで効率的な検索を行うデータ構造を使用することもできます。各要素には以前に追加された要素へのリンクが含まれているため、逆のリストを作成する必要があります。すなわち、最後に追加された要素。これらのアップグレードは、エレメントのプッシュとポップを容易にするために必要です。