tlx
|
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 > |
class | StringView |
StringView is a reference to a part of a string, consisting of only a char pointer and a length. More... | |
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 > |
using | string_view = StringView |
make alias due to STL similarity More... | |
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... | |
static bool | operator== (const std::string &a, const StringView &b) noexcept |
Equality operator to compare a std::string with a StringView. More... | |
static bool | operator!= (const std::string &a, const StringView &b) noexcept |
Inequality operator to compare a std::string with a StringView. More... | |
static bool | operator< (const std::string &a, const StringView &b) noexcept |
Less operator to compare a std::string with a StringView lexicographically. More... | |
Containers and Data Structures.
using d_ary_addressable_int_heap = DAryAddressableIntHeap<KeyType, Arity, Compare> |
make template alias due to similarity with std::priority_queue
Definition at line 374 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 270 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 679 of file radix_heap.hpp.
using simple_vector = SimpleVector<T> |
make template alias due to similarity with std::vector
Definition at line 241 of file simple_vector.hpp.
using splay_multiset = SplayTree<Key, Compare, true, Allocator> |
Definition at line 348 of file splay_tree.hpp.
Definition at line 343 of file splay_tree.hpp.
using string_view = StringView |
make alias due to STL similarity
Definition at line 182 of file string_view.hpp.
|
strong |
enum class to select SimpleVector object initialization
Definition at line 40 of file simple_vector.hpp.
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 659 of file radix_heap.hpp.
|
inlinestaticnoexcept |
Inequality operator to compare a std::string with a StringView.
Definition at line 170 of file string_view.hpp.
|
inlinestaticnoexcept |
Less operator to compare a std::string with a StringView lexicographically.
Definition at line 176 of file string_view.hpp.
|
inlinestaticnoexcept |
Equality operator to compare a std::string with a StringView.
Definition at line 164 of file string_view.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 105 of file splay_tree.hpp.
bool tlx::splay_check | ( | const Tree * | t, |
const Compare & | cmp | ||
) |
check the tree order
Definition at line 96 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 77 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 184 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 164 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 218 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 209 of file splay_tree.hpp.