meow::SplayTree< Key, Value > Class Template Reference

是一種神乎其技的資料結構, 維護一堆 Key->Value . 並且支援 一些 std::map 難以快速實踐的操作, 如 split , merge , keyOffset More...

#include "SplayTree.h"

Classes
class	Element
	類似 stl 的 iterator ,不過這邊叫做Element More...

Public Member Functions
	SplayTree ()
	constructor More...
	SplayTree (SplayTree const &tree2)
	constructor, 複製資料 More...
	~SplayTree ()
	destructor More...
SplayTree &	copyFrom (SplayTree const &tree2)
	複製資料 More...
void	moveTo (SplayTree *tree2)
	將資料都丟到 tree2 身上, 並且清空自己 More...
Element	lowerBound (Key const &key) const
	找出第一個(最小的) Element且 k <= 它的 Key, 並且回傳之. More...
Element	upperBound (Key const &key) const
	找出第一個(最小的) Element且 k < 它的 Key, 並且回傳之. More...
Element	rLowerBound (Key const &key) const
	找出第一個(最小的) Element且 k >= 它的 Key, 並且回傳之. More...
Element	rUpperBound (Key const &key) const
	找出第一個(最小的) Element且 k > 它的 Key, 並且回傳之. More...
Element	find (Key const &key) const
	找出 Key= k 的Elemenet 並回傳. 找不到的話回傳 this->end() More...
Element	order (size_t order) const
	將Elements依照Key由小到大排序, 回傳第 ord 個Element (由0算起). More...
Element	first () const
	回傳Key最小的Element, 如果SplayTree為空, 則回傳 this->end() More...
Element	last () const
	回傳Key最大的Element, 如果SplayTree為空, 則回傳 this->end() More...
Element	end () const
	回傳一個指向NULL的Element, More...
size_t	size () const
	回傳資料個數 More...
bool	empty () const
	回傳是否為空 More...
void	clear ()
	清空 More...
bool	insert (Key const &key, Value const &value)
	插入一組(Key —> Value) More...
bool	erase (Key const &key)
	刪除一組資料 More...
void	keyOffset (Key const &delta)
	將所有Element的Key同加上 delta More...
void	splitOut (Key const &upper_bound, SplayTree *right)
	將tree2 清空, 再將所有Key > upper_bound 的Element都丟過去 More...
bool	mergeAfter (SplayTree *tree2)
	合併 More...
bool	merge (SplayTree *tree2)
	合併 More...
Value &	operator[] (Key const &key)
	就像stl::map::operator[] More...
SplayTree &	operator= (SplayTree const &tree2)
	same as copyFrom(tree2) More...

Detailed Description

template<class Key, class Value>
class meow::SplayTree< Key, Value >

是一種神乎其技的資料結構, 維護一堆 Key->Value . 並且支援 一些 std::map 難以快速實踐的操作, 如 split , merge , keyOffset

Template Class Operators Request

const?	Typename	Operator	Parameters	Return Type	Description
const	Key	operator+	(Key k)	Key	相加
const	Key	operator<	(Key k)	bool	大小比較
	Key	operator=	(Key k)	Key	copy oper
	Key	Key	(int n)		構子,n 永遠是0
	Value	Value	( )		建構子

Note

: -假設現在有兩個SplayTree A 和 B, 則: -執行 B.moveTo(&A) 後 B 會變成空的, A 原本擁有的資料也會覆蓋掉 -行 A.merge(&B) 或 A.mergeAfter(&B) 後 如果檢查發現確實可以merge, 則之後 B 會變成空的

Author

cat_leopard

Constructor & Destructor Documentation

template<class Key , class Value >

meow::SplayTree< Key, Value >::SplayTree ( )

inline

constructor

template<class Key , class Value >

meow::SplayTree< Key, Value >::SplayTree ( SplayTree< Key, Value > const &  tree2 )

inline

constructor, 複製資料

template<class Key , class Value >

meow::SplayTree< Key, Value >::~SplayTree ( )

inline

destructor

Member Function Documentation

template<class Key , class Value >

void meow::SplayTree< Key, Value >::clear ( )

inline

清空

template<class Key , class Value >

SplayTree& meow::SplayTree< Key, Value >::copyFrom ( SplayTree< Key, Value > const &  tree2 )

inline

複製資料

template<class Key , class Value >

bool meow::SplayTree< Key, Value >::empty ( ) const

inline

回傳是否為空

template<class Key , class Value >

Element meow::SplayTree< Key, Value >::end ( ) const

inline

回傳一個指向NULL的Element,

以供 find ,order ,first ,last 等判斷是否有找到相對應的Element

template<class Key , class Value >

bool meow::SplayTree< Key, Value >::erase ( Key const &  key )

inline

刪除一組資料

檢查是否已有Element的Key 為 key, 若有則刪除之, 並回傳 true, 否則則回傳 false

template<class Key , class Value >

Element meow::SplayTree< Key, Value >::find ( Key const &  key ) const

inline

找出 Key= k 的Elemenet 並回傳. 找不到的話回傳 this->end()

template<class Key , class Value >

Element meow::SplayTree< Key, Value >::first ( ) const

inline

回傳Key最小的Element, 如果SplayTree為空, 則回傳 this->end()

template<class Key , class Value >

bool meow::SplayTree< Key, Value >::insert ( Key const &  key, Value const &  value  )

inline

插入一組(Key —> Value)

檢查是否已有Element的Key 為 key, 若有則回傳 false , 否則將 一個 (Key -> Value) = (key -> value)的Element加入, 並回傳 true

template<class Key , class Value >

void meow::SplayTree< Key, Value >::keyOffset ( Key const &  delta )

inline

將所有Element的Key同加上 delta

template<class Key , class Value >

Element meow::SplayTree< Key, Value >::last ( ) const

inline

回傳Key最大的Element, 如果SplayTree為空, 則回傳 this->end()

template<class Key , class Value >

Element meow::SplayTree< Key, Value >::lowerBound ( Key const &  key ) const

inline

找出第一個(最小的) Element且 k <= 它的 Key, 並且回傳之.

找不到的話回傳 this->end()

template<class Key , class Value >

bool meow::SplayTree< Key, Value >::merge ( SplayTree< Key, Value > *  tree2 )

inline

合併

檢查是否自己中的 Key 都小於 tree2 中的Key, 或是完全相反, 是的話把 tree2`中的 Element 都搬到自己這, 同時清空 tree2 , 否則回傳 false

template<class Key , class Value >

bool meow::SplayTree< Key, Value >::mergeAfter ( SplayTree< Key, Value > *  tree2 )

inline

合併

檢查是否自己中的 Key 都小於 tree2 中的Key, 是的話把 tree2` 中的 Element 都搬到自己這, 同時清空 tree2 , 否則回傳 false

template<class Key , class Value >

void meow::SplayTree< Key, Value >::moveTo ( SplayTree< Key, Value > *  tree2 )

inline

將資料都丟到 tree2 身上, 並且清空自己

template<class Key , class Value >

SplayTree& meow::SplayTree< Key, Value >::operator= ( SplayTree< Key, Value > const &  tree2 )

inline

same as copyFrom(tree2)

template<class Key , class Value >

Value& meow::SplayTree< Key, Value >::operator[] ( Key const &  key )

inline

就像stl::map::operator[]

會先檢查是否已有Element的Key 為 key, 若有則回傳相對應的Value的Reference 否則先執行 insert(key,Value()) 再回傳相對應的Reference

template<class Key , class Value >

Element meow::SplayTree< Key, Value >::order ( size_t  order ) const

inline

將Elements依照Key由小到大排序, 回傳第 ord 個Element (由0算起).

其中如果 ord>N-1, 則會回傳 this->last()

template<class Key , class Value >

Element meow::SplayTree< Key, Value >::rLowerBound ( Key const &  key ) const

inline

找出第一個(最小的) Element且 k >= 它的 Key, 並且回傳之.

找不到的話回傳 this->end()

template<class Key , class Value >

Element meow::SplayTree< Key, Value >::rUpperBound ( Key const &  key ) const

inline

找出第一個(最小的) Element且 k > 它的 Key, 並且回傳之.

找不到的話回傳 this->end()

template<class Key , class Value >

size_t meow::SplayTree< Key, Value >::size ( ) const

inline

回傳資料個數

template<class Key , class Value >

void meow::SplayTree< Key, Value >::splitOut ( Key const &  upper_bound, SplayTree< Key, Value > *  right  )

inline

將tree2 清空, 再將所有Key > upper_bound 的Element都丟過去

template<class Key , class Value >

Element meow::SplayTree< Key, Value >::upperBound ( Key const &  key ) const

inline

找出第一個(最小的) Element且 k < 它的 Key, 並且回傳之.

找不到的話回傳 this->end()

---

The documentation for this class was generated from the following file:

• meowpp/dsa/SplayTree.h