木コンテナ [詳解]

#include <wordring/tree/tree.hpp>

公開型
using	value_type = T

using	allocator_type = Allocator

using	size_type = std::size_t

using	difference_type = std::ptrdiff_t

using	reference = value_type &

using	const_reference = value_type const &

using	pointer = value_type *

using	const_pointer = value_type const *

using	iterator = detail::tree_node_iterator< container >

using	const_iterator = detail::tree_node_iterator< container const >

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

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

	tree (value_type const &value, allocator_type const &alloc=allocator_type())
	要素からコンテナを構築する [詳解]

	tree (value_type &&value, allocator_type const &alloc=allocator_type())
	要素からコンテナを構築する [詳解]

void	assign (value_type const &value)

void	assign (value_type &&value)

allocator_type	get_allocator () const

reference	front ()

const_reference	front () const

reference	back ()

const_reference	back () const

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

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

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

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

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

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

bool	empty () const noexcept
	要素を格納していないことを調べる [詳解]

size_type	size () const
	格納している要素数を調べる [詳解]

size_type	size (const_iterator pos) const
	部分木が格納するノード数を調べる [詳解]

size_type	max_size () const noexcept
	格納可能な要素の最大数を調べる [詳解]

void	clear () noexcept
	すべての要素を削除する

void	swap (tree &other)

iterator	insert (const_iterator pos, value_type &&value)
	ノードを挿入する [詳解]

iterator	insert (const_iterator pos, value_type const &value)
	要素を挿入する [詳解]

iterator	insert (const_iterator pos, const_iterator sub)
	部分木を挿入する [詳解]

template<typename... Args>
iterator	emplace (const_iterator pos, Args &&... args)

iterator	move (const_iterator pos, const_iterator sub)
	部分木を移動する [詳解]

iterator	erase (const_iterator pos)
	要素を削除する [詳解]

限定公開型
using	node_type = detail::tree_node< T >

using	index_type = typename node_type::index_type

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

限定公開メンバ関数
index_type	allocate (value_type &&val)
	ノードを確保する [詳解]

void	free (index_type idx)
	ノードを解放する [詳解]

void	link (index_type parent, index_type pos, index_type idx)
	ノードを木に挿入する [詳解]

void	unlink (index_type idx)
	ノードを木から取り除く [詳解]

限定公開変数類
container	m_c

静的限定公開変数類
static constexpr index_type	null_value = node_type::null_value

フレンド
template<typename Container1 >
class	detail::tree_node_iterator

詳解

木コンテナ

木

根以外のノードは一つの親を持つ。ノードは0あるいはそれ以上の子を持つ。子を持たないノードを葉と呼ぶ。ノードは0以上の兄弟を持つ。

この tree 実装は、HTML5 パーサーの要求にこたえるため、複数の根を持つことが可能。

イテレータ

tree において要素間の移動はイテレータを使う。 tree のメンバ関数 begin() で根を指すイテレータを取得する。

イテレータのメンバ関数 parent() で親を取得する。イテレータのメンバ関数 begin() で先頭の子を取得する。イテレータのメンバ関数 end() で子の終端を取得する。イテレータのメンバ関数 operator++() で次の兄弟を取得する。

木ノード

tree の内部は、一つの配列にすべてのノードが収まっている。各ノードは、親、子の先頭、前の兄弟、次の兄弟の各インデックスを持つ。配列のインデックスは 1 から始まる。根のインデックスは配列の 0 番目の要素の m_child に格納される。

子の先頭の m_prev には最後の兄弟のインデックスを格納する。先頭の子であることを確認するには、親の m_child と自身が一致するか調べる。

イテレータは、指すノードのインデックスと親のインデックスを保持する。終端を指すイテレータは、インデックスを 0 として示す。終端を指すイテレータも（デクリメントで必要となるため）親のインデックスを保持する。根の親は 0 である。終端を指すイテレータをデクリメントする場合、親の m_child の m_prev へ移動する。

インデックス 0

配列のインデックス 0 は、ノードとして使用されない。そのため、未使用ノードの先頭、格納するノード数を保持するのに使う。

未使用ノード

未使用ノードは、 m_prev に前の未使用ノード、 m_next に次の未使用ノードの各インデックスを格納して双方向リンクリストとする。

未使用ノード末尾は、 m_next に 0 を格納して示す。未使用ノードが一つも無い場合、インデックス 0 の m_next に 0 を格納して示す。

現在の実装は、インデックス順に未使用ノードのリンクが並ぶよう、解放時に整列させる。この動作によって検索性能が向上するが、解放時間が増える。

構築子と解体子

◆ tree() [1/3]

wordring::tree::tree ( allocator_type const & alloc )

inlineexplicit

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

引数

[in] alloc アロケータ

◆ tree() [2/3]

wordring::tree::tree	(	value_type const &	value,
		allocator_type const &	alloc = `allocator_type()`
	)

inlineexplicit

要素からコンテナを構築する

引数

[in]	value	根となる要素
[in]	alloc	アロケータ

◆ tree() [3/3]

wordring::tree::tree	(	value_type &&	value,
		allocator_type const &	alloc = `allocator_type()`
	)

inlineexplicit

要素からコンテナを構築する

引数

[in]	value	根となる要素
[in]	alloc	アロケータ

関数詳解

◆ begin() [1/2]

iterator wordring::tree::begin ( )

inlinenoexcept

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

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

◆ begin() [2/2]

const_iterator wordring::tree::begin ( ) const

inlinenoexcept

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

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

◆ cbegin()

const_iterator wordring::tree::cbegin ( ) const

inlinenoexcept

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

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

◆ end() [1/2]

iterator wordring::tree::end ( )

inlinenoexcept

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

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

◆ end() [2/2]

const_iterator wordring::tree::end ( ) const

inlinenoexcept

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

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

◆ cend()

const_iterator wordring::tree::cend ( ) const

inlinenoexcept

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

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

◆ empty()

bool wordring::tree::empty ( ) const

inlinenoexcept

要素を格納していないことを調べる

戻り値: 要素を格納していない場合 true 、それ以外の場合 false

◆ size() [1/2]

size_type wordring::tree::size ( ) const

inline

格納している要素数を調べる

戻り値: 木に格納されている要素の数

◆ size() [2/2]

size_type wordring::tree::size ( const_iterator pos ) const

inline

部分木が格納するノード数を調べる

引数

[in] pos 部分木の頂点を指すイテレータ

戻り値: 頂点を含めて部分木が格納するノード数

◆ max_size()

size_type wordring::tree::max_size ( ) const

inlinenoexcept

格納可能な要素の最大数を調べる

戻り値: 格納可能な要素の最大数

◆ insert() [1/3]

iterator wordring::tree::insert	(	const_iterator	pos,
		value_type &&	value
	)

inline

ノードを挿入する

引数

[in]	pos	挿入位置を指すイテレータ
[in]	value	挿入する値

戻り値: 挿入されたノードを指すイテレータ

挿入位置は、引数 pos の前。子として追加されるのではないことに注意。

◆ insert() [2/3]

iterator wordring::tree::insert	(	const_iterator	pos,
		value_type const &	value
	)

inline

要素を挿入する

引数

[in]	pos	挿入位置を指すイテレータ
[in]	value	挿入する値

戻り値: 挿入された要素を指すイテレータ

参照: iterator insert(const_iterator pos, value_type&& value)

◆ insert() [3/3]

iterator wordring::tree::insert	(	const_iterator	pos,
		const_iterator	sub
	)

inline

部分木を挿入する

引数

[in]	pos	挿入位置を指すイテレータ
[in]	sub	部分木の根を指すイテレータ

戻り値: 挿入されたノードを指すイテレータ

二つのスタックを使って部分木をコピーするアルゴリズム

スタックを使った一般的な木探索アルゴリズムは、木の構造を保持しないため、 POPしたノードを「どこに挿入するか？」という情報を取り出せない。そこで、挿入地点を記録する「親スタック」を使う。

探索スタックから値をPOPするとき、子が有ればすべて探索スタックにPUSHする。同時に、親を親スタックにPUSHする。 親スタックにPUSHするとき、スタックTOPが挿入しようとするノードの親であるか検査する。親でない場合、POPしてからノードをPUSHする。

以上の操作で、親スタックのTOPは常に挿入地点となる。

ところで、以上のアルゴリズムは、引数の部分木について親を記録する。実際に必要なのは、挿入先の親である。そこで、親スタックには、挿入先の親も一緒に記録する。

実装

根の挿入位置は pos だが、それ以外は親スタックTOPの end() 。従って、根だけ特別扱いが必要。

todo:: スタックはインデックスが有れば十分で、イテレータを入れておくのは冗長。今後、性能を改良するときに考慮する必要がある。

◆ move()

iterator wordring::tree::move	(	const_iterator	pos,
		const_iterator	sub
	)

inline

部分木を移動する

引数

[in]	pos	挿入位置を指すイテレータ
[in]	sub	部分木の根を指すイテレータ

戻り値: 挿入されたノードを指すイテレータ

例外

std::invalid_argument 祖先を子孫へ移動させようとした場合

sub を根とする部分木を pos の前へ移動する。循環するため、祖先を子孫へ移動する事は出来ない。移動後は親が変わるため、sub は不正なイテレータとなる。戻り値のイテレータを使うこと。

親をたどって pos から sub に到達できる場合、祖先を子孫へ移動させようとしている。

◆ erase()

iterator wordring::tree::erase ( const_iterator pos )

inline

要素を削除する

引数

[in] pos 削除する要素を指すイテレータ

戻り値: 削除された要素の次を指すイテレータ

◆ allocate()

index_type wordring::tree::allocate ( value_type && val )

inlineprotected

ノードを確保する

引数

[in] val 格納する値

戻り値: 確保されたノードのインデックス値

◆ free()

void wordring::tree::free ( index_type idx )

inlineprotected

ノードを解放する

引数

[in] idx 解放するノードのインデックス

◆ link()

void wordring::tree::link	(	index_type	parent,
		index_type	pos,
		index_type	idx
	)

inlineprotected

ノードを木に挿入する

引数

[in]	parent	挿入位置の親のインデックス
[in]	pos	挿入位置のインデックス
[in]	idx	挿入するノードのインデックス

挿入するノードは allocate() で得た新規ノード、あるいは unlink() された既存のノード。挿入するノードは子を持つ部分木であっても、子を持たない単独のノードでも構わない。

idx は、allocate() で取得した新規ノードのインデックス。

parent は、引数 pos から取得する。

child は、 parent の m_child 。

after は、（挿入後にAfterとなるので）挿入位置のインデックス。 end() に挿入する場合、 0 。

before は

after が有り
- 且つ parent の m_child が after でない場合、after の m_prev
- それ以外の場合、 0
after が無く
- child が有る場合、 child の m_prev
- それ以外の場合、 0

根を挿入する場合

インデックス 0 の前に挿入。

idx == 1
before == 無し
after == 無し

根は一つしか無い。挿入前に格納数は 0 でなければならない。

ノードの間に挿入する場合

インデックス 3 の前に挿入。

idx == 4
before == 2
after == 3

子が無い場合の挿入

インデックス 0 の前に挿入。

idx == 2
before == 無し
after == 無し

先頭の前に挿入

インデックス 2 の前に挿入。

idx == 4
before == 無し
after == 2

単独の子の先頭の前に挿入

インデックス 2 の前に挿入。

idx == 3
before == 無し
after == 2

終端の前に挿入

インデックス 0 の前に挿入。

idx == 4
before == 3
after == 無し

単独の子の終端の前に挿入

インデックス 0 の前に挿入。

idx == 3
before == 2
after == 無し

before が無い場合

親の m_child を新規挿入されるノードとする。
after が有る場合
- after の m_prev には tail のインデックスが入っている。
after が無い場合
- tail は新規挿入されるノード自身である。
新規挿入されるノードの m_prev を tail とする。

before が有る場合

before の m_next を新規挿入されるノードとする。

after が無い場合

新規挿入されるノードの m_next を 0 とする。
before が有る場合
- 親の m_child には先頭のインデックスが入っている。
- 先頭の m_prev を新規挿入されるノードとする。

after が有る場合

after の m_prev を新規挿入されるノードとする。

◆ unlink()

void wordring::tree::unlink ( index_type idx )

inlineprotected

ノードを木から取り除く

引数

[in] idx 取り除くノード

この関数で取り除いたノードは木の中に無く、解放もされていない。取り除いた後、どこかに挿入するか、解放する必要が有る。

根を除去

idx == 1
before == 0
after == 0

ノードの間を除去

idx == 4
before == 2
after == 3

先頭の前を除去

idx == 4
before == 0
after == 2

除去で単独になる子の前を除去

idx == 4
before == 0
after == 2

終端の前を除去

idx == 4
before == 3
after == 0

除去で単独になる子の終端の前を除去

idx == 3
before == 2
after == 0

parent 、 idx は、 pos から取得する。
child は、 parent の m_child 。
beore は、 idx の m_prev 。
child が idx と一致する場合、before は無い。
after は、 idx の m_next 。

before が無い場合
- 除去後、 after が先頭になる
  - after が有る場合
    - parent の m_child に after を設定する。
    - after の m_prev に idx の m_prev （ココには今、末尾のインデックスが入っている）を設定する。
  - after が無い場合、 parent の m_child に 0 を設定する。
before が有る場合
- before の m_next に after を設定する。 after が無い場合、末尾を表す 0 なので、そのまま設定できる。
after が無い場合
- 除去後、 before が末尾になる
  - before が有る（つまり兄弟がある）場合、 parent の m_child （つまり child ）に before を設定する。
after が有る場合
- after の m_prev に idx の m_prev を設定する。

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

tree.hpp

公開型

公開メンバ関数

限定公開型

限定公開メンバ関数

限定公開変数類

静的限定公開変数類

フレンド

詳解

構築子と解体子

◆ tree() [1/3]

◆ tree() [2/3]

◆ tree() [3/3]

関数詳解

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ end() [1/2]

◆ end() [2/2]

◆ cend()

◆ empty()

◆ size() [1/2]

◆ size() [2/2]

◆ max_size()

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ move()

◆ erase()

◆ allocate()

◆ free()

◆ link()

◆ unlink()