c++ - 挿入順序を維持し、重複を排除するための C++ のデータ構造

Question

ユーザーがデータを入力した順序を維持する必要がありますが、重複を排除する必要があります。マップを見たところ、重複は解消されましたが、ユーザーが入力した順序を維持することはできません。セットと同じ問題。両方の要件を満たすことができる stl のデータ構造はありますか? このプロジェクトではブーストを使用できません。

Answer 1

問題は、検索順序を維持すると、重複を検索するのにコストがかかるため、両方を実行するデータ構造を見つける傾向がないことです。C++11 では が導入されstd::unordered_setていますが、これはおそらくあなたが望むものです。

C++11 を使用しない場合は、いくつかの標準コンテナーをクラスにカプセル化できます。項目を asetまたはにポップmapし、イテレータを項目に格納することをお勧めしますvector。

Answer 2

マップとリストを維持します。各要素について、リストに追加する前にマップを検索します。見つからない場合は、リストに追加してマップに挿入します。それ以外の場合は続行します。