任意の整数型をラベルとして用いることが出来る汎用Trie [詳解]

#include <wordring/trie/trie.hpp>

wordring::basic_trie< Label, Base > の継承関係図

公開型
using	label_type = Label

using	value_type = std::uint32_t

using	size_type = typename container::size_type

using	allocator_type = typename base_type::allocator_type

using	reference = detail::trie_value_proxy

using	const_reference = detail::trie_value_proxy const

using	const_iterator = detail::const_trie_iterator< label_type, typename base_type::const_iterator >

公開メンバ関数
	basic_trie ()
	空のコンテナを構築する [詳解]

	basic_trie (allocator_type const &alloc)
	アロケータを指定して空のコンテナを構築する [詳解]

template<typename InputIterator , typename std::enable_if_t< std::is_integral_v< typename std::iterator_traits< InputIterator >::value_type >, std::nullptr_t > = nullptr>
	basic_trie (InputIterator first, InputIterator last, allocator_type const &alloc=allocator_type())
	直列化データから構築する [詳解]

template<typename ForwardIterator , typename std::enable_if_t< std::negation_v< std::is_integral< typename std::iterator_traits< ForwardIterator >::value_type >>, std::nullptr_t > = nullptr>
	basic_trie (ForwardIterator first, ForwardIterator last, allocator_type const &alloc=allocator_type())
	文字列のリストから構築する [詳解]

	basic_trie (std::initializer_list< detail::trie_node > il, allocator_type const &alloc=allocator_type())
	初期化子リストから構築する [詳解]

template<typename InputIterator , typename std::enable_if_t< std::is_integral_v< typename std::iterator_traits< InputIterator >::value_type >, std::nullptr_t > = nullptr>
void	assign (InputIterator first, InputIterator last)
	直列化データから割り当てる [詳解]

template<typename ForwardIterator , typename std::enable_if_t< std::negation_v< std::is_integral< typename std::iterator_traits< ForwardIterator >::value_type >>, std::nullptr_t > = nullptr>
void	assign (ForwardIterator first, ForwardIterator last)
	文字列リストから割り当てる [詳解]

reference	at (const_iterator pos, index_type &idx)
	葉の値への参照を返す [詳解]

reference	at (const_iterator pos)
	葉の値への参照を返す [詳解]

const_reference	at (const_iterator pos) const
	葉の値への参照を返す [詳解]

template<typename InputIterator >
reference	at (InputIterator first, InputIterator last)
	葉の値への参照を返す [詳解]

template<typename InputIterator >
const_reference	at (InputIterator first, InputIterator last) const
	葉の値への参照を返す [詳解]

template<typename Key >
reference	at (Key const &key)
	葉の値への参照を返す [詳解]

template<typename Key >
const const_reference	at (Key const &key) const
	葉の値への参照を返す [詳解]

template<typename Key >
reference	operator[] (Key const &key)
	葉の値への参照を返す [詳解]

const_iterator	begin () const noexcept
	根を指すイテレータを返す [詳解]

const_iterator	cbegin () const noexcept
	根を指すイテレータを返す [詳解]

const_iterator	end () const noexcept
	根の終端を指すイテレータを返す [詳解]

const_iterator	cend () const noexcept
	根の終端を指すイテレータを返す [詳解]

bool	empty () const noexcept
	キー文字列を格納していないことを調べる [詳解]

size_type	size () const noexcept
	格納しているキー文字列数を調べる [詳解]

template<typename InputIterator >
const_iterator	insert (InputIterator first, InputIterator last, value_type value=0)
	キー文字列を挿入する [詳解]

template<typename Key >
const_iterator	insert (Key const &key, value_type value=0)
	キー文字列を挿入する [詳解]

void	erase (const_iterator pos)
	キー文字列を削除する [詳解]

template<typename InputIterator >
void	erase (InputIterator first, InputIterator last)
	キー文字列を削除する [詳解]

template<typename Key >
void	erase (Key const &key)
	キー文字列を削除する [詳解]

void	swap (basic_trie< Label, Base > &other)

template<typename InputIterator >
auto	lookup (InputIterator first, InputIterator last) const
	部分一致検索 [詳解]

template<typename InputIterator >
const_iterator	search (InputIterator first, InputIterator last) const
	前方一致検索 [詳解]

template<typename Key >
const_iterator	search (Key const &key) const
	前方一致検索 [詳解]

template<typename InputIterator >
const_iterator	find (InputIterator first, InputIterator last) const
	完全一致検索 [詳解]

template<typename Key >
const_iterator	find (Key const &key) const
	完全一致検索 [詳解]

template<typename InputIterator >
bool	contains (InputIterator first, InputIterator last) const
	キー文字列が格納されているか調べる [詳解]

template<typename Key >
bool	contains (Key const &key) const
	キー文字列が格納されているか調べる [詳解]

静的公開メンバ関数
static constexpr size_type	max_size () noexcept
	キー文字列の格納可能な最大数を調べる [詳解]

限定公開型
using	base_type = Base

静的限定公開変数類
static constexpr std::uint32_t	coefficient = sizeof(label_type) / sizeof(typename base_type::label_type)

フレンド
template<typename Label1 , typename Base1 >
std::ostream &	operator<< (std::ostream &, basic_trie< Label1, Base1 > const &)
	ストリームへ出力する [詳解]

template<typename Label1 , typename Base1 >
std::istream &	operator>> (std::istream &, basic_trie< Label1, Base1 > &)
	ストリームから入力する [詳解]

詳解

template<typename Label, typename Base>
class wordring::basic_trie< Label, Base >

任意の整数型をラベルとして用いることが出来る汎用Trie

テンプレート引数

Label	ラベルとして使用する任意の整数型
Base	基本クラスとして使用するTrie実装クラス

メモリー使用量削減を目標とする trie と葉からの空遷移先INDEXが衝突によって変更されない stable_trie が事前に定義されている。

template <typename Label, typename Allocator = std::allocator<detail::trie_node>>
using trie = basic_trie<Label, detail::trie_base<Allocator>>;
 
template <typename Label, typename Allocator = std::allocator<detail::trie_node>>
using stable_trie = basic_trie<Label, detail::stable_trie_base<Allocator>>;

Trie木のコンセプト

Trie木の一般的な説明は、以下のページが詳しい。
https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%82%A4%E6%9C%A8

このクラスは、木に一般化するため、遷移ラベルをノードの値と見做せるよう設計した。そのため、木に対するアルゴリズムを適用できる。

このクラスは任意の整数列を格納できるが、文書内では、キーとして使う整数列のことを文字列と表記する。

利用者からは、以下の図のように見える。

wordring::tree

ラベル

一般的にダブル・アレイはラベルとして8ビット整数を使うが、このクラスは直列化によって任意の整数型をラベルとして利用することが出来る。根はラベルを持たない。

値の格納

葉に2,147,483,647までの正の整数値を格納できる。 mapのように任意の型の値を格納できるよう拡張する場合、値の配列に対する添字を葉に格納することを想定している。葉に格納される値の取得・設定にはメンバ関数 at() を使う。イテレータの逆参照によって得られる値は遷移ラベルであり、葉に格納される値と明確に区別される。

イテレータ

ノード間の移動には、イテレータを用いる。イテレータは木に対するイテレータと互換性を保つよう設計した。イテレータを逆参照すると親から当該ノードへの遷移に使われたラベルを取り出せる。

親を得るには parent() を使う。子を得るには、begin() 、 end() 、 operator[]() を使う。次の兄弟を得るには、 operator++() を使う。葉を指しているか調べるには、operator bool() あるいは operator!() を使う。

detail::const_trie_iterator

予測入力への適用

部分木全体の走査にイテレータ・アダプタを使用できる。 search() と wordring::basic_tree_iterator を組み合わせることで、予測入力などに使える。

search() で前方一致検索を行い、戻り値のイテレータを親として wordring::basic_tree_iterator によって全走査を行う。 operator bool() で葉を確認し、葉を発見するたびに parent() で親をたどると、後続の文字列を容易に列挙できる。候補数を制限したい場合、数に達した時点で走査を止めると良い。

wordring::basic_tree_iterator

直列化

Trie木は辞書や文字列アトムに使われるため、直列化が必要な場合がある。直列化には ibegin(), iend() を使う。

ibegin() の逆参照は32ビット整数値を返す。ファイルへ保存するためにバイト列を必要とする場合、直列化イテレータを使う。

wordring::serialize_iterator

速度

テンプレート・パラメータ Label の大きさが1バイト
文字列リストがソートされている
文字列リストに重複が無い

以上の条件を満たした時、 assign() は最速となる。

挿入される文字列リストが事前にソートされている場合、挿入速度、検索速度共に高速化される。ソートにかかる時間と挿入にかかる時間を足しても、ソートせずに挿入する時間に満たない。したがって、文字列リストを事前にソートしておくことが望ましい。検索速度に顕著な影響を与えることを考慮して事前のソートを推奨する。挿入順による影響は std::set と同様の特性を示す。

ごく少量の文字列しか格納していない場合を除き、大部分が辞書順に挿入された条件下で、検索速度はどのSTLコンテナよりも速い。一方、挿入速度はどのSTLコンテナよりも遅い。

構築子と解体子

◆ basic_trie() [1/5]

template<typename Label , typename Base >

wordring::basic_trie< Label, Base >::basic_trie ( )

inline

空のコンテナを構築する

例: auto t = trie<char32_t>();

◆ basic_trie() [2/5]

template<typename Label , typename Base >

wordring::basic_trie< Label, Base >::basic_trie ( allocator_type const & alloc )

inlineexplicit

アロケータを指定して空のコンテナを構築する

引数

[in] alloc アロケータ

例: auto t = trie<char32_t>(std::allocator<detail::trie_node>());

◆ basic_trie() [3/5]

template<typename Label , typename Base >

template<typename InputIterator , typename std::enable_if_t< std::is_integral_v< typename std::iterator_traits< InputIterator >::value_type >, std::nullptr_t > = nullptr>

wordring::basic_trie< Label, Base >::basic_trie	(	InputIterator	first,
		InputIterator	last,
		allocator_type const &	alloc = `allocator_type()`
	)

inline

直列化データから構築する

引数

[in]	first	直列化データの先頭を指すイテレータ
[in]	last	直列化データの終端を指すイテレータ
[in]	alloc	アロケータ

参照: assign(InputIterator first, InputIterator last); detail::trie_heap::ibegin() const; detail::trie_heap::iend() const

例: // 直列化データを作成

std::vector<std::u32string> v1{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t1 = trie<char32_t>(v1.begin(), v1.end());

std::vector<std::int32_t> v2{ t1.ibegin(), t1.iend() };

// 直列化データから構築

auto t2 = trie<char32_t>(v2.begin(), v2.end());

◆ basic_trie() [4/5]

template<typename Label , typename Base >

template<typename ForwardIterator , typename std::enable_if_t< std::negation_v< std::is_integral< typename std::iterator_traits< ForwardIterator >::value_type >>, std::nullptr_t > = nullptr>

wordring::basic_trie< Label, Base >::basic_trie	(	ForwardIterator	first,
		ForwardIterator	last,
		allocator_type const &	alloc = `allocator_type()`
	)

inline

文字列のリストから構築する

引数

[in]	first	文字列リストの先頭を指すイテレータ
[in]	last	文字列リストの終端を指すイテレータ
[in]	alloc	アロケータ

参照: assign(ForwardIterator first, ForwardIterator last)

例: // 文字列のリスト

std::vector<std::u32string> v1{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

// 文字列のリストから構築

auto t1 = trie<char32_t>(v1.begin(), v1.end());

◆ basic_trie() [5/5]

template<typename Label , typename Base >

wordring::basic_trie< Label, Base >::basic_trie	(	std::initializer_list< detail::trie_node >	il,
		allocator_type const &	alloc = `allocator_type()`
	)

inline

初期化子リストから構築する

引数

[in]	il	ノード・データの初期化子リスト
[in]	alloc	アロケータ

参照: detail::trie_heap::trie_heap(std::initializer_list<trie_node>, allocator_type const&)

例: // 初期化子リストから構築

auto t1 = trie<char32_t>({ { 1, 2 }, { 3, 4 }, { 5, 6 } });

関数詳解

◆ assign() [1/2]

template<typename Label , typename Base >

template<typename InputIterator , typename std::enable_if_t< std::is_integral_v< typename std::iterator_traits< InputIterator >::value_type >, std::nullptr_t > = nullptr>

void wordring::basic_trie< Label, Base >::assign	(	InputIterator	first,
		InputIterator	last
	)

inline

直列化データから割り当てる

引数

[in]	first	直列化データの先頭を指すイテレータ
[in]	last	直列化データの終端を指すイテレータ

バイト直列化の例は以下を参照。

参照: detail::trie_heap::ibegin() const

例: // 元となるtrieを作成

std::vector<std::u32string> v1{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t1 = trie<char32_t>(v1.begin(), v1.end());

// 直列化データを作成

auto v2 = std::vector<std::int32_t>(t1.ibegin(), t1.iend());

// 直列化データから割り当てる

trie<char32_t> t2;

t2.assign(v2.begin(), v2.end());

◆ assign() [2/2]

template<typename Label , typename Base >

template<typename ForwardIterator , typename std::enable_if_t< std::negation_v< std::is_integral< typename std::iterator_traits< ForwardIterator >::value_type >>, std::nullptr_t > = nullptr>

void wordring::basic_trie< Label, Base >::assign	(	ForwardIterator	first,
		ForwardIterator	last
	)

inline

文字列リストから割り当てる

引数

[in]	first	文字列リストの先頭を指すイテレータ
[in]	last	文字列リストの終端を指すイテレータ

参照: trie_heap::assign(InputIterator first, InputIterator last)

例: // 文字列リスト

std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

// 文字列リストから割り当てる

trie<char32_t> t;

t.assign(v.begin(), v.end());

◆ at() [1/7]

template<typename Label , typename Base >

reference wordring::basic_trie< Label, Base >::at	(	const_iterator	pos,
		index_type &	idx
	)

inline

葉の値への参照を返す

引数

[in]	pos	葉を指すイテレータ
[out]	idx	葉の値のインデックス

戻り値: 葉の値に対するプロキシ

葉に2,147,483,647までの正の整数値を格納できる。実際に返される値は軽量プロキシである。

入力の正当性はチェックされない。

このメンバは、継承するクラスから呼び出される目的で用意した。

◆ at() [2/7]

template<typename Label , typename Base >

reference wordring::basic_trie< Label, Base >::at ( const_iterator pos )

inline

葉の値への参照を返す

引数

[in] pos 葉を指すイテレータ

戻り値: 葉の値に対するプロキシ

葉に2,147,483,647までの正の整数値を格納できる。実際に返される値は軽量プロキシである。

入力の正当性はチェックされない。

例: // Trie木を作成

std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t = trie<char32_t>(v.begin(), v.end());

// 検索

auto pos = t.find(std::u32string(U"あう"));

// 値への参照を取得

auto val = t.at(pos);

// 値を設定

val = 100;

// 検証

assert(t.at(std::u32string(U"あう")) == 100);

◆ at() [3/7]

template<typename Label , typename Base >

const_reference wordring::basic_trie< Label, Base >::at ( const_iterator pos ) const

inline

葉の値への参照を返す

引数

[in] pos 葉を指すイテレータ

戻り値: 葉の値に対するプロキシ

参照: at(const_iterator pos)

◆ at() [4/7]

template<typename Label , typename Base >

template<typename InputIterator >

reference wordring::basic_trie< Label, Base >::at	(	InputIterator	first,
		InputIterator	last
	)

inline

葉の値への参照を返す

引数

[in]	first	キー文字列の先頭を指すイテレータ
[in]	last	キー文字列の終端を指すイテレータ

戻り値: 葉の値に対するプロキシ

例外

std::out_of_range キー文字列が格納されていない場合

参照: at(const_iterator pos)

入力の正当性はチェックされる。

例: // Trie木を作成

std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t = trie<char32_t>(v.begin(), v.end());

// 値への参照を取得

std::u32string key{ U"あう" };

auto val = t.at(key.begin(), key.end());

// 値を設定

val = 100;

// 検証

assert(t.at(std::u32string(U"あう")) == 100);

◆ at() [5/7]

template<typename Label , typename Base >

template<typename InputIterator >

const_reference wordring::basic_trie< Label, Base >::at	(	InputIterator	first,
		InputIterator	last
	)		const

inline

葉の値への参照を返す

引数

[in]	first	キー文字列の先頭を指すイテレータ
[in]	last	キー文字列の終端を指すイテレータ

戻り値: 葉の値に対するプロキシ

参照: at(InputIterator first, InputIterator last)

◆ at() [6/7]

template<typename Label , typename Base >

template<typename Key >

reference wordring::basic_trie< Label, Base >::at ( Key const & key )

inline

葉の値への参照を返す

引数

[in] key キー文字列（ラベル列）

戻り値: 葉の値に対するプロキシ

例外

std::out_of_range キーが格納されていない場合

参照: at(const_iterator pos)

入力の正当性はチェックされる。

例: // Trie木を作成

std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t = trie<char32_t>(v.begin(), v.end());

// 値への参照を取得

auto val = t.at(std::u32string(U"あう"));

// 値を設定

val = 100;

// 検証

assert(t.at(std::u32string(U"あう")) == 100);

◆ at() [7/7]

template<typename Label , typename Base >

template<typename Key >

const const_reference wordring::basic_trie< Label, Base >::at ( Key const & key ) const

inline

葉の値への参照を返す

引数

[in] key キー文字列（ラベル列）

戻り値: 葉の値に対するプロキシ

例外

std::out_of_range キーが格納されていない場合

参照: at(Key const& key)

◆ operator[]()

template<typename Label , typename Base >

template<typename Key >

reference wordring::basic_trie< Label, Base >::operator[] ( Key const & key )

inline

葉の値への参照を返す

引数

[in] key キー文字列（ラベル列）

戻り値: 葉の値に対するプロキシ

参照: at(const_iterator pos)

キー文字列が格納されていない場合、新たに挿入し、その葉の値への参照を返す。

例: // Trie木を作成

std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t = trie<char32_t>(v.begin(), v.end());

// 値への参照を取得して、値を設定

t[std::u32string(U"あう")] = 100;

// 検証

assert(t.at(std::u32string(U"あう")) == 100);

◆ begin()

template<typename Label , typename Base >

const_iterator wordring::basic_trie< Label, Base >::begin ( ) const

inlinenoexcept

根を指すイテレータを返す

戻り値: 根を指すイテレータ

空のTrieも根を持つ。

◆ cbegin()

template<typename Label , typename Base >

const_iterator wordring::basic_trie< Label, Base >::cbegin ( ) const

inlinenoexcept

根を指すイテレータを返す

戻り値: 根を指すイテレータ

空のTrieも根を持つ。

◆ end()

template<typename Label , typename Base >

const_iterator wordring::basic_trie< Label, Base >::end ( ) const

inlinenoexcept

根の終端を指すイテレータを返す

戻り値: 根の終端を指すイテレータ

◆ cend()

template<typename Label , typename Base >

const_iterator wordring::basic_trie< Label, Base >::cend ( ) const

inlinenoexcept

根の終端を指すイテレータを返す

戻り値: 根の終端を指すイテレータ

◆ empty()

template<typename Label , typename Base >

bool wordring::basic_trie< Label, Base >::empty ( ) const

inlinenoexcept

キー文字列を格納していないことを調べる

戻り値: 格納している文字列が0の場合 true 、それ以外は false を返す。

◆ size()

template<typename Label , typename Base >

size_type wordring::basic_trie< Label, Base >::size ( ) const

inlinenoexcept

格納しているキー文字列数を調べる

戻り値: コンテナに格納されているキー文字列の数

◆ max_size()

template<typename Label , typename Base >

static constexpr size_type wordring::basic_trie< Label, Base >::max_size ( )

inlinestaticconstexprnoexcept

キー文字列の格納可能な最大数を調べる

戻り値: キー文字列の格納可能な最大数

◆ insert() [1/2]

template<typename Label , typename Base >

template<typename InputIterator >

const_iterator wordring::basic_trie< Label, Base >::insert	(	InputIterator	first,
		InputIterator	last,
		value_type	value = `0`
	)

inline

キー文字列を挿入する

引数

[in]	first	キー文字列の先頭を指すイテレータ
[in]	last	キー文字列の終端を指すイテレータ
[in]	value	葉へ格納する値（省略時は0）

戻り値: 挿入された最後の文字に対応するノードを指すイテレータ

空遷移で終わるとしても、空遷移ではなく最後の文字に対応するノードを指すイテレータを返す。

例: trie<char32_t> t;

// キー文字列と値100を挿入する

auto key = std::u32string(U"あう");

auto it = t.insert(key.begin(), key.end(), 100);

// 挿入された最後の文字に対応するイテレータが返されている

assert(*it == U'う');

// 値100が設定されている

assert(t.at(it) == 100);

// 挿入したキー文字列が格納されている

assert(t.contains(std::u32string(U"あう")));

◆ insert() [2/2]

template<typename Label , typename Base >

template<typename Key >

const_iterator wordring::basic_trie< Label, Base >::insert	(	Key const &	key,
		value_type	value = `0`
	)

inline

キー文字列を挿入する

引数

[in]	key	キー文字列
[in]	value	葉へ格納する値（省略時は0）

戻り値: 挿入された最後の文字に対応するノードを指すイテレータ

空遷移で終わるとしても、空遷移ではなく最後の文字に対応するノードを指すイテレータを返す。

例: trie<char32_t> t;

// キー文字列と値100を挿入する

auto it = t.insert(std::u32string(U"あう"), 100);

// 挿入された最後の文字に対応するイテレータが返されている

assert(*it == U'う');

// 値100が設定されている

assert(t.at(it) == 100);

// 挿入したキー文字列が格納されている

assert(t.contains(std::u32string(U"あう")));

◆ erase() [1/3]

template<typename Label , typename Base >

void wordring::basic_trie< Label, Base >::erase ( const_iterator pos )

inline

キー文字列を削除する

引数

[in] pos 削除するキー文字列の末尾に対応するノードへのイテレータ

例: // Trie木を作成

std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t = trie<char32_t>(v.begin(), v.end());

// キー文字列を検索する

auto it = t.find(std::u32string(U"あう"));

// キーを削除する

t.erase(it);

// 検証

assert(! t.contains(std::u32string(U"あう")));

◆ erase() [2/3]

template<typename Label , typename Base >

template<typename InputIterator >

void wordring::basic_trie< Label, Base >::erase	(	InputIterator	first,
		InputIterator	last
	)

inline

キー文字列を削除する

引数

[in]	first	削除するキー文字列の先頭を指すイテレータ
[in]	last	削除するキー文字列の終端を指すイテレータ

参照: erase(const_iterator pos)

例: // Trie木を作成

std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t = trie<char32_t>(v.begin(), v.end());

// キー文字列を削除する

auto key = std::u32string(U"あう");

t.erase(key.begin(), key.end());

// 検証

assert(! t.contains(std::u32string(U"あう")));

◆ erase() [3/3]

template<typename Label , typename Base >

template<typename Key >

void wordring::basic_trie< Label, Base >::erase ( Key const & key )

inline

キー文字列を削除する

引数

[in] key 削除するキー文字列

参照: erase(const_iterator pos)

例: // Trie木を作成

std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t = trie<char32_t>(v.begin(), v.end());

// キー文字列を削除する

t.erase(std::u32string(U"あう"));

// 検証

assert(! t.contains(std::u32string(U"あう")));

◆ lookup()

template<typename Label , typename Base >

template<typename InputIterator >

auto wordring::basic_trie< Label, Base >::lookup	(	InputIterator	first,
		InputIterator	last
	)		const

inline

部分一致検索

引数

[in]	first	検索するキー文字列の先頭を指すイテレータ
[in]	last	検索するキー文字列の終端を指すイテレータ

戻り値: 一致した最後のノードと次の文字を指すイテレータのペア

一文字も一致しない場合、cbegin()を返す。

例: // Trie木を作成

std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t = trie<char32_t>(v.begin(), v.end());

// キー文字列を部分一致検索する

std::u32string s{ U"うい" };

auto pair = t.lookup(s.begin(), s.end());

// 一致した最後のノードと

assert(*pair.first == U'う');

// 一致した最後のキー文字の次を返す

assert(*pair.second == U'い');

◆ search() [1/2]

template<typename Label , typename Base >

template<typename InputIterator >

const_iterator wordring::basic_trie< Label, Base >::search	(	InputIterator	first,
		InputIterator	last
	)		const

inline

前方一致検索

引数

[in] key 検索するキー文字列

戻り値: 一致した最後のノード

一文字も一致しない場合、cbegin()を返す。

◆ search() [2/2]

template<typename Label , typename Base >

template<typename Key >

const_iterator wordring::basic_trie< Label, Base >::search ( Key const & key ) const

inline

前方一致検索

引数

[in] key 検索するキー文字列

戻り値: 一致した最後のノード

一文字も一致しない場合、cbegin()を返す。

例: // Trie木を作成

std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t = trie<char32_t>(v.begin(), v.end());

// キー文字列を前方一致検索する

auto it = t.search(std::u32string(U"うあ"));

// 葉以外のノードにも一致する

assert(!it);

// 検索文字列全体のみに一致する

assert(*it == U'あ');

◆ find() [1/2]

template<typename Label , typename Base >

template<typename InputIterator >

const_iterator wordring::basic_trie< Label, Base >::find	(	InputIterator	first,
		InputIterator	last
	)		const

inline

完全一致検索

引数

[in]	first	検索するキー文字列の先頭を指すイテレータ
[in]	last	検索するキー文字列の終端を指すイテレータ

戻り値: 入力されたキー文字列と完全に一致する葉がある場合、そのノードを指すイテレータ。それ以外の場合、 cend() 。

◆ find() [2/2]

template<typename Label , typename Base >

template<typename Key >

const_iterator wordring::basic_trie< Label, Base >::find ( Key const & key ) const

inline

完全一致検索

引数

[in] key 検索するキー文字列

戻り値: 入力されたキー文字列と完全に一致する葉がある場合、そのノードを指すイテレータ。それ以外の場合、 cend() 。

例: // Trie木を作成

std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t = trie<char32_t>(v.begin(), v.end());

// キー文字列を完全一致検索する

auto it = t.find(std::u32string(U"あ"));

// 葉のみに一致する

BOOST_CHECK(it);

// 検索文字列全体のみに一致する

BOOST_CHECK(*it == U'あ');

◆ contains() [1/2]

template<typename Label , typename Base >

template<typename InputIterator >

bool wordring::basic_trie< Label, Base >::contains	(	InputIterator	first,
		InputIterator	last
	)		const

inline

キー文字列が格納されているか調べる

引数

[in]	first	キー文字列の先頭を指すイテレータ
[in]	last	キー文字列の終端を指すイテレータ

戻り値: 格納されている場合 true 、それ以外の場合 false

◆ contains() [2/2]

template<typename Label , typename Base >

template<typename Key >

bool wordring::basic_trie< Label, Base >::contains ( Key const & key ) const

inline

キー文字列が格納されているか調べる

引数

[in] key キー文字列

戻り値: 格納されている場合 true 、それ以外の場合 false

例: // Trie木を作成

std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t = trie<char32_t>(v.begin(), v.end());

// キー文字列「うあい」は格納されている

assert(t.contains(std::u32string(U"うあい")));

// キー文字列「え」は格納されていない

assert(t.contains(std::u32string(U"え")) == false);

フレンドと関連関数の詳解

◆ operator<<

template<typename Label , typename Base >

template<typename Label1 , typename Base1 >

std::ostream& operator<<	(	std::ostream &	os,
		basic_trie< Label1, Base1 > const &	trie
	)

friend

ストリームへ出力する

速度を必要とする場合、使用を推奨しない。

例: // Trie木を作成

std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };

auto t1 = trie<char32_t>(v.begin(), v.end());

// ストリームへ出力

std::stringstream ss;

ss << t1;

// ストリームから入力

trie<char32_t> t2;

ss >> t2;

// 検証

assert(t1.size() == t2.size());

◆ operator>>

template<typename Label , typename Base >

template<typename Label1 , typename Base1 >

std::istream& operator>>	(	std::istream &	is,
		basic_trie< Label1, Base1 > &	trie
	)

friend

ストリームから入力する

速度を必要とする場合、使用を推奨しない。

このクラス詳解は次のファイルから抽出されました:

trie.hpp

公開型

公開メンバ関数

静的公開メンバ関数

限定公開型

静的限定公開変数類

フレンド

詳解

template<typename Label, typename Base> class wordring::basic_trie< Label, Base >

構築子と解体子

◆ basic_trie() [1/5]

◆ basic_trie() [2/5]

◆ basic_trie() [3/5]

◆ basic_trie() [4/5]

◆ basic_trie() [5/5]

関数詳解

◆ assign() [1/2]

◆ assign() [2/2]

◆ at() [1/7]

◆ at() [2/7]

◆ at() [3/7]

◆ at() [4/7]

◆ at() [5/7]

◆ at() [6/7]

◆ at() [7/7]

◆ operator[]()

◆ begin()

◆ cbegin()

◆ end()

◆ cend()

◆ empty()

◆ size()

◆ max_size()

◆ insert() [1/2]

◆ insert() [2/2]

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ lookup()

◆ search() [1/2]

◆ search() [2/2]

◆ find() [1/2]

◆ find() [2/2]

◆ contains() [1/2]

◆ contains() [2/2]

フレンドと関連関数の詳解

◆ operator<<

◆ operator>>

template<typename Label, typename Base>
class wordring::basic_trie< Label, Base >