#include <btree.h>
Public Types | |
| typedef _Key | key_type |
| First template parameter: The key type of the B+ tree. | |
| typedef _Data | data_type |
| Second template parameter: The data type associated with each key. | |
| typedef _Value | value_type |
| Third template parameter: Composition pair of key and data types, this is required by the STL standard. | |
| typedef _Compare | key_compare |
| Fourth template parameter: Key comparison function object. | |
| typedef _Traits | traits |
| Fifth template parameter: Traits object used to define more parameters of the B+ tree. | |
| typedef btree< key_type, data_type, value_type, key_compare, traits, allow_duplicates > | btree_self |
| Typedef of our own type. | |
| typedef size_t | size_type |
| Size type used to count keys. | |
| typedef std::pair< key_type, data_type > | pair_type |
| The pair of key_type and data_type, this may be different from value_type. | |
| typedef std::reverse_iterator< iterator > | reverse_iterator |
| create mutable reverse iterator by using STL magic | |
| typedef std::reverse_iterator< const_iterator > | const_reverse_iterator |
| create constant reverse iterator by using STL magic | |
Public Member Functions | |
| btree () | |
| Default constructor initializing an empty B+ tree with the standard key comparison function. | |
| btree (const key_compare &kcf) | |
| Constructor initializing an empty B+ tree with a special key comparison object. | |
| template<class InputIterator> | |
| btree (InputIterator first, InputIterator last) | |
| Constructor initializing a B+ tree with the range [first,last). | |
| template<class InputIterator> | |
| btree (InputIterator first, InputIterator last, const key_compare &kcf) | |
| Constructor initializing a B+ tree with the range [first,last) and a special key comparison object. | |
| ~btree () | |
| Frees up all used B+ tree memory pages. | |
| void | swap (btree_self &from) |
| Fast swapping of two identical B+ tree objects. | |
| key_compare | key_comp () const |
| Constant access to the key comparison object sorting the B+ tree. | |
| value_compare | value_comp () const |
| Constant access to a constructed value_type comparison object. | |
| 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. | |
| 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 key less or equal to the parameter. | |
| const_iterator | lower_bound (const key_type &key) const |
| Searches the B+ tree and returns an constant iterator to the first key less or equal to the parameter. | |
| iterator | upper_bound (const key_type &key) |
| Searches the B+ tree and returns an iterator to the first key greater than the parameter. | |
| const_iterator | upper_bound (const key_type &key) const |
| Searches the B+ tree and returns an constant iterator to the first key greater than the parameter. | |
| 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 btree_self &other) const |
| Equality relation of B+ trees of the same type. | |
| bool | operator!= (const btree_self &other) const |
| Inequality relation. Based on operator==. | |
| bool | operator< (const btree_self &other) const |
| Total ordering relation of B+ trees of the same type. | |
| bool | operator> (const btree_self &other) const |
| Greater relation. Based on operator<. | |
| bool | operator<= (const btree_self &other) const |
| Less-equal relation. Based on operator<. | |
| bool | operator>= (const btree_self &other) const |
| Greater-equal relation. Based on operator<. | |
| btree_self & | operator= (const btree_self &other) |
| Assignment operator. All the key/data pairs are copied. | |
| btree (const btree_self &other) | |
| Copy constructor. | |
| std::pair< iterator, bool > | insert (const pair_type &x) |
| Attempt to insert a key/data pair into the B+ tree. | |
| std::pair< iterator, bool > | insert (const key_type &key, const data_type &data) |
| Attempt to insert a key/data pair into the B+ tree. | |
| std::pair< iterator, bool > | insert2 (const key_type &key, const data_type &data) |
| Attempt to insert a key/data pair into the B+ tree. | |
| iterator | insert (iterator, const pair_type &x) |
| Attempt to insert a key/data pair into the B+ tree. | |
| iterator | insert2 (iterator, const key_type &key, const data_type &data) |
| Attempt to insert a key/data pair into the B+ tree. | |
| template<typename InputIterator> | |
| void | insert (InputIterator first, InputIterator last) |
| Attempt to insert the range [first,last) of value_type pairs into the B+ tree. | |
| bool | erase_one (const key_type &key) |
| Erases one (the first) of the key/data pairs associated with the given key. | |
| size_type | erase (const key_type &key) |
| Erases all the key/data pairs associated with the given key. | |
| void | erase (iterator iter) |
| Erase the key/data pair referenced by the iterator. | |
| void | erase (iterator, iterator) |
| Erase all key/data pairs in the range [first,last). | |
| void | print () const |
| Print out the B+ tree structure with keys onto std::cout. | |
| void | print_leaves () const |
| Print out only the leaves via the double linked list. | |
| void | verify () const |
| Run a thorough verification of all B+ tree invariants. | |
| void | dump (std::ostream &os) const |
| Dump the contents of the B+ tree out onto an ostream as a binary image. | |
| bool | restore (std::istream &is) |
| Restore a binary image of a dumped B+ tree from an istream. | |
Static Public Attributes | |
| static const bool | allow_duplicates = _Duplicates |
| Sixth template parameter: Allow duplicate keys in the B+ tree. | |
| static const unsigned short | leafslotmax = traits::leafslots |
| Base B+ tree parameter: The number of key/data slots in each leaf. | |
| static const unsigned short | innerslotmax = traits::innerslots |
| Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in each leaf. | |
| static const unsigned short | minleafslots = (leafslotmax / 2) |
| Computed B+ tree parameter: The minimum number of key/data slots used in a leaf. | |
| static const unsigned short | mininnerslots = (innerslotmax / 2) |
| Computed B+ tree parameter: The minimum number of key slots used in an inner node. | |
| static const bool | selfverify = traits::selfverify |
| Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation. | |
| static const bool | debug = traits::debug |
| Debug parameter: Prints out lots of debug information about how the algorithms change the tree. | |
Classes | |
| struct | btree_pair_to_value |
| struct | btree_pair_to_value< value_type, value_type > |
| class | const_iterator |
| STL-like read-only iterator object for B+ tree items. More... | |
| struct | dump_header |
| struct | inner_node |
| Extended structure of a inner node in-memory. | |
| class | iterator |
| STL-like iterator object for B+ tree items. More... | |
| struct | leaf_node |
| Extended structure of a leaf node in memory. | |
| struct | node |
| The header structure of each node in-memory. | |
| struct | result_t |
| struct | tree_stats |
| A small struct containing basic statistics about the B+ tree. More... | |
| class | value_compare |
| Function class to compare value_type objects. Required by the STL. More... | |
The base implementation of a memory B+ tree. It is based on the implementation in Cormen's Introduction into Algorithms, Jan Jannink's paper and other algorithm resources. Almost all STL-required function calls are implemented. The asymptotic time requirements of the STL are not always fulfilled in theory, however in practice this B+ tree performs better than a red-black tree by using more memory. The insertion function splits the nodes on the recursion unroll. Erase is largely based on Jannink's ideas.
This class is specialized into btree_set, btree_multiset, btree_map and btree_multimap using default template parameters and facade functions.
Definition at line 130 of file btree.h.
| typedef _Key stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::key_type |
| typedef _Data stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::data_type |
| typedef _Value stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::value_type |
| typedef _Compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::key_compare |
| typedef _Traits stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::traits |
| typedef btree<key_type, data_type, value_type, key_compare, traits, allow_duplicates> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree_self |
| typedef size_t stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::size_type |
| typedef std::pair<key_type, data_type> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::pair_type |
| typedef std::reverse_iterator<iterator> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::reverse_iterator |
| typedef std::reverse_iterator<const_iterator> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::const_reverse_iterator |
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree | ( | ) | [inline] |
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree | ( | const key_compare & | kcf | ) | [inline] |
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree | ( | InputIterator | first, | |
| InputIterator | last | |||
| ) | [inline] |
Constructor initializing a B+ tree with the range [first,last).
Definition at line 796 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert().
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree | ( | InputIterator | first, | |
| InputIterator | last, | |||
| const key_compare & | kcf | |||
| ) | [inline] |
Constructor initializing a B+ tree with the range [first,last) and a special key comparison object.
Definition at line 805 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert().
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::~btree | ( | ) | [inline] |
Frees up all used B+ tree memory pages.
Definition at line 813 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::clear().
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree | ( | const btree_self & | other | ) | [inline] |
Copy constructor.
The newly initialized B+ tree object will contain a copy of all key/data pairs.
Definition at line 1422 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::tree_stats::innernodes, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::tree_stats::leaves, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::root, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::selfverify, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::size(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::verify().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::swap | ( | btree_self & | from | ) | [inline] |
Fast swapping of two identical B+ tree objects.
Definition at line 819 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::headleaf, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::key_less, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::root, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::stats, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::tailleaf.
| key_compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::key_comp | ( | ) | const [inline] |
Constant access to the key comparison object sorting the B+ tree.
Definition at line 855 of file btree.h.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::key_comp(), stx::btree_multiset< _Key, _Compare, _Traits >::key_comp(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::key_comp(), stx::btree_map< _Key, _Data, _Compare, _Traits >::key_comp(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator=().
| value_compare stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::value_comp | ( | ) | const [inline] |
Constant access to a constructed value_type comparison object.
Required by the STL
Definition at line 862 of file btree.h.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::value_comp(), stx::btree_multiset< _Key, _Compare, _Traits >::value_comp(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::value_comp(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::value_comp().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::clear | ( | ) | [inline] |
Frees all key/data pairs and all nodes of the tree.
Definition at line 934 of file btree.h.
References BTREE_ASSERT, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::tree_stats::itemcount.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::clear(), stx::btree_multiset< _Key, _Compare, _Traits >::clear(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::clear(), stx::btree_map< _Key, _Data, _Compare, _Traits >::clear(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator=(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::~btree().
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 980 of file btree.h.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::begin(), stx::btree_multiset< _Key, _Compare, _Traits >::begin(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::begin(), stx::btree_map< _Key, _Data, _Compare, _Traits >::begin(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator<(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator==(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rend().
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 987 of file btree.h.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::end(), stx::btree_multiset< _Key, _Compare, _Traits >::end(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::end(), stx::btree_map< _Key, _Data, _Compare, _Traits >::end(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::find(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::lower_bound(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator<(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator==(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rbegin(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::upper_bound().
| const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::begin | ( | ) | const [inline] |
| const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end | ( | ) | const [inline] |
| reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 1008 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end().
Referenced by stx::btree_set< _Key, _Compare, _Traits >::rbegin(), stx::btree_multiset< _Key, _Compare, _Traits >::rbegin(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::rbegin(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::rbegin().
| reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 1015 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::begin().
Referenced by stx::btree_set< _Key, _Compare, _Traits >::rend(), stx::btree_multiset< _Key, _Compare, _Traits >::rend(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::rend(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::rend().
| const_reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 1022 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end().
| const_reverse_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 1029 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::begin().
| size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::size | ( | ) | const [inline] |
Return the number of key/data pairs in the B+ tree.
Definition at line 1135 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::tree_stats::itemcount.
Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::empty(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase_one(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator=(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator==(), stx::btree_set< _Key, _Compare, _Traits >::size(), stx::btree_multiset< _Key, _Compare, _Traits >::size(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::size(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::size().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::empty | ( | ) | const [inline] |
Returns true if there is at least one key/data pair in the B+ tree.
Definition at line 1141 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::size().
Referenced by stx::btree_set< _Key, _Compare, _Traits >::empty(), stx::btree_multiset< _Key, _Compare, _Traits >::empty(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::empty(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::empty().
| size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 1148 of file btree.h.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::max_size(), stx::btree_multiset< _Key, _Compare, _Traits >::max_size(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::max_size(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::max_size().
| struct tree_stats& stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::get_stats | ( | ) | const [inline, read] |
Return a const reference to the current statistics.
Definition at line 1154 of file btree.h.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::get_stats(), stx::btree_multiset< _Key, _Compare, _Traits >::get_stats(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::get_stats(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::get_stats().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 1164 of file btree.h.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::exists(), stx::btree_multiset< _Key, _Compare, _Traits >::exists(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::exists(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::exists().
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 1186 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end().
Referenced by stx::btree_set< _Key, _Compare, _Traits >::find(), stx::btree_multiset< _Key, _Compare, _Traits >::find(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::find(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::find().
| const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 1207 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end().
| size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 1228 of file btree.h.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::count(), stx::btree_multiset< _Key, _Compare, _Traits >::count(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::count(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::count().
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::lower_bound | ( | const key_type & | key | ) | [inline] |
Searches the B+ tree and returns an iterator to the first key less or equal to the parameter.
If unsuccessful it returns end().
Definition at line 1261 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end().
Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::equal_range(), stx::btree_set< _Key, _Compare, _Traits >::lower_bound(), stx::btree_multiset< _Key, _Compare, _Traits >::lower_bound(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::lower_bound(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::lower_bound().
| const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::lower_bound | ( | const key_type & | key | ) | const [inline] |
Searches the B+ tree and returns an constant iterator to the first key less or equal to the parameter.
If unsuccessful it returns end().
Definition at line 1282 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end().
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::upper_bound | ( | const key_type & | key | ) | [inline] |
Searches the B+ tree and returns an iterator to the first key greater than the parameter.
If unsuccessful it returns end().
Definition at line 1303 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end().
Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::equal_range(), stx::btree_set< _Key, _Compare, _Traits >::upper_bound(), stx::btree_multiset< _Key, _Compare, _Traits >::upper_bound(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::upper_bound(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::upper_bound().
| const_iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::upper_bound | ( | const key_type & | key | ) | const [inline] |
Searches the B+ tree and returns an constant iterator to the first key greater than the parameter.
If unsuccessful it returns end().
Definition at line 1324 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end().
| std::pair<iterator, iterator> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::equal_range | ( | const key_type & | key | ) | [inline] |
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition at line 1344 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::lower_bound(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::upper_bound().
Referenced by stx::btree_set< _Key, _Compare, _Traits >::equal_range(), stx::btree_multiset< _Key, _Compare, _Traits >::equal_range(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::equal_range(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::equal_range().
| std::pair<const_iterator, const_iterator> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::equal_range | ( | const key_type & | key | ) | const [inline] |
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition at line 1350 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::lower_bound(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::upper_bound().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator== | ( | const btree_self & | other | ) | const [inline] |
Equality relation of B+ trees of the same type.
B+ trees of the same size and equal elements (both key and data) are considered equal. Beware of the random ordering of duplicate keys.
Definition at line 1361 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::begin(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::size().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator!= | ( | const btree_self & | other | ) | const [inline] |
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator< | ( | const btree_self & | other | ) | const [inline] |
Total ordering relation of B+ trees of the same type.
It uses std::lexicographical_compare() for the actual comparison of elements.
Definition at line 1374 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::begin(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator> | ( | const btree_self & | other | ) | const [inline] |
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator<= | ( | const btree_self & | other | ) | const [inline] |
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator>= | ( | const btree_self & | other | ) | const [inline] |
| btree_self& stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator= | ( | const btree_self & | other | ) | [inline] |
Assignment operator. All the key/data pairs are copied.
Definition at line 1401 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::clear(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::tree_stats::innernodes, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::key_comp(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::tree_stats::leaves, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::root, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::selfverify, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::size(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::stats, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::verify().
| std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert | ( | const pair_type & | x | ) | [inline] |
Attempt to insert a key/data pair into the B+ tree.
If the tree does not allow duplicate keys, then the insert may fail if it is already present.
Definition at line 1485 of file btree.h.
Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::insert(), stx::btree_map< _Key, _Data, _Compare, _Traits >::insert(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert().
| std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert | ( | const key_type & | key, | |
| const data_type & | data | |||
| ) | [inline] |
| std::pair<iterator, bool> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert2 | ( | const key_type & | key, | |
| const data_type & | data | |||
| ) | [inline] |
Attempt to insert a key/data pair into the B+ tree.
This function is the same as the other insert, however if key_type == data_type then the non-template function cannot be called. If the tree does not allow duplicate keys, then the insert may fail if it is already present.
Definition at line 1503 of file btree.h.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::insert(), stx::btree_multiset< _Key, _Compare, _Traits >::insert(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::insert(), stx::btree_map< _Key, _Data, _Compare, _Traits >::insert(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::insert2(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::insert2().
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert | ( | iterator | , | |
| const pair_type & | x | |||
| ) | [inline] |
| iterator stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert2 | ( | iterator | , | |
| const key_type & | key, | |||
| const data_type & | data | |||
| ) | [inline] |
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 1525 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase_one | ( | const key_type & | key | ) | [inline] |
Erases one (the first) of the key/data pairs associated with the given key.
Definition at line 1865 of file btree.h.
References BTREE_PRINT, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::debug, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::tree_stats::itemcount, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::print(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::selfverify, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::size(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::verify().
Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase(), stx::btree_set< _Key, _Compare, _Traits >::erase_one(), stx::btree_multiset< _Key, _Compare, _Traits >::erase_one(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::erase_one(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::erase_one().
| size_type stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase | ( | const key_type & | key | ) | [inline] |
Erases all the key/data pairs associated with the given key.
This is implemented using erase_one().
Definition at line 1884 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::allow_duplicates, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase_one().
Referenced by stx::btree_set< _Key, _Compare, _Traits >::erase(), stx::btree_multiset< _Key, _Compare, _Traits >::erase(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::erase(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::erase().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase | ( | iterator | iter | ) | [inline] |
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase | ( | iterator | , | |
| iterator | ||||
| ) | [inline] |
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::print | ( | ) | const [inline] |
Print out the B+ tree structure with keys onto std::cout.
This function requires that the header is compiled with BTREE_PRINT and that key_type is printable via std::ostream.
Definition at line 2484 of file btree.h.
Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase_one(), stx::btree_set< _Key, _Compare, _Traits >::print(), stx::btree_multiset< _Key, _Compare, _Traits >::print(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::print(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::print().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::print_leaves | ( | ) | const [inline] |
Print out only the leaves via the double linked list.
Definition at line 2490 of file btree.h.
References BTREE_PRINT.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::print_leaves(), stx::btree_multiset< _Key, _Compare, _Traits >::print_leaves(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::print_leaves(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::print_leaves().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::verify | ( | ) | const [inline] |
Run a thorough verification of all B+ tree invariants.
The program aborts via assert() if something is wrong.
Definition at line 2556 of file btree.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::tree_stats::innernodes, stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::tree_stats::itemcount, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::tree_stats::leaves.
Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase_one(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator=(), stx::btree_set< _Key, _Compare, _Traits >::verify(), stx::btree_multiset< _Key, _Compare, _Traits >::verify(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::verify(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::verify().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 2770 of file btree.h.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::dump(), stx::btree_multiset< _Key, _Compare, _Traits >::dump(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::dump(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::dump().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::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 2786 of file btree.h.
References BTREE_PRINT.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::restore(), stx::btree_multiset< _Key, _Compare, _Traits >::restore(), stx::btree_multimap< _Key, _Data, _Compare, _Traits >::restore(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::restore().
const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::allow_duplicates = _Duplicates [static] |
Sixth template parameter: Allow duplicate keys in the B+ tree.
Used to implement multiset and multimap.
Definition at line 158 of file btree.h.
Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase().
const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::leafslotmax = traits::leafslots [static] |
const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::innerslotmax = traits::innerslots [static] |
const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::minleafslots = (leafslotmax / 2) [static] |
const unsigned short stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::mininnerslots = (innerslotmax / 2) [static] |
const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::selfverify = traits::selfverify [static] |
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation.
Definition at line 195 of file btree.h.
Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree(), stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase_one(), and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::operator=().
const bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::debug = traits::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_PRINT and the key type must be std::ostream printable.
Definition at line 200 of file btree.h.
Referenced by stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase_one().
1.5.2