是一種神乎其技的資料結構, 維護一堆 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

Definition at line 37 of file SplayTree.h.