#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. | |
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. | |
| struct 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) |
| *** Fast Copy: Assign Operator and Copy Constructors | |
| 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 (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 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. | |
Private Types | |
| enum | result_flags_t { btree_ok = 0, btree_not_found = 1, btree_update_lastkey = 2, btree_fixmerge = 4 } |
| Result flags of recursive deletion. More... | |
| typedef btree_pair_to_value < value_type, pair_type > | pair_to_value_type |
| Using template specialization select the correct converter used by the iterators. | |
Private Member Functions | |
| bool | key_lessequal (const key_type &a, const key_type b) const |
| True if a <= b ? constructed from key_less(). | |
| bool | key_greater (const key_type &a, const key_type &b) const |
| True if a > b ? constructed from key_less(). | |
| bool | key_greaterequal (const key_type &a, const key_type b) const |
| True if a >= b ? constructed from key_less(). | |
| bool | key_equal (const key_type &a, const key_type &b) const |
| True if a == b ? constructed from key_less(). | |
| leaf_node * | allocate_leaf () |
| Allocate and initialize a leaf node. | |
| inner_node * | allocate_inner (unsigned short l) |
| Allocate and initialize an inner node. | |
| void | free_node (node *n) |
| Correctly free either inner or leaf node, destructs all contained key and value objects. | |
| void | clear_recursive (node *n) |
| Recursively free up nodes. | |
| template<typename node_type> | |
| int | find_lower (const node_type *n, const key_type &key) const |
| Searches for the first key in the node n less or equal to key. | |
| template<typename node_type> | |
| int | find_upper (const node_type *n, const key_type &key) const |
| Searches for the first key in the node n greater than key. | |
| struct node * | copy_recursive (const node *n) |
| Recursively copy nodes from another B+ tree object. | |
| std::pair< iterator, bool > | insert_start (const key_type &key, const data_type &value) |
| Start the insertion descent at the current root and handle root splits. | |
| std::pair< iterator, bool > | insert_descend (node *n, const key_type &key, const data_type &value, key_type *splitkey, node **splitnode) |
| Insert an item into the B+ tree. | |
| void | split_leaf_node (leaf_node *leaf, key_type *_newkey, node **_newleaf) |
| Split up a leaf node into two equally-filled sibling leaves. | |
| void | split_inner_node (inner_node *inner, key_type *_newkey, node **_newinner, unsigned int addslot) |
| Split up an inner node into two equally-filled sibling nodes. | |
| result_t | erase_one_descend (const key_type &key, node *curr, node *left, node *right, inner_node *leftparent, inner_node *rightparent, inner_node *parent, unsigned int parentslot) |
| Erase one (the first) key/data pair in the B+ tree matching key. | |
| result_t | merge_leaves (leaf_node *left, leaf_node *right, inner_node *parent) |
| Merge two leaf nodes. | |
| void | verify_node (const node *n, key_type *minkey, key_type *maxkey, tree_stats &vstats) const |
| Recursively descend down the tree and verify each node. | |
| void | verify_leaflinks () const |
| Verify the double linked list of leaves. | |
| void | dump_node (std::ostream &os, const node *n) const |
| Recursively descend down the tree and dump each node in a precise order. | |
| node * | restore_node (std::istream &is) |
| Read the dump image and construct a tree from the node order in the serialization. | |
Static Private Member Functions | |
| static result_t | merge_inner (inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot) |
| Merge two inner nodes. | |
| static result_t | shift_left_leaf (leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot) |
| Balance two leaf nodes. | |
| static void | shift_left_inner (inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot) |
| Balance two inner nodes. | |
| static void | shift_right_leaf (leaf_node *left, leaf_node *right, inner_node *parent, unsigned int parentslot) |
| Balance two leaf nodes. | |
| static void | shift_right_inner (inner_node *left, inner_node *right, inner_node *parent, unsigned int parentslot) |
| Balance two inner nodes. | |
| static void | print_node (std::ostream &os, const node *node, unsigned int depth=0, bool recursive=false) |
| Recursively descend down the tree and print out nodes. | |
Private Attributes | |
| node * | root |
| Pointer to the B+ tree's root node, either leaf or inner node. | |
| leaf_node * | headleaf |
| Pointer to first leaf in the double linked leaf chain. | |
| leaf_node * | tailleaf |
| Pointer to last leaf in the double linked leaf chain. | |
| tree_stats | stats |
| Other small statistics about the B+ tree. | |
| key_compare | key_less |
| Key comparison object. | |
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... | |
| class | const_reverse_iterator |
| STL-like read-only reverse iterator object for B+ tree items. More... | |
| struct | dump_header |
| struct | inner_node |
| Extended structure of a inner node in-memory. More... | |
| class | iterator |
| STL-like iterator object for B+ tree items. More... | |
| struct | leaf_node |
| Extended structure of a leaf node in memory. More... | |
| struct | node |
| The header structure of each node in-memory. More... | |
| struct | result_t |
| class | reverse_iterator |
| STL-like mutable reverse iterator object for B+ tree items. More... | |
| 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 137 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 btree_pair_to_value<value_type, pair_type> stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::pair_to_value_type [private] |
enum stx::btree::result_flags_t [private] |
Result flags of recursive deletion.
| btree_ok | Deletion successful and no fix-ups necessary. |
| btree_not_found | Deletion not successful because key was not found. |
| btree_update_lastkey |
Deletion successful, the last key was updated so parent slotkeys need updates.
|
| btree_fixmerge |
Deletion successful, children nodes were merged and the parent needs to remove the empty node.
|
| 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] |
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree | ( | InputIterator | first, | |
| InputIterator | last, | |||
| const key_compare & | kcf | |||
| ) | [inline] |
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::~btree | ( | ) | [inline] |
| stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::btree | ( | const btree_self & | other | ) | [inline] |
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::swap | ( | btree_self & | from | ) | [inline] |
| 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 1318 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, std::pair< key_type, data_type >, _Compare, _Traits, true >::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 1325 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().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::key_lessequal | ( | const key_type & | a, | |
| const key_type | b | |||
| ) | const [inline, private] |
True if a <= b ? constructed from key_less().
Definition at line 1334 of file btree.h.
Referenced by stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::find_lower(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::find_upper(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::verify_leaflinks(), and stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::verify_node().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::key_greater | ( | const key_type & | a, | |
| const key_type & | b | |||
| ) | const [inline, private] |
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::key_greaterequal | ( | const key_type & | a, | |
| const key_type | b | |||
| ) | const [inline, private] |
True if a >= b ? constructed from key_less().
Definition at line 1346 of file btree.h.
Referenced by stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::verify_node().
| bool stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::key_equal | ( | const key_type & | a, | |
| const key_type & | b | |||
| ) | const [inline, private] |
True if a == b ? constructed from key_less().
This requires the < relation to be a total order, otherwise the B+ tree cannot be sorted.
Definition at line 1353 of file btree.h.
Referenced by stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::count(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::erase_one_descend(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::exists(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::find(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::insert_descend(), and stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::verify_node().
| leaf_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::allocate_leaf | ( | ) | [inline, private] |
Allocate and initialize a leaf node.
Definition at line 1362 of file btree.h.
Referenced by stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::copy_recursive(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::insert_start(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::restore_node(), and stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::split_leaf_node().
| inner_node* stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::allocate_inner | ( | unsigned short | l | ) | [inline, private] |
Allocate and initialize an inner node.
Definition at line 1371 of file btree.h.
Referenced by stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::copy_recursive(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::insert_start(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::restore_node(), and stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::split_inner_node().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::free_node | ( | node * | n | ) | [inline, private] |
Correctly free either inner or leaf node, destructs all contained key and value objects.
Definition at line 1381 of file btree.h.
Referenced by stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::clear(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::clear_recursive(), and stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::erase_one_descend().
| 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 1397 of file btree.h.
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, std::pair< key_type, data_type >, _Compare, _Traits, true >::operator=(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::restore(), and stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::~btree().
| void stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::clear_recursive | ( | node * | n | ) | [inline, private] |
Recursively free up nodes.
Definition at line 1415 of file btree.h.
Referenced by stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::clear(), and stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::clear_recursive().
| 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 1443 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, std::pair< key_type, data_type >, _Compare, _Traits, true >::operator<(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::operator==(), and stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::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 1450 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, std::pair< key_type, data_type >, _Compare, _Traits, true >::find(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::lower_bound(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::operator<(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::operator==(), stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::rbegin(), and stx::btree< _Key, _Data, std::pair< key_type, data_type >, _Compare, _Traits, true >::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 1471 of file btree.h.
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 1478 of file btree.h.
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] |