Trie ライブラリ
ポインタベースの 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"); // 存在に関係無くノードを取る assert(p3->reside); // そのノードは存在ノードか? assert(not p4->reside); root->insert("abab"); assert(root->size_st == 2) // 部分木に存在する数 p3->erase(); // 削除 assert(not p3->reside); assert(p4->size_st == 1); インタフェース テンプレートパラメタ 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 でも良かったか…....