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.

Collaboration diagram for SplayTree< Key, Compare, Duplicates, Allocator >:

#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	check () const
	check the tree order More...

void	clear ()
	free all nodes More...

bool	empty () const
	return true if tree is empty More...

bool	erase (const Key &k)
	erase key from tree, return true if it existed. More...

bool	erase (const Node *n)
	erase node from tree, return true if it existed. More...

bool	exists (const Key &k)
	check if key exists More...

Node *	find (const Key &k)
	find tree node containing key or return smallest key larger than k More...

bool	insert (const Key &k)
	insert key into tree if it does not exist, returns true if inserted. More...

size_t	size () const
	return number of items in tree More...

template<typename Functor >
void	traverse_preorder (const Functor &f) const
	traverse the whole tree in preorder (key order)s More...

Private Types
typedef Allocator::template rebind< Node >::other	node_alloc_type
	node allocator More...

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

Private Attributes
Allocator	alloc_
	key allocator More...

Compare	cmp_
	key comparator More...

node_alloc_type	node_allocator_
	node allocator More...

Node *	root_ = nullptr
	root tree node More...

size_t	size_ = 0
	number of items in tree container More...

Member Typedef Documentation

◆ node_alloc_type

typedef Allocator::template rebind<Node>::other node_alloc_type

private

node allocator

Definition at line 320 of file splay_tree.hpp.

Constructor & Destructor Documentation

◆ SplayTree() [1/2]

SplayTree ( Allocator alloc = Allocator() )

inlineexplicit

Definition at line 233 of file splay_tree.hpp.

◆ SplayTree() [2/2]

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

inlineexplicit

Definition at line 236 of file splay_tree.hpp.

◆ ~SplayTree()

~SplayTree ( )

inline

Definition at line 239 of file splay_tree.hpp.

References SplayTree< Key, Compare, Duplicates, Allocator >::clear().

Member Function Documentation

◆ check()

bool check ( ) const

inline

check the tree order

Definition at line 299 of file splay_tree.hpp.

References SplayTree< Key, Compare, Duplicates, Allocator >::cmp_, SplayTree< Key, Compare, Duplicates, Allocator >::root_, and tlx::splay_check().

◆ clear()

void clear ( )

inline

free all nodes

Definition at line 273 of file splay_tree.hpp.

References SplayTree< Key, Compare, Duplicates, Allocator >::delete_node(), SplayTree< Key, Compare, Duplicates, Allocator >::root_, and tlx::splay_traverse_postorder().

Referenced by SplayTree< Key, Compare, Duplicates, Allocator >::~SplayTree().

◆ delete_node()

void delete_node ( Node * n )

inlineprivate

delete node

Definition at line 326 of file splay_tree.hpp.

Referenced by SplayTree< Key, Compare, Duplicates, Allocator >::clear(), and SplayTree< Key, Compare, Duplicates, Allocator >::erase().

◆ empty()

bool empty ( ) const

inline

return true if tree is empty

Definition at line 289 of file splay_tree.hpp.

References SplayTree< Key, Compare, Duplicates, Allocator >::size_.

◆ erase() [1/2]

bool erase ( const Key & k )

inline

erase key from tree, return true if it existed.

Definition at line 260 of file splay_tree.hpp.

References SplayTree< Key, Compare, Duplicates, Allocator >::cmp_, SplayTree< Key, Compare, Duplicates, Allocator >::delete_node(), SplayTree< Key, Compare, Duplicates, Allocator >::root_, and tlx::splay_erase().

Referenced by SplayTree< Key, Compare, Duplicates, Allocator >::erase().

◆ erase() [2/2]

bool erase ( const Node * n )

inline

erase node from tree, return true if it existed.

Definition at line 268 of file splay_tree.hpp.

References SplayTree< Key, Compare, Duplicates, Allocator >::erase(), and SplayTree< Key, Compare, Duplicates, Allocator >::Node::key.

◆ exists()

bool exists ( const Key & k )

inline

check if key exists

Definition at line 278 of file splay_tree.hpp.

References SplayTree< Key, Compare, Duplicates, Allocator >::cmp_, SplayTree< Key, Compare, Duplicates, Allocator >::Node::key, SplayTree< Key, Compare, Duplicates, Allocator >::root_, and tlx::splay().

◆ find()

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.

References SplayTree< Key, Compare, Duplicates, Allocator >::cmp_, SplayTree< Key, Compare, Duplicates, Allocator >::root_, and tlx::splay().

◆ insert()

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.

References SplayTree< Key, Compare, Duplicates, Allocator >::cmp_, SplayTree< Key, Compare, Duplicates, Allocator >::Node::key, SplayTree< Key, Compare, Duplicates, Allocator >::Node::Node(), SplayTree< Key, Compare, Duplicates, Allocator >::node_allocator_, SplayTree< Key, Compare, Duplicates, Allocator >::root_, SplayTree< Key, Compare, Duplicates, Allocator >::size_, tlx::splay(), and tlx::splay_insert().

◆ size()

size_t size ( ) const

inline

return number of items in tree

Definition at line 284 of file splay_tree.hpp.

References SplayTree< Key, Compare, Duplicates, Allocator >::size_.

◆ traverse_preorder()

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.

References SplayTree< Key, Compare, Duplicates, Allocator >::Node::key, SplayTree< Key, Compare, Duplicates, Allocator >::root_, and tlx::splay_traverse_preorder().

Member Data Documentation

◆ alloc_

Allocator alloc_

private

key allocator

Definition at line 317 of file splay_tree.hpp.

◆ cmp_

Compare cmp_

private

key comparator

Definition at line 315 of file splay_tree.hpp.

Referenced by SplayTree< Key, Compare, Duplicates, Allocator >::check(), SplayTree< Key, Compare, Duplicates, Allocator >::erase(), SplayTree< Key, Compare, Duplicates, Allocator >::exists(), SplayTree< Key, Compare, Duplicates, Allocator >::find(), and SplayTree< Key, Compare, Duplicates, Allocator >::insert().

◆ node_allocator_

node_alloc_type node_allocator_

private

node allocator

Definition at line 323 of file splay_tree.hpp.

Referenced by SplayTree< Key, Compare, Duplicates, Allocator >::insert().

◆ root_

Node* root_ = nullptr

private

root tree node

Definition at line 311 of file splay_tree.hpp.

Referenced by SplayTree< Key, Compare, Duplicates, Allocator >::check(), SplayTree< Key, Compare, Duplicates, Allocator >::clear(), SplayTree< Key, Compare, Duplicates, Allocator >::erase(), SplayTree< Key, Compare, Duplicates, Allocator >::exists(), SplayTree< Key, Compare, Duplicates, Allocator >::find(), SplayTree< Key, Compare, Duplicates, Allocator >::insert(), and SplayTree< Key, Compare, Duplicates, Allocator >::traverse_preorder().

◆ size_

size_t size_ = 0

private

number of items in tree container

Definition at line 313 of file splay_tree.hpp.

Referenced by SplayTree< Key, Compare, Duplicates, Allocator >::empty(), SplayTree< Key, Compare, Duplicates, Allocator >::insert(), and SplayTree< Key, Compare, Duplicates, Allocator >::size().

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

extlib/tlx/tlx/container/splay_tree.hpp

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 >

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Member Typedef Documentation

◆ node_alloc_type

Constructor & Destructor Documentation

◆ SplayTree() [1/2]

◆ SplayTree() [2/2]

◆ ~SplayTree()

Member Function Documentation

◆ check()

◆ clear()

◆ delete_node()

◆ empty()

◆ erase() [1/2]

◆ erase() [2/2]

◆ exists()

◆ find()

◆ insert()

◆ size()

◆ traverse_preorder()

Member Data Documentation

◆ alloc_

◆ cmp_

◆ node_allocator_

◆ root_

◆ size_

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