tlx
Loading...
Searching...
No Matches
Containers and Data Structures

Containers and Data Structures. More...

Topics

 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
 make template alias due to similarity with std::priority_queue
template<typename KeyType, unsigned Arity = 2, typename Compare = std::less<KeyType>>
using d_ary_heap
 make template alias due to similarity with std::priority_queue
template<typename KeyType, typename DataType, unsigned Radix = 8>
using RadixHeapPair
 This class is a variant of tlx::RadixHeap for data types which do not include the key directly.
template<typename T>
using simple_vector
 make template alias due to similarity with std::vector
template<typename Key, typename Compare = std::less<Key>, typename Allocator = std::allocator<Key>>
using splay_set
template<typename Key, typename Compare = std::less<Key>, typename Allocator = std::allocator<Key>>
using splay_multiset
using string_view
 make alias due to STL similarity

Enumerations

enum class  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.
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
template<typename Tree, typename Compare>
bool splay_check (const Tree *t, const Compare &cmp)
 check the tree order
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.
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.
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.
template<typename Tree, typename Functor>
void splay_traverse_preorder (const Functor &f, const Tree *t)
 traverse the tree in preorder (left, node, right)
template<typename Tree, typename Functor>
void splay_traverse_postorder (const Functor &f, Tree *t)
 traverse the tree in postorder (left, right, node)
static bool operator== (const StringView &a, const std::string &b) noexcept
 equality operator to compare a StringView with a std::string
static bool operator== (const std::string &a, const StringView &b) noexcept
 equality operator to compare a StringView with a std::string
static bool operator!= (const StringView &a, const std::string &b) noexcept
 inequality operator to compare a StringView with a std::string
static bool operator!= (const std::string &a, const StringView &b) noexcept
 inequality operator to compare a StringView with a std::string
static bool operator< (const StringView &a, const std::string &b) noexcept
 less operator to compare a StringView with a std::string lexicographically
static bool operator< (const std::string &a, const StringView &b) noexcept
 less operator to compare a StringView with a std::string lexicographically
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*
static bool operator== (const char *x, const StringView &y) noexcept
 equality operator to compare a StringView with a const char*
static bool operator!= (const StringView &x, const char *y) noexcept
 inequality operator to compare a StringView with a const char*
static bool operator!= (const char *x, const StringView &y) noexcept
 inequality operator to compare a StringView with a const char*
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

◆ d_ary_addressable_int_heap

template<typename KeyType, unsigned Arity = 2, typename Compare = std::less<KeyType>>
using d_ary_addressable_int_heap

make template alias due to similarity with std::priority_queue

Definition at line 364 of file d_ary_addressable_int_heap.hpp.

◆ d_ary_heap

template<typename KeyType, unsigned Arity = 2, typename Compare = std::less<KeyType>>
using d_ary_heap

make template alias due to similarity with std::priority_queue

Definition at line 261 of file d_ary_heap.hpp.

◆ RadixHeapPair

template<typename KeyType, typename DataType, unsigned Radix = 8>
using RadixHeapPair

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 669 of file radix_heap.hpp.

◆ simple_vector

template<typename T>
using simple_vector

make template alias due to similarity with std::vector

Definition at line 255 of file simple_vector.hpp.

◆ splay_multiset

template<typename Key, typename Compare = std::less<Key>, typename Allocator = std::allocator<Key>>
using splay_multiset

Definition at line 339 of file splay_tree.hpp.

◆ splay_set

template<typename Key, typename Compare = std::less<Key>, typename Allocator = std::allocator<Key>>
using splay_set

Definition at line 335 of file splay_tree.hpp.

◆ string_view

using string_view

make alias due to STL similarity

Definition at line 473 of file string_view.hpp.

Enumeration Type Documentation

◆ SimpleVectorMode

enum class 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()

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.

Refer to RadixHeap for description of parameters.

Definition at line 653 of file radix_heap.hpp.

◆ operator!=() [1/4]

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

◆ operator!=() [2/4]

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

◆ operator!=() [3/4]

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

◆ operator!=() [4/4]

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

◆ operator<() [1/4]

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

Definition at line 583 of file string_view.hpp.

◆ operator<() [2/4]

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

◆ operator<() [3/4]

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

◆ operator<() [4/4]

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

Definition at line 578 of file string_view.hpp.

◆ operator<=() [1/4]

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

Definition at line 603 of file string_view.hpp.

◆ operator<=() [2/4]

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

Definition at line 536 of file string_view.hpp.

◆ operator<=() [3/4]

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

Definition at line 598 of file string_view.hpp.

◆ operator<=() [4/4]

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

Definition at line 531 of file string_view.hpp.

◆ operator==() [1/4]

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

◆ operator==() [2/4]

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

◆ operator==() [3/4]

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

◆ operator==() [4/4]

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

◆ operator>() [1/4]

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

Definition at line 593 of file string_view.hpp.

◆ operator>() [2/4]

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

Definition at line 526 of file string_view.hpp.

◆ operator>() [3/4]

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

Definition at line 588 of file string_view.hpp.

◆ operator>() [4/4]

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

Definition at line 521 of file string_view.hpp.

◆ operator>=() [1/4]

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

Definition at line 613 of file string_view.hpp.

◆ operator>=() [2/4]

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

Definition at line 546 of file string_view.hpp.

◆ operator>=() [3/4]

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

Definition at line 608 of file string_view.hpp.

◆ operator>=() [4/4]

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

Definition at line 541 of file string_view.hpp.

◆ splay()

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.

Definition at line 97 of file splay_tree.hpp.

◆ splay_check() [1/2]

template<typename Tree, typename Compare>
bool splay_check ( const Tree * t,
const Compare & cmp )

check the tree order

Definition at line 88 of file splay_tree.hpp.

◆ splay_check() [2/2]

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

Definition at line 69 of file splay_tree.hpp.

◆ splay_erase()

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.

Return a pointer to the resulting tree.

Definition at line 176 of file splay_tree.hpp.

◆ splay_insert()

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.

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.

◆ splay_traverse_postorder()

template<typename Tree, typename Functor>
void 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.

◆ splay_traverse_preorder()

template<typename Tree, typename Functor>
void 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.