Basic class implementing a base B+ tree data structure in memory. More...

#include <btree.h>

Classes
struct	btree_pair_to_value
	For sets the second pair_type is an empty struct, so the value_type should only be the first. More...
struct	btree_pair_to_value< value_type, value_type >
	For maps value_type is the same as the pair_type. More...
class	const_iterator
	STL-like read-only iterator object for B+ tree items. More...
class	const_reverse_iterator
	STL-like read-only reverse iterator object for B+ tree items. More...
struct	dump_header
	A header for the binary image containing the base properties of the B+ tree. More...
struct	inner_node
	Extended structure of a inner node in-memory. More...
class	iterator
	STL-like iterator object for B+ tree items. More...
struct	leaf_node
	Extended structure of a leaf node in memory. More...
struct	node
	The header structure of each node in-memory. More...
struct	result_t
	B+ tree recursive deletion has much information which is needs to be passed upward. More...
class	reverse_iterator
	STL-like mutable reverse iterator object for B+ tree items. More...
struct	tree_stats
	A small struct containing basic statistics about the B+ tree. More...
class	value_compare
	Function class to compare value_type objects. Required by the STL. More...
Public Types
typedef _Key	key_type
	First template parameter: The key type of the B+ tree.
typedef _Data	data_type
	Second template parameter: The data type associated with each key.
typedef _Value	value_type
	Third template parameter: Composition pair of key and data types, this is required by the STL standard.
typedef _Compare	key_compare
	Fourth template parameter: Key comparison function object.
typedef _Traits	traits
	Fifth template parameter: Traits object used to define more parameters of the B+ tree.
typedef _Alloc	allocator_type
	Seventh template parameter: STL allocator for tree nodes.
typedef btree< key_type, data_type, value_type, key_compare, traits, allow_duplicates, allocator_type, used_as_set >	btree_self
	Typedef of our own type.
typedef size_t	size_type
	Size type used to count keys.
typedef std::pair< key_type, data_type >	pair_type
	The pair of key_type and data_type, this may be different from value_type.
Public Member Functions
	btree (const allocator_type &alloc=allocator_type())
	Default constructor initializing an empty B+ tree with the standard key comparison function.
	btree (const key_compare &kcf, const allocator_type &alloc=allocator_type())
	Constructor initializing an empty B+ tree with a special key comparison object.
template<class InputIterator >
	btree (InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
	Constructor initializing a B+ tree with the range [first,last).
template<class InputIterator >
	btree (InputIterator first, InputIterator last, const key_compare &kcf, const allocator_type &alloc=allocator_type())
	Constructor initializing a B+ tree with the range [first,last) and a special key comparison object.
	~btree ()
	Frees up all used B+ tree memory pages.
void	swap (btree_self &from)
	Fast swapping of two identical B+ tree objects.
key_compare	key_comp () const
	Constant access to the key comparison object sorting the B+ tree.
value_compare	value_comp () const
	Constant access to a constructed value_type comparison object.
allocator_type	get_allocator () const
	Return the base node allocator provided during construction.
void	clear ()
	Frees all key/data pairs and all nodes of the tree.
iterator	begin ()
	Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree.
iterator	end ()
	Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B+ tree.
const_iterator	begin () const
	Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tree.
const_iterator	end () const
	Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of the B+ tree.
reverse_iterator	rbegin ()
	Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf of the B+ tree.
reverse_iterator	rend ()
	Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the B+ tree.
const_reverse_iterator	rbegin () const
	Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the B+ tree.
const_reverse_iterator	rend () const
	Constructs a read-only reverse iterator that points to the first slot in the first leaf of the B+ tree.
size_type	size () const
	Return the number of key/data pairs in the B+ tree.
bool	empty () const
	Returns true if there is at least one key/data pair in the B+ tree.
size_type	max_size () const
	Returns the largest possible size of the B+ Tree.
struct tree_stats &	get_stats () const
	Return a const reference to the current statistics.
bool	exists (const key_type &key) const
	Non-STL function checking whether a key is in the B+ tree.
iterator	find (const key_type &key)
	Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found.
const_iterator	find (const key_type &key) const
	Tries to locate a key in the B+ tree and returns an constant iterator to the key/data slot if found.
size_type	count (const key_type &key) const
	Tries to locate a key in the B+ tree and returns the number of identical key entries found.
iterator	lower_bound (const key_type &key)
	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.
const_iterator	lower_bound (const key_type &key) const
	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.
iterator	upper_bound (const key_type &key)
	Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys are smaller or equal.
const_iterator	upper_bound (const key_type &key) const
	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.
std::pair< iterator, iterator >	equal_range (const key_type &key)
	Searches the B+ tree and returns both lower_bound() and upper_bound().
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().
bool	operator== (const btree_self &other) const
	Equality relation of B+ trees of the same type.
bool	operator!= (const btree_self &other) const
	Inequality relation. Based on operator==.
bool	operator< (const btree_self &other) const
	Total ordering relation of B+ trees of the same type.
bool	operator> (const btree_self &other) const
	Greater relation. Based on operator<.
bool	operator<= (const btree_self &other) const
	Less-equal relation. Based on operator<.
bool	operator>= (const btree_self &other) const
	Greater-equal relation. Based on operator<.
btree_self &	operator= (const btree_self &other)
	*** Fast Copy: Assign Operator and Copy Constructors
	btree (const btree_self &other)
	Copy constructor.
std::pair< iterator, bool >	insert (const pair_type &x)
	Attempt to insert a key/data pair into the B+ tree.
std::pair< iterator, bool >	insert (const key_type &key, const data_type &data)
	Attempt to insert a key/data pair into the B+ tree.
std::pair< iterator, bool >	insert2 (const key_type &key, const data_type &data)
	Attempt to insert a key/data pair into the B+ tree.
iterator	insert (iterator, const pair_type &x)
	Attempt to insert a key/data pair into the B+ tree.
iterator	insert2 (iterator, const key_type &key, const data_type &data)
	Attempt to insert a key/data pair into the B+ tree.
template<typename InputIterator >
void	insert (InputIterator first, InputIterator last)
	Attempt to insert the range [first,last) of value_type pairs into the B+ tree.
template<typename Iterator >
void	bulk_load (Iterator ibegin, Iterator iend)
	Bulk load a sorted range.
bool	erase_one (const key_type &key)
	Erases one (the first) of the key/data pairs associated with the given key.
size_type	erase (const key_type &key)
	Erases all the key/data pairs associated with the given key.
void	erase (iterator iter)
	Erase the key/data pair referenced by the iterator.
void	erase (iterator, iterator)
	Erase all key/data pairs in the range [first,last).
void	print (std::ostream &os) const
	Print out the B+ tree structure with keys onto the given ostream.
void	print_leaves (std::ostream &os) const
	Print out only the leaves via the double linked list.
void	verify () const
	Run a thorough verification of all B+ tree invariants.
void	dump (std::ostream &os) const
	Dump the contents of the B+ tree out onto an ostream as a binary image.
bool	restore (std::istream &is)
	Restore a binary image of a dumped B+ tree from an istream.
Static Public Attributes
static const bool	allow_duplicates = _Duplicates
	Sixth template parameter: Allow duplicate keys in the B+ tree.
static const bool	used_as_set = _UsedAsSet
	Eighth template parameter: boolean indicator whether the btree is used as a set.
static const unsigned short	leafslotmax = traits::leafslots
	Base B+ tree parameter: The number of key/data slots in each leaf.
static const unsigned short	innerslotmax = traits::innerslots
	Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in each leaf.
static const unsigned short	minleafslots = (leafslotmax / 2)
	Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
static const unsigned short	mininnerslots = (innerslotmax / 2)
	Computed B+ tree parameter: The minimum number of key slots used in an inner node.
static const bool	selfverify = traits::selfverify
	Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation.
static const bool	debug = traits::debug
	Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
Private Types
enum	result_flags_t { btree_ok = 0, btree_not_found = 1, btree_update_lastkey = 2, btree_fixmerge = 4 }
	Result flags of recursive deletion. More...
typedef btree_pair_to_value < value_type, pair_type >	pair_to_value_type
	Using template specialization select the correct converter used by the iterators.
Private Member Functions
bool	key_less (const key_type &a, const key_type b) const
	True if a < b ? "constructed" from m_key_less()
bool	key_lessequal (const key_type &a, const key_type b) const
	True if a <= b ? constructed from key_less()
bool	key_greater (const key_type &a, const key_type &b) const
	True if a > b ? constructed from key_less()
bool	key_greaterequal (const key_type &a, const key_type b) const
	True if a >= b ? constructed from key_less()
bool	key_equal (const key_type &a, const key_type &b) const
	True if a == b ? constructed from key_less().
leaf_node::alloc_type	leaf_node_allocator ()
	Return an allocator for leaf_node objects.
inner_node::alloc_type	inner_node_allocator ()
	Return an allocator for inner_node objects.
leaf_node *	allocate_leaf ()
	Allocate and initialize a leaf node.
inner_node *	allocate_inner (unsigned short level)
	Allocate and initialize an inner node.
void	free_node (node *n)
	Correctly free either inner or leaf node, destructs all contained key and value objects.
void	clear_recursive (node *n)
	Recursively free up nodes.
template<typename node_type >
int	find_lower (const node_type *n, const key_type &key) const
	Searches for the first key in the node n greater or equal to key.
template<typename node_type >
int	find_upper (const node_type *n, const key_type &key) const
	Searches for the first key in the node n greater than key.
struct node *	copy_recursive (const node *n)
	Recursively copy nodes from another B+ tree object.
std::pair< iterator, bool >	insert_start (const key_type &key, const data_type &value)
	Start the insertion descent at the current root and handle root splits.
std::pair< iterator, bool >	insert_descend (node n, const key_type &key, const data_type &value, key_type splitkey, node **splitnode)
	Insert an item into the B+ tree.
void	split_leaf_node (leaf_node leaf, key_type _newkey, node **_newleaf)
	Split up a leaf node into two equally-filled sibling leaves.
void	split_inner_node (inner_node inner, key_type _newkey, node **_newinner, unsigned int addslot)
	Split up an inner node into two equally-filled sibling nodes.
result_t	erase_one_descend (const key_type &key, node curr, node left, node right, inner_node leftparent, inner_node rightparent, inner_node parent, unsigned int parentslot)
	Erase one (the first) key/data pair in the B+ tree matching key.
result_t	erase_iter_descend (const iterator &iter, node curr, node left, node right, inner_node leftparent, inner_node rightparent, inner_node parent, unsigned int parentslot)
	Erase one key/data pair referenced by an iterator in the B+ tree.
result_t	merge_leaves (leaf_node left, leaf_node right, inner_node *parent)
	Merge two leaf nodes.
void	verify_node (const node n, key_type minkey, key_type *maxkey, tree_stats &vstats) const
	Recursively descend down the tree and verify each node.
void	verify_leaflinks () const
	Verify the double linked list of leaves.
void	dump_node (std::ostream &os, const node *n) const
	Recursively descend down the tree and dump each node in a precise order.
node *	restore_node (std::istream &is)
	Read the dump image and construct a tree from the node order in the serialization.
Static Private Member Functions
template<class InputIterator , class OutputIterator >
static OutputIterator	data_copy (InputIterator first, InputIterator last, OutputIterator result)
	Convenient template function for conditional copying of slotdata.
template<class InputIterator , class OutputIterator >
static OutputIterator	data_copy_backward (InputIterator first, InputIterator last, OutputIterator result)
	Convenient template function for conditional copying of slotdata.
static result_t	merge_inner (inner_node left, inner_node right, inner_node *parent, unsigned int parentslot)
	Merge two inner nodes.
static result_t	shift_left_leaf (leaf_node left, leaf_node right, inner_node *parent, unsigned int parentslot)
	Balance two leaf nodes.
static void	shift_left_inner (inner_node left, inner_node right, inner_node *parent, unsigned int parentslot)
	Balance two inner nodes.
static void	shift_right_leaf (leaf_node left, leaf_node right, inner_node *parent, unsigned int parentslot)
	Balance two leaf nodes.
static void	shift_right_inner (inner_node left, inner_node right, inner_node *parent, unsigned int parentslot)
	Balance two inner nodes.
static void	print_node (std::ostream &os, const node *node, unsigned int depth=0, bool recursive=false)
	Recursively descend down the tree and print out nodes.
Private Attributes
node *	m_root
	Pointer to the B+ tree's root node, either leaf or inner node.
leaf_node *	m_headleaf
	Pointer to first leaf in the double linked leaf chain.
leaf_node *	m_tailleaf
	Pointer to last leaf in the double linked leaf chain.
tree_stats	m_stats
	Other small statistics about the B+ tree.
key_compare	m_key_less
	Key comparison object.
allocator_type	m_allocator
	Memory allocator.

Detailed Description

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>
class stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >

Basic class implementing a base B+ tree data structure in memory.

The base implementation of a memory B+ tree. It is based on the implementation in Cormen's Introduction into Algorithms, Jan Jannink's paper and other algorithm resources. Almost all STL-required function calls are implemented. The asymptotic time requirements of the STL are not always fulfilled in theory, however in practice this B+ tree performs better than a red-black tree by using more memory. The insertion function splits the nodes on the recursion unroll. Erase is largely based on Jannink's ideas.

This class is specialized into btree_set, btree_multiset, btree_map and btree_multimap using default template parameters and facade functions.

Definition at line 163 of file btree.h.

Member Typedef Documentation

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

typedef _Alloc stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::allocator_type

Seventh template parameter: STL allocator for tree nodes.

Definition at line 194 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

typedef btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates, allocator_type, used_as_set> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree_self

Typedef of our own type.

Definition at line 213 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

typedef _Data stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::data_type

Second template parameter: The data type associated with each key.

Stored in the B+ tree's leaves

Definition at line 174 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

typedef _Compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_compare

Fourth template parameter: Key comparison function object.

Definition at line 183 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

typedef _Key stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_type

First template parameter: The key type of the B+ tree.

This is stored in inner nodes and leaves

Definition at line 170 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

typedef btree_pair_to_value<value_type, pair_type> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::pair_to_value_type [private]

Using template specialization select the correct converter used by the iterators.

Definition at line 415 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

typedef std::pair<key_type, data_type> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::pair_type

The pair of key_type and data_type, this may be different from value_type.

Definition at line 219 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

typedef size_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::size_type

Size type used to count keys.

Definition at line 216 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

typedef _Traits stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::traits

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

Definition at line 187 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

typedef _Value stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::value_type

Third template parameter: Composition pair of key and data types, this is required by the STL standard.

The B+ tree does not store key and data together. If value_type == key_type then the B+ tree implements a set.

Definition at line 180 of file btree.h.

Member Enumeration Documentation

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

enum stx::btree::result_flags_t [private]

Result flags of recursive deletion.

Enumerator:

btree_ok	Deletion successful and no fix-ups necessary.
btree_not_found	Deletion not successful because key was not found.
btree_update_lastkey	Deletion successful, the last key was updated so parent slotkeys need updates.
btree_fixmerge	Deletion successful, children nodes were merged and the parent needs to remove the empty node.

Definition at line 2534 of file btree.h.

Constructor & Destructor Documentation

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree ( const allocator_type & alloc = allocator_type() ) [inline, explicit]

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

Definition at line 1313 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree	(	const key_compare &	kcf,
		const allocator_type &	alloc = `allocator_type()`
	)		`[inline, explicit]`

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

Definition at line 1320 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

template<class InputIterator >

stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree	(	InputIterator	first,
		InputIterator	last,
		const allocator_type &	alloc = `allocator_type()`
	)		`[inline]`

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

The range need not be sorted. To create a B+ tree from a sorted range, use bulk_load().

Definition at line 1331 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

template<class InputIterator >

stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree	(	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.

The range need not be sorted. To create a B+ tree from a sorted range, use bulk_load().

Definition at line 1342 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::~btree ( ) [inline]

Frees up all used B+ tree memory pages.

Definition at line 1351 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::btree ( const btree_self & other ) [inline]

Copy constructor.

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

Definition at line 2022 of file btree.h.

Member Function Documentation

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

inner_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::allocate_inner ( unsigned short level ) [inline, private]

Allocate and initialize an inner node.

Definition at line 1475 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::copy_recursive(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore_node(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::split_inner_node().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::allocate_leaf ( ) [inline, private]

Allocate and initialize a leaf node.

Definition at line 1466 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::copy_recursive(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore_node(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::split_leaf_node().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1573 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::begin(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::begin(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::begin(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::begin(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator<(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator==(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::rend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1587 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

template<typename Iterator >

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::bulk_load	(	Iterator	ibegin,
		Iterator	iend
	)		`[inline]`

Bulk load a sorted range.

Loads items into leaves and constructs a B-tree above them. The tree must be empty when calling this function.

Definition at line 2401 of file btree.h.

Referenced by stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::bulk_load(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::bulk_load(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::bulk_load(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::bulk_load().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::clear ( ) [inline]

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

Definition at line 1527 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::clear(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::clear(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::clear(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::clear(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::~btree().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::clear_recursive ( node * n ) [inline, private]

Recursively free up nodes.

Definition at line 1545 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::clear(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::clear_recursive().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

struct node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::copy_recursive ( const node * n ) [inline, read, private]

Recursively copy nodes from another B+ tree object.

Definition at line 2040 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::btree(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::copy_recursive(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1822 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::count(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::count(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::count(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::count().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

template<class InputIterator , class OutputIterator >

static OutputIterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::data_copy	(	InputIterator	first,
		InputIterator	last,
		OutputIterator	result
	)		`[inline, static, private]`

Convenient template function for conditional copying of slotdata.

This should be used instead of std::copy for all slotdata manipulations.

Definition at line 1506 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::copy_recursive(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::merge_leaves(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_left_leaf(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_leaf(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::split_leaf_node().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

template<class InputIterator , class OutputIterator >

static OutputIterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::data_copy_backward	(	InputIterator	first,
		InputIterator	last,
		OutputIterator	result
	)		`[inline, static, private]`

Convenient template function for conditional copying of slotdata.

This should be used instead of std::copy for all slotdata manipulations.

Definition at line 1516 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_leaf().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::dump ( std::ostream & os ) const [inline]

Dump the contents of the B+ tree out onto an ostream as a binary image.

The image contains memory pointers which will be fixed when the image is restored. For this to work your key_type and data_type must be integral types and contain no pointers or references.

Definition at line 3843 of file btree.h.

Referenced by stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::dump(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::dump(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::dump(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::dump().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::dump_node	(	std::ostream &	os,
		const node *	n
	)		const `[inline, private]`

Recursively descend down the tree and dump each node in a precise order.

Definition at line 3897 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::dump(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::dump_node().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::empty ( ) const [inline]

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

Definition at line 1734 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::empty(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::empty(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::empty(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::empty().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1580 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::end(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::end(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::end(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::end(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::lower_bound(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator<(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator==(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::rbegin(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::upper_bound().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1594 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

std::pair<iterator, iterator> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::equal_range ( const key_type & key ) [inline]

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

Definition at line 1940 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::equal_range(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::equal_range(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::equal_range(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::equal_range().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

std::pair<const_iterator, const_iterator> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::equal_range ( const key_type & key ) const [inline]

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

Definition at line 1946 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase ( const key_type & key ) [inline]

Erases all the key/data pairs associated with the given key.

This is implemented using erase_one().

Definition at line 2619 of file btree.h.

Referenced by stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::erase(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::erase(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::erase(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::erase().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase ( iterator iter ) [inline]

Erase the key/data pair referenced by the iterator.

Definition at line 2633 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase	(	iterator	,
		iterator
	)		`[inline]`

Erase all key/data pairs in the range [first,last).

This function is currently not implemented by the B+ Tree.

Definition at line 2655 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase_iter_descend	(	const iterator &	iter,
		node *	curr,
		node *	left,
		node *	right,
		inner_node *	leftparent,
		inner_node *	rightparent,
		inner_node *	parent,
		unsigned int	parentslot
	)		`[inline, private]`

Erase one key/data pair referenced by an iterator in the B+ tree.

Descends down the tree in search of an iterator. During the descent the parent, left and right siblings and their parents are computed and passed down. The difficulty is that the iterator contains only a pointer to a leaf_node, which means that this function must do a recursive depth first search for that leaf node in the subtree containing all pairs of the same key. This subtree can be very large, even the whole tree, though in practice it would not make sense to have so many duplicate keys.

Once the referenced key/data pair is found, it is removed from the leaf and the same underflow cases are handled as in erase_one_descend.

Definition at line 2962 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase_one ( const key_type & key ) [inline]

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

Definition at line 2596 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::erase_one(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::erase_one(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::erase_one(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::erase_one().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase_one_descend	(	const key_type &	key,
		node *	curr,
		node *	left,
		node *	right,
		inner_node *	leftparent,
		inner_node *	rightparent,
		inner_node *	parent,
		unsigned int	parentslot
	)		`[inline, private]`

Erase one (the first) key/data pair in the B+ tree matching key.

Descends down the tree in search of key. During the descent the parent, left and right siblings and their parents are computed and passed down. Once the key/data pair is found, it is removed from the leaf. If the leaf underflows 6 different cases are handled. These cases resolve the underflow by shifting key/data pairs from adjacent sibling nodes, merging two sibling nodes or trimming the tree.

Definition at line 2673 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1757 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::exists(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::exists(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::exists(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::exists(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1778 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::find(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::find(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::find(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::find().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1800 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

template<typename node_type >

int stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::find_lower	(	const node_type *	n,
		const key_type &	key
	)		const `[inline, private]`

Searches for the first key in the node n greater or equal to key.

Uses binary search with an optional linear self-verification. This is a template function, because the slotkey array is located at different places in leaf_node and inner_node.

Definition at line 1635 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::count(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::exists(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::lower_bound().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

template<typename node_type >

int stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::find_upper	(	const node_type *	n,
		const key_type &	key
	)		const `[inline, private]`

Searches for the first key in the node n greater than key.

Uses binary search with an optional linear self-verification. This is a template function, because the slotkey array is located at different places in leaf_node and inner_node.

Definition at line 1682 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::upper_bound().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::free_node ( node * n ) [inline, private]

Correctly free either inner or leaf node, destructs all contained key and value objects.

Definition at line 1485 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::clear(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::clear_recursive(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

allocator_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::get_allocator ( ) const [inline]

Return the base node allocator provided during construction.

Definition at line 1445 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::get_allocator(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::get_allocator(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::get_allocator(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::get_allocator(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

struct tree_stats& stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::get_stats ( ) const [inline, read]

Return a const reference to the current statistics.

Definition at line 1747 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::get_stats(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::get_stats(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::get_stats(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::get_stats().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

inner_node::alloc_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::inner_node_allocator ( ) [inline, private]

Return an allocator for inner_node objects.

Definition at line 1460 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::allocate_inner(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::free_node().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert ( const pair_type & x ) [inline]

Attempt to insert a key/data pair into the B+ tree.

If the tree does not allow duplicate keys, then the insert may fail if it is already present.

Definition at line 2088 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::btree(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::insert(), stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::insert(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert	(	const key_type &	key,
		const data_type &	data
	)		`[inline]`

Attempt to insert a key/data pair into the B+ tree.

Beware that if key_type == data_type, then the template iterator insert() is called instead. If the tree does not allow duplicate keys, then the insert may fail if it is already present.

Definition at line 2097 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert	(	iterator	,
		const pair_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 2113 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

template<typename InputIterator >

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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; to bulk load the tree, use a constructor with range.

Definition at line 2129 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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, however if key_type == data_type then the non-template function cannot be called. If the tree does not allow duplicate keys, then the insert may fail if it is already present.

Definition at line 2106 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::insert(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::insert(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::insert(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::insert(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::insert2(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::insert2().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert2	(	iterator	,
		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 2120 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert_descend	(	node *	n,
		const key_type &	key,
		const data_type &	value,
		key_type *	splitkey,
		node **	splitnode
	)		`[inline, private]`

Insert an item into the B+ tree.

Descend down the nodes to a leaf, insert the key/data pair in a free slot. If the node overflows, then it must be split and the new split node inserted into the parent. Unroll / this splitting up to the root.

Definition at line 2190 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert_start	(	const key_type &	key,
		const data_type &	value
	)		`[inline, private]`

Start the insertion descent at the current root and handle root splits.

Returns true if the item was inserted

Definition at line 2144 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert2().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

key_compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_comp ( ) const [inline]

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

Definition at line 1395 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::key_comp(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::key_comp(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::key_comp(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::key_comp(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_equal	(	const key_type &	a,
		const key_type &	b
	)		const `[inline, private]`

True if a == b ? constructed from key_less().

This requires the < relation to be a total order, otherwise the B+ tree cannot be sorted.

Definition at line 1436 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::count(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::exists(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_node().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_greater	(	const key_type &	a,
		const key_type &	b
	)		const `[inline, private]`

True if a > b ? constructed from key_less()

Definition at line 1423 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_greaterequal	(	const key_type &	a,
		const key_type	b
	)		const `[inline, private]`

True if a >= b ? constructed from key_less()

Definition at line 1429 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_node().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_less	(	const key_type &	a,
		const key_type	b
	)		const `[inline, private]`

True if a < b ? "constructed" from m_key_less()

Definition at line 1411 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find_lower(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find_upper().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_lessequal	(	const key_type &	a,
		const key_type	b
	)		const `[inline, private]`

True if a <= b ? constructed from key_less()

Definition at line 1417 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find_lower(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::find_upper(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_leaflinks(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_node().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

leaf_node::alloc_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node_allocator ( ) [inline, private]

Return an allocator for leaf_node objects.

Definition at line 1454 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::allocate_leaf(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::free_node().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1855 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::equal_range(), stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::lower_bound(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::lower_bound(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::lower_bound(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::lower_bound().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1877 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1741 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::max_size(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::max_size(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::max_size(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::max_size().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

static result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::merge_inner	(	inner_node *	left,
		inner_node *	right,
		inner_node *	parent,
		unsigned int	parentslot
	)		`[inline, static, private]`

Merge two inner nodes.

The function moves all key/childid pairs from right to left and sets right's slotuse to zero. The right slot is then removed by the calling parent node.

Definition at line 3293 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::merge_leaves	(	leaf_node *	left,
		leaf_node *	right,
		inner_node *	parent
	)		`[inline, private]`

Merge two leaf nodes.

The function moves all key/data pairs from right to left and sets right's slotuse to zero. The right slot is then removed by the calling parent node.

Definition at line 3262 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator!= ( const btree_self & other ) const [inline]

Inequality relation. Based on operator==.

Definition at line 1963 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator< ( const btree_self & 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 1970 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator<= ( const btree_self & other ) const [inline]

Less-equal relation. Based on operator<.

Definition at line 1982 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

btree_self& stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator= ( const btree_self & other ) [inline]

*** Fast Copy: Assign Operator and Copy Constructors

Assignment operator. All the key/data pairs are copied

Definition at line 1997 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator== ( const btree_self & 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 1957 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator> ( const btree_self & other ) const [inline]

Greater relation. Based on operator<.

Definition at line 1976 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::operator>= ( const btree_self & other ) const [inline]

Greater-equal relation. Based on operator<.

Definition at line 1988 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::print ( std::ostream & os ) const [inline]

Print out the B+ tree structure with keys onto the given ostream.

This function requires that the header is compiled with BTREE_DEBUG and that key_type is printable via std::ostream.

Definition at line 3556 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::print(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::print(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::print(), stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::print(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::print_leaves ( std::ostream & os ) const [inline]

Print out only the leaves via the double linked list.

Definition at line 3564 of file btree.h.

Referenced by stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::print_leaves(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::print_leaves(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::print_leaves(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::print_leaves().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

static void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::print_node	(	std::ostream &	os,
		const node *	node,
		unsigned int	depth = `0`,
		bool	recursive = `false`
	)		`[inline, static, private]`

Recursively descend down the tree and print out nodes.

Definition at line 3581 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::print(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::print_node().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1601 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::rbegin(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::rbegin(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::rbegin(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::rbegin().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const_reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1615 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1608 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::rend(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::rend(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::rend(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::rend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const_reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1622 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::restore ( std::istream & is ) [inline]

Restore a binary image of a dumped B+ tree from an istream.

The B+ tree pointers are fixed using the dump order. For dump and restore to work your key_type and data_type must be integral types and contain no pointers or references. Returns true if the restore was successful.

Definition at line 3860 of file btree.h.

Referenced by stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::restore(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::restore(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::restore(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::restore().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::restore_node ( std::istream & is ) [inline, private]

Read the dump image and construct a tree from the node order in the serialization.

Definition at line 3924 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore_node().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

static void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::shift_left_inner	(	inner_node *	left,
		inner_node *	right,
		inner_node *	parent,
		unsigned int	parentslot
	)		`[inline, static, private]`

Balance two inner nodes.

The function moves key/data pairs from right to left so that both nodes are equally filled. The parent node is updated if possible.

Definition at line 3385 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

static result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::shift_left_leaf	(	leaf_node *	left,
		leaf_node *	right,
		inner_node *	parent,
		unsigned int	parentslot
	)		`[inline, static, private]`

Balance two leaf nodes.

The function moves key/data pairs from right to left so that both nodes are equally filled. The parent node is updated if possible.

Definition at line 3337 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

static void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::shift_right_inner	(	inner_node *	left,
		inner_node *	right,
		inner_node *	parent,
		unsigned int	parentslot
	)		`[inline, static, private]`

Balance two inner nodes.

The function moves key/data pairs from left to right so that both nodes are equally filled. The parent node is updated if possible.

Definition at line 3497 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

static void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::shift_right_leaf	(	leaf_node *	left,
		leaf_node *	right,
		inner_node *	parent,
		unsigned int	parentslot
	)		`[inline, static, private]`

Balance two leaf nodes.

The function moves key/data pairs from left to right so that both nodes are equally filled. The parent node is updated if possible.

Definition at line 3443 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one_descend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::size ( ) const [inline]

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

Definition at line 1728 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::split_inner_node	(	inner_node *	inner,
		key_type *	_newkey,
		node **	_newinner,
		unsigned int	addslot
	)		`[inline, private]`

Split up an inner node into two equally-filled sibling nodes.

Returns the new nodes and it's insertion key in the two parameters. Requires the slot of the item will be inserted, so the nodes will be the same size after the insert.

Definition at line 2362 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::split_leaf_node	(	leaf_node *	leaf,
		key_type *	_newkey,
		node **	_newleaf
	)		`[inline, private]`

Split up a leaf node into two equally-filled sibling leaves.

Returns the new nodes and it's insertion key in the two parameters.

Definition at line 2324 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::swap ( btree_self & from ) [inline]

Fast swapping of two identical B+ tree objects.

Definition at line 1357 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::swap().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1898 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::equal_range(), stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::upper_bound(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::upper_bound(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::upper_bound(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::upper_bound().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::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 1920 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

value_compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::value_comp ( ) const [inline]

Constant access to a constructed value_type comparison object.

Required by the STL

Definition at line 1402 of file btree.h.

Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::value_comp(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::value_comp(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::value_comp(), and stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::value_comp().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::verify ( ) const [inline]

Run a thorough verification of all B+ tree invariants.

The program aborts via assert() if something is wrong.

Definition at line 3630 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::btree(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::verify(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::verify(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::verify(), and stx::btree_map< _Key, _Data, _Compare, _Traits, _Alloc >::verify().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::verify_leaflinks ( ) const [inline, private]

Verify the double linked list of leaves.

Definition at line 3735 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::verify_node	(	const node *	n,
		key_type *	minkey,
		key_type *	maxkey,
		tree_stats &	vstats
	)		const `[inline, private]`

Recursively descend down the tree and verify each node.

Definition at line 3650 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::verify_node().

Member Data Documentation

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::allow_duplicates = _Duplicates [static]

Sixth template parameter: Allow duplicate keys in the B+ tree.

Used to implement multiset and multimap.

Definition at line 191 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::debug = traits::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 BTREE_DEBUG and the key type must be std::ostream printable.

Definition at line 248 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::erase_one(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_start(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::restore().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::innerslotmax = traits::innerslots [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 229 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::dump_header::fill(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::inner_node::isfull(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::merge_inner(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_left_inner(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_inner().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leafslotmax = traits::leafslots [static]

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

Definition at line 225 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::bulk_load(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::dump_header::fill(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::isfull(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::merge_leaves(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_left_leaf(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::shift_right_leaf().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

allocator_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::m_allocator [private]

Memory allocator.

Definition at line 1306 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::get_allocator(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::inner_node_allocator(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::leaf_node_allocator(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::operator=(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::swap().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::m_headleaf [private]

Pointer to first leaf in the double linked leaf chain.

Definition at line 1293 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

key_compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::m_key_less [private]

Key comparison object.

More comparison functions are generated from this < relation.

Definition at line 1303 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::m_root [private]

Pointer to the B+ tree's root node, either leaf or inner node.

Definition at line 1290 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

tree_stats stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::m_stats [private]

Other small statistics about the B+ tree.

Definition at line 1299 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::m_tailleaf [private]

Pointer to last leaf in the double linked leaf chain.

Definition at line 1296 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::mininnerslots = (innerslotmax / 2) [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 239 of file btree.h.

Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::inner_node::isfew(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::inner_node::isunderflow().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::minleafslots = (leafslotmax / 2) [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 234 of file btree.h.

Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::isfew(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::isunderflow().

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::selfverify = traits::selfverify [static]

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

Definition at line 243 of file btree.h.

template<typename _Key, typename _Data, typename _Value = std::pair<_Key, _Data>, typename _Compare = std::less<_Key>, typename _Traits = btree_default_map_traits<_Key, _Data>, bool _Duplicates = false, typename _Alloc = std::allocator<_Value>, bool _UsedAsSet = false>

const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::used_as_set = _UsedAsSet [static]

Eighth template parameter: boolean indicator whether the btree is used as a set.

In this case all operations on the data arrays are omitted. This flag is kind of hacky, but required because sizeof(empty_struct) = 1 due to the C standard. Without the flag, lots of superfluous copying would occur.

Definition at line 201 of file btree.h.

Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::iterator::data(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_iterator::data(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::reverse_iterator::data(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::const_reverse_iterator::data(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::data_copy(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::data_copy_backward(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false >::insert_descend(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::leaf_node::set_slot().

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

stx/btree.h

Classes

Public Types

Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation