終端の空遷移を併合したTrie木の実装 [詳解]

#include <trie_base.hpp>

wordring::detail::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_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 >

公開メンバ関数
	trie_base ()
	空のコンテナを構築する

	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>
	trie_base (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>
	trie_base (ForwardIterator first, ForwardIterator last, allocator_type const &alloc=allocator_type())
	文字列リストからの構築 [詳解]

	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 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)
	葉の値への参照を返す [詳解]

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

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
	部分一致検索 [詳解]

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)
	直列化データから割り当てる [詳解]

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	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)

基底クラス 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 &, trie_base< Allocator1 > const &)
	ストリームへ出力する [詳解]

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

詳解

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

終端の空遷移を併合したTrie木の実装

テンプレート引数

Allocator アロケータ

ダブルアレイの制約により、labelの型は8ビット固定。挿入や削除による衝突によってすべてのイテレータが無効となる。

内部構造

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

BASEが0以下の場合、子が無い、つまり葉であることを示す。値を反転させ負の値とすることで、葉に数値を格納できる（省略時は0）。

検索によって返されるイテレータは文字列の末尾を指す。上図で、文字列「ac」の遷移途中のノードに文字列「a」の葉がある。こういう場合は、nullによる遷移を追加して葉を表現する。

イテレータが文字列末尾を指しているか確認するには、イテレータの operator bool() あるいは operator !() を使う。値にアクセスするにはコンテナの at() あるいは operator[]() を使う。

以下の表に位置を示す。

格納されている文字列	find() が返す位置	値の格納位置
a	98	258
ac	101	101
b	99	99
cab	103	103
cd	105	105

参照: wordring::basic_trie

構築子と解体子

◆ trie_base() [1/4]

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

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

inlineexplicit

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

引数

[in] alloc アロケータ

◆ trie_base() [2/4]

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::trie_base< Allocator >::trie_base	(	InputIterator	first,
		InputIterator	last,
		allocator_type const &	alloc = `allocator_type()`
	)

inline

直列化データからの構築

引数

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

参照: assign(InputIterator first, InputIterator last)

◆ trie_base() [3/4]

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

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::detail::trie_base< Allocator >::trie_base	(	ForwardIterator	first,
		ForwardIterator	last,
		allocator_type const &	alloc = `allocator_type()`
	)

inline

文字列リストからの構築

引数

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

◆ trie_base() [4/4]

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

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

inline

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

引数

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

関数詳解

◆ assign() [1/3]

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::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

◆ assign() [2/3]

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

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

inline

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

引数

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

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

◆ at() [1/7]

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

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

inline

葉の値への参照を返す

引数

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

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

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

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

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

◆ at() [2/7]

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

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

inline

葉の値への参照を返す

引数

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

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

参照: at(const_iterator pos)

◆ at() [3/7]

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

template<typename InputIterator >

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

inline

葉の値への参照を返す

引数

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

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

例外

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

参照: at(const_iterator pos)

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

◆ at() [4/7]

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

template<typename InputIterator >

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

inline

葉の値への参照を返す

引数

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

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

参照: at(InputIterator first, InputIterator last)

◆ at() [5/7]

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

template<typename Key >

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

inline

葉の値への参照を返す

引数

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

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

例外

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

参照: at(const_iterator pos)

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

◆ at() [6/7]

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

template<typename Key >

const const_reference wordring::detail::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::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::trie_base< Allocator >::begin ( ) const

inlinenoexcept

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

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

空のTrieも根を持つ。

◆ cbegin()

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

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

inlinenoexcept

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

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

空のTrieも根を持つ。

◆ end()

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

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

inlinenoexcept

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

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

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

◆ cend()

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

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

inlinenoexcept

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

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

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

◆ empty()

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

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

inlinenoexcept

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

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

◆ size()

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

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

inlinenoexcept

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

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

◆ max_size()

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

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

inlinestaticconstexprnoexcept

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

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

◆ insert() [1/2]

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

template<typename InputIterator >

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

inline

キー文字列を挿入する

引数

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

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

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

◆ insert() [2/2]

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

template<typename Key >

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

inline

キー文字列を挿入する

引数

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

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

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

◆ erase() [1/3]

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

void wordring::detail::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::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::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::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::trie_base< Allocator >::lookup	(	InputIterator	first,
		InputIterator	last
	)		const

inline

部分一致検索

引数

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

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

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

◆ search() [1/2]

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

template<typename InputIterator >

const_iterator wordring::detail::trie_base< Allocator >::search	(	InputIterator	first,
		InputIterator	last
	)		const

inline

前方一致検索

引数

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

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

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

◆ search() [2/2]

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

template<typename Key >

const_iterator wordring::detail::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::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::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::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::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

すべての要素を削除する

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

◆ assign() [3/3]

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::trie_heap< Allocator >::assign	(	typename InputIterator	,
		typename std::enable_if_t< std::is_integral_v< typename std::iterator_traits< InputIterator >::value_type >, std::nullptr_t >	= `nullptr`
	)

inlineprotected

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

引数

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

直列化データは[ibegin(), iend())から作成された整数値のリストを想定する。整数の型（ビットの大きさ）は指定されず、適切に処理される。 [ibegin(), iend())から返される32ビット整数のコンテナでも、ファイルから読み込まれた8ビット整数のコンテナでも構わない。

参照: ibegin() const
iend() const

例

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

// 元となる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());

◆ 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を解放して未使用リンクにつなげる

◆ is_tail()

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

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

inlineprotected

idxが遷移終端に達しているか、あるいはnull_valueによる遷移を持つ場合、trueを返す

has_childとhas_nullの組み合わせで表現できるが、検索高速化のため独立して用意した。

◆ 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を返す

◆ has_sibling() [1/2]

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

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

inlineprotected

idxにnull_value以外の兄弟がある場合、trueを返す

◆ has_sibling() [2/2]

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

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

inlineprotected

idxにnull_value以外の兄弟がある場合、trueを返す

◆ at() [7/7]

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,
		trie_base< Allocator1 > const &	trie
	)

friend

ストリームへ出力する

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

◆ operator>>

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

template<typename Allocator1 >

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

friend

ストリームから入力する

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

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

trie_base.hpp

公開型

公開メンバ関数

静的公開メンバ関数

限定公開型

限定公開メンバ関数

限定公開変数類

静的限定公開変数類

フレンド

詳解

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

構築子と解体子

◆ trie_base() [1/4]

◆ trie_base() [2/4]

◆ trie_base() [3/4]

◆ trie_base() [4/4]

関数詳解

◆ assign() [1/3]

◆ assign() [2/3]

◆ at() [1/7]

◆ at() [2/7]

◆ at() [3/7]

◆ at() [4/7]

◆ at() [5/7]

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

◆ lookup() [2/2]

◆ search() [1/2]

◆ search() [2/2]

◆ find() [1/2]

◆ find() [2/2]

◆ contains() [1/2]

◆ contains() [2/2]

◆ get_allocator()

◆ ibegin()

◆ iend()

◆ clear()

◆ assign() [3/3]

◆ free() [1/2]

◆ free() [2/2]

◆ is_tail()

◆ has_child()

◆ has_null()

◆ has_sibling() [1/2]

◆ has_sibling() [2/2]

◆ at() [7/7]

◆ add()

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

◆ operator<<

◆ operator>>

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