tlx
|
Specialized B+ tree template class implementing STL's set container. More...
#include <btree_set.hpp>
Classes | |
struct | key_of_value |
Key Extractor Struct. More... | |
Public Types | |
Template Parameter Types | |
typedef Key_ | key_type |
First template parameter: The key type of the B+ tree. More... | |
typedef Compare_ | key_compare |
Second template parameter: Key comparison function object. More... | |
typedef Traits_ | traits |
Third template parameter: Traits object used to define more parameters of the B+ tree. More... | |
typedef Alloc_ | allocator_type |
Fourth template parameter: STL allocator. More... | |
Constructed Types | |
typedef key_type | value_type |
Construct the set value_type: the key_type. More... | |
typedef btree_set< key_type, key_compare, traits, allocator_type > | self |
Typedef of our own type. More... | |
typedef BTree< key_type, value_type, key_of_value, key_compare, traits, false, allocator_type > | btree_impl |
Implementation type of the btree_base. More... | |
typedef btree_impl::value_compare | value_compare |
Function class comparing two value_type keys. More... | |
typedef btree_impl::size_type | size_type |
Size type used to count keys. More... | |
typedef btree_impl::tree_stats | tree_stats |
Small structure containing statistics about the tree. More... | |
Iterators and Reverse Iterators | |
typedef btree_impl::iterator | iterator |
STL-like iterator object for B+ tree items. More... | |
typedef btree_impl::const_iterator | const_iterator |
STL-like iterator object for B+ tree items. More... | |
typedef btree_impl::reverse_iterator | reverse_iterator |
create mutable reverse iterator by using STL magic More... | |
typedef btree_impl::const_reverse_iterator | const_reverse_iterator |
create constant reverse iterator by using STL magic More... | |
Public Member Functions | |
Constructors and Destructor | |
btree_set (const allocator_type &alloc=allocator_type()) | |
Default constructor initializing an empty B+ tree with the standard key comparison function. More... | |
btree_set (const key_compare &kcf, const allocator_type &alloc=allocator_type()) | |
Constructor initializing an empty B+ tree with a special key comparison object. More... | |
template<class InputIterator > | |
btree_set (InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type()) | |
Constructor initializing a B+ tree with the range [first,last) More... | |
template<class InputIterator > | |
btree_set (InputIterator first, InputIterator last, const key_compare &kcf, const allocator_type &alloc=allocator_type()) | |
Constructor initializing a B+ tree with the range [first,last) and a special key comparison object. More... | |
~btree_set () | |
Frees up all used B+ tree memory pages. More... | |
void | swap (btree_set &from) |
Fast swapping of two identical B+ tree objects. More... | |
Key and Value Comparison Function Objects | |
key_compare | key_comp () const |
Constant access to the key comparison object sorting the B+ tree. More... | |
value_compare | value_comp () const |
Constant access to a constructed value_type comparison object. More... | |
Allocators | |
allocator_type | get_allocator () const |
Return the base node allocator provided during construction. More... | |
Fast Destruction of the B+ Tree | |
void | clear () |
Frees all keys and all nodes of the tree. More... | |
STL Iterator Construction Functions | |
iterator | begin () |
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree. More... | |
iterator | end () |
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B+ tree. More... | |
const_iterator | begin () const |
Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tree. More... | |
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. More... | |
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. More... | |
reverse_iterator | rend () |
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the B+ tree. More... | |
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. More... | |
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. More... | |
Access Functions to the Item Count | |
size_type | size () const |
Return the number of keys in the B+ tree. More... | |
bool | empty () const |
Returns true if there is at least one key in the B+ tree. More... | |
size_type | max_size () const |
Returns the largest possible size of the B+ Tree. More... | |
const tree_stats & | get_stats () const |
Return a const reference to the current statistics. More... | |
STL Access Functions Querying the Tree by Descending to a Leaf | |
bool | exists (const key_type &key) const |
Non-STL function checking whether a key is in the B+ tree. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
std::pair< iterator, iterator > | equal_range (const key_type &key) |
Searches the B+ tree and returns both lower_bound() and upper_bound(). More... | |
std::pair< const_iterator, const_iterator > | equal_range (const key_type &key) const |
Searches the B+ tree and returns both lower_bound() and upper_bound(). More... | |
B+ Tree Object Comparison Functions | |
bool | operator== (const btree_set &other) const |
Equality relation of B+ trees of the same type. More... | |
bool | operator!= (const btree_set &other) const |
Inequality relation. Based on operator==. More... | |
bool | operator< (const btree_set &other) const |
Total ordering relation of B+ trees of the same type. More... | |
bool | operator> (const btree_set &other) const |
Greater relation. Based on operator<. More... | |
bool | operator<= (const btree_set &other) const |
Less-equal relation. Based on operator<. More... | |
bool | operator>= (const btree_set &other) const |
Greater-equal relation. Based on operator<. More... | |
Fast Copy: Assign Operator and Copy Constructors | |
btree_set & | operator= (const btree_set &other) |
Assignment operator. All the keys are copied. More... | |
btree_set (const btree_set &other) | |
Copy constructor. More... | |
Public Insertion Functions | |
std::pair< iterator, bool > | insert (const key_type &x) |
Attempt to insert a key into the B+ tree. More... | |
iterator | insert (iterator hint, const key_type &x) |
Attempt to insert a key into the B+ tree. More... | |
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. More... | |
template<typename Iterator > | |
void | bulk_load (Iterator first, Iterator last) |
Bulk load a sorted range [first,last). More... | |
Public Erase Functions | |
bool | erase_one (const key_type &key) |
Erases the key from the set. More... | |
size_type | erase (const key_type &key) |
Erases all the key/data pairs associated with the given key. More... | |
void | erase (iterator iter) |
Erase the key/data pair referenced by the iterator. More... | |
Verification of B+ Tree Invariants | |
void | verify () const |
Run a thorough verification of all B+ tree invariants. More... | |
Public Attributes | |
TLX_BTREE_FRIENDS | |
The macro TLX_BTREE_FRIENDS can be used by outside class to access the B+ tree internals. More... | |
Static Public Attributes | |
Static Constant Options and Values of the B+ Tree | |
static const unsigned short | leaf_slotmax |
Base B+ tree parameter: The number of key slots in each leaf. More... | |
static const unsigned short | inner_slotmax |
Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in each leaf. More... | |
static const unsigned short | leaf_slotmin |
Computed B+ tree parameter: The minimum number of key slots used in a leaf. More... | |
static const unsigned short | inner_slotmin |
Computed B+ tree parameter: The minimum number of key slots used in an inner node. More... | |
static const bool | self_verify |
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation. More... | |
static const bool | debug |
Debug parameter: Prints out lots of debug information about how the algorithms change the tree. More... | |
static const bool | allow_duplicates |
Operational parameter: Allow duplicate keys in the btree. More... | |
Private Attributes | |
Tree Implementation Object | |
btree_impl | tree_ |
The contained implementation object. More... | |
Specialized B+ tree template class implementing STL's set container.
Implements the STL set using a B+ tree. It can be used as a drop-in replacement for std::set. Not all asymptotic time requirements are met in theory. The class has a traits class defining B+ tree properties like slots and self-verification. Furthermore an allocator can be specified for tree nodes.
It is somewhat inefficient to implement a set using a B+ tree, a plain B tree would hold fewer copies of the keys.
Definition at line 49 of file btree_set.hpp.
typedef Alloc_ allocator_type |
Fourth template parameter: STL allocator.
Definition at line 67 of file btree_set.hpp.
typedef BTree<key_type, value_type, key_of_value, key_compare, traits, false, allocator_type> btree_impl |
Implementation type of the btree_base.
Definition at line 94 of file btree_set.hpp.
typedef btree_impl::const_iterator const_iterator |
STL-like iterator object for B+ tree items.
The iterator points to a specific slot number in a leaf.
Definition at line 152 of file btree_set.hpp.
typedef btree_impl::const_reverse_iterator const_reverse_iterator |
create constant reverse iterator by using STL magic
Definition at line 158 of file btree_set.hpp.
typedef btree_impl::iterator iterator |
STL-like iterator object for B+ tree items.
The iterator points to a specific slot number in a leaf.
Definition at line 148 of file btree_set.hpp.
typedef Compare_ key_compare |
Second template parameter: Key comparison function object.
Definition at line 60 of file btree_set.hpp.
typedef Key_ key_type |
First template parameter: The key type of the B+ tree.
This is stored in inner nodes and leaves.
Definition at line 57 of file btree_set.hpp.
typedef btree_impl::reverse_iterator reverse_iterator |
create mutable reverse iterator by using STL magic
Definition at line 155 of file btree_set.hpp.
typedef btree_set<key_type, key_compare, traits, allocator_type> self |
Typedef of our own type.
Definition at line 84 of file btree_set.hpp.
typedef btree_impl::size_type size_type |
Size type used to count keys.
Definition at line 100 of file btree_set.hpp.
typedef Traits_ traits |
Third template parameter: Traits object used to define more parameters of the B+ tree.
Definition at line 64 of file btree_set.hpp.
typedef btree_impl::tree_stats tree_stats |
Small structure containing statistics about the tree.
Definition at line 103 of file btree_set.hpp.
typedef btree_impl::value_compare value_compare |
Function class comparing two value_type keys.
Definition at line 97 of file btree_set.hpp.
typedef key_type value_type |
Construct the set value_type: the key_type.
Definition at line 81 of file btree_set.hpp.
|
inlineexplicit |
Default constructor initializing an empty B+ tree with the standard key comparison function.
Definition at line 177 of file btree_set.hpp.
|
inlineexplicit |
Constructor initializing an empty B+ tree with a special key comparison object.
Definition at line 183 of file btree_set.hpp.
|
inline |
Constructor initializing a B+ tree with the range [first,last)
Definition at line 190 of file btree_set.hpp.
|
inline |
Constructor initializing a B+ tree with the range [first,last) and a special key comparison object.
Definition at line 199 of file btree_set.hpp.
|
inline |
Frees up all used B+ tree memory pages.
Definition at line 206 of file btree_set.hpp.
Copy constructor.
The newly initialized B+ tree object will contain a copy of all keys.
Definition at line 452 of file btree_set.hpp.
|
inline |
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree.
Definition at line 261 of file btree_set.hpp.
|
inline |
Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tree.
Definition at line 273 of file btree_set.hpp.
|
inline |
Bulk load a sorted range [first,last).
Loads items into leaves and constructs a B-tree above them. The tree must be empty when calling this function.
Definition at line 490 of file btree_set.hpp.
|
inline |
Frees all keys and all nodes of the tree.
Definition at line 249 of file btree_set.hpp.
Tries to locate a key in the B+ tree and returns the number of identical key entries found.
As this is a unique set, count() returns either 0 or
Definition at line 361 of file btree_set.hpp.
|
inline |
Returns true if there is at least one key in the B+ tree.
Definition at line 319 of file btree_set.hpp.
|
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 267 of file btree_set.hpp.
|
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 279 of file btree_set.hpp.
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition at line 390 of file btree_set.hpp.
|
inline |
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition at line 395 of file btree_set.hpp.
Erases all the key/data pairs associated with the given key.
Definition at line 507 of file btree_set.hpp.
|
inline |
Erase the key/data pair referenced by the iterator.
Definition at line 512 of file btree_set.hpp.
|
inline |
Erases the key from the set.
As this is a unique set, there is no difference to erase().
Definition at line 502 of file btree_set.hpp.
|
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 342 of file btree_set.hpp.
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 348 of file btree_set.hpp.
|
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 354 of file btree_set.hpp.
|
inline |
Return the base node allocator provided during construction.
Definition at line 238 of file btree_set.hpp.
|
inline |
Return a const reference to the current statistics.
Definition at line 330 of file btree_set.hpp.
Attempt to insert a key into the B+ tree.
The insert will fail if it is already present.
Definition at line 464 of file btree_set.hpp.
|
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 477 of file btree_set.hpp.
Attempt to insert a key into the B+ tree.
The iterator hint is currently ignored by the B+ tree insertion routine.
Definition at line 470 of file btree_set.hpp.
|
inline |
Constant access to the key comparison object sorting the B+ tree.
Definition at line 221 of file btree_set.hpp.
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 367 of file btree_set.hpp.
|
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 373 of file btree_set.hpp.
|
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 325 of file btree_set.hpp.
|
inline |
Inequality relation. Based on operator==.
Definition at line 413 of file btree_set.hpp.
|
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 419 of file btree_set.hpp.
|
inline |
Less-equal relation. Based on operator<.
Definition at line 429 of file btree_set.hpp.
Assignment operator. All the keys are copied.
Definition at line 444 of file btree_set.hpp.
|
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 408 of file btree_set.hpp.
|
inline |
Greater relation. Based on operator<.
Definition at line 424 of file btree_set.hpp.
|
inline |
Greater-equal relation. Based on operator<.
Definition at line 434 of file btree_set.hpp.
|
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 285 of file btree_set.hpp.
|
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 297 of file btree_set.hpp.
|
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 291 of file btree_set.hpp.
|
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 303 of file btree_set.hpp.
|
inline |
Return the number of keys in the B+ tree.
Definition at line 314 of file btree_set.hpp.
|
inline |
Fast swapping of two identical B+ tree objects.
Definition at line 210 of file btree_set.hpp.
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 379 of file btree_set.hpp.
|
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 385 of file btree_set.hpp.
|
inline |
Constant access to a constructed value_type comparison object.
required by the STL
Definition at line 227 of file btree_set.hpp.
|
inline |
Run a thorough verification of all B+ tree invariants.
The program aborts via TLX_BTREE_ASSERT() if something is wrong.
Definition at line 553 of file btree_set.hpp.
|
static |
Operational parameter: Allow duplicate keys in the btree.
Definition at line 138 of file btree_set.hpp.
|
static |
Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
Requires the header file to be compiled with TLX_BTREE_DEBUG and the key type must be std::ostream printable.
Definition at line 135 of file btree_set.hpp.
|
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 116 of file btree_set.hpp.
|
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 126 of file btree_set.hpp.
|
static |
Base B+ tree parameter: The number of key slots in each leaf.
Definition at line 112 of file btree_set.hpp.
|
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 121 of file btree_set.hpp.
|
static |
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation.
Definition at line 130 of file btree_set.hpp.
TLX_BTREE_FRIENDS |
The macro TLX_BTREE_FRIENDS can be used by outside class to access the B+ tree internals.
This was added for wxBTreeDemo to be able to draw the tree.
Definition at line 74 of file btree_set.hpp.
|
private |
The contained implementation object.
Definition at line 167 of file btree_set.hpp.