STX B+ Tree Template Classes 0.8.6
Classes | Public Types | Public Member Functions | Static Public Attributes | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes

stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc > Class Template Reference

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

#include <btree.h>

List of all members.

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
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_statsget_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, iteratorequal_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_selfoperator= (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.
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 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_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_nodeallocate_leaf ()
 Allocate and initialize a leaf node.
inner_nodeallocate_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 less 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 nodecopy_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.
noderestore_node (std::istream &is)
 Read the dump image and construct a tree from the node order in the serialization.

Static Private Member Functions

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

noderoot
 Pointer to the B+ tree's root node, either leaf or inner node.
leaf_nodeheadleaf
 Pointer to first leaf in the double linked leaf chain.
leaf_nodetailleaf
 Pointer to last leaf in the double linked leaf chain.
tree_stats stats
 Other small statistics about the B+ tree.
key_compare key_less
 Key comparison object.
allocator_type 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>>
class stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >

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 140 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>>
typedef _Alloc stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::allocator_type

Seventh template parameter: STL allocator for tree nodes.

Definition at line 171 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>>
typedef btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates, allocator_type> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::btree_self

Typedef of our own type.

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>>
typedef _Data stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::data_type

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

Stored in the B+ tree's leaves

Definition at line 151 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>>
typedef _Compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::key_compare

Fourth template parameter: Key comparison function object.

Definition at line 160 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>>
typedef _Key stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::key_type

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

This is stored in inner nodes and leaves

Definition at line 147 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>>
typedef btree_pair_to_value<value_type, pair_type> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::pair_to_value_type [private]

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

Definition at line 366 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>>
typedef std::pair<key_type, data_type> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::pair_type

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

Definition at line 189 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>>
typedef size_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::size_type

Size type used to count keys.

Definition at line 186 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>>
typedef _Traits stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::traits

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

Definition at line 164 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>>
typedef _Value stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 157 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>>
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 2328 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>>
stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1263 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>>
stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1270 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>>
template<class InputIterator >
stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::btree ( InputIterator  first,
InputIterator  last,
const allocator_type alloc = allocator_type() 
) [inline]

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

Definition at line 1279 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>>
template<class InputIterator >
stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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.

Definition at line 1289 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>>
stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::~btree ( ) [inline]

Frees up all used B+ tree memory pages.

Definition at line 1298 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>>
stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1942 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>>
inner_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::allocate_inner ( unsigned short  level) [inline, private]
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>>
leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::allocate_leaf ( ) [inline, private]
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>>
iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::begin ( ) [inline]
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>>
const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1507 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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::clear ( ) [inline]
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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::clear_recursive ( node n) [inline, private]
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>>
struct node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::copy_recursive ( const node n) [inline, read, private]
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>>
size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::count ( const key_type key) const [inline]
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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 3643 of file btree.h.

Referenced by stx::btree_set< _Key, _Compare, _Traits, _Alloc >::dump(), stx::btree_multiset< _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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::dump_node ( std::ostream &  os,
const node n 
) const [inline, private]
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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::empty ( ) const [inline]
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>>
const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1514 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>>
iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::end ( ) [inline]
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>>
std::pair<const_iterator, const_iterator> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::equal_range ( const key_type key) const [inline]

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

Definition at line 1866 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>>
std::pair<iterator, iterator> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::equal_range ( const key_type key) [inline]
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>>
size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::erase ( const key_type key) [inline]
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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::erase ( iterator  iter) [inline]

Erase the key/data pair referenced by the iterator.

Definition at line 2427 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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 2449 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>>
result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 2756 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::erase_one ( const key_type key) [inline]
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>>
result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 2467 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase_one(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::exists ( const key_type key) const [inline]
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>>
const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1720 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>>
iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::find ( const key_type key) [inline]
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>>
template<typename node_type >
int stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::find_lower ( const node_type *  n,
const key_type key 
) const [inline, private]
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>>
template<typename node_type >
int stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1602 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::free_node ( node n) [inline, private]
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>>
allocator_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::get_allocator ( ) const [inline]
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>>
struct tree_stats& stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::get_stats ( ) const [inline, read]
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>>
inner_node::alloc_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::inner_node_allocator ( ) [inline, private]
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>>
std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::insert ( const pair_type x) [inline]
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>>
std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 2017 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>>
iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 2033 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>>
template<typename InputIterator >
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::insert ( InputIterator  first,
InputIterator  last 
) [inline]

Attempt to insert the range [first,last) of value_type pairs into the B+ tree.

Each key/data pair is inserted individually.

Definition at line 2048 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>>
std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 2026 of file btree.h.

Referenced by stx::btree_set< _Key, _Compare, _Traits, _Alloc >::insert(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::insert(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::insert(), stx::btree_map< _Key, _Data, _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>>
iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 2040 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>>
std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 2109 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::insert_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 2063 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::insert(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
key_compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::key_comp ( ) const [inline]
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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::key_equal ( const key_type a,
const key_type b 
) const [inline, private]
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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::key_greater ( const key_type a,
const key_type b 
) const [inline, private]

True if a > b ? constructed from key_less()

Definition at line 1363 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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::key_greaterequal ( const key_type a,
const key_type  b 
) const [inline, private]
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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::key_lessequal ( const key_type a,
const key_type  b 
) const [inline, private]
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>>
leaf_node::alloc_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::leaf_node_allocator ( ) [inline, private]
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>>
iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::lower_bound ( const key_type key) [inline]
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>>
const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1797 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>>
size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1661 of file btree.h.

Referenced by stx::btree_set< _Key, _Compare, _Traits, _Alloc >::max_size(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::max_size(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::max_size(), and stx::btree_map< _Key, _Data, _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>>
static result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 3086 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 3055 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::operator!= ( const btree_self other) const [inline]

Inequality relation. Based on operator==.

Definition at line 1883 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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1890 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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::operator<= ( const btree_self other) const [inline]

Less-equal relation. Based on operator<.

Definition at line 1902 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>>
btree_self& stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1917 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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::operator> ( const btree_self other) const [inline]

Greater relation. Based on operator<.

Definition at line 1896 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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::operator>= ( const btree_self other) const [inline]

Greater-equal relation. Based on operator<.

Definition at line 1908 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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::print ( std::ostream &  os) const [inline]
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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::print_leaves ( std::ostream &  os) const [inline]
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>>
static void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::print_node ( std::ostream &  os,
const node node,
unsigned int  depth = 0,
bool  recursive = false 
) [inline, static, private]
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>>
reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1521 of file btree.h.

Referenced by stx::btree_set< _Key, _Compare, _Traits, _Alloc >::rbegin(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::rbegin(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::rbegin(), and stx::btree_map< _Key, _Data, _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>>
const_reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1535 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>>
reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1528 of file btree.h.

Referenced by stx::btree_set< _Key, _Compare, _Traits, _Alloc >::rend(), stx::btree_multiset< _Key, _Compare, _Traits, _Alloc >::rend(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::rend(), and stx::btree_map< _Key, _Data, _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>>
const_reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1542 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 stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 3660 of file btree.h.

Referenced by stx::btree_set< _Key, _Compare, _Traits, _Alloc >::restore(), stx::btree_multiset< _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>>
node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::restore_node ( std::istream &  is) [inline, private]
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>>
static void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 3180 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
static result_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 3133 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
static void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 3294 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
static void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 3240 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase_iter_descend(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::size ( ) const [inline]
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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 2289 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 2249 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::swap ( btree_self from) [inline]

Fast swapping of two identical B+ tree objects.

Definition at line 1304 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 1840 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>>
iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::upper_bound ( const key_type key) [inline]
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>>
value_compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::value_comp ( ) const [inline]
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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::verify ( ) const [inline]
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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::verify_leaflinks ( ) const [inline, private]

Verify the double linked list of leaves.

Definition at line 3535 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::verify_node ( const node n,
key_type minkey,
key_type maxkey,
tree_stats vstats 
) const [inline, private]

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>>
allocator_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::allocator [private]
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>>
const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::allow_duplicates = _Duplicates [static]

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

Used to implement multiset and multimap.

Definition at line 168 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::debug = traits::debug [static]
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>>
leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::headleaf [private]
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>>
const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::innerslotmax = traits::innerslots [static]
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>>
key_compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::key_less [private]
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>>
const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::leafslotmax = traits::leafslots [static]
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>>
const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 209 of file btree.h.

Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::inner_node::isfew(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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>>
const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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 204 of file btree.h.

Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::leaf_node::isfew(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::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>>
node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::root [private]

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

Definition at line 1240 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::btree(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::clear(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::count(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::dump(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase_iter_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase_one(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase_one_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::exists(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::find(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::insert_start(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::lower_bound(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::operator=(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::print(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::restore(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::swap(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::upper_bound(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::verify(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::selfverify = traits::selfverify [static]
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>>
tree_stats stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::stats [private]

Other small statistics about the B+ tree.

Definition at line 1249 of file btree.h.

Referenced by stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::allocate_inner(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::allocate_leaf(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::btree(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::clear(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase_iter_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase_one(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::erase_one_descend(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::free_node(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::get_stats(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::insert_start(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::operator=(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::restore(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::size(), stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::swap(), and stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type >::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>>
leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::tailleaf [private]

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines