高速検索のC ++リスト

Question

私はで働いていstd::listます。

要素は、要素の値ではなく、リストへの「挿入順序」で表示されます。

std::find()要素を作成するときは、リスト全体を検索する必要があります。

O（n）からO（log（n））への「検索」を高速化するために、std::list要素の位置を格納するハッシュマップを自分で実装するか、ブースト多重指数を使用することができます。https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookup。

質問：今日、C ++ 17では、リストのすべてのプロパティに加えて高速なfind（たとえばremove）コンテナを実装するための標準/共通またはベストプラクティスの方法はありますか？または、そのようなコンテナタイプはすでに存在しますか？おそらくC ++ 20？

Edit / Nb：リスト内の要素の順序は関連しているため、std :: mapを直接使用することはできません。

Answer 1

の反復子はstd::list挿入と削除の間で有効なままなので（もちろん、削除した要素を除く）、タイプのsecondarayデータ構造std::map <my_key, my_list_iterator>（またはstd::unordered_mapそれがより適切な場合はa ）を維持できます。

次に、リストエントリを追加または削除するたびに、同じことをstd::map / unordered_map実行すれば完了です。もちろん、O（log（n））（またはO（1））の複雑さで検索できます。

Answer 2

Boost MultiIndexを使用して目的の機能を備えたコンテナーを実装する方法に関する非常に短くて理解しやすいガイド（単一の例に基づく） https://stackoverflow.com/a/39510606/11608725

私にとっては、よりフォーマルなスタイルよりも実践的で理解しやすいものです。 https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookupそれはすべての可能な使用法をカバーします（例も使用しますが）。

Answer 3

現在の回答の部分的で非常に原始的な（プロトタイプ）実装 https://stackoverflow.com/a/64539693/11608725 （ポールサンダースによる）：

 #include <unordered_map>
 #include <list>
 #include <iterator>
 #include <iostream>

 using std::unordered_map;
 using std::list;
 using std::make_pair;
 using std::begin;
 using std::end;
 using std::prev;
 using std::cout;

 template <typename T>
 struct fastlist {
    list<T> l;
    unordered_map<T, typename list<T>::iterator> m;
     
    void push_front(T e) {
        l.push_front(e);
        m.insert(make_pair(e, begin(l)));
    }

    void push_back(T e) {
        l.push_back(e);
        m.insert(make_pair(e, prev(end(l))));
    }

    auto find(T e) {
        return m[e];
    }

    void remove(T e) {
        auto it = m[e];
        m.erase(*it);
        l.erase(it);
    }
};

int main() {          // Giving it a spin
    fastlist<int> f;

    f.push_back(3);
    f.push_back(4);
    f.push_back(5);
    f.push_front(2);
    f.push_front(1);
    f.remove(3);
    f.remove(5);
    f.remove(1); 
    f.push_back(200); 
    f.push_front(-100);
    cout << *f.find(4);
}

デモ： https://godbolt.org/z/jdnvdM

他の多くのものの中で、このプロトタイプにはカスタムコンテナを実装するためのイテレータメソッドがありません。これに関する情報はここにあります：STLスタイルのイテレータを実装して一般的な落とし穴を回避する方法は？。

（編集：以下のコメントのTed Lyngmoは、ここでより良いバージョンを提供しています： https://godbolt.org/z/6xfbq7）。

この種のコンテナが箱から出して提供されるとしたら、それは本当に素晴らしいことです。より基本的なコンテナをモデルにした/派生した他のコンテナと同様に、特定の使用状況を反映して特定のパフォーマンス上の利点を追加します。そのような特殊なコンテナを提供するライブラリを知っている人がいたら、教えてください;-)