|
STX B+ Tree Template Classes
0.9
|
|
STX B+ Tree Template Classes
0.9
|
Specialized B+ tree template class implementing STL's multimap container. More...
#include <btree_multimap.h>
Public Types | |
| typedef _Key | key_type |
| First template parameter: The key type of the btree. | |
| typedef _Data | data_type |
| Second template parameter: The data type associated with each key. | |
| typedef _Compare | key_compare |
| Third template parameter: Key comparison function object. | |
| typedef _Traits | traits |
| Fourth template parameter: Traits object used to define more parameters of the B+ tree. | |
| typedef _Alloc | allocator_type |
| Fifth template parameter: STL allocator. | |
| typedef btree_multimap < key_type, data_type, key_compare, traits, allocator_type > | self |
| Typedef of our own type. | |
| typedef std::pair< key_type, data_type > | value_type |
| Construct the STL-required value_type as a composition pair of key and data types. | |
| typedef stx::btree< key_type, data_type, value_type, key_compare, traits, true, allocator_type, false > | btree_impl |
| Implementation type of the btree_base. | |
| typedef btree_impl::value_compare | value_compare |
| Function class comparing two value_type pairs. | |
| 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_multimap (const allocator_type &alloc=allocator_type()) | |
| Default constructor initializing an empty B+ tree with the standard key comparison function. | |
| btree_multimap (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_multimap (InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type()) | |
| Constructor initializing a B+ tree with the range [first,last) | |
| template<class InputIterator > | |
| btree_multimap (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_multimap () | |
| 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 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. | |
| const tree_stats & | get_stats () const |
| Return a const reference to the current statistics. | |
| bool | exists (const key_type &key) const |
| Non-STL function checking whether a key is in the B+ tree. | |
| iterator | find (const key_type &key) |
| Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found. | |
| const_iterator | find (const key_type &key) const |
| Tries to locate a key in the B+ tree and returns an constant iterator to the key/data slot if found. | |
| size_type | count (const key_type &key) const |
| Tries to locate a key in the B+ tree and returns the number of identical key entries found. | |
| iterator | lower_bound (const key_type &key) |
| Searches the B+ tree and returns an iterator to the first pair equal to or greater than key, or end() if all keys are smaller. | |
| const_iterator | lower_bound (const key_type &key) const |
| Searches the B+ tree and returns a constant iterator to the first pair equal to or greater than key, or end() if all keys are smaller. | |
| iterator | upper_bound (const key_type &key) |
| Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys are smaller or equal. | |
| const_iterator | upper_bound (const key_type &key) const |
| Searches the B+ tree and returns a constant iterator to the first pair greater than key, or end() if all keys are smaller or equal. | |
| std::pair< iterator, iterator > | equal_range (const key_type &key) |
| Searches the B+ tree and returns both lower_bound() and upper_bound(). | |
| std::pair< const_iterator, const_iterator > | equal_range (const key_type &key) const |
| Searches the B+ tree and returns both lower_bound() and upper_bound(). | |
| bool | operator== (const 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<. | |
| self & | operator= (const self &other) |
| *** Fast Copy: Assign Operator and Copy Constructors | |
| btree_multimap (const self &other) | |
| Copy constructor. | |
| iterator | insert (const value_type &x) |
| Attempt to insert a key/data pair into the B+ tree. | |
| iterator | insert (const key_type &key, const data_type &data) |
| Attempt to insert a key/data pair into the B+ tree. | |
| iterator | insert2 (const key_type &key, const data_type &data) |
| Attempt to insert a key/data pair into the B+ tree. | |
| iterator | insert (iterator hint, const value_type &x) |
| Attempt to insert a key/data pair into the B+ tree. | |
| iterator | insert2 (iterator hint, const key_type &key, const data_type &data) |
| Attempt to insert a key/data pair into the B+ tree. | |
| template<typename InputIterator > | |
| void | insert (InputIterator first, InputIterator last) |
| Attempt to insert the range [first,last) of value_type pairs into the B+ tree. | |
| template<typename Iterator > | |
| void | bulk_load (Iterator first, Iterator last) |
| Bulk load a sorted range [first,last). | |
| 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 unsigned short | leafslotmax = btree_impl::leafslotmax |
| Base B+ tree parameter: The number of key/data 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/data 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. | |
Specialized B+ tree template class implementing STL's multimap container.
Implements the STL multimap using a B+ tree. It can be used as a drop-in replacement for std::multimap. 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.
Most noteworthy difference to the default red-black implementation of std::multimap is that the B+ tree does not hold key and data pair together in memory. Instead each B+ tree node has two arrays of keys and data values. This design directly generates many problems in implementing the iterator's operator's which return value_type composition pairs.
Definition at line 60 of file btree_multimap.h.
| typedef _Alloc stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::allocator_type |
Fifth template parameter: STL allocator.
Definition at line 81 of file btree_multimap.h.
| typedef stx::btree<key_type, data_type, value_type, key_compare, traits, true, allocator_type, false> stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::btree_impl |
Implementation type of the btree_base.
Definition at line 100 of file btree_multimap.h.
| typedef btree_impl::const_iterator stx::btree_multimap< _Key, _Data, _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 152 of file btree_multimap.h.
| typedef btree_impl::const_reverse_iterator stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::const_reverse_iterator |
create constant reverse iterator by using STL magic
Definition at line 158 of file btree_multimap.h.
| typedef _Data stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::data_type |
Second template parameter: The data type associated with each key.
Stored in the B+ tree's leaves
Definition at line 71 of file btree_multimap.h.
| typedef btree_impl::iterator stx::btree_multimap< _Key, _Data, _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 148 of file btree_multimap.h.
| typedef _Compare stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::key_compare |
Third template parameter: Key comparison function object.
Definition at line 74 of file btree_multimap.h.
| typedef _Key stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::key_type |
First template parameter: The key type of the btree.
This is stored in inner nodes and leaves
Definition at line 67 of file btree_multimap.h.
| typedef btree_impl::reverse_iterator stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::reverse_iterator |
create mutable reverse iterator by using STL magic
Definition at line 155 of file btree_multimap.h.
| typedef btree_multimap<key_type, data_type, key_compare, traits, allocator_type> stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::self |
Typedef of our own type.
Definition at line 92 of file btree_multimap.h.
| typedef btree_impl::size_type stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::size_type |
Size type used to count keys.
Definition at line 106 of file btree_multimap.h.
| typedef _Traits stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::traits |
Fourth template parameter: Traits object used to define more parameters of the B+ tree.
Definition at line 78 of file btree_multimap.h.
| typedef btree_impl::tree_stats stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree_stats |
Small structure containing statistics about the tree.
Definition at line 109 of file btree_multimap.h.
| typedef btree_impl::value_compare stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::value_compare |
Function class comparing two value_type pairs.
Definition at line 103 of file btree_multimap.h.
| typedef std::pair<key_type, data_type> stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::value_type |
Construct the STL-required value_type as a composition pair of key and data types.
Definition at line 96 of file btree_multimap.h.
| stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::btree_multimap | ( | const allocator_type & | alloc = allocator_type() | ) | [inline, explicit] |
Default constructor initializing an empty B+ tree with the standard key comparison function.
Definition at line 171 of file btree_multimap.h.
| stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::btree_multimap | ( | 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 178 of file btree_multimap.h.
| stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::btree_multimap | ( | InputIterator | first, |
| InputIterator | last, | ||
| const allocator_type & | alloc = allocator_type() |
||
| ) | [inline] |
Constructor initializing a B+ tree with the range [first,last)
Definition at line 186 of file btree_multimap.h.
| stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::btree_multimap | ( | 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_multimap.h.
| stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::~btree_multimap | ( | ) | [inline] |
Frees up all used B+ tree memory pages.
Definition at line 202 of file btree_multimap.h.
| stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::btree_multimap | ( | const self & | other | ) | [inline] |
Copy constructor.
The newly initialized B+ tree object will contain a copy or all key/data pairs.
Definition at line 463 of file btree_multimap.h.
| iterator stx::btree_multimap< _Key, _Data, _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 251 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::begin(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| const_iterator stx::btree_multimap< _Key, _Data, _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 265 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::begin(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| void stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::bulk_load | ( | Iterator | first, |
| Iterator | last | ||
| ) | [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 521 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::bulk_load(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| void stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::clear | ( | ) | [inline] |
Frees all key/data pairs and all nodes of the tree.
Definition at line 241 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::clear(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| size_type stx::btree_multimap< _Key, _Data, _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.
Definition at line 359 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::count(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| void stx::btree_multimap< _Key, _Data, _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 and data_type must be integral types and contain no pointers or references.
Definition at line 593 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::dump(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| bool stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::empty | ( | ) | const [inline] |
Returns true if there is at least one key/data pair in the B+ tree.
Definition at line 315 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::empty(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| iterator stx::btree_multimap< _Key, _Data, _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 258 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::end(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| const_iterator stx::btree_multimap< _Key, _Data, _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 272 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::end(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| std::pair<iterator, iterator> stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::equal_range | ( | const key_type & | key | ) | [inline] |
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition at line 395 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::equal_range(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| std::pair<const_iterator, const_iterator> stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::equal_range | ( | const key_type & | key | ) | const [inline] |
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition at line 401 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::equal_range(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| size_type stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::erase | ( | const key_type & | key | ) | [inline] |
Erases all the key/data pairs associated with the given key.
This is implemented using erase_one() and thus not very efficient.
Definition at line 538 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| void stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::erase | ( | iterator | iter | ) | [inline] |
Erase the key/data pair referenced by the iterator.
Definition at line 544 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| void stx::btree_multimap< _Key, _Data, _Compare, _Traits, _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 552 of file btree_multimap.h.
| bool stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::erase_one | ( | const key_type & | key | ) | [inline] |
Erases one (the first) of the key/data pairs associated with the given key.
Definition at line 531 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::erase_one(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| bool stx::btree_multimap< _Key, _Data, _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 338 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::exists(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| iterator stx::btree_multimap< _Key, _Data, _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/data slot if found.
If unsuccessful it returns end().
Definition at line 345 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::find(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| const_iterator stx::btree_multimap< _Key, _Data, _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/data slot if found.
If unsuccessful it returns end().
Definition at line 352 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::find(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| allocator_type stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::get_allocator | ( | ) | const [inline] |
Return the base node allocator provided during construction.
Definition at line 232 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::get_allocator(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| const tree_stats& stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::get_stats | ( | ) | const [inline] |
Return a const reference to the current statistics.
Definition at line 328 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::get_stats(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| iterator stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::insert | ( | const value_type & | x | ) | [inline] |
Attempt to insert a key/data pair into the B+ tree.
As this tree allows duplicates insertion never fails.
Definition at line 473 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert2(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| iterator stx::btree_multimap< _Key, _Data, _Compare, _Traits, _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. As this tree allows duplicates insertion never fails.
Definition at line 481 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert2(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| iterator stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::insert | ( | iterator | hint, |
| const value_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 497 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert2(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| void stx::btree_multimap< _Key, _Data, _Compare, _Traits, _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 512 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| iterator stx::btree_multimap< _Key, _Data, _Compare, _Traits, _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. As this tree allows duplicates insertion never fails.
Definition at line 490 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert2(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| iterator stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::insert2 | ( | iterator | hint, |
| 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 504 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::insert2(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| key_compare stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::key_comp | ( | ) | const [inline] |
Constant access to the key comparison object sorting the B+ tree.
Definition at line 216 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::key_comp(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| iterator stx::btree_multimap< _Key, _Data, _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 366 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::lower_bound(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| const_iterator stx::btree_multimap< _Key, _Data, _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 374 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::lower_bound(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| size_type stx::btree_multimap< _Key, _Data, _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 322 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::max_size(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| bool stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::operator!= | ( | const self & | other | ) | const [inline] |
Inequality relation. Based on operator==.
Definition at line 418 of file btree_multimap.h.
References stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| bool stx::btree_multimap< _Key, _Data, _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 425 of file btree_multimap.h.
References stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| bool stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::operator<= | ( | const self & | other | ) | const [inline] |
Less-equal relation. Based on operator<.
Definition at line 437 of file btree_multimap.h.
References stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| self& stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::operator= | ( | const self & | other | ) | [inline] |
*** Fast Copy: Assign Operator and Copy Constructors
Assignment operator. All the key/data pairs are copied
Definition at line 452 of file btree_multimap.h.
References stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| bool stx::btree_multimap< _Key, _Data, _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 (both key and data) are considered equal. Beware of the random ordering of duplicate keys.
Definition at line 412 of file btree_multimap.h.
References stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| bool stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::operator> | ( | const self & | other | ) | const [inline] |
Greater relation. Based on operator<.
Definition at line 431 of file btree_multimap.h.
References stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| bool stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::operator>= | ( | const self & | other | ) | const [inline] |
Greater-equal relation. Based on operator<.
Definition at line 443 of file btree_multimap.h.
References stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| void stx::btree_multimap< _Key, _Data, _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 565 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::print(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| void stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::print_leaves | ( | std::ostream & | os | ) | const [inline] |
Print out only the leaves via the double linked list.
Definition at line 571 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::print_leaves(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| reverse_iterator stx::btree_multimap< _Key, _Data, _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 279 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::rbegin(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| const_reverse_iterator stx::btree_multimap< _Key, _Data, _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 293 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::rbegin(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| reverse_iterator stx::btree_multimap< _Key, _Data, _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 286 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::rend(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| const_reverse_iterator stx::btree_multimap< _Key, _Data, _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 300 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::rend(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| bool stx::btree_multimap< _Key, _Data, _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 and data_type must be integral types and contain no pointers or references. Returns true if the restore was successful.
Definition at line 602 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::restore(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| size_type stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::size | ( | ) | const [inline] |
Return the number of key/data pairs in the B+ tree.
Definition at line 309 of file btree_multimap.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::size(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| void stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::swap | ( | self & | from | ) | [inline] |
Fast swapping of two identical B+ tree objects.
Definition at line 207 of file btree_multimap.h.
References stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree.
| iterator stx::btree_multimap< _Key, _Data, _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 381 of file btree_multimap.h.
References stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::upper_bound().
| const_iterator stx::btree_multimap< _Key, _Data, _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 389 of file btree_multimap.h.
References stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::upper_bound().
| value_compare stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::value_comp | ( | ) | const [inline] |
Constant access to a constructed value_type comparison object.
required by the STL
Definition at line 223 of file btree_multimap.h.
References stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::value_comp().
| void stx::btree_multimap< _Key, _Data, _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 582 of file btree_multimap.h.
References stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates, _Alloc, _UsedAsSet >::verify().
const bool stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::allow_duplicates = btree_impl::allow_duplicates [static] |
Operational parameter: Allow duplicate keys in the btree.
Definition at line 141 of file btree_multimap.h.
const bool stx::btree_multimap< _Key, _Data, _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 138 of file btree_multimap.h.
const unsigned short stx::btree_multimap< _Key, _Data, _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 119 of file btree_multimap.h.
const unsigned short stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::leafslotmax = btree_impl::leafslotmax [static] |
Base B+ tree parameter: The number of key/data slots in each leaf.
Definition at line 115 of file btree_multimap.h.
const unsigned short stx::btree_multimap< _Key, _Data, _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 129 of file btree_multimap.h.
const unsigned short stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::minleafslots = btree_impl::minleafslots [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 124 of file btree_multimap.h.
const bool stx::btree_multimap< _Key, _Data, _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 133 of file btree_multimap.h.
btree_impl stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::tree [private] |
The contained implementation object.
Definition at line 164 of file btree_multimap.h.
Referenced by stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::begin(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::bulk_load(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::clear(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::count(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::dump(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::empty(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::end(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::equal_range(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::erase(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::erase_one(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::exists(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::find(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::get_allocator(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::get_stats(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::insert(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::insert2(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::key_comp(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::lower_bound(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::max_size(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::operator!=(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::operator<(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::operator<=(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::operator=(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::operator==(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::operator>(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::operator>=(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::print(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::print_leaves(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::rbegin(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::rend(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::restore(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::size(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::swap(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::upper_bound(), stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::value_comp(), and stx::btree_multimap< _Key, _Data, _Compare, _Traits, _Alloc >::verify().
1.7.6.1
