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

stx::btree_set< _Key, _Compare, _Traits, _Alloc > Class Template Reference

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

#include <btree_set.h>

List of all members.

Classes

struct  empty_struct
 The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals. More...

Public Types

typedef _Key key_type
 First template parameter: The key type of the B+ tree.
typedef _Compare key_compare
 Second template parameter: Key comparison function object.
typedef _Traits traits
 Third template parameter: Traits object used to define more parameters of the B+ tree.
typedef _Alloc allocator_type
 Fourth template parameter: STL allocator.
typedef struct empty_struct data_type
 The empty data_type.
typedef key_type value_type
 Construct the set value_type: the key_type.
typedef btree_set< key_type,
key_compare, traits,
allocator_type
self
 Typedef of our own type.
typedef stx::btree< key_type,
data_type, value_type,
key_compare, traits, false,
allocator_type
btree_impl
 Implementation type of the btree_base.
typedef btree_impl::value_compare value_compare
 Function class comparing two value_type keys.
typedef btree_impl::size_type size_type
 Size type used to count keys.
typedef btree_impl::tree_stats tree_stats
 Small structure containing statistics about the tree.
typedef btree_impl::iterator iterator
 STL-like iterator object for B+ tree items.
typedef btree_impl::const_iterator const_iterator
 STL-like iterator object for B+ tree items.
typedef
btree_impl::reverse_iterator 
reverse_iterator
 create mutable reverse iterator by using STL magic
typedef
btree_impl::const_reverse_iterator 
const_reverse_iterator
 create constant reverse iterator by using STL magic

Public Member Functions

 btree_set (const allocator_type &alloc=allocator_type())
 Default constructor initializing an empty B+ tree with the standard key comparison function.
 btree_set (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_set (InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
 Constructor initializing a B+ tree with the range [first,last)
template<class InputIterator >
 btree_set (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_set ()
 Frees up all used B+ tree memory pages.
void swap (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 keys 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 keys in the B+ tree.
bool empty () const
 Returns true if there is at least one key in the B+ tree.
size_type max_size () const
 Returns the largest possible size of the B+ Tree.
const 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 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 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 self &other) const
 Equality relation of B+ trees of the same type.
bool operator!= (const self &other) const
 Inequality relation. Based on operator==.
bool operator< (const self &other) const
 Total ordering relation of B+ trees of the same type.
bool operator> (const self &other) const
 Greater relation. Based on operator<.
bool operator<= (const self &other) const
 Less-equal relation. Based on operator<.
bool operator>= (const self &other) const
 Greater-equal relation. Based on operator<.
selfoperator= (const self &other)
 *** Fast Copy: Assign Operator and Copy Constructors
 btree_set (const self &other)
 Copy constructor.
std::pair< iterator, bool > insert (const key_type &x)
 Attempt to insert a key into the B+ tree.
iterator insert (iterator hint, const key_type &x)
 Attempt to insert a key into the B+ tree.
template<typename InputIterator >
void insert (InputIterator first, InputIterator last)
 Attempt to insert the range [first,last) of iterators dereferencing to key_type into the B+ tree.
bool erase_one (const key_type &key)
 Erases the key from the set.
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 keys 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 unsigned short leafslotmax = btree_impl::leafslotmax
 Base B+ tree parameter: The number of key slots in each leaf.
static const unsigned short innerslotmax = btree_impl::innerslotmax
 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 = btree_impl::minleafslots
 Computed B+ tree parameter: The minimum number of key slots used in a leaf.
static const unsigned short mininnerslots = btree_impl::mininnerslots
 Computed B+ tree parameter: The minimum number of key slots used in an inner node.
static const bool selfverify = btree_impl::selfverify
 Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation.
static const bool debug = btree_impl::debug
 Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
static const bool allow_duplicates = btree_impl::allow_duplicates
 Operational parameter: Allow duplicate keys in the btree.

Private Attributes

btree_impl tree
 The contained implementation object.

Detailed Description

template<typename _Key, typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
class stx::btree_set< _Key, _Compare, _Traits, _Alloc >

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

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

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

The set class is derived from the base implementation class btree by specifying an empty struct as data_type. All function are adapted to provide the inner class with placeholder objects. Most tricky to get right were the return type's of iterators which as value_type should be the same as key_type, and not a pair of key and dummy-struct. This is taken case of using some template magic in the btree class.

Definition at line 54 of file btree_set.h.


Member Typedef Documentation

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef _Alloc stx::btree_set< _Key, _Compare, _Traits, _Alloc >::allocator_type

Fourth template parameter: STL allocator.

Definition at line 71 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef stx::btree<key_type, data_type, value_type, key_compare, traits, false, allocator_type> stx::btree_set< _Key, _Compare, _Traits, _Alloc >::btree_impl

Implementation type of the btree_base.

Definition at line 99 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef btree_impl::const_iterator stx::btree_set< _Key, _Compare, _Traits, _Alloc >::const_iterator

STL-like iterator object for B+ tree items.

The iterator points to a specific slot number in a leaf.

Definition at line 151 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef btree_impl::const_reverse_iterator stx::btree_set< _Key, _Compare, _Traits, _Alloc >::const_reverse_iterator

create constant reverse iterator by using STL magic

Definition at line 157 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef struct empty_struct stx::btree_set< _Key, _Compare, _Traits, _Alloc >::data_type

The empty data_type.

Definition at line 90 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef btree_impl::iterator stx::btree_set< _Key, _Compare, _Traits, _Alloc >::iterator

STL-like iterator object for B+ tree items.

The iterator points to a specific slot number in a leaf.

Definition at line 147 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef _Compare stx::btree_set< _Key, _Compare, _Traits, _Alloc >::key_compare

Second template parameter: Key comparison function object.

Definition at line 64 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef _Key stx::btree_set< _Key, _Compare, _Traits, _Alloc >::key_type

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

This is stored in inner nodes and leaves

Definition at line 61 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef btree_impl::reverse_iterator stx::btree_set< _Key, _Compare, _Traits, _Alloc >::reverse_iterator

create mutable reverse iterator by using STL magic

Definition at line 154 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef btree_set<key_type, key_compare, traits, allocator_type> stx::btree_set< _Key, _Compare, _Traits, _Alloc >::self

Typedef of our own type.

Definition at line 96 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef btree_impl::size_type stx::btree_set< _Key, _Compare, _Traits, _Alloc >::size_type

Size type used to count keys.

Definition at line 105 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef _Traits stx::btree_set< _Key, _Compare, _Traits, _Alloc >::traits

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

Definition at line 68 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef btree_impl::tree_stats stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree_stats

Small structure containing statistics about the tree.

Definition at line 108 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef btree_impl::value_compare stx::btree_set< _Key, _Compare, _Traits, _Alloc >::value_compare

Function class comparing two value_type keys.

Definition at line 102 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
typedef key_type stx::btree_set< _Key, _Compare, _Traits, _Alloc >::value_type

Construct the set value_type: the key_type.

Definition at line 93 of file btree_set.h.


Constructor & Destructor Documentation

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
stx::btree_set< _Key, _Compare, _Traits, _Alloc >::btree_set ( const allocator_type alloc = allocator_type()) [inline, explicit]

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

Definition at line 170 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
stx::btree_set< _Key, _Compare, _Traits, _Alloc >::btree_set ( 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 177 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
template<class InputIterator >
stx::btree_set< _Key, _Compare, _Traits, _Alloc >::btree_set ( InputIterator  first,
InputIterator  last,
const allocator_type alloc = allocator_type() 
) [inline]

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

Definition at line 185 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::insert().

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
template<class InputIterator >
stx::btree_set< _Key, _Compare, _Traits, _Alloc >::btree_set ( InputIterator  first,
InputIterator  last,
const key_compare kcf,
const allocator_type alloc = allocator_type() 
) [inline]

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

Definition at line 195 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::insert().

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
stx::btree_set< _Key, _Compare, _Traits, _Alloc >::~btree_set ( ) [inline]

Frees up all used B+ tree memory pages.

Definition at line 203 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
stx::btree_set< _Key, _Compare, _Traits, _Alloc >::btree_set ( const self other) [inline]

Copy constructor.

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

Definition at line 464 of file btree_set.h.


Member Function Documentation

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
iterator stx::btree_set< _Key, _Compare, _Traits, _Alloc >::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 252 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::begin(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const_iterator stx::btree_set< _Key, _Compare, _Traits, _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 266 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::begin(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
void stx::btree_set< _Key, _Compare, _Traits, _Alloc >::clear ( ) [inline]
template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
size_type stx::btree_set< _Key, _Compare, _Traits, _Alloc >::count ( const key_type key) const [inline]

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

As this is a unique set, count() returns either 0 or 1.

Definition at line 361 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::count(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
void stx::btree_set< _Key, _Compare, _Traits, _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 must be an integral type and contain no pointers or references.

Definition at line 566 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::dump(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
bool stx::btree_set< _Key, _Compare, _Traits, _Alloc >::empty ( ) const [inline]

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

Definition at line 316 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::empty(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const_iterator stx::btree_set< _Key, _Compare, _Traits, _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 273 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::end(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
iterator stx::btree_set< _Key, _Compare, _Traits, _Alloc >::end ( ) [inline]

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

Definition at line 259 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::end(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
std::pair<iterator, iterator> stx::btree_set< _Key, _Compare, _Traits, _Alloc >::equal_range ( const key_type key) [inline]
template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
std::pair<const_iterator, const_iterator> stx::btree_set< _Key, _Compare, _Traits, _Alloc >::equal_range ( const key_type key) const [inline]
template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
size_type stx::btree_set< _Key, _Compare, _Traits, _Alloc >::erase ( const key_type key) [inline]

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

Definition at line 510 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::erase(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
void stx::btree_set< _Key, _Compare, _Traits, _Alloc >::erase ( iterator  iter) [inline]

Erase the key/data pair referenced by the iterator.

Definition at line 516 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::erase(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
void stx::btree_set< _Key, _Compare, _Traits, _Alloc >::erase ( iterator  ,
iterator   
) [inline]

Erase all keys in the range [first,last).

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

Definition at line 524 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
bool stx::btree_set< _Key, _Compare, _Traits, _Alloc >::erase_one ( const key_type key) [inline]

Erases the key from the set.

As this is a unique set, there is no difference to erase().

Definition at line 504 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::erase_one(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
bool stx::btree_set< _Key, _Compare, _Traits, _Alloc >::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 339 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::exists(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
iterator stx::btree_set< _Key, _Compare, _Traits, _Alloc >::find ( const key_type key) [inline]

Tries to locate a key in the B+ tree and returns an iterator to the key slot if found.

If unsuccessful it returns end().

Definition at line 346 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::find(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const_iterator stx::btree_set< _Key, _Compare, _Traits, _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 slot if found.

If unsuccessful it returns end().

Definition at line 353 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::find(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
allocator_type stx::btree_set< _Key, _Compare, _Traits, _Alloc >::get_allocator ( ) const [inline]

Return the base node allocator provided during construction.

Definition at line 233 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::get_allocator(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const tree_stats& stx::btree_set< _Key, _Compare, _Traits, _Alloc >::get_stats ( ) const [inline]
template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
std::pair<iterator, bool> stx::btree_set< _Key, _Compare, _Traits, _Alloc >::insert ( const key_type x) [inline]
template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
iterator stx::btree_set< _Key, _Compare, _Traits, _Alloc >::insert ( iterator  hint,
const key_type x 
) [inline]

Attempt to insert a key into the B+ tree.

The iterator hint is currently ignored by the B+ tree insertion routine.

Definition at line 481 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::insert2(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
template<typename InputIterator >
void stx::btree_set< _Key, _Compare, _Traits, _Alloc >::insert ( InputIterator  first,
InputIterator  last 
) [inline]

Attempt to insert the range [first,last) of iterators dereferencing to key_type into the B+ tree.

Each key/data pair is inserted individually.

Definition at line 489 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::insert().

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
key_compare stx::btree_set< _Key, _Compare, _Traits, _Alloc >::key_comp ( ) const [inline]

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

Definition at line 217 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::key_comp(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
iterator stx::btree_set< _Key, _Compare, _Traits, _Alloc >::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 368 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::lower_bound(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const_iterator stx::btree_set< _Key, _Compare, _Traits, _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 376 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::lower_bound(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
size_type stx::btree_set< _Key, _Compare, _Traits, _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 323 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::max_size(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
bool stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator!= ( const self other) const [inline]

Inequality relation. Based on operator==.

Definition at line 419 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
bool stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator< ( const 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 426 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
bool stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator<= ( const self other) const [inline]

Less-equal relation. Based on operator<.

Definition at line 438 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
self& stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator= ( const self other) [inline]

*** Fast Copy: Assign Operator and Copy Constructors

Assignment operator. All the keys are copied

Definition at line 453 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
bool stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator== ( const self other) const [inline]

Equality relation of B+ trees of the same type.

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

Definition at line 413 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
bool stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator> ( const self other) const [inline]

Greater relation. Based on operator<.

Definition at line 432 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
bool stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator>= ( const self other) const [inline]

Greater-equal relation. Based on operator<.

Definition at line 444 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
void stx::btree_set< _Key, _Compare, _Traits, _Alloc >::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 537 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::print(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
void stx::btree_set< _Key, _Compare, _Traits, _Alloc >::print_leaves ( std::ostream &  os) const [inline]
template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const_reverse_iterator stx::btree_set< _Key, _Compare, _Traits, _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 294 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::rbegin(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
reverse_iterator stx::btree_set< _Key, _Compare, _Traits, _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 280 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::rbegin(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const_reverse_iterator stx::btree_set< _Key, _Compare, _Traits, _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 301 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::rend(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
reverse_iterator stx::btree_set< _Key, _Compare, _Traits, _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 287 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::rend(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
bool stx::btree_set< _Key, _Compare, _Traits, _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 must be an integral type and contain no pointers or references. Returns true if the restore was successful.

Definition at line 575 of file btree_set.h.

References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::restore(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
size_type stx::btree_set< _Key, _Compare, _Traits, _Alloc >::size ( ) const [inline]
template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
void stx::btree_set< _Key, _Compare, _Traits, _Alloc >::swap ( self from) [inline]

Fast swapping of two identical B+ tree objects.

Definition at line 208 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const_iterator stx::btree_set< _Key, _Compare, _Traits, _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 391 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::upper_bound().

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
iterator stx::btree_set< _Key, _Compare, _Traits, _Alloc >::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 383 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::upper_bound().

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
value_compare stx::btree_set< _Key, _Compare, _Traits, _Alloc >::value_comp ( ) const [inline]

Constant access to a constructed value_type comparison object.

required by the STL

Definition at line 224 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::value_comp().

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
void stx::btree_set< _Key, _Compare, _Traits, _Alloc >::verify ( ) const [inline]

Run a thorough verification of all B+ tree invariants.

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

Definition at line 555 of file btree_set.h.

References stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc >::verify().


Member Data Documentation

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const bool stx::btree_set< _Key, _Compare, _Traits, _Alloc >::allow_duplicates = btree_impl::allow_duplicates [static]

Operational parameter: Allow duplicate keys in the btree.

Definition at line 140 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const bool stx::btree_set< _Key, _Compare, _Traits, _Alloc >::debug = btree_impl::debug [static]

Debug parameter: Prints out lots of debug information about how the algorithms change the tree.

Requires the header file to be compiled with BTREE_DEBUG and the key type must be std::ostream printable.

Definition at line 137 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const unsigned short stx::btree_set< _Key, _Compare, _Traits, _Alloc >::innerslotmax = btree_impl::innerslotmax [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 118 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const unsigned short stx::btree_set< _Key, _Compare, _Traits, _Alloc >::leafslotmax = btree_impl::leafslotmax [static]

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

Definition at line 114 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const unsigned short stx::btree_set< _Key, _Compare, _Traits, _Alloc >::mininnerslots = btree_impl::mininnerslots [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 128 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const unsigned short stx::btree_set< _Key, _Compare, _Traits, _Alloc >::minleafslots = btree_impl::minleafslots [static]

Computed B+ tree parameter: The minimum number of key slots used in a leaf.

If fewer slots are used, the leaf will be merged or slots shifted from it's siblings.

Definition at line 123 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
const bool stx::btree_set< _Key, _Compare, _Traits, _Alloc >::selfverify = btree_impl::selfverify [static]

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

Definition at line 132 of file btree_set.h.

template<typename _Key , typename _Compare = std::less<_Key>, typename _Traits = btree_default_set_traits<_Key>, typename _Alloc = std::allocator<_Key>>
btree_impl stx::btree_set< _Key, _Compare, _Traits, _Alloc >::tree [private]

The contained implementation object.

Definition at line 163 of file btree_set.h.

Referenced by stx::btree_set< _Key, _Compare, _Traits, _Alloc >::begin(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::clear(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::count(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::dump(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::empty(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::end(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::equal_range(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::erase(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::erase_one(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::exists(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::find(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::get_allocator(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::get_stats(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::insert(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::key_comp(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::lower_bound(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::max_size(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator!=(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator<(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator<=(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator=(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator==(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator>(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::operator>=(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::print(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::print_leaves(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::rbegin(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::rend(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::restore(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::size(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::swap(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::upper_bound(), stx::btree_set< _Key, _Compare, _Traits, _Alloc >::value_comp(), and stx::btree_set< _Key, _Compare, _Traits, _Alloc >::verify().


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