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 StringView &a, const std::string &b) noexcept
	equality operator to compare a StringView with a std::string More...

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

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

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

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

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

static bool	operator> (const StringView &x, const std::string &y) noexcept

static bool	operator> (const std::string &x, const StringView &y) noexcept

static bool	operator<= (const StringView &x, const std::string &y) noexcept

static bool	operator<= (const std::string &x, const StringView &y) noexcept

static bool	operator>= (const StringView &x, const std::string &y) noexcept

static bool	operator>= (const std::string &x, const StringView &y) noexcept

static bool	operator== (const StringView &x, const char *y) noexcept
	equality operator to compare a StringView with a const char* More...

static bool	operator== (const char *x, const StringView &y) noexcept
	equality operator to compare a StringView with a const char* More...

static bool	operator!= (const StringView &x, const char *y) noexcept
	inequality operator to compare a StringView with a const char* More...

static bool	operator!= (const char *x, const StringView &y) noexcept
	inequality operator to compare a StringView with a const char* More...

static bool	operator< (const StringView &x, const char *y) noexcept

static bool	operator< (const char *x, const StringView &y) noexcept

static bool	operator> (const StringView &x, const char *y) noexcept

static bool	operator> (const char *x, const StringView &y) noexcept

static bool	operator<= (const StringView &x, const char *y) noexcept

static bool	operator<= (const char *x, const StringView &y) noexcept

static bool	operator>= (const StringView &x, const char *y) noexcept

static bool	operator>= (const char *x, const StringView &y) noexcept

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 365 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 261 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 672 of file radix_heap.hpp.

using simple_vector = SimpleVector<T>

make template alias due to similarity with std::vector

Definition at line 255 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.

using string_view = StringView

make alias due to STL similarity

Definition at line 473 of file string_view.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 652 of file radix_heap.hpp.

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

inlinestaticnoexcept

inequality operator to compare a StringView with a std::string

Definition at line 494 of file string_view.hpp.

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

inlinestaticnoexcept

inequality operator to compare a StringView with a std::string

Definition at line 500 of file string_view.hpp.

static bool tlx::operator!=	(	const StringView &	x,
		const char *	y
	)

inlinestaticnoexcept

inequality operator to compare a StringView with a const char*

Definition at line 567 of file string_view.hpp.

static bool tlx::operator!=	(	const char *	x,
		const StringView &	y
	)

inlinestaticnoexcept

inequality operator to compare a StringView with a const char*

Definition at line 573 of file string_view.hpp.

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

inlinestaticnoexcept

less operator to compare a StringView with a std::string lexicographically

Definition at line 507 of file string_view.hpp.

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

inlinestaticnoexcept

less operator to compare a StringView with a std::string lexicographically

Definition at line 515 of file string_view.hpp.

static bool tlx::operator<	(	const StringView &	x,
		const char *	y
	)

inlinestaticnoexcept

Definition at line 578 of file string_view.hpp.

static bool tlx::operator<	(	const char *	x,
		const StringView &	y
	)

inlinestaticnoexcept

Definition at line 583 of file string_view.hpp.

static bool tlx::operator<=	(	const StringView &	x,
		const std::string &	y
	)

inlinestaticnoexcept

Definition at line 531 of file string_view.hpp.

static bool tlx::operator<=	(	const std::string &	x,
		const StringView &	y
	)

inlinestaticnoexcept

Definition at line 536 of file string_view.hpp.

static bool tlx::operator<=	(	const StringView &	x,
		const char *	y
	)

inlinestaticnoexcept

Definition at line 598 of file string_view.hpp.

static bool tlx::operator<=	(	const char *	x,
		const StringView &	y
	)

inlinestaticnoexcept

Definition at line 603 of file string_view.hpp.

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

inlinestaticnoexcept

equality operator to compare a StringView with a std::string

Definition at line 480 of file string_view.hpp.

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

inlinestaticnoexcept

equality operator to compare a StringView with a std::string

Definition at line 487 of file string_view.hpp.

static bool tlx::operator==	(	const StringView &	x,
		const char *	y
	)

inlinestaticnoexcept

equality operator to compare a StringView with a const char*

Definition at line 555 of file string_view.hpp.

static bool tlx::operator==	(	const char *	x,
		const StringView &	y
	)

inlinestaticnoexcept

equality operator to compare a StringView with a const char*

Definition at line 561 of file string_view.hpp.

static bool tlx::operator>	(	const StringView &	x,
		const std::string &	y
	)

inlinestaticnoexcept

Definition at line 521 of file string_view.hpp.

static bool tlx::operator>	(	const std::string &	x,
		const StringView &	y
	)

inlinestaticnoexcept

Definition at line 526 of file string_view.hpp.

static bool tlx::operator>	(	const StringView &	x,
		const char *	y
	)

inlinestaticnoexcept

Definition at line 588 of file string_view.hpp.

static bool tlx::operator>	(	const char *	x,
		const StringView &	y
	)

inlinestaticnoexcept

Definition at line 593 of file string_view.hpp.

static bool tlx::operator>=	(	const StringView &	x,
		const std::string &	y
	)

inlinestaticnoexcept

Definition at line 541 of file string_view.hpp.

static bool tlx::operator>=	(	const std::string &	x,
		const StringView &	y
	)

inlinestaticnoexcept

Definition at line 546 of file string_view.hpp.

static bool tlx::operator>=	(	const StringView &	x,
		const char *	y
	)

inlinestaticnoexcept

Definition at line 608 of file string_view.hpp.

static bool tlx::operator>=	(	const char *	x,
		const StringView &	y
	)

inlinestaticnoexcept

Definition at line 613 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 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.

Modules

Classes

Typedefs

Enumerations

Functions

Detailed Description

Typedef Documentation

Enumeration Type Documentation

Function Documentation