Detailed Description

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

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

Implements the STL set using a B+ tree. It can be used as a drop-in replacement for std::set. 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.

It is somewhat inefficient to implement a set using a B+ tree, a plain B tree would hold fewer copies of the keys.

Definition at line 41 of file btree_set.hpp.

Collaboration diagram for btree_set< Key_, Compare_, Traits_, Alloc_ >:

#include <btree_set.hpp>

Classes
struct	key_of_value
	Key Extractor Struct. More...

Public Types
Template Parameter Types
typedef Key_	key_type

typedef Compare_	key_compare
	Second template parameter: Key comparison function object. More...

typedef Traits_	traits

typedef Alloc_	allocator_type
	Fourth template parameter: STL allocator. More...

Constructed Types
typedef key_type	value_type
	Construct the set value_type: the key_type. More...

typedef btree_set< key_type, key_compare, traits, allocator_type >	self
	Typedef of our own type. More...

typedef BTree< key_type, value_type, key_of_value, key_compare, traits, false, allocator_type >	btree_impl
	Implementation type of the btree_base. More...

typedef btree_impl::value_compare	value_compare
	Function class comparing two value_type keys. 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_set (const allocator_type &alloc=allocator_type())

	btree_set (const key_compare &kcf, const allocator_type &alloc=allocator_type())

template<class InputIterator >
	btree_set (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_set (InputIterator first, InputIterator last, const key_compare &kcf, const allocator_type &alloc=allocator_type())

	~btree_set ()
	Frees up all used B+ tree memory pages. More...

void	swap (btree_set &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 keys 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 keys in the B+ tree. More...

bool	empty () const
	Returns true if there is at least one key in the B+ tree. More...

size_type	max_size () const

const tree_stats &	get_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, iterator >	equal_range (const key_type &key)
	Searches the B+ tree and returns both lower_bound() and upper_bound(). More...

std::pair< const_iterator, const_iterator >	equal_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_set &other) const

bool	operator!= (const btree_set &other) const
	Inequality relation. Based on operator==. More...

bool	operator< (const btree_set &other) const

bool	operator> (const btree_set &other) const
	Greater relation. Based on operator<. More...

bool	operator<= (const btree_set &other) const
	Less-equal relation. Based on operator<. More...

bool	operator>= (const btree_set &other) const
	Greater-equal relation. Based on operator<. More...

Fast Copy: Assign Operator and Copy Constructors
btree_set &	operator= (const btree_set &other)
	Assignment operator. All the keys are copied. More...

	btree_set (const btree_set &other)

Public Insertion Functions
std::pair< iterator, bool >	insert (const key_type &x)

iterator	insert (iterator hint, const key_type &x)

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)
	Erases all the key/data pairs associated with the given key. More...

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

Fourth template parameter: STL allocator.

Definition at line 59 of file btree_set.hpp.

◆ btree_impl

typedef BTree<key_type, value_type, key_of_value, key_compare, traits, false, allocator_type> btree_impl

Implementation type of the btree_base.

Definition at line 86 of file btree_set.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 144 of file btree_set.hpp.

◆ const_reverse_iterator

typedef btree_impl::const_reverse_iterator const_reverse_iterator

create constant reverse iterator by using STL magic

Definition at line 150 of file btree_set.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 140 of file btree_set.hpp.

◆ key_compare

typedef Compare_ key_compare

Second template parameter: Key comparison function object.

Definition at line 52 of file btree_set.hpp.

◆ key_type

typedef Key_ key_type

First template parameter: The key type of the B+ tree. This is stored in inner nodes and leaves.

Definition at line 49 of file btree_set.hpp.

◆ reverse_iterator

typedef btree_impl::reverse_iterator reverse_iterator

create mutable reverse iterator by using STL magic

Definition at line 147 of file btree_set.hpp.

◆ self

typedef btree_set<key_type, key_compare, traits, allocator_type> self

Typedef of our own type.

Definition at line 76 of file btree_set.hpp.

◆ size_type

typedef btree_impl::size_type size_type

Size type used to count keys.

Definition at line 92 of file btree_set.hpp.

◆ traits

typedef Traits_ traits

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

Definition at line 56 of file btree_set.hpp.

◆ tree_stats

typedef btree_impl::tree_stats tree_stats

Small structure containing statistics about the tree.

Definition at line 95 of file btree_set.hpp.

◆ value_compare

typedef btree_impl::value_compare value_compare

Function class comparing two value_type keys.

Definition at line 89 of file btree_set.hpp.

◆ value_type

typedef key_type value_type

Construct the set value_type: the key_type.

Definition at line 73 of file btree_set.hpp.

Constructor & Destructor Documentation

◆ btree_set() [1/5]

btree_set ( const allocator_type & alloc = allocator_type() )

inlineexplicit

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

Definition at line 169 of file btree_set.hpp.

◆ btree_set() [2/5]

btree_set	(	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 175 of file btree_set.hpp.

◆ btree_set() [3/5]

btree_set	(	InputIterator	first,
		InputIterator	last,
		const allocator_type &	alloc = `allocator_type()`
	)

inline

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

Definition at line 182 of file btree_set.hpp.

References btree_set< Key_, Compare_, Traits_, Alloc_ >::insert().

◆ btree_set() [4/5]

btree_set	(	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 191 of file btree_set.hpp.

References btree_set< Key_, Compare_, Traits_, Alloc_ >::insert().

◆ ~btree_set()

~btree_set ( )

inline

Frees up all used B+ tree memory pages.

Definition at line 198 of file btree_set.hpp.

◆ btree_set() [5/5]

btree_set ( const btree_set< Key_, Compare_, Traits_, Alloc_ > & other )

inline

Copy constructor. The newly initialized B+ tree object will contain a copy of all keys.

Definition at line 444 of file btree_set.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 253 of file btree_set.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 265 of file btree_set.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 482 of file btree_set.hpp.

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

◆ clear()

void clear ( )

inline

Frees all keys and all nodes of the tree.

Definition at line 241 of file btree_set.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. As this is a unique set, count() returns either 0 or

Definition at line 353 of file btree_set.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 in the B+ tree.

Definition at line 311 of file btree_set.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 259 of file btree_set.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 271 of file btree_set.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 382 of file btree_set.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 387 of file btree_set.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.

Definition at line 499 of file btree_set.hpp.

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

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

◆ erase() [2/2]

void erase ( iterator iter )

inline

Erase the key/data pair referenced by the iterator.

Definition at line 504 of file btree_set.hpp.

References btree_set< Key_, Compare_, Traits_, Alloc_ >::erase(), and BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >::erase().

◆ erase_one()

bool erase_one ( const key_type & key )

inline

Erases the key from the set. As this is a unique set, there is no difference to erase().

Definition at line 494 of file btree_set.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 334 of file btree_set.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 slot if found. If unsuccessful it returns end().

Definition at line 340 of file btree_set.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 slot if found. If unsuccessful it returns end().

Definition at line 346 of file btree_set.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 230 of file btree_set.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 322 of file btree_set.hpp.

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

◆ insert() [1/3]

std::pair<iterator, bool> insert ( const key_type & x )

inline

Attempt to insert a key into the B+ tree. The insert will fail if it is already present.

Definition at line 456 of file btree_set.hpp.

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

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::btree_set(), and btree_set< Key_, Compare_, Traits_, Alloc_ >::insert().

◆ insert() [2/3]

iterator insert	(	iterator	hint,
		const key_type &	x
	)

inline

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

Definition at line 462 of file btree_set.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 iterators dereferencing to key_type into the B+ tree. Each key/data pair is inserted individually.

Definition at line 469 of file btree_set.hpp.

References btree_set< Key_, Compare_, Traits_, Alloc_ >::insert().

◆ key_comp()

key_compare key_comp ( ) const

inline

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

Definition at line 213 of file btree_set.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 359 of file btree_set.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 365 of file btree_set.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 317 of file btree_set.hpp.

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

◆ operator!=()

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

inline

Inequality relation. Based on operator==.

Definition at line 405 of file btree_set.hpp.

References btree_set< Key_, Compare_, Traits_, Alloc_ >::tree_.

◆ operator<()

bool operator< ( const btree_set< Key_, 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 411 of file btree_set.hpp.

References btree_set< Key_, Compare_, Traits_, Alloc_ >::tree_.

◆ operator<=()

bool operator<= ( const btree_set< Key_, Compare_, Traits_, Alloc_ > & other ) const

inline

Less-equal relation. Based on operator<.

Definition at line 421 of file btree_set.hpp.

References btree_set< Key_, Compare_, Traits_, Alloc_ >::tree_.

◆ operator=()

btree_set& operator= ( const btree_set< Key_, Compare_, Traits_, Alloc_ > & other )

inline

Assignment operator. All the keys are copied.

Definition at line 436 of file btree_set.hpp.

References btree_set< Key_, Compare_, Traits_, Alloc_ >::tree_.

◆ operator==()

bool operator== ( const btree_set< Key_, Compare_, Traits_, Alloc_ > & other ) const

inline

Equality relation of B+ trees of the same type. B+ trees of the same size and equal elements are considered equal.

Definition at line 400 of file btree_set.hpp.

References btree_set< Key_, Compare_, Traits_, Alloc_ >::tree_.

◆ operator>()

bool operator> ( const btree_set< Key_, Compare_, Traits_, Alloc_ > & other ) const

inline

Greater relation. Based on operator<.

Definition at line 416 of file btree_set.hpp.

References btree_set< Key_, Compare_, Traits_, Alloc_ >::tree_.

◆ operator>=()

bool operator>= ( const btree_set< Key_, Compare_, Traits_, Alloc_ > & other ) const

inline

Greater-equal relation. Based on operator<.

Definition at line 426 of file btree_set.hpp.

References btree_set< Key_, 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 277 of file btree_set.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 289 of file btree_set.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 283 of file btree_set.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 295 of file btree_set.hpp.

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

◆ size()

size_type size ( ) const

inline

Return the number of keys in the B+ tree.

Definition at line 306 of file btree_set.hpp.

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

◆ swap()

void swap ( btree_set< Key_, Compare_, Traits_, Alloc_ > & from )

inline

Fast swapping of two identical B+ tree objects.

Definition at line 202 of file btree_set.hpp.

References tlx::swap(), and btree_set< Key_, 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 371 of file btree_set.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 377 of file btree_set.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 219 of file btree_set.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 545 of file btree_set.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 130 of file btree_set.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 127 of file btree_set.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 108 of file btree_set.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 118 of file btree_set.hpp.

◆ leaf_slotmax

const unsigned short leaf_slotmax = btree_impl::leaf_slotmax

static

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

Definition at line 104 of file btree_set.hpp.

◆ leaf_slotmin

const unsigned short leaf_slotmin = btree_impl::leaf_slotmin

static

Computed B+ tree parameter: The minimum number of key 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 113 of file btree_set.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 122 of file btree_set.hpp.

◆ TLX_BTREE_FRIENDS

TLX_BTREE_FRIENDS

The macro TLX_BTREE_FRIENDS can be used by outside class to access the B+ tree internals. This was added for wxBTreeDemo to be able to draw the tree.

Definition at line 66 of file btree_set.hpp.

◆ tree_

btree_impl tree_

private

The contained implementation object.

Definition at line 159 of file btree_set.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::operator!=(), btree_set< Key_, Compare_, Traits_, Alloc_ >::operator<(), btree_set< Key_, Compare_, Traits_, Alloc_ >::operator<=(), btree_set< Key_, Compare_, Traits_, Alloc_ >::operator=(), btree_set< Key_, Compare_, Traits_, Alloc_ >::operator==(), btree_set< Key_, Compare_, Traits_, Alloc_ >::operator>(), btree_set< Key_, Compare_, Traits_, Alloc_ >::operator>=(), and btree_set< Key_, Compare_, Traits_, Alloc_ >::swap().

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

extlib/tlx/tlx/container/btree_set.hpp

Detailed Description

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

Classes

Public Types

Public Member Functions

Public Attributes

Static Public Attributes

Private Attributes

Member Typedef Documentation

◆ allocator_type

◆ btree_impl

◆ const_iterator

◆ const_reverse_iterator

◆ iterator

◆ key_compare

◆ key_type

◆ reverse_iterator

◆ self

◆ size_type

◆ traits

◆ tree_stats

◆ value_compare

◆ value_type

Constructor & Destructor Documentation

◆ btree_set() [1/5]

◆ btree_set() [2/5]

◆ btree_set() [3/5]

◆ btree_set() [4/5]

◆ ~btree_set()

◆ btree_set() [5/5]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ bulk_load()

◆ clear()

◆ count()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ equal_range() [1/2]

◆ equal_range() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ erase_one()

◆ exists()

◆ find() [1/2]

◆ find() [2/2]

◆ get_allocator()

◆ get_stats()

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ key_comp()

◆ lower_bound() [1/2]

◆ lower_bound() [2/2]

◆ max_size()

◆ operator!=()

◆ operator<()

◆ operator<=()

◆ operator=()

◆ operator==()

◆ operator>()

◆ operator>=()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ size()

◆ swap()

◆ upper_bound() [1/2]

◆ upper_bound() [2/2]

◆ value_comp()

◆ verify()

Member Data Documentation

◆ allow_duplicates

◆ debug

◆ inner_slotmax

◆ inner_slotmin

◆ leaf_slotmax

◆ leaf_slotmin

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