c++ - C++ インターバル ツリー アルゴリズムの実装を見つける

Question

バイラルまたは制限的なライセンスなしで、効率的な C++ 間隔ツリーの実装 (ほとんどの場合、赤黒木に基づく) を見つけようとしています。クリーンで軽量なスタンドアロン実装へのポインタはありますか? 私が念頭に置いているユースケースでは、一連の間隔は最初からわかっており (100 万と言うでしょう)、特定の間隔と重なる間隔のリストをすばやく取得できるようにしたいと考えています。したがって、一度構築されたツリーは変更されません。迅速なクエリが必要なだけです。

Answer 1

テンプレートベースの間隔ツリーの実装を C++ で作成しました ( https://github.com/ekg/intervaltree )。MIT ライセンス。楽しみ。

Answer 2

C++ 標準ライブラリには、赤/黒の木std::map、std::multimap、std::setおよびが用意されていますstd::multiset。

実際、これをより効率的に処理するには、 a の反復子のペアを保持し、std::mapそれらの反復子のペアを and に渡すupper_bound()方法は考えられませんlower_bound()。どのペアが間隔内にある可能性が高いかを簡単にゼロにできるように、イテレータのペアをマップ自体に保持する必要があります (「候補間隔」の開始イテレータが指定された間隔の終了後に来る場合)。あなたが見ているなら、そのチェックをスキップすることができます-そしてそれ以降-イテレータのペア)。

Answer 3

このリンクには、間隔ツリーの C# 実装もあります。必要な人のために C++ に変換するのは簡単です。