trie

ポインタベースの Trie ライブラリ． ソース ポイント ポインタと new で実装．Trie という構造体がノードを表す． 実装上のノードは増やす一方で，削除はしない． 「そのノードに要素があるか」と「そのノード以下の部分木に存在する要素の数」は，自動で取れる． ノードに存在する要素数は 0/1．そこはマルチセットではない． その他の操作をしたければ，自分で定義する．(user というフィールドが Trie 構造体にある) 使用法 auto root = new Trie<26, 'a'>(); auto p1 = root->insert("abcde"); // 挿入．必要なノードを作ると同時に，「要素」としても登録． auto p2 = root->search("abc"); // 要素ではないので p2 == nullptr auto p3 = root->search("abcde"); // 要素なので，p3 == p1 auto p4 = root->get_node("abc"); // 要素かどうかに関係なくノードを取る // ノードがないときには nullptr が返るが，この場合 "abcde" ノードがあるので "abc" ノードもある assert(p3->reside); // p3が表す文字列は要素である． assert(not p4->reside); // p4が表す文字列は要素でない． root->insert("abab"); assert(root->size_st == 2) // 部分木に存在する要素の数 p3->erase(); // 要素としての削除．葉であってもノードは削除しない． assert(not p3->reside); assert(p4->size_st == 1); // p1 から root まで辿るループ for (auto p = p1; p; p = p->parent) { /* p に対する処理を書く */ } // 文字列 s の全prefixを処理するループ for (auto [p, i] = make_pair(root, 0); true; p = p->get_child_val(s[i++], true)) { /* 長さ i の prefix に対する処理を書く */ if (i == ssize(s)) break; } // 文字列 s のprefixのうち，要素になっているものを処理するループ for (auto [p, i] = make_pair(root, 0); p; p = p->get_child_val(s[i++])) { if (p->reside) { /* 長さ i の prefix に対する処理を書く */ } if (i == ssize(s)) break; } インタフェース テンプレートパラメタ template < int bt_size, // 文字種 char from, // 最初の文字 typename User = monostate, // ユーザデータの型 typename S = string, // 管理するデータの型．string とか vector<char> とか bool compact = 2 < bt_size, // 省メモリ型 bool has_offset = true // オフセットの管理方法 > struct Trie { bt_size … 文字種．小文字の文字列なら 26, 01列なら 2 など． from … 最初の文字．小文字なら 'a', 01文字列なら '0'，整数の01列なら 0 など． User … ユーザデータの型．引数無しで構築できなければならない．省略値は monostate で，これは，何も要素を持たない構造体． S … この trie で管理するデータの型．たいてい string だろうけれど，vector<int> とかでも可．ただし，値は from から from + bt_size までで，char の範囲に入っていること． compact … たとえば全ノードに長さ26のベクトルを持たせるというのはちょっと無駄なので，ここを true にすると，もう少し領域を節約する．ただし，少しは遅くなる (そんなには遅くないと思う)．false にすると，固定長 array になる． has_offset … ノードに，何文字目であるかを持たせるかどうか．これはノードごと 4 バイトしか違わないので，いつでも true でも良かったか…....