Modules
	B+ Trees

	Loser Trees

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	LruCacheMap< Key, Value, Alloc >
	This is an expected O(1) LRU cache which contains a map of (key -> value) elements. More...

class	LruCacheSet< Key, Alloc >
	This is an expected O(1) LRU cache which contains a set of key-only 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_multiset = SplayTree< Key, Compare, true, Allocator >

template<typename Key , typename Compare = std::less<Key>, typename Allocator = std::allocator<Key>>
using	splay_set = SplayTree< Key, Compare, false, 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...

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...

static bool	operator== (const std::string &a, const StringView &b) noexcept
	Equality operator to compare a std::string with a StringView. More...

template<typename Key , typename Tree , typename Compare >
Tree *	splay (const Key &k, Tree *t, const Compare &cmp)

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_erase (const Key &k, Tree *&t, const Compare &cmp)

template<typename Tree , typename Compare >
Tree *	splay_insert (Tree nn, Tree t, const Compare &cmp)

template<typename Tree , typename Functor >
void	splay_traverse_postorder (const Functor &f, Tree *t)
	traverse the tree in postorder (left, right, node) 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...

Detailed Description

Containers and Data Structures

Typedef Documentation

◆ d_ary_addressable_int_heap

using d_ary_addressable_int_heap = DAryAddressableIntHeap<KeyType, Arity, Compare>

make template alias due to similarity with std::priority_queue

Definition at line 365 of file d_ary_addressable_int_heap.hpp.

◆ d_ary_heap

using d_ary_heap = DAryHeap<KeyType, Arity, Compare>

make template alias due to similarity with std::priority_queue

Definition at line 261 of file d_ary_heap.hpp.

◆ RadixHeapPair

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.

◆ simple_vector

using simple_vector = SimpleVector<T>

make template alias due to similarity with std::vector

Definition at line 229 of file simple_vector.hpp.

◆ splay_multiset

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

Definition at line 340 of file splay_tree.hpp.

◆ splay_set

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

Definition at line 335 of file splay_tree.hpp.

◆ string_view

using string_view = StringView

make alias due to STL similarity

Definition at line 172 of file string_view.hpp.

Enumeration Type Documentation

◆ SimpleVectorMode

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

◆ make_radix_heap()

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.

◆ operator!=()

static bool tlx::operator!=	(	const std::string &	a,
		const StringView &	b
	)

inlinestaticnoexcept

Inequality operator to compare a std::string with a StringView.

Definition at line 160 of file string_view.hpp.

◆ operator<()

static bool tlx::operator<	(	const std::string &	a,
		const StringView &	b
	)

inlinestaticnoexcept

Less operator to compare a std::string with a StringView lexicographically.

Definition at line 166 of file string_view.hpp.

◆ operator==()

static bool tlx::operator==	(	const std::string &	a,
		const StringView &	b
	)

inlinestaticnoexcept

Equality operator to compare a std::string with a StringView.

Definition at line 154 of file string_view.hpp.

Referenced by StackAllocator< Type, Size >::operator!=(), and Delegate< R(A...), Allocator >::operator!=().

◆ splay()

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.

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

◆ splay_check() [1/2]

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.

Referenced by SplayTree< Key, Compare, Duplicates, Allocator >::check(), and tlx::splay_check().

◆ splay_check() [2/2]

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

check the tree order

Definition at line 88 of file splay_tree.hpp.

References tlx::splay_check().

◆ splay_erase()

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.

References tlx::splay(), and gen_data::x.

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

◆ splay_insert()

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.

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

◆ splay_traverse_postorder()

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.

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

◆ splay_traverse_preorder()

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.

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

Modules

Classes

Typedefs

Enumerations

Functions

Detailed Description

Typedef Documentation

◆ d_ary_addressable_int_heap

◆ d_ary_heap

◆ RadixHeapPair

◆ simple_vector

◆ splay_multiset

◆ splay_set

◆ string_view

Enumeration Type Documentation

◆ SimpleVectorMode

Function Documentation

◆ make_radix_heap()

◆ operator!=()

◆ operator<()

◆ operator==()

◆ splay()

◆ splay_check() [1/2]

◆ splay_check() [2/2]

◆ splay_erase()

◆ splay_insert()

◆ splay_traverse_postorder()

◆ splay_traverse_preorder()