tlx
Loading...
Searching...
No Matches
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
Nodefind (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< Nodenode_alloc_type
 node allocator

Private Member Functions

void delete_node (Node *n)
 delete node

Private Attributes

Noderoot_
 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: