|
|
| trie_heap (allocator_type const &alloc) |
| |
| | trie_heap (std::initializer_list< trie_node > il, allocator_type const &alloc=allocator_type()) |
| | 初期化子リストから構築する [詳解]
|
| |
|
index_type | limit () const |
| |
|
void | reserve (std::size_t n, index_type before=0) |
| |
| void | allocate (index_type idx, index_type before=0) |
| |
| void | allocate (index_type base, label_vector const &labels, index_type before=0) |
| |
| index_type | relocate (index_type parent, index_type from, label_vector const &labels) |
| |
| index_type | free (index_type idx, index_type before=0) |
| |
| void | free (index_type base, label_vector const &labels, index_type before=0) |
| |
| index_type | locate (label_vector const &labels, index_type &before) const |
| |
| bool | is_free (index_type base, label_vector const &labels) const |
| |
| bool | is_free (index_type parent, index_type base, label_vector const &labels) const |
| |
| bool | is_tail (index_type idx) const |
| |
| bool | has_child (index_type parent) const |
| |
| bool | has_null (index_type parent) const |
| |
| bool | has_sibling (index_type idx) const |
| |
| bool | has_sibling (index_type parent, index_type idx) const |
| |
| index_type | at (index_type parent, std::uint16_t label) const |
| |
|
index_type | add (index_type parent, std::uint16_t label) |
| |
| index_type | add (index_type parent, label_vector const &labels) |
| |
template<typename Allocator>
class wordring::detail::trie_heap< Allocator >
ダブル・アレイによるTrie実装のメモリー管理を行う
根は常にINDEX1となる。 INDEX0は使用されないため、0は末尾を示す値としても使用される。
- 配列の利用法
ダブル・アレイの添字は1から始まるため、INDEX0は使用されない。 そのため、以下の用途で使う。
- INDEX0のBASEに葉の数を記録し、size()の戻り値として使う（葉は格納するキーの数と同義）。
- INDEX0のCHECKに符号を反転させて未使用ノードの先頭INDEXを記録する（未使用ノードが無い場合、0）。
ダブル・アレイのBASEは子の配置基準INDEXを示すため、1未満の値は格納されない。 および、葉は子を持たないため、BASEを使用しない。 そのため、以下の用途で使う。
- 1未満の値が格納されている場合、そのノードは葉である（デフォルト値は0）。
- オプションとして葉に正の整数値を格納可能とする。
- 葉に正の整数値を格納する場合、符号を反転させて格納し、葉であることを示す。
- 値を取り出す場合、符号を反転させて、正の整数値として返す。
ダブル・アレイのCHECKは親のINDEXを示すため、1未満の値は格納されない。 そのため、以下の用途に使う。
- 1未満の値が格納されている場合、そのノードは未使用である（ただし、根のCHECKは常に使用状態且つ値は0）。
- 未使用ノードのINDEXの符号を反転させてつなげ、一方向リンクリストとする。
- 未使用ノードの末尾は、値を0として示す。
- 未使用ノードのリンクリストは、解放のたびに、INDEX順に並ぶよう整列させる。
- 整列によってキーの挿入・検索速度が30％～40％向上する。
- 検索速度の向上は、キー挿入時にINDEXが散らばらず、キャッシュに乗りやすく配置されるためと 考えられる。
- 配列のイメージ
- 上図で未使用ノードは2と4。
- 格納される文字列は「2」一つ。
- 根である1からラベル「2」で3へ遷移。
- 葉3の値として100を保持。
template<typename Allocator >
template<typename InputIterator , typename std::enable_if_t< std::is_integral_v< typename std::iterator_traits< InputIterator >::value_type >, std::nullptr_t > = nullptr>
直列化データから割り当てる
- 引数
-
| [in] | first | 直列化データの先頭を指すイテレータ |
| [in] | last | 直列化データの終端を指すイテレータ |
直列化データは[ibegin(), iend())から作成された整数値のリストを想定する。 整数の型（ビットの大きさ）は指定されず、適切に処理される。 [ibegin(), iend())から返される32ビット整数のコンテナでも、ファイルから読み込まれた8ビット整数のコンテナでも構わない。
- 参照
- ibegin() const
iend() const
- 例
※trie_heapは単独で構築できないため、サンプルはtrieを使用。
std::vector<std::string> v1{ "a", "ac", "b", "cab", "cd" };
auto t1 = trie<char>(v1.begin(), v1.end());
std::vector<std::int32_t> v2{ t1.ibegin(), t1.iend() };
trie<char> t2;
t2.assign(v2.begin(), v2.end());
