wordring::detail::const_trie_iterator< Label, Base > クラステンプレート

basic_trie のイテレータ [詳解]

#include <trie_iterator.hpp>

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

公開型
using	difference_type = std::ptrdiff_t
using	value_type = Label
using	pointer = value_type *
using	reference = value_type &
using	iterator_category = std::input_iterator_tag

公開メンバ関数
value_type	operator* () const
const_trie_iterator	operator[] (value_type label) const
	ラベルで遷移できる子を返す [詳解]
const_trie_iterator &	operator++ ()
const_trie_iterator	operator++ (int)
template<typename String >
void	string (String &result) const
	根からイテレータが指すノードまでのラベル列を返す [詳解]
const_trie_iterator	parent () const
	親を取得する [詳解]
const_trie_iterator	begin () const
const_trie_iterator	end () const

静的公開変数類
static constexpr std::uint16_t	null_value = 256u
static constexpr std::uint32_t	coefficient = sizeof(value_type) / sizeof(typename base_type::value_type)

限定公開型
using	base_type = Base
using	unsigned_type = std::make_unsigned_t< Label >

限定公開メンバ関数
	const_trie_iterator (container &c, index_type index)
	const_trie_iterator (base_type const &it)

フレンド
template<typename Label1 , typename Base1 >
class	wordring::basic_trie
template<typename Label1 , typename Base1 >
bool	operator== (const_trie_iterator< Label1, Base1 > const &, const_trie_iterator< Label1, Base1 > const &)
template<typename Label1 , typename Base1 >
bool	operator!= (const_trie_iterator< Label1, Base1 > const &, const_trie_iterator< Label1, Base1 > const &)

詳解

template<typename Label, typename Base>
class wordring::detail::const_trie_iterator< Label, Base >

basic_trie のイテレータ

テンプレート引数

Label	ラベルとして使用する任意の整数型
Base	元となる trie_base::const_iterator あるいは stable_trie_base::const_iterator

ダブル・アレイのイテレータを任意の整数型に拡張する。

バイト単位の遷移から複数バイト単位の遷移にするために、いくつかのアルゴリズムを実装する。

関数詳解

operator[]()

template<typename Label , typename Base >

const_trie_iterator wordring::detail::const_trie_iterator< Label, Base >::operator[] ( value_type  label ) const

inline

ラベルで遷移できる子を返す

引数

[in]

label

遷移ラベル

戻り値

遷移先のノードを指すイテレータ

イテレータを使ってノード間を移動する場合、この関数と parent() が最速。 operator++() は若干の探索が発生する。

例

// Trie木を作成
std::vector<std::u32string> v{ U"あ", U"あう", U"い", U"うあい", U"うえ" };
auto t = trie<char32_t>(v.begin(), v.end());
 
// 根を指すイテレータを取得する
auto it = t.begin();
 
// ラベル「う」で遷移する子を取得する
auto it1 = it[U'う'];
 
// 検証
assert(*it1 == U'う');

string()

template<typename Label , typename Base >

template<typename String >

void wordring::detail::const_trie_iterator< Label, Base >::string ( String &  result ) const

inline

根からイテレータが指すノードまでのラベル列を返す

引数

[out]

result

ラベル列を出力する先のコンテナ

出力先を使いまわすために引数でコンテナへの参照を受け取るよう設計した。 コンテナはBidirectionalIteratorを持つ必要がある。

例

// 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"うあ"));
 
// 根からイテレータ「it」迄のラベル列を取得する
std::u32string s;
it.string(s);
 
// 検証
assert(s == U"うあ");

parent()

template<typename Label , typename Base >

const_trie_iterator wordring::detail::const_trie_iterator< Label, Base >::parent ( ) const

inline

親を取得する

戻り値

親ノードを指すイテレータ

例

// 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"うあ"));
 
// イテレータ「it」の親を取得する
auto it1 = it.parent();
 
// 検証
assert(*it1 == U'う');

---

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

• trie_iterator.hpp