SplayTree< Key, Compare, Duplicates, Allocator > Class Template Reference

#include <splay_tree.hpp>

Classes
struct	Node
	splay tree node, also seen as public iterator More...

Public Member Functions
	SplayTree (Allocator alloc=Allocator())
	SplayTree (Compare cmp, Allocator alloc=Allocator())
	~SplayTree ()
bool	insert (const Key &k)
	insert key into tree if it does not exist, returns true if inserted.
bool	erase (const Key &k)
	erase key from tree, return true if it existed.
bool	erase (const Node *n)
	erase node from tree, return true if it existed.
void	clear ()
	free all nodes
bool	exists (const Key &k)
	check if key exists
size_t	size () const
	return number of items in tree
bool	empty () const
	return true if tree is empty
Node *	find (const Key &k)
	find tree node containing key or return smallest key larger than k
bool	check () const
	check the tree order
template<typename Functor>
void	traverse_preorder (const Functor &f) const
	traverse the whole tree in preorder (key order)s

Private Types
typedef std::allocator_traits< Allocator >::template rebind_alloc< Node >	node_alloc_type
	node allocator

Private Member Functions
void	delete_node (Node *n)
	delete node

Private Attributes
Node *	root_
	root tree node
size_t	size_
	number of items in tree container
Compare	cmp_
	key comparator
Allocator	alloc_
	key allocator
node_alloc_type	node_allocator_
	node allocator

Detailed Description

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>
class tlx::SplayTree< Key, Compare, Duplicates, Allocator >

Definition at line 223 of file splay_tree.hpp.

Member Typedef Documentation

node_alloc_type

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

typedef std::allocator_traits<Allocator>::template rebind_alloc<Node> node_alloc_type

private

node allocator

Definition at line 320 of file splay_tree.hpp.

Constructor & Destructor Documentation

SplayTree() [1/2]

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

SplayTree ( Allocator alloc = Allocator() )

inlineexplicit

Definition at line 233 of file splay_tree.hpp.

SplayTree() [2/2]

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

SplayTree ( Compare cmp, Allocator alloc = Allocator() )

inlineexplicit

Definition at line 236 of file splay_tree.hpp.

~SplayTree()

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

~SplayTree ( )

inline

Definition at line 239 of file splay_tree.hpp.

Member Function Documentation

check()

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

bool check ( ) const

inline

check the tree order

Definition at line 299 of file splay_tree.hpp.

clear()

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

void clear ( )

inline

free all nodes

Definition at line 273 of file splay_tree.hpp.

delete_node()

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

void delete_node ( Node * n )

inlineprivate

delete node

Definition at line 326 of file splay_tree.hpp.

empty()

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

bool empty ( ) const

inline

return true if tree is empty

Definition at line 289 of file splay_tree.hpp.

erase() [1/2]

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

bool erase ( const Key & k )

inline

erase key from tree, return true if it existed.

Definition at line 260 of file splay_tree.hpp.

erase() [2/2]

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

bool erase ( const Node * n )

inline

erase node from tree, return true if it existed.

Definition at line 268 of file splay_tree.hpp.

exists()

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

bool exists ( const Key & k )

inline

check if key exists

Definition at line 278 of file splay_tree.hpp.

find()

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

Node * find ( const Key & k )

inline

find tree node containing key or return smallest key larger than k

Definition at line 294 of file splay_tree.hpp.

insert()

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

bool insert ( const Key & k )

inline

insert key into tree if it does not exist, returns true if inserted.

Definition at line 244 of file splay_tree.hpp.

size()

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

size_t size ( ) const

inline

return number of items in tree

Definition at line 284 of file splay_tree.hpp.

traverse_preorder()

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

template<typename Functor>

void traverse_preorder ( const Functor & f ) const

inline

traverse the whole tree in preorder (key order)s

Definition at line 305 of file splay_tree.hpp.

Member Data Documentation

alloc_

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

Allocator alloc_

private

key allocator

Definition at line 317 of file splay_tree.hpp.

cmp_

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

Compare cmp_

private

key comparator

Definition at line 315 of file splay_tree.hpp.

node_allocator_

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

node_alloc_type node_allocator_

private

node allocator

Definition at line 323 of file splay_tree.hpp.

root_

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

Node* root_

private

root tree node

Definition at line 311 of file splay_tree.hpp.

size_

template<typename Key, typename Compare = std::less<Key>, bool Duplicates = false, typename Allocator = std::allocator<Key>>

size_t size_

private

number of items in tree container

Definition at line 313 of file splay_tree.hpp.

---

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

• tlx/container/splay_tree.hpp