tlx
Containers and Data Structures

Containers and Data Structures. More...

Modules

 B+ Trees
 B+ tree variants.
 
 Loser Trees
 Loser/Tournament tree variants.
 

Classes

class  DAryAddressableIntHeap< KeyType, Arity, Compare >
 This class implements an addressable integer priority queue, precisely a d-ary heap. More...
 
class  DAryHeap< KeyType, Arity, Compare >
 This class implements a d-ary comparison-based heap usable as a priority queue. More...
 
class  LruCacheSet< Key, Alloc >
 This is an expected O(1) LRU cache which contains a set of key-only elements. More...
 
class  LruCacheMap< Key, Value, Alloc >
 This is an expected O(1) LRU cache which contains a map of (key -> value) elements. More...
 
class  RadixHeap< ValueType, KeyExtract, KeyType, Radix >
 This class implements a monotonic integer min priority queue, more specific a multi-level radix heap. More...
 
class  RingBuffer< Type, Allocator >
 A ring (circular) buffer of static (non-growing) size. More...
 
class  SimpleVector< ValueType, Mode >
 Simpler non-growing vector without initialization. More...
 
class  SplayTree< Key, Compare, Duplicates, Allocator >
 

Typedefs

template<typename KeyType , unsigned Arity = 2, typename Compare = std::less<KeyType>>
using d_ary_addressable_int_heap = DAryAddressableIntHeap< KeyType, Arity, Compare >
 make template alias due to similarity with std::priority_queue More...
 
template<typename KeyType , unsigned Arity = 2, typename Compare = std::less<KeyType>>
using d_ary_heap = DAryHeap< KeyType, Arity, Compare >
 make template alias due to similarity with std::priority_queue More...
 
template<typename KeyType , typename DataType , unsigned Radix = 8>
using RadixHeapPair = RadixHeap< std::pair< KeyType, DataType >, radix_heap_detail::PairKeyExtract< KeyType, DataType >, KeyType, Radix >
 This class is a variant of tlx::RadixHeap for data types which do not include the key directly. More...
 
template<typename T >
using simple_vector = SimpleVector< T >
 make template alias due to similarity with std::vector More...
 
template<typename Key , typename Compare = std::less<Key>, typename Allocator = std::allocator<Key>>
using splay_set = SplayTree< Key, Compare, false, Allocator >
 
template<typename Key , typename Compare = std::less<Key>, typename Allocator = std::allocator<Key>>
using splay_multiset = SplayTree< Key, Compare, true, Allocator >
 

Enumerations

enum  SimpleVectorMode { Normal, NoInitButDestroy, NoInitNoDestroy }
 enum class to select SimpleVector object initialization More...
 

Functions

template<typename DataType , unsigned Radix = 8, typename KeyExtract = void>
auto make_radix_heap (KeyExtract &&key_extract) -> RadixHeap< DataType, KeyExtract, decltype(key_extract(std::declval< DataType >())), Radix >
 Helper to easily derive type of RadixHeap for a pre-C++17 compiler. More...
 
template<typename Tree , typename Compare >
bool splay_check (const Tree *t, const Tree *&out_tmin, const Tree *&out_tmax, const Compare &cmp)
 check the tree order, recursively calculate min and max elements More...
 
template<typename Tree , typename Compare >
bool splay_check (const Tree *t, const Compare &cmp)
 check the tree order More...
 
template<typename Key , typename Tree , typename Compare >
Tree * splay (const Key &k, Tree *t, const Compare &cmp)
 Splay using the key i (which may or may not be in the tree.) The starting root is t, and the tree used is defined by rat size fields are maintained. More...
 
template<typename Tree , typename Compare >
Tree * splay_insert (Tree *nn, Tree *t, const Compare &cmp)
 Insert key i into the tree t, if it is not already there. More...
 
template<typename Key , typename Tree , typename Compare >
Tree * splay_erase (const Key &k, Tree *&t, const Compare &cmp)
 Erases i from the tree if it's there. More...
 
template<typename Tree , typename Functor >
void splay_traverse_preorder (const Functor &f, const Tree *t)
 traverse the tree in preorder (left, node, right) More...
 
template<typename Tree , typename Functor >
void splay_traverse_postorder (const Functor &f, Tree *t)
 traverse the tree in postorder (left, right, node) More...
 

Detailed Description

Containers and Data Structures.

Typedef Documentation

using d_ary_addressable_int_heap = DAryAddressableIntHeap<KeyType, Arity, Compare>

make template alias due to similarity with std::priority_queue

Definition at line 296 of file d_ary_addressable_int_heap.hpp.

using d_ary_heap = DAryHeap<KeyType, Arity, Compare>

make template alias due to similarity with std::priority_queue

Definition at line 200 of file d_ary_heap.hpp.

using RadixHeapPair = RadixHeap< std::pair<KeyType, DataType>, radix_heap_detail::PairKeyExtract<KeyType, DataType>, KeyType, Radix >

This class is a variant of tlx::RadixHeap for data types which do not include the key directly.

Hence each entry is stored as an (Key,Value)-Pair implemented with std::pair.

Definition at line 671 of file radix_heap.hpp.

using simple_vector = SimpleVector<T>

make template alias due to similarity with std::vector

Definition at line 222 of file simple_vector.hpp.

using splay_multiset = SplayTree<Key, Compare, true, Allocator>

Definition at line 340 of file splay_tree.hpp.

using splay_set = SplayTree<Key, Compare, false, Allocator>

Definition at line 335 of file splay_tree.hpp.

Enumeration Type Documentation

enum SimpleVectorMode
strong

enum class to select SimpleVector object initialization

Enumerator
Normal 

Initialize objects at allocation and destroy on deallocation.

NoInitButDestroy 

Do not initialize objects at allocation, but destroy on deallocation.

Thus, all objects must be constructed from outside.

NoInitNoDestroy 

Do not initialize objects at allocation and do not destroy them.

Definition at line 28 of file simple_vector.hpp.

Function Documentation

auto tlx::make_radix_heap ( KeyExtract &&  key_extract) -> RadixHeap<DataType, KeyExtract, decltype(key_extract(std::declval<DataType>())), Radix>

Helper to easily derive type of RadixHeap for a pre-C++17 compiler.

Refer to RadixHeap for description of parameters.

Definition at line 651 of file radix_heap.hpp.

Tree* tlx::splay ( const Key &  k,
Tree *  t,
const Compare &  cmp 
)

Splay using the key i (which may or may not be in the tree.) The starting root is t, and the tree used is defined by rat size fields are maintained.

Definition at line 97 of file splay_tree.hpp.

bool tlx::splay_check ( const Tree *  t,
const Tree *&  out_tmin,
const Tree *&  out_tmax,
const Compare &  cmp 
)

check the tree order, recursively calculate min and max elements

Definition at line 69 of file splay_tree.hpp.

bool tlx::splay_check ( const Tree *  t,
const Compare &  cmp 
)

check the tree order

Definition at line 88 of file splay_tree.hpp.

Tree* tlx::splay_erase ( const Key &  k,
Tree *&  t,
const Compare &  cmp 
)

Erases i from the tree if it's there.

Return a pointer to the resulting tree.

Definition at line 176 of file splay_tree.hpp.

Tree* tlx::splay_insert ( Tree *  nn,
Tree *  t,
const Compare &  cmp 
)

Insert key i into the tree t, if it is not already there.

Before calling this method, one MUST call splay() to rotate the tree to the right position. Return a pointer to the resulting tree.

Definition at line 156 of file splay_tree.hpp.

void tlx::splay_traverse_postorder ( const Functor &  f,
Tree *  t 
)

traverse the tree in postorder (left, right, node)

Definition at line 210 of file splay_tree.hpp.

void tlx::splay_traverse_preorder ( const Functor &  f,
const Tree *  t 
)

traverse the tree in preorder (left, node, right)

Definition at line 201 of file splay_tree.hpp.