挿入や削除によって葉を指すイテレータが無効とならない安定なTrie木の実装 [詳解]

#include <stable_trie_base.hpp>

wordring::detail::stable_trie_base< Allocator > の継承関係図

公開型
using	label_type = typename base_type::label_type

using	value_type = std::uint32_t

using	size_type = typename container::size_type

using	allocator_type = Allocator

using	reference = trie_value_proxy

using	const_reference = trie_value_proxy const

using	const_iterator = const_stable_trie_base_iterator< container const >

using	serialize_iterator = trie_heap_serialize_iterator< container const >

基底クラス wordring::detail::trie_heap< std::allocator< trie_node > > に属する継承公開型
using	label_type = std::uint8_t

using	allocator_type = std::allocator< trie_node >

using	serialize_iterator = trie_heap_serialize_iterator< container const >

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

	stable_trie_base (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>
	stable_trie_base (InputIterator first, InputIterator last, allocator_type const &alloc=allocator_type())
	直列化データからの構築 [詳解]

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

	stable_trie_base (std::initializer_list< 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 InputIterator , typename std::enable_if_t< std::negation_v< std::is_integral< typename std::iterator_traits< InputIterator >::value_type >>, std::nullptr_t > = nullptr>
void	assign (InputIterator first, InputIterator 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_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 (stable_trie_base &other)

template<typename InputIterator >
auto	lookup (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
	キー文字列が格納されているか調べる [詳解]

allocator_type	get_allocator () const
	コンテナに関連付けられているアロケータを返す [詳解]

serialize_iterator	ibegin () const
	直列化用のイテレータを返す [詳解]

serialize_iterator	iend () const
	直列化用のイテレータを返す [詳解]

void	clear () noexcept
	すべての要素を削除する [詳解]

基底クラス wordring::detail::trie_heap< std::allocator< trie_node > > に属する継承公開メンバ関数
allocator_type	get_allocator () const
	コンテナに関連付けられているアロケータを返す [詳解]

void	assign (InputIterator first, InputIterator last)
	直列化データから割り当てる [詳解]

serialize_iterator	ibegin () const
	直列化用のイテレータを返す [詳解]

serialize_iterator	iend () const
	直列化用のイテレータを返す [詳解]

void	clear () noexcept
	すべての要素を削除する [詳解]

void	swap (trie_heap &other)

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

限定公開型
using	base_type = trie_heap< Allocator >

using	container = std::vector< trie_node, Allocator >

using	label_vector = static_vector< std::uint16_t, 257 >

using	index_type = typename trie_node::index_type

using	node_type = trie_node

基底クラス wordring::detail::trie_heap< std::allocator< trie_node > > に属する継承限定公開型
using	index_type = typename trie_node::index_type

using	node_type = trie_node

using	container = std::vector< trie_node, std::allocator< trie_node > >

using	label_vector = static_vector< std::uint16_t, 257 >

限定公開メンバ関数
template<typename InputIterator >
auto	lookup (InputIterator first, InputIterator last, std::uint32_t &i) const
	部分一致検索 [詳解]

index_type	limit () const

index_type	free (index_type idx, index_type before=0)

void	free (index_type base, label_vector const &labels, index_type before=0)

bool	has_child (index_type parent) const

bool	has_null (index_type parent) 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)

基底クラス wordring::detail::trie_heap< std::allocator< trie_node > > に属する継承限定公開メンバ関数
	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)

限定公開変数類
container	m_c

基底クラス wordring::detail::trie_heap< std::allocator< trie_node > > に属する継承限定公開変数類
container	m_c

静的限定公開変数類
static constexpr std::uint16_t	null_value

基底クラス wordring::detail::trie_heap< std::allocator< trie_node > > に属する継承静的限定公開変数類
static constexpr std::uint16_t	null_value

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

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

詳解

template<typename Allocator = std::allocator<trie_node>>
class wordring::detail::stable_trie_base< Allocator >

挿入や削除によって葉を指すイテレータが無効とならない安定なTrie木の実装

テンプレート引数

Allocator アロケータ

ダブルアレイの制約により、labelの型は8ビット固定。葉を指すイテレータ以外は、衝突した場合、無効となる。

このクラスは、文字列末尾の次に葉を表現するnull値を挿入することで葉の安定性を保つ。 null値に子は無いため、挿入や削除によって衝突が起きることが無い。末尾にnull値が挿入される分、わずかながらメモリー使用量が増える。

このクラスは、葉のINDEXが変わらない必要のある文字列アトム等の用途を想定している。

内部構造

下図には実際の木構造とダブル・アレイのデータ配置が含まれる。

trie_base との互換性のため、文字列の末尾と値の格納位置は異なる。検索によって返されるイテレータは文字列の末尾を指す。一方、値はさらにnull値で遷移したノードに格納される。イテレータが文字列末尾を指しているか確認するには、イテレータの operator bool() あるいは operator !() を使う。値にアクセスするにはコンテナの at() あるいは operator[]() を使う。

以下の表に位置を示す。

格納されている文字列	find() が返す位置	値の格納位置
a	101	257
ac	100	258
b	102	259
cab	99	260
cd	107	261

参照: wordring::basic_trie

構築子と解体子

◆ stable_trie_base() [1/5]

template<typename Allocator = std::allocator<trie_node>>

wordring::detail::stable_trie_base< Allocator >::stable_trie_base ( )

inline

空のコンテナを構築する

例: auto trie = stable_trie_base();

◆ stable_trie_base() [2/5]

template<typename Allocator = std::allocator<trie_node>>

wordring::detail::stable_trie_base< Allocator >::stable_trie_base ( allocator_type const & alloc )

inlineexplicit

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

引数

[in] alloc アロケータ

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

◆ stable_trie_base() [3/5]

template<typename Allocator = std::allocator<trie_node>>

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

wordring::detail::stable_trie_base< Allocator >::stable_trie_base	(	InputIterator	first,
		InputIterator	last,
		allocator_type const &	alloc = `allocator_type()`
	)

inline

直列化データからの構築

引数

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

参照: assign(InputIterator first, InputIterator last)

例: std::vector<std::string> v1{ "a", "ac", "b", "cab", "cd" };

auto t1 = stable_trie_base(v1.begin(), v1.end());

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

auto t2 = stable_trie_base(v2.begin(), v2.end());

◆ stable_trie_base() [4/5]

template<typename Allocator = std::allocator<trie_node>>

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

wordring::detail::stable_trie_base< Allocator >::stable_trie_base	(	InputIterator	first,
		InputIterator	last,
		allocator_type const &	alloc = `allocator_type()`
	)

inline

文字列リストからの構築

引数

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

例: std::vector<std::string> v{ "a", "ac", "b", "cab", "cd" };

auto trie = stable_trie_base(v.begin(), v.end());

◆ stable_trie_base() [5/5]

template<typename Allocator = std::allocator<trie_node>>

wordring::detail::stable_trie_base< Allocator >::stable_trie_base	(	std::initializer_list< trie_node >	il,
		allocator_type const &	alloc = `allocator_type()`
	)

inline

初期化子リストからの構築

引数

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

例: auto trie = stable_trie_base({ { 0, 1 }, { 2, 3 } });

関数詳解

◆ assign() [1/2]

template<typename Allocator = std::allocator<trie_node>>

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::detail::stable_trie_base< Allocator >::assign	(	InputIterator	first,
		InputIterator	last
	)

inline

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

引数

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

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

例: std::vector<std::string> v1{ "a", "ac", "b", "cab", "cd" };

auto t1 = stable_trie_base(v1.begin(), v1.end());

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

stable_trie_base<> t2;

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

◆ assign() [2/2]

template<typename Allocator = std::allocator<trie_node>>

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

void wordring::detail::stable_trie_base< Allocator >::assign	(	InputIterator	first,
		InputIterator	last
	)

inline

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

引数

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

例: std::vector<std::string> v{ "a", "ac", "b", "cab", "cd" };

stable_trie_base<> trie;

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

葉の値は全て0に初期化される。

◆ at() [1/8]

template<typename Allocator = std::allocator<trie_node>>

reference wordring::detail::stable_trie_base< Allocator >::at	(	const_iterator	pos,
		index_type &	idx
	)

inline

葉の値への参照を返す

引数

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

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

葉からnullで遷移したノードに値が格納される。葉と葉の値のインデックスは明確に異なる。

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

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

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

◆ at() [2/8]

template<typename Allocator = std::allocator<trie_node>>

reference wordring::detail::stable_trie_base< Allocator >::at ( const_iterator pos )

inline

葉の値への参照を返す

引数

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

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

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

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

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

◆ at() [3/8]

template<typename Allocator = std::allocator<trie_node>>

const_reference wordring::detail::stable_trie_base< Allocator >::at ( const_iterator pos ) const

inline

葉の値への参照を返す

引数

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

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

参照: at(const_iterator pos)

◆ at() [4/8]

template<typename Allocator = std::allocator<trie_node>>

template<typename InputIterator >

reference wordring::detail::stable_trie_base< Allocator >::at	(	InputIterator	first,
		InputIterator	last
	)

inline

葉の値への参照を返す

引数

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

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

例外

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

参照: at(const_iterator pos)

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

◆ at() [5/8]

template<typename Allocator = std::allocator<trie_node>>

template<typename InputIterator >

const_reference wordring::detail::stable_trie_base< Allocator >::at	(	InputIterator	first,
		InputIterator	last
	)		const

inline

葉の値への参照を返す

引数

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

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

参照: at(InputIterator first, InputIterator last)

◆ at() [6/8]

template<typename Allocator = std::allocator<trie_node>>

template<typename Key >

reference wordring::detail::stable_trie_base< Allocator >::at ( Key const & key )

inline

葉の値への参照を返す

引数

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

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

例外

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

参照: at(const_iterator pos)

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

◆ at() [7/8]

template<typename Allocator = std::allocator<trie_node>>

template<typename Key >

const_reference wordring::detail::stable_trie_base< Allocator >::at ( Key const & key ) const

inline

葉の値への参照を返す

引数

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

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

例外

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

参照: at(Key const& key)

◆ operator[]()

template<typename Allocator = std::allocator<trie_node>>

template<typename Key >

reference wordring::detail::stable_trie_base< Allocator >::operator[] ( Key const & key )

inline

葉の値への参照を返す

引数

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

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

参照: at(const_iterator pos)

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

◆ begin()

template<typename Allocator = std::allocator<trie_node>>

const_iterator wordring::detail::stable_trie_base< Allocator >::begin ( ) const

inlinenoexcept

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

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

空のTrieも根を持つ。

◆ cbegin()

template<typename Allocator = std::allocator<trie_node>>

const_iterator wordring::detail::stable_trie_base< Allocator >::cbegin ( ) const

inlinenoexcept

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

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

空のTrieも根を持つ。

◆ end()

template<typename Allocator = std::allocator<trie_node>>

const_iterator wordring::detail::stable_trie_base< Allocator >::end ( ) const

inlinenoexcept

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

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

end() と cend() はシグネチャ以外同一である。 stable_trie_base::end() と const_iterator::end() は同一である。

◆ cend()

template<typename Allocator = std::allocator<trie_node>>

const_iterator wordring::detail::stable_trie_base< Allocator >::cend ( ) const

inlinenoexcept

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

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

end() と cend() はシグネチャ以外同一である。 stable_trie_base::end() と const_iterator::end() は同一である。

◆ empty()

template<typename Allocator = std::allocator<trie_node>>

bool wordring::detail::stable_trie_base< Allocator >::empty ( ) const

inlinenoexcept

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

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

◆ size()

template<typename Allocator = std::allocator<trie_node>>

size_type wordring::detail::stable_trie_base< Allocator >::size ( ) const

inlinenoexcept

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

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

◆ max_size()

template<typename Allocator = std::allocator<trie_node>>

static constexpr size_type wordring::detail::stable_trie_base< Allocator >::max_size ( )

inlinestaticconstexprnoexcept

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

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

◆ insert() [1/2]

template<typename Allocator = std::allocator<trie_node>>

template<typename InputIterator >

const_iterator wordring::detail::stable_trie_base< Allocator >::insert	(	InputIterator	first,
		InputIterator	last,
		value_type	value = `0`
	)

inline

キー文字列を挿入する

引数

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

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

キー文字列「ab」を挿入した場合の戻り値は以下の図の通り。

stable_trie_base の葉は必ず空遷移で終わるが、空遷移ではなく最後の文字に対応するノードを指すイテレータを返す。

◆ insert() [2/2]

template<typename Allocator = std::allocator<trie_node>>

template<typename Key >

const_iterator wordring::detail::stable_trie_base< Allocator >::insert	(	Key const &	key,
		value_type	value = `0`
	)

inline

キー文字列を挿入する

引数

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

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

参照: insert(InputIterator, InputIterator, value_type)

stable_trie_base の葉は必ず空遷移で終わるが、空遷移ではなく最後の文字に対応するノードを指すイテレータを返す。

◆ erase() [1/3]

template<typename Allocator = std::allocator<trie_node>>

void wordring::detail::stable_trie_base< Allocator >::erase ( const_iterator pos )

inline

キー文字列を削除する

引数

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

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

◆ erase() [2/3]

template<typename Allocator = std::allocator<trie_node>>

template<typename InputIterator >

void wordring::detail::stable_trie_base< Allocator >::erase	(	InputIterator	first,
		InputIterator	last
	)

inline

キー文字列を削除する

引数

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

参照: erase(const_iterator pos)

◆ erase() [3/3]

template<typename Allocator = std::allocator<trie_node>>

template<typename Key >

void wordring::detail::stable_trie_base< Allocator >::erase ( Key const & key )

inline

キー文字列を削除する

引数

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

参照: erase(const_iterator pos)

◆ lookup() [1/2]

template<typename Allocator = std::allocator<trie_node>>

template<typename InputIterator >

auto wordring::detail::stable_trie_base< Allocator >::lookup	(	InputIterator	first,
		InputIterator	last,
		std::uint32_t &	i
	)		const

inlineprotected

部分一致検索

引数

[in]	first	検索するキー文字列の先頭を指すイテレータ
[in]	last	検索するキー文字列の終端を指すイテレータ
[out]	i	遷移した数（0で初期化されている必要がある）

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

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

このメンバは、 wordring::basic_trie::lookup() から使用される意図で用意された。仮にラベルが4バイトの場合、3バイト目でマッチしなくなった時、3バイト戻る要求があるため、引数 i を通して遷移した数を返すようにした。

◆ lookup() [2/2]

template<typename Allocator = std::allocator<trie_node>>

template<typename InputIterator >

auto wordring::detail::stable_trie_base< Allocator >::lookup	(	InputIterator	first,
		InputIterator	last
	)		const

inline

部分一致検索

引数

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

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

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

◆ search()

template<typename Allocator = std::allocator<trie_node>>

template<typename Key >

const_iterator wordring::detail::stable_trie_base< Allocator >::search ( Key const & key ) const

inline

前方一致検索

引数

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

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

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

◆ find() [1/2]

template<typename Allocator = std::allocator<trie_node>>

template<typename InputIterator >

const_iterator wordring::detail::stable_trie_base< Allocator >::find	(	InputIterator	first,
		InputIterator	last
	)		const

inline

完全一致検索

引数

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

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

◆ find() [2/2]

template<typename Allocator = std::allocator<trie_node>>

template<typename Key >

const_iterator wordring::detail::stable_trie_base< Allocator >::find ( Key const & key ) const

inline

完全一致検索

引数

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

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

◆ contains() [1/2]

template<typename Allocator = std::allocator<trie_node>>

template<typename InputIterator >

bool wordring::detail::stable_trie_base< Allocator >::contains	(	InputIterator	first,
		InputIterator	last
	)		const

inline

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

引数

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

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

◆ contains() [2/2]

template<typename Allocator = std::allocator<trie_node>>

template<typename Key >

bool wordring::detail::stable_trie_base< Allocator >::contains ( Key const & key ) const

inline

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

引数

[in] key キー文字列

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

◆ get_allocator()

template<typename Allocator = std::allocator<trie_node>>

allocator_type wordring::detail::trie_heap< Allocator >::get_allocator

inline

コンテナに関連付けられているアロケータを返す

戻り値: コンテナに関連付けられているアロケータ

◆ ibegin()

template<typename Allocator = std::allocator<trie_node>>

serialize_iterator wordring::detail::trie_heap< Allocator >::ibegin

inline

直列化用のイテレータを返す

戻り値: 直列化データの先頭を示すイテレータ

参照: assign(InputIterator first, InputIterator last); trie_heap::iend() const; wordring::serialize_iterator

このイテレータは逆参照すると32ビット整数値を返すが、 wordring::serialize_iterator を使用してバイト値を返すイテレータに変換できる。一般に、ファイルへ保存する場合にバイトへ直列化する。いずれの場合も、逆参照時に最小限の計算によって値を返すため、軽量である。

バイト直列化イテレータを使用する例

※trie_heapは単独で構築できないため、サンプルはtrieを使用。

// 元となるTrieを作成
std::vector<std::string> v1{ "a", "ac", "b", "cab", "cd" };
auto t1 = trie<char>(v1.begin(), v1.end());
 
// バイト直列化イテレータを作成
auto it1 = serialize_iterator(t1.ibegin());
auto it2 = serialize_iterator(t1.iend());
 
// バイト直列化イテレータから構築
auto t2 = trie<char>(it1, it2);

バイト列に保存する例

※trie_heapは単独で構築できないため、サンプルはtrieを使用。

// 元となるTrieを作成
std::vector<std::string> v1{ "a", "ac", "b", "cab", "cd" };
auto t1 = trie<char>(v1.begin(), v1.end());
 
// バイト直列化イテレータを作成
auto it1 = serialize_iterator(t1.ibegin());
auto it2 = serialize_iterator(t1.iend());
 
// バイト列に保存
auto v2 = std::vector<char>(it1, it2);
 
// バイト列から構築
auto t2 = trie<char>(v2.begin(), v2.end());

◆ iend()

template<typename Allocator = std::allocator<trie_node>>

serialize_iterator wordring::detail::trie_heap< Allocator >::iend

inline

直列化用のイテレータを返す

戻り値: 直列化データの終端を示すイテレータ

参照: trie_heap::ibegin() const

◆ clear()

template<typename Allocator = std::allocator<trie_node>>

void wordring::detail::trie_heap< Allocator >::clear

inlinenoexcept

すべての要素を削除する

ただし、根は削除されない。

◆ free() [1/2]

template<typename Allocator = std::allocator<trie_node>>

index_type wordring::detail::trie_heap< Allocator >::free

inlineprotected

idxを解放して未使用リンクにつなげる

before を返す。
これが次のfree呼び出しのヒントとして使える。

◆ free() [2/2]

template<typename Allocator = std::allocator<trie_node>>

void wordring::detail::trie_heap< Allocator >::free

inlineprotected

base + labelsを解放して未使用リンクにつなげる

◆ has_child()

template<typename Allocator = std::allocator<trie_node>>

bool wordring::detail::trie_heap< Allocator >::has_child

inlineprotected

parentからのラベルによる遷移がある場合、trueを返す

◆ has_null()

template<typename Allocator = std::allocator<trie_node>>

bool wordring::detail::trie_heap< Allocator >::has_null

inlineprotected

parentからの空遷移がある場合、trueを返す

◆ at() [8/8]

template<typename Allocator = std::allocator<trie_node>>

index_type wordring::detail::trie_heap< Allocator >::at

inlineprotected

parentからlabelで遷移したINDEXを返す

遷移先が無ければ0を返す。

◆ add()

template<typename Allocator = std::allocator<trie_node>>

index_type wordring::detail::trie_heap< Allocator >::add

inlineprotected

parentの子としてラベル集合labels内の各ラベルによる遷移を挿入する

配置起点を返す。

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

◆ operator<<

template<typename Allocator = std::allocator<trie_node>>

template<typename Allocator1 >

std::ostream& operator<<	(	std::ostream &	os,
		stable_trie_base< Allocator1 > const &	trie
	)

friend

ストリームへ出力する

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

◆ operator>>

template<typename Allocator = std::allocator<trie_node>>

template<typename Allocator1 >

std::istream& operator>>	(	std::istream &	is,
		stable_trie_base< Allocator1 > &	trie
	)

friend

ストリームから入力する

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

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

stable_trie_base.hpp

公開型

公開メンバ関数

静的公開メンバ関数

限定公開型

限定公開メンバ関数

限定公開変数類

静的限定公開変数類

フレンド

詳解

template<typename Allocator = std::allocator<trie_node>> class wordring::detail::stable_trie_base< Allocator >

構築子と解体子

◆ stable_trie_base() [1/5]

◆ stable_trie_base() [2/5]

◆ stable_trie_base() [3/5]

◆ stable_trie_base() [4/5]

◆ stable_trie_base() [5/5]

関数詳解

◆ assign() [1/2]

◆ assign() [2/2]

◆ at() [1/8]

◆ at() [2/8]

◆ at() [3/8]

◆ at() [4/8]

◆ at() [5/8]

◆ at() [6/8]

◆ at() [7/8]

◆ 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() [1/2]

◆ lookup() [2/2]

◆ search()

◆ find() [1/2]

◆ find() [2/2]

◆ contains() [1/2]

◆ contains() [2/2]

◆ get_allocator()

◆ ibegin()

◆ iend()

◆ clear()

◆ free() [1/2]

◆ free() [2/2]

◆ has_child()

◆ has_null()

◆ at() [8/8]

◆ add()

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

◆ operator<<

◆ operator>>

template<typename Allocator = std::allocator<trie_node>>
class wordring::detail::stable_trie_base< Allocator >