Thrill  0.1
btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ > Class Template Reference

Detailed Description

template<typename Key_, typename Data_, typename Compare_ = std::less<Key_>, typename Traits_ = btree_default_traits<Key_, std::pair<Key_, Data_> >, typename Alloc_ = std::allocator<std::pair<Key_, Data_> >>
class tlx::btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >

Specialized B+ tree template class implementing STL's multimap container.

Implements the STL multimap using a B+ tree. It can be used as a drop-in replacement for std::multimap. Not all asymptotic time requirements are met in theory. The class has a traits class defining B+ tree properties like slots and self-verification. Furthermore an allocator can be specified for tree nodes.

Definition at line 39 of file btree_multimap.hpp.

+ Collaboration diagram for btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >:

#include <btree_multimap.hpp>

Classes

struct  key_of_value
 Key Extractor Struct. More...
 

Public Types

Template Parameter Types
typedef Key_ key_type
 
typedef Data_ data_type
 
typedef Compare_ key_compare
 Third template parameter: Key comparison function object. More...
 
typedef Traits_ traits
 
typedef Alloc_ allocator_type
 Fifth template parameter: STL allocator. More...
 
Constructed Types
typedef btree_multimap< key_type, data_type, key_compare, traits, allocator_typeself
 Typedef of our own type. More...
 
typedef std::pair< key_type, data_typevalue_type
 
typedef BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_typebtree_impl
 Implementation type of the btree_base. More...
 
typedef btree_impl::value_compare value_compare
 Function class comparing two value_type pairs. More...
 
typedef btree_impl::size_type size_type
 Size type used to count keys. More...
 
typedef btree_impl::tree_stats tree_stats
 Small structure containing statistics about the tree. More...
 
Iterators and Reverse Iterators
typedef btree_impl::iterator iterator
 
typedef btree_impl::const_iterator const_iterator
 
typedef btree_impl::reverse_iterator reverse_iterator
 create mutable reverse iterator by using STL magic More...
 
typedef btree_impl::const_reverse_iterator const_reverse_iterator
 create constant reverse iterator by using STL magic More...
 

Public Member Functions

Constructors and Destructor
 btree_multimap (const allocator_type &alloc=allocator_type())
 
 btree_multimap (const key_compare &kcf, const allocator_type &alloc=allocator_type())
 
template<class InputIterator >
 btree_multimap (InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
 Constructor initializing a B+ tree with the range [first,last) More...
 
template<class InputIterator >
 btree_multimap (InputIterator first, InputIterator last, const key_compare &kcf, const allocator_type &alloc=allocator_type())
 
 ~btree_multimap ()
 Frees up all used B+ tree memory pages. More...
 
void swap (btree_multimap &from)
 Fast swapping of two identical B+ tree objects. More...
 
Key and Value Comparison Function Objects
key_compare key_comp () const
 Constant access to the key comparison object sorting the B+ tree. More...
 
value_compare value_comp () const
 
Allocators
allocator_type get_allocator () const
 Return the base node allocator provided during construction. More...
 
Fast Destruction of the B+ Tree
void clear ()
 Frees all key/data pairs and all nodes of the tree. More...
 
STL Iterator Construction Functions
iterator begin ()
 
iterator end ()
 
const_iterator begin () const
 
const_iterator end () const
 
reverse_iterator rbegin ()
 
reverse_iterator rend ()
 
const_reverse_iterator rbegin () const
 
const_reverse_iterator rend () const
 
Access Functions to the Item Count
size_type size () const
 Return the number of key/data pairs in the B+ tree. More...
 
bool empty () const
 Returns true if there is at least one key/data pair in the B+ tree. More...
 
size_type max_size () const
 
const tree_statsget_stats () const
 Return a const reference to the current statistics. More...
 
STL Access Functions Querying the Tree by Descending to a Leaf
bool exists (const key_type &key) const
 
iterator find (const key_type &key)
 
const_iterator find (const key_type &key) const
 
size_type count (const key_type &key) const
 
iterator lower_bound (const key_type &key)
 
const_iterator lower_bound (const key_type &key) const
 
iterator upper_bound (const key_type &key)
 
const_iterator upper_bound (const key_type &key) const
 
std::pair< iterator, iteratorequal_range (const key_type &key)
 Searches the B+ tree and returns both lower_bound() and upper_bound(). More...
 
std::pair< const_iterator, const_iteratorequal_range (const key_type &key) const
 Searches the B+ tree and returns both lower_bound() and upper_bound(). More...
 
B+ Tree Object Comparison Functions
bool operator== (const btree_multimap &other) const
 
bool operator!= (const btree_multimap &other) const
 Inequality relation. Based on operator==. More...
 
bool operator< (const btree_multimap &other) const
 
bool operator> (const btree_multimap &other) const
 Greater relation. Based on operator<. More...
 
bool operator<= (const btree_multimap &other) const
 Less-equal relation. Based on operator<. More...
 
bool operator>= (const btree_multimap &other) const
 Greater-equal relation. Based on operator<. More...
 
Fast Copy: Assign Operator and Copy Constructors
btree_multimapoperator= (const btree_multimap &other)
 Assignment operator. All the key/data pairs are copied. More...
 
 btree_multimap (const btree_multimap &other)
 
Public Insertion Functions
iterator insert (const value_type &x)
 
iterator insert2 (const key_type &key, const data_type &data)
 
iterator insert (iterator hint, const value_type &x)
 
iterator insert2 (iterator hint, const key_type &key, const data_type &data)
 
template<typename InputIterator >
void insert (InputIterator first, InputIterator last)
 
template<typename Iterator >
void bulk_load (Iterator first, Iterator last)
 
Public Erase Functions
bool erase_one (const key_type &key)
 
size_type erase (const key_type &key)
 
void erase (iterator iter)
 Erase the key/data pair referenced by the iterator. More...
 
Verification of B+ Tree Invariants
void verify () const
 

Public Attributes

 TLX_BTREE_FRIENDS
 

Static Public Attributes

Static Constant Options and Values of the B+ Tree
static const unsigned short leaf_slotmax = btree_impl::leaf_slotmax
 Base B+ tree parameter: The number of key/data slots in each leaf. More...
 
static const unsigned short inner_slotmax = btree_impl::inner_slotmax
 
static const unsigned short leaf_slotmin = btree_impl::leaf_slotmin
 
static const unsigned short inner_slotmin = btree_impl::inner_slotmin
 
static const bool self_verify = btree_impl::self_verify
 
static const bool debug = btree_impl::debug
 
static const bool allow_duplicates = btree_impl::allow_duplicates
 Operational parameter: Allow duplicate keys in the btree. More...
 

Private Attributes

Tree Implementation Object
btree_impl tree_
 The contained implementation object. More...
 

Member Typedef Documentation

◆ allocator_type

typedef Alloc_ allocator_type

Fifth template parameter: STL allocator.

Definition at line 61 of file btree_multimap.hpp.

◆ btree_impl

Implementation type of the btree_base.

Definition at line 90 of file btree_multimap.hpp.

◆ const_iterator

typedef btree_impl::const_iterator const_iterator

STL-like iterator object for B+ tree items. The iterator points to a specific slot number in a leaf.

Definition at line 148 of file btree_multimap.hpp.

◆ const_reverse_iterator

typedef btree_impl::const_reverse_iterator const_reverse_iterator

create constant reverse iterator by using STL magic

Definition at line 154 of file btree_multimap.hpp.

◆ data_type

typedef Data_ data_type

Second template parameter: The data type associated with each key. Stored in the B+ tree's leaves

Definition at line 51 of file btree_multimap.hpp.

◆ iterator

typedef btree_impl::iterator iterator

STL-like iterator object for B+ tree items. The iterator points to a specific slot number in a leaf.

Definition at line 144 of file btree_multimap.hpp.

◆ key_compare

typedef Compare_ key_compare

Third template parameter: Key comparison function object.

Definition at line 54 of file btree_multimap.hpp.

◆ key_type

typedef Key_ key_type

First template parameter: The key type of the btree. This is stored in inner nodes.

Definition at line 47 of file btree_multimap.hpp.

◆ reverse_iterator

typedef btree_impl::reverse_iterator reverse_iterator

create mutable reverse iterator by using STL magic

Definition at line 151 of file btree_multimap.hpp.

◆ self

Typedef of our own type.

Definition at line 76 of file btree_multimap.hpp.

◆ size_type

Size type used to count keys.

Definition at line 96 of file btree_multimap.hpp.

◆ traits

typedef Traits_ traits

Fourth template parameter: Traits object used to define more parameters of the B+ tree

Definition at line 58 of file btree_multimap.hpp.

◆ tree_stats

typedef btree_impl::tree_stats tree_stats

Small structure containing statistics about the tree.

Definition at line 99 of file btree_multimap.hpp.

◆ value_compare

typedef btree_impl::value_compare value_compare

Function class comparing two value_type pairs.

Definition at line 93 of file btree_multimap.hpp.

◆ value_type

typedef std::pair<key_type, data_type> value_type

Construct the STL-required value_type as a composition pair of key and data types

Definition at line 80 of file btree_multimap.hpp.

Constructor & Destructor Documentation

◆ btree_multimap() [1/5]

btree_multimap ( const allocator_type alloc = allocator_type())
inlineexplicit

Default constructor initializing an empty B+ tree with the standard key comparison function

Definition at line 173 of file btree_multimap.hpp.

◆ btree_multimap() [2/5]

btree_multimap ( const key_compare kcf,
const allocator_type alloc = allocator_type() 
)
inlineexplicit

Constructor initializing an empty B+ tree with a special key comparison object

Definition at line 179 of file btree_multimap.hpp.

◆ btree_multimap() [3/5]

btree_multimap ( InputIterator  first,
InputIterator  last,
const allocator_type alloc = allocator_type() 
)
inline

Constructor initializing a B+ tree with the range [first,last)

Definition at line 186 of file btree_multimap.hpp.

◆ btree_multimap() [4/5]

btree_multimap ( InputIterator  first,
InputIterator  last,
const key_compare kcf,
const allocator_type alloc = allocator_type() 
)
inline

Constructor initializing a B+ tree with the range [first,last) and a special key comparison object

Definition at line 194 of file btree_multimap.hpp.

◆ ~btree_multimap()

~btree_multimap ( )
inline

Frees up all used B+ tree memory pages.

Definition at line 201 of file btree_multimap.hpp.

◆ btree_multimap() [5/5]

btree_multimap ( const btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ > &  other)
inline

Copy constructor. The newly initialized B+ tree object will contain a copy or all key/data pairs.

Definition at line 448 of file btree_multimap.hpp.

Member Function Documentation

◆ begin() [1/2]

iterator begin ( )
inline

Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree.

Definition at line 256 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::begin().

◆ begin() [2/2]

const_iterator begin ( ) const
inline

Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tree.

Definition at line 268 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::begin().

◆ bulk_load()

void bulk_load ( Iterator  first,
Iterator  last 
)
inline

Bulk load a sorted range [first,last). Loads items into leaves and constructs a B-tree above them. The tree must be empty when calling this function.

Definition at line 495 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::bulk_load().

◆ clear()

void clear ( )
inline

Frees all key/data pairs and all nodes of the tree.

Definition at line 244 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::clear().

◆ count()

size_type count ( const key_type key) const
inline

Tries to locate a key in the B+ tree and returns the number of identical key entries found.

Definition at line 355 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::count().

◆ empty()

bool empty ( ) const
inline

Returns true if there is at least one key/data pair in the B+ tree.

Definition at line 314 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::empty().

◆ end() [1/2]

iterator end ( )
inline

Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B+ tree.

Definition at line 262 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::end().

◆ end() [2/2]

const_iterator end ( ) const
inline

Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of the B+ tree.

Definition at line 274 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::end().

◆ equal_range() [1/2]

std::pair<iterator, iterator> equal_range ( const key_type key)
inline

Searches the B+ tree and returns both lower_bound() and upper_bound().

Definition at line 384 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::equal_range().

◆ equal_range() [2/2]

std::pair<const_iterator, const_iterator> equal_range ( const key_type key) const
inline

Searches the B+ tree and returns both lower_bound() and upper_bound().

Definition at line 390 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::equal_range().

◆ erase() [1/2]

size_type erase ( const key_type key)
inline

Erases all the key/data pairs associated with the given key. This is implemented using erase_one() and thus not very efficient.

Definition at line 513 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::erase().

Referenced by btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::erase().

◆ erase() [2/2]

void erase ( iterator  iter)
inline

◆ erase_one()

bool erase_one ( const key_type key)
inline

Erases one (the first) of the key/data pairs associated with the given key.

Definition at line 507 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::erase_one().

◆ exists()

bool exists ( const key_type key) const
inline

Non-STL function checking whether a key is in the B+ tree. The same as (find(k) != end()) or (count() != 0).

Definition at line 337 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::exists().

◆ find() [1/2]

iterator find ( const key_type key)
inline

Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found. If unsuccessful it returns end().

Definition at line 343 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::find().

◆ find() [2/2]

const_iterator find ( const key_type key) const
inline

Tries to locate a key in the B+ tree and returns an constant iterator to the key/data slot if found. If unsuccessful it returns end().

Definition at line 349 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::find().

◆ get_allocator()

allocator_type get_allocator ( ) const
inline

Return the base node allocator provided during construction.

Definition at line 233 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::get_allocator().

◆ get_stats()

const tree_stats& get_stats ( ) const
inline

Return a const reference to the current statistics.

Definition at line 325 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::get_stats().

◆ insert() [1/3]

iterator insert ( const value_type x)
inline

Attempt to insert a key/data pair into the B+ tree. As this tree allows duplicates, insertion never fails.

Definition at line 460 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::insert().

◆ insert() [2/3]

iterator insert ( iterator  hint,
const value_type x 
)
inline

Attempt to insert a key/data pair into the B+ tree. The iterator hint is currently ignored by the B+ tree insertion routine.

Definition at line 473 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::insert().

◆ insert() [3/3]

void insert ( InputIterator  first,
InputIterator  last 
)
inline

Attempt to insert the range [first,last) of value_type pairs into the B+ tree. Each key/data pair is inserted individually.

Definition at line 487 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::insert().

◆ insert2() [1/2]

iterator insert2 ( const key_type key,
const data_type data 
)
inline

Attempt to insert a key/data pair into the B+ tree. This function is the same as the other insert. As this tree allows duplicates, insertion never fails.

Definition at line 467 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::insert().

◆ insert2() [2/2]

iterator insert2 ( iterator  hint,
const key_type key,
const data_type data 
)
inline

Attempt to insert a key/data pair into the B+ tree. The iterator hint is currently ignored by the B+ tree insertion routine.

Definition at line 479 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::insert().

◆ key_comp()

key_compare key_comp ( ) const
inline

Constant access to the key comparison object sorting the B+ tree.

Definition at line 216 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::key_comp().

◆ lower_bound() [1/2]

iterator lower_bound ( const key_type key)
inline

Searches the B+ tree and returns an iterator to the first pair equal to or greater than key, or end() if all keys are smaller.

Definition at line 361 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::lower_bound().

◆ lower_bound() [2/2]

const_iterator lower_bound ( const key_type key) const
inline

Searches the B+ tree and returns a constant iterator to the first pair equal to or greater than key, or end() if all keys are smaller.

Definition at line 367 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::lower_bound().

◆ max_size()

size_type max_size ( ) const
inline

Returns the largest possible size of the B+ Tree. This is just a function required by the STL standard, the B+ Tree can hold more items.

Definition at line 320 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::max_size().

◆ operator!=()

bool operator!= ( const btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ > &  other) const
inline

Inequality relation. Based on operator==.

Definition at line 408 of file btree_multimap.hpp.

References btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::tree_.

◆ operator<()

bool operator< ( const btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ > &  other) const
inline

Total ordering relation of B+ trees of the same type. It uses std::lexicographical_compare() for the actual comparison of elements.

Definition at line 414 of file btree_multimap.hpp.

References btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::tree_.

◆ operator<=()

bool operator<= ( const btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ > &  other) const
inline

Less-equal relation. Based on operator<.

Definition at line 424 of file btree_multimap.hpp.

References btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::tree_.

◆ operator=()

btree_multimap& operator= ( const btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ > &  other)
inline

Assignment operator. All the key/data pairs are copied.

Definition at line 440 of file btree_multimap.hpp.

References btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::tree_.

◆ operator==()

bool operator== ( const btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ > &  other) const
inline

Equality relation of B+ trees of the same type. B+ trees of the same size and equal elements (both key and data) are considered equal. Beware of the random ordering of duplicate keys.

Definition at line 403 of file btree_multimap.hpp.

References btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::tree_.

◆ operator>()

bool operator> ( const btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ > &  other) const
inline

Greater relation. Based on operator<.

Definition at line 419 of file btree_multimap.hpp.

References btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::tree_.

◆ operator>=()

bool operator>= ( const btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ > &  other) const
inline

Greater-equal relation. Based on operator<.

Definition at line 429 of file btree_multimap.hpp.

References btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::tree_.

◆ rbegin() [1/2]

reverse_iterator rbegin ( )
inline

Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf of the B+ tree. Uses STL magic.

Definition at line 280 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::rbegin().

◆ rbegin() [2/2]

const_reverse_iterator rbegin ( ) const
inline

Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the B+ tree. Uses STL magic.

Definition at line 292 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::rbegin().

◆ rend() [1/2]

reverse_iterator rend ( )
inline

Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the B+ tree. Uses STL magic.

Definition at line 286 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::rend().

◆ rend() [2/2]

const_reverse_iterator rend ( ) const
inline

Constructs a read-only reverse iterator that points to the first slot in the first leaf of the B+ tree. Uses STL magic.

Definition at line 298 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::rend().

◆ size()

size_type size ( ) const
inline

Return the number of key/data pairs in the B+ tree.

Definition at line 309 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::size().

◆ swap()

void swap ( btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ > &  from)
inline

Fast swapping of two identical B+ tree objects.

Definition at line 205 of file btree_multimap.hpp.

References tlx::swap(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::tree_.

◆ upper_bound() [1/2]

iterator upper_bound ( const key_type key)
inline

Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys are smaller or equal.

Definition at line 373 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::upper_bound().

◆ upper_bound() [2/2]

const_iterator upper_bound ( const key_type key) const
inline

Searches the B+ tree and returns a constant iterator to the first pair greater than key, or end() if all keys are smaller or equal.

Definition at line 379 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::upper_bound().

◆ value_comp()

value_compare value_comp ( ) const
inline

Constant access to a constructed value_type comparison object. required by the STL

Definition at line 222 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::value_comp().

◆ verify()

void verify ( ) const
inline

Run a thorough verification of all B+ tree invariants. The program aborts via TLX_BTREE_ASSERT() if something is wrong.

Definition at line 559 of file btree_multimap.hpp.

References BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::verify().

Member Data Documentation

◆ allow_duplicates

const bool allow_duplicates = btree_impl::allow_duplicates
static

Operational parameter: Allow duplicate keys in the btree.

Definition at line 134 of file btree_multimap.hpp.

◆ debug

const bool debug = btree_impl::debug
static

Debug parameter: Prints out lots of debug information about how the algorithms change the tree. Requires the header file to be compiled with TLX_BTREE_DEBUG and the key type must be std::ostream printable.

Definition at line 131 of file btree_multimap.hpp.

◆ inner_slotmax

const unsigned short inner_slotmax = btree_impl::inner_slotmax
static

Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in each leaf.

Definition at line 112 of file btree_multimap.hpp.

◆ inner_slotmin

const unsigned short inner_slotmin = btree_impl::inner_slotmin
static

Computed B+ tree parameter: The minimum number of key slots used in an inner node. If fewer slots are used, the inner node will be merged or slots shifted from it's siblings.

Definition at line 122 of file btree_multimap.hpp.

◆ leaf_slotmax

const unsigned short leaf_slotmax = btree_impl::leaf_slotmax
static

Base B+ tree parameter: The number of key/data slots in each leaf.

Definition at line 108 of file btree_multimap.hpp.

◆ leaf_slotmin

const unsigned short leaf_slotmin = btree_impl::leaf_slotmin
static

Computed B+ tree parameter: The minimum number of key/data slots used in a leaf. If fewer slots are used, the leaf will be merged or slots shifted from it's siblings.

Definition at line 117 of file btree_multimap.hpp.

◆ self_verify

const bool self_verify = btree_impl::self_verify
static

Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation.

Definition at line 126 of file btree_multimap.hpp.

◆ TLX_BTREE_FRIENDS

TLX_BTREE_FRIENDS

Definition at line 68 of file btree_multimap.hpp.

◆ tree_


The documentation for this class was generated from the following file: