tlx
|
Specialized B+ tree template class implementing STL's map container. More...
#include <btree_map.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 btree. More... | |
typedef Data_ | data_type |
Second template parameter: The value type associated with each key. More... | |
typedef Compare_ | key_compare |
Third template parameter: Key comparison function object. More... | |
typedef Traits_ | traits |
Fourth template parameter: Traits object used to define more parameters of the B+ tree. More... | |
typedef Alloc_ | allocator_type |
Fifth template parameter: STL allocator. More... | |
Constructed Types | |
typedef btree_map< key_type, data_type, key_compare, traits, allocator_type > | self |
Typedef of our own type. More... | |
typedef std::pair< key_type, data_type > | value_type |
Construct the STL-required value_type as a composition pair of key and data types. 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 pairs. 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_map (const allocator_type &alloc=allocator_type()) | |
Default constructor initializing an empty B+ tree with the standard key comparison function. More... | |
btree_map (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_map (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_map (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_map () | |
Frees up all used B+ tree memory pages. More... | |
void | swap (btree_map &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 key/data pairs 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 key/data pairs in the B+ tree. More... | |
bool | empty () const |
Returns true if there is at least one key/data pair 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/data 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/data 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_map &other) const |
Equality relation of B+ trees of the same type. More... | |
bool | operator!= (const btree_map &other) const |
Inequality relation. Based on operator==. More... | |
bool | operator< (const btree_map &other) const |
Total ordering relation of B+ trees of the same type. More... | |
bool | operator> (const btree_map &other) const |
Greater relation. Based on operator<. More... | |
bool | operator<= (const btree_map &other) const |
Less-equal relation. Based on operator<. More... | |
bool | operator>= (const btree_map &other) const |
Greater-equal relation. Based on operator<. More... | |
Fast Copy: Assign Operator and Copy Constructors | |
btree_map & | operator= (const btree_map &other) |
Assignment operator. All the key/data pairs are copied. More... | |
btree_map (const btree_map &other) | |
Copy constructor. More... | |
Public Insertion Functions | |
std::pair< iterator, bool > | insert (const value_type &x) |
Attempt to insert a key/data pair into the B+ tree. More... | |
std::pair< iterator, bool > | insert2 (const key_type &key, const data_type &data) |
Attempt to insert a key/data pair into the B+ tree. More... | |
iterator | insert (iterator hint, const value_type &x) |
Attempt to insert a key/data pair into the B+ tree. More... | |
iterator | insert2 (iterator hint, const key_type &key, const data_type &data) |
Attempt to insert a key/data pair into the B+ tree. More... | |
data_type & | operator[] (const key_type &key) |
Returns a reference to the object that is associated with a particular key. More... | |
template<typename InputIterator > | |
void | insert (InputIterator first, InputIterator last) |
Attempt to insert the range [first,last) of value_type pairs 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/data pairs associated with the given key. 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 | |
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/data 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/data 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 map container.
Implements the STL map using a B+ tree. It can be used as a drop-in replacement for std::map. 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.
Definition at line 47 of file btree_map.hpp.
typedef Alloc_ allocator_type |
Fifth template parameter: STL allocator.
Definition at line 69 of file btree_map.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 98 of file btree_map.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 156 of file btree_map.hpp.
typedef btree_impl::const_reverse_iterator const_reverse_iterator |
create constant reverse iterator by using STL magic
Definition at line 162 of file btree_map.hpp.
typedef Data_ data_type |
Second template parameter: The value type associated with each key.
Stored in the B+ tree's leaves
Definition at line 59 of file btree_map.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 152 of file btree_map.hpp.
typedef Compare_ key_compare |
Third template parameter: Key comparison function object.
Definition at line 62 of file btree_map.hpp.
typedef Key_ key_type |
First template parameter: The key type of the btree.
This is stored in inner nodes.
Definition at line 55 of file btree_map.hpp.
typedef btree_impl::reverse_iterator reverse_iterator |
create mutable reverse iterator by using STL magic
Definition at line 159 of file btree_map.hpp.
typedef btree_map<key_type, data_type, key_compare, traits, allocator_type> self |
Typedef of our own type.
Definition at line 84 of file btree_map.hpp.
typedef btree_impl::size_type size_type |
Size type used to count keys.
Definition at line 104 of file btree_map.hpp.
typedef Traits_ traits |
Fourth template parameter: Traits object used to define more parameters of the B+ tree.
Definition at line 66 of file btree_map.hpp.
typedef btree_impl::tree_stats tree_stats |
Small structure containing statistics about the tree.
Definition at line 107 of file btree_map.hpp.
typedef btree_impl::value_compare value_compare |
Function class comparing two value_type pairs.
Definition at line 101 of file btree_map.hpp.
typedef std::pair<key_type, data_type> value_type |
Construct the STL-required value_type as a composition pair of key and data types.
Definition at line 88 of file btree_map.hpp.
|
inlineexplicit |
Default constructor initializing an empty B+ tree with the standard key comparison function.
Definition at line 181 of file btree_map.hpp.
|
inlineexplicit |
Constructor initializing an empty B+ tree with a special key comparison object.
Definition at line 187 of file btree_map.hpp.
|
inline |
Constructor initializing a B+ tree with the range [first,last)
Definition at line 194 of file btree_map.hpp.
|
inline |
Constructor initializing a B+ tree with the range [first,last) and a special key comparison object.
Definition at line 202 of file btree_map.hpp.
|
inline |
Frees up all used B+ tree memory pages.
Definition at line 208 of file btree_map.hpp.
Copy constructor.
The newly initialized B+ tree object will contain a copy of all key/data pairs.
Definition at line 455 of file btree_map.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 263 of file btree_map.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 275 of file btree_map.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 510 of file btree_map.hpp.
|
inline |
Frees all key/data pairs and all nodes of the tree.
Definition at line 251 of file btree_map.hpp.
Tries to locate a key in the B+ tree and returns the number of identical key entries found.
Since this is a unique map, count() returns either 0 or 1.
Definition at line 363 of file btree_map.hpp.
|
inline |
Returns true if there is at least one key/data pair in the B+ tree.
Definition at line 321 of file btree_map.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 269 of file btree_map.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 281 of file btree_map.hpp.
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition at line 392 of file btree_map.hpp.
|
inline |
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition at line 398 of file btree_map.hpp.
Erases all the key/data pairs associated with the given key.
This is implemented using erase_one().
Definition at line 528 of file btree_map.hpp.
|
inline |
Erase the key/data pair referenced by the iterator.
Definition at line 533 of file btree_map.hpp.
|
inline |
Erases the key/data pairs associated with the given key.
For this unique-associative map there is no difference to erase().
Definition at line 522 of file btree_map.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 344 of file btree_map.hpp.
Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found.
If unsuccessful it returns end().
Definition at line 350 of file btree_map.hpp.
|
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 356 of file btree_map.hpp.
|
inline |
Return the base node allocator provided during construction.
Definition at line 240 of file btree_map.hpp.
|
inline |
Return a const reference to the current statistics.
Definition at line 332 of file btree_map.hpp.
|
inline |
Attempt to insert a key/data pair into the B+ tree.
Fails if the pair is already present.
Definition at line 467 of file btree_map.hpp.
|
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 502 of file btree_map.hpp.
|
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 480 of file btree_map.hpp.
Attempt to insert a key/data pair into the B+ tree.
This function is the same as the other insert. Fails if the inserted pair is already present.
Definition at line 473 of file btree_map.hpp.
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 486 of file btree_map.hpp.
|
inline |
Constant access to the key comparison object sorting the B+ tree.
Definition at line 223 of file btree_map.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 369 of file btree_map.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 375 of file btree_map.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 327 of file btree_map.hpp.
|
inline |
Inequality relation. Based on operator==.
Definition at line 415 of file btree_map.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 421 of file btree_map.hpp.
|
inline |
Less-equal relation. Based on operator<.
Definition at line 431 of file btree_map.hpp.
Assignment operator. All the key/data pairs are copied.
Definition at line 447 of file btree_map.hpp.
|
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.
Definition at line 410 of file btree_map.hpp.
|
inline |
Greater relation. Based on operator<.
Definition at line 426 of file btree_map.hpp.
|
inline |
Greater-equal relation. Based on operator<.
Definition at line 436 of file btree_map.hpp.
Returns a reference to the object that is associated with a particular key.
If the map does not already contain such an object, operator[] inserts the default object data_type().
Definition at line 494 of file btree_map.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 287 of file btree_map.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 299 of file btree_map.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 293 of file btree_map.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 305 of file btree_map.hpp.
|
inline |
Return the number of key/data pairs in the B+ tree.
Definition at line 316 of file btree_map.hpp.
|
inline |
Fast swapping of two identical B+ tree objects.
Definition at line 212 of file btree_map.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 381 of file btree_map.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 387 of file btree_map.hpp.
|
inline |
Constant access to a constructed value_type comparison object.
required by the STL
Definition at line 229 of file btree_map.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 574 of file btree_map.hpp.
|
static |
Operational parameter: Allow duplicate keys in the btree.
Definition at line 142 of file btree_map.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 139 of file btree_map.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 120 of file btree_map.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 130 of file btree_map.hpp.
|
static |
Base B+ tree parameter: The number of key/data slots in each leaf.
Definition at line 116 of file btree_map.hpp.
|
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 125 of file btree_map.hpp.
|
static |
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation.
Definition at line 134 of file btree_map.hpp.
TLX_BTREE_FRIENDS |
Definition at line 76 of file btree_map.hpp.
|
private |
The contained implementation object.
Definition at line 171 of file btree_map.hpp.