c++ - C++-区間木実装

Question

誰かがinterval treeC++での良い実装を知っていますか？

明らかに、テンプレート駆動型で、boostスタイルのようなものが優れています。

そして別の質問-誰かがテストした場合、std::vectorソートを使用した基本ベースの区間木実装は、実際には一般的な区間木（O（lg）操作を使用）を打ち負かすことができますか？

Answer 1

私にはまったく同じニーズがありました。適切な（シンプル、モダン、ポータブル）実装が見つからなかったため、Brent PedersenによるPython実装をガイドとして使用し、必要最低限​​のC++バージョンを作成しました。IntervalTreeは、標準のSTLコンテナーのように動作しますが、その単純さのためにいくつかの注意点があります（たとえば、イテレーターはありません）。次のように使用します（「T」は任意のタイプです）。

vector<Interval<T> > intervals;
// ... make intervals!
IntervalTree<T> tree(intervals);

そして、次のようにクエリします。

vector<Interval<T> > results;
tree.findContained(start, stop, results);
// results now contains Intervals which are fully contained in the query interval
results.clear();
tree.findOverlapping(start, stop, results);
// results now contains Intervals which overlap the query interval

Answer 2

ブーストのような？ICLをブースト！

ブーストインターバルコンテナライブラリ

Answer 3

NCBI C++Toolkitに1つあるようです。

ジュリーは、それが「良い」かどうかについてはまだ検討していません（そして、それがテンプレート駆動型であるかどうかさえも。私はまだC ++に少し慣れていないので、完全にはわかりませんが、同じくらい疑っています）。

Answer 4

インターバルツリーの簡単な実装をgithubにアップロードしました：https ：//github.com/coolsoftware/ITree

itree.hでクラスitreeを見てください。

Answer 5

ac＃実装をc ++に変換してもかまわない場合は、avl自己平衡ツリーに基づいてhttp://code.google.com/p/intervaltree/にアクセスしてください。