重複のないリストまたは順序付きセット

Question

データ構造を提供するライブラリがあり、アイテムの順序を保持し、重複は含まれていませんか？そのようなデータ構造には適切な名前がありますか？

私はそれがnubのリストのように振舞うと予想します。もちろん、私はそれが非効率的に実装されることは期待していません。

があなたの措置としてSetモノイドでfingertreeを使用します。

Answer 1

は、ここで一つの解決策です。次に、インサートで、完全な指先のmeasureを使用してメンバーシップを最初にチェックします。これにより、あなたはO(log(n))とsnoc、O(1)の削除を行います。

通常Setとのペア通常のリストと基本的に同じ効果を得る：

はここで別のソリューションです。より良い一定の要因が得られますが、O(log(n))が削除されます。

ここに質問があります：複製物を挿入したらどうしますか？既存のポジションを維持すべきか？新しいポジション？優先度キューは、必要に応じて、近くにある可能性があります。