#include <btree_set.h>
Public Types | |
| typedef _Key | key_type |
| First template parameter: The key type of the B+ tree. | |
| typedef _Compare | key_compare |
| Second template parameter: Key comparison function object. | |
| typedef _Traits | traits |
| Third template parameter: Traits object used to define more parameters of the B+ tree. | |
| typedef struct empty_struct | data_type |
| The empty data_type. | |
| typedef key_type | value_type |
| Construct the set value_type: the key_type. | |
| typedef btree_set< key_type, key_compare, traits > | self |
| Typedef of our own type. | |
| typedef stx::btree< key_type, data_type, value_type, key_compare, traits, false > | btree_impl |
| Implementation type of the btree_base. | |
| typedef btree_impl::value_compare | value_compare |
| Function class comparing two value_type keys. | |
| 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_set () | |
| Default constructor initializing an empty B+ tree with the standard key comparison function. | |
| btree_set (const key_compare &kcf) | |
| Constructor initializing an empty B+ tree with a special key comparison object. | |
| template<class InputIterator> | |
| btree_set (InputIterator first, InputIterator last) | |
| Constructor initializing a B+ tree with the range [first,last). | |
| template<class InputIterator> | |
| btree_set (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_set () | |
| 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. | |
| void | clear () |
| Frees all keys 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 keys in the B+ tree. | |
| bool | empty () const |
| Returns true if there is at least one key 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 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 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 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_set (const self &other) | |
| Copy constructor. | |
| std::pair< iterator, bool > | insert (const key_type &x) |
| Attempt to insert a key into the B+ tree. | |
| iterator | insert (iterator hint, const key_type &x) |
| Attempt to insert a key into the B+ tree. | |
| template<typename InputIterator> | |
| void | insert (InputIterator first, InputIterator last) |
| Attempt to insert the range [first,last) of iterators dereferencing to key_type into the B+ tree. | |
| bool | erase_one (const key_type &key) |
| Erases the key from the set. | |
| size_type | erase (const key_type &key) |
| Erases all the key/data pairs associated with the given key. | |
| void | erase (iterator iter) |
| Erase the keys referenced by the iterator. | |
| void | erase (iterator, iterator) |
| Erase all keys 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 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 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. | |
Classes | |
| struct | empty_struct |
| The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals. More... | |
Implements the STL set using a B+ tree. It can be used as a drop-in replacement for std::set. Not all asymptotic time requirements are met in theory. There is no allocator template parameter, instead the class has a traits class defining B+ tree properties like slots and self-verification.
It is somewhat inefficient to implement a set using a B+ tree, a plain B tree would hold fewer copies of the keys.
The set class is derived from the base implementation class btree by specifying an empty struct as data_type. All function are adapted to provide the inner class with placeholder objects. Most tricky to get right were the return type's of iterators which as value_type should be the same as key_type, and not a pair of key and dummy-struct. This is taken case of using some template magic in the btree class.
Definition at line 52 of file btree_set.h.
| typedef _Key stx::btree_set< _Key, _Compare, _Traits >::key_type |
First template parameter: The key type of the B+ tree.
This is stored in inner nodes and leaves
Definition at line 59 of file btree_set.h.
| typedef _Compare stx::btree_set< _Key, _Compare, _Traits >::key_compare |
Second template parameter: Key comparison function object.
Definition at line 62 of file btree_set.h.
| typedef _Traits stx::btree_set< _Key, _Compare, _Traits >::traits |
Third template parameter: Traits object used to define more parameters of the B+ tree.
Definition at line 66 of file btree_set.h.
typedef struct empty_struct stx::btree_set< _Key, _Compare, _Traits >::data_type [read] |
| typedef key_type stx::btree_set< _Key, _Compare, _Traits >::value_type |
| typedef btree_set<key_type, key_compare, traits> stx::btree_set< _Key, _Compare, _Traits >::self |
| typedef stx::btree<key_type, data_type, value_type, key_compare, traits, false> stx::btree_set< _Key, _Compare, _Traits >::btree_impl |
| typedef btree_impl::value_compare stx::btree_set< _Key, _Compare, _Traits >::value_compare |
| typedef btree_impl::size_type stx::btree_set< _Key, _Compare, _Traits >::size_type |
| typedef btree_impl::tree_stats stx::btree_set< _Key, _Compare, _Traits >::tree_stats |
| typedef btree_impl::iterator stx::btree_set< _Key, _Compare, _Traits >::iterator |
STL-like iterator object for B+ tree items.
The iterator points to a specific slot number in a leaf.
Definition at line 142 of file btree_set.h.
| typedef btree_impl::const_iterator stx::btree_set< _Key, _Compare, _Traits >::const_iterator |
STL-like iterator object for B+ tree items.
The iterator points to a specific slot number in a leaf.
Definition at line 146 of file btree_set.h.
| typedef btree_impl::reverse_iterator stx::btree_set< _Key, _Compare, _Traits >::reverse_iterator |
| typedef btree_impl::const_reverse_iterator stx::btree_set< _Key, _Compare, _Traits >::const_reverse_iterator |
| stx::btree_set< _Key, _Compare, _Traits >::btree_set | ( | ) | [inline] |
Default constructor initializing an empty B+ tree with the standard key comparison function.
Definition at line 165 of file btree_set.h.
| stx::btree_set< _Key, _Compare, _Traits >::btree_set | ( | const key_compare & | kcf | ) | [inline] |
Constructor initializing an empty B+ tree with a special key comparison object.
Definition at line 172 of file btree_set.h.
| stx::btree_set< _Key, _Compare, _Traits >::btree_set | ( | InputIterator | first, | |
| InputIterator | last | |||
| ) | [inline] |
Constructor initializing a B+ tree with the range [first,last).
Definition at line 179 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::insert().
| stx::btree_set< _Key, _Compare, _Traits >::btree_set | ( | 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 188 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::insert().
| stx::btree_set< _Key, _Compare, _Traits >::~btree_set | ( | ) | [inline] |
| stx::btree_set< _Key, _Compare, _Traits >::btree_set | ( | const self & | other | ) | [inline] |
Copy constructor.
The newly initialized B+ tree object will contain a copy of all keys.
Definition at line 445 of file btree_set.h.
| void stx::btree_set< _Key, _Compare, _Traits >::swap | ( | self & | from | ) | [inline] |
Fast swapping of two identical B+ tree objects.
Definition at line 200 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::tree.
| key_compare stx::btree_set< _Key, _Compare, _Traits >::key_comp | ( | ) | const [inline] |
Constant access to the key comparison object sorting the B+ tree.
Definition at line 209 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::key_comp(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| value_compare stx::btree_set< _Key, _Compare, _Traits >::value_comp | ( | ) | const [inline] |
Constant access to a constructed value_type comparison object.
required by the STL
Definition at line 216 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::value_comp().
| void stx::btree_set< _Key, _Compare, _Traits >::clear | ( | ) | [inline] |
Frees all keys and all nodes of the tree.
Definition at line 225 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::clear(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| iterator stx::btree_set< _Key, _Compare, _Traits >::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 235 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::begin(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| iterator stx::btree_set< _Key, _Compare, _Traits >::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 242 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| const_iterator stx::btree_set< _Key, _Compare, _Traits >::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 249 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::begin(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| const_iterator stx::btree_set< _Key, _Compare, _Traits >::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 256 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| reverse_iterator stx::btree_set< _Key, _Compare, _Traits >::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 263 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rbegin(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| reverse_iterator stx::btree_set< _Key, _Compare, _Traits >::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 270 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rend(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| const_reverse_iterator stx::btree_set< _Key, _Compare, _Traits >::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 277 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rbegin(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| const_reverse_iterator stx::btree_set< _Key, _Compare, _Traits >::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 284 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rend(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| size_type stx::btree_set< _Key, _Compare, _Traits >::size | ( | ) | const [inline] |
Return the number of keys in the B+ tree.
Definition at line 293 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::size(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| bool stx::btree_set< _Key, _Compare, _Traits >::empty | ( | ) | const [inline] |
Returns true if there is at least one key in the B+ tree.
Definition at line 299 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::empty(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| size_type stx::btree_set< _Key, _Compare, _Traits >::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 306 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::max_size(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| const tree_stats& stx::btree_set< _Key, _Compare, _Traits >::get_stats | ( | ) | const [inline] |
Return a const reference to the current statistics.
Definition at line 312 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::get_stats(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| bool stx::btree_set< _Key, _Compare, _Traits >::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 322 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::exists(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| iterator stx::btree_set< _Key, _Compare, _Traits >::find | ( | const key_type & | key | ) | [inline] |
Tries to locate a key in the B+ tree and returns an iterator to the key slot if found.
If unsuccessful it returns end().
Definition at line 329 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::find(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| const_iterator stx::btree_set< _Key, _Compare, _Traits >::find | ( | const key_type & | key | ) | const [inline] |
Tries to locate a key in the B+ tree and returns an constant iterator to the key slot if found.
If unsuccessful it returns end().
Definition at line 336 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::find(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| size_type stx::btree_set< _Key, _Compare, _Traits >::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.
As this is a unique set, count() returns either 0 or 1.
Definition at line 344 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::count(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| iterator stx::btree_set< _Key, _Compare, _Traits >::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 351 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::lower_bound(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| const_iterator stx::btree_set< _Key, _Compare, _Traits >::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 358 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::lower_bound(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| iterator stx::btree_set< _Key, _Compare, _Traits >::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 365 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::upper_bound().
| const_iterator stx::btree_set< _Key, _Compare, _Traits >::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 372 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::upper_bound().
| std::pair<iterator, iterator> stx::btree_set< _Key, _Compare, _Traits >::equal_range | ( | const key_type & | key | ) | [inline] |
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition at line 378 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::equal_range(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| std::pair<const_iterator, const_iterator> stx::btree_set< _Key, _Compare, _Traits >::equal_range | ( | const key_type & | key | ) | const [inline] |
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition at line 384 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::equal_range(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| bool stx::btree_set< _Key, _Compare, _Traits >::operator== | ( | const self & | other | ) | const [inline] |
Equality relation of B+ trees of the same type.
B+ trees of the same size and equal elements are considered equal.
Definition at line 394 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::tree.
| bool stx::btree_set< _Key, _Compare, _Traits >::operator!= | ( | const self & | other | ) | const [inline] |
Inequality relation. Based on operator==.
Definition at line 400 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::tree.
| bool stx::btree_set< _Key, _Compare, _Traits >::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 407 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::tree.
| bool stx::btree_set< _Key, _Compare, _Traits >::operator> | ( | const self & | other | ) | const [inline] |
Greater relation. Based on operator<.
Definition at line 413 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::tree.
| bool stx::btree_set< _Key, _Compare, _Traits >::operator<= | ( | const self & | other | ) | const [inline] |
Less-equal relation. Based on operator<.
Definition at line 419 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::tree.
| bool stx::btree_set< _Key, _Compare, _Traits >::operator>= | ( | const self & | other | ) | const [inline] |
Greater-equal relation. Based on operator<.
Definition at line 425 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::tree.
| self& stx::btree_set< _Key, _Compare, _Traits >::operator= | ( | const self & | other | ) | [inline] |
*** Fast Copy: Assign Operator and Copy Constructors
Assignment operator. All the keys are copied
Definition at line 434 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::tree.
| std::pair<iterator, bool> stx::btree_set< _Key, _Compare, _Traits >::insert | ( | const key_type & | x | ) | [inline] |
Attempt to insert a key into the B+ tree.
The insert will fail if it is already present.
Definition at line 455 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert2(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::btree_set(), and stx::btree_set< _Key, _Compare, _Traits >::insert().
| iterator stx::btree_set< _Key, _Compare, _Traits >::insert | ( | iterator | hint, | |
| const key_type & | x | |||
| ) | [inline] |
Attempt to insert a key into the B+ tree.
The iterator hint is currently ignored by the B+ tree insertion routine.
Definition at line 462 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert2(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| void stx::btree_set< _Key, _Compare, _Traits >::insert | ( | InputIterator | first, | |
| InputIterator | last | |||
| ) | [inline] |
Attempt to insert the range [first,last) of iterators dereferencing to key_type into the B+ tree.
Each key/data pair is inserted individually.
Definition at line 470 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::insert().
| bool stx::btree_set< _Key, _Compare, _Traits >::erase_one | ( | const key_type & | key | ) | [inline] |
Erases the key from the set.
As this is a unique set, there is no difference to erase().
Definition at line 485 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase_one(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| size_type stx::btree_set< _Key, _Compare, _Traits >::erase | ( | const key_type & | key | ) | [inline] |
Erases all the key/data pairs associated with the given key.
Definition at line 491 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| void stx::btree_set< _Key, _Compare, _Traits >::erase | ( | iterator | iter | ) | [inline] |
| void stx::btree_set< _Key, _Compare, _Traits >::erase | ( | iterator | , | |
| iterator | ||||
| ) | [inline] |
Erase all keys in the range [first,last).
This function is currently not implemented by the B+ Tree.
Definition at line 507 of file btree_set.h.
| void stx::btree_set< _Key, _Compare, _Traits >::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 520 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::print(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| void stx::btree_set< _Key, _Compare, _Traits >::print_leaves | ( | std::ostream & | os | ) | const [inline] |
Print out only the leaves via the double linked list.
Definition at line 526 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::print_leaves(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| void stx::btree_set< _Key, _Compare, _Traits >::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 538 of file btree_set.h.
References stx::btree_set< _Key, _Compare, _Traits >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::verify().
| void stx::btree_set< _Key, _Compare, _Traits >::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 must be an integral type and contain no pointers or references.
Definition at line 549 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::dump(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
| bool stx::btree_set< _Key, _Compare, _Traits >::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 must be an integral type and contain no pointers or references. Returns true if the restore was successful.
Definition at line 558 of file btree_set.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::restore(), and stx::btree_set< _Key, _Compare, _Traits >::tree.
const unsigned short stx::btree_set< _Key, _Compare, _Traits >::leafslotmax = btree_impl::leafslotmax [static] |
Base B+ tree parameter: The number of key slots in each leaf.
Definition at line 109 of file btree_set.h.
const unsigned short stx::btree_set< _Key, _Compare, _Traits >::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 113 of file btree_set.h.
const unsigned short stx::btree_set< _Key, _Compare, _Traits >::minleafslots = btree_impl::minleafslots [static] |
Computed B+ tree parameter: The minimum number of key slots used in a leaf.
If fewer slots are used, the leaf will be merged or slots shifted from it's siblings.
Definition at line 118 of file btree_set.h.
const unsigned short stx::btree_set< _Key, _Compare, _Traits >::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 123 of file btree_set.h.
const bool stx::btree_set< _Key, _Compare, _Traits >::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 127 of file btree_set.h.
const bool stx::btree_set< _Key, _Compare, _Traits >::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 132 of file btree_set.h.
const bool stx::btree_set< _Key, _Compare, _Traits >::allow_duplicates = btree_impl::allow_duplicates [static] |
Operational parameter: Allow duplicate keys in the btree.
Definition at line 135 of file btree_set.h.
btree_impl stx::btree_set< _Key, _Compare, _Traits >::tree [private] |
The contained implementation object.
Definition at line 158 of file btree_set.h.
Referenced by stx::btree_set< _Key, _Compare, _Traits >::begin(), stx::btree_set< _Key, _Compare, _Traits >::clear(), stx::btree_set< _Key, _Compare, _Traits >::count(), stx::btree_set< _Key, _Compare, _Traits >::dump(), stx::btree_set< _Key, _Compare, _Traits >::empty(), stx::btree_set< _Key, _Compare, _Traits >::end(), stx::btree_set< _Key, _Compare, _Traits >::equal_range(), stx::btree_set< _Key, _Compare, _Traits >::erase(), stx::btree_set< _Key, _Compare, _Traits >::erase_one(), stx::btree_set< _Key, _Compare, _Traits >::exists(), stx::btree_set< _Key, _Compare, _Traits >::find(), stx::btree_set< _Key, _Compare, _Traits >::get_stats(), stx::btree_set< _Key, _Compare, _Traits >::insert(), stx::btree_set< _Key, _Compare, _Traits >::key_comp(), stx::btree_set< _Key, _Compare, _Traits >::lower_bound(), stx::btree_set< _Key, _Compare, _Traits >::max_size(), stx::btree_set< _Key, _Compare, _Traits >::operator!=(), stx::btree_set< _Key, _Compare, _Traits >::operator<(), stx::btree_set< _Key, _Compare, _Traits >::operator<=(), stx::btree_set< _Key, _Compare, _Traits >::operator=(), stx::btree_set< _Key, _Compare, _Traits >::operator==(), stx::btree_set< _Key, _Compare, _Traits >::operator>(), stx::btree_set< _Key, _Compare, _Traits >::operator>=(), stx::btree_set< _Key, _Compare, _Traits >::print(), stx::btree_set< _Key, _Compare, _Traits >::print_leaves(), stx::btree_set< _Key, _Compare, _Traits >::rbegin(), stx::btree_set< _Key, _Compare, _Traits >::rend(), stx::btree_set< _Key, _Compare, _Traits >::restore(), stx::btree_set< _Key, _Compare, _Traits >::size(), stx::btree_set< _Key, _Compare, _Traits >::swap(), stx::btree_set< _Key, _Compare, _Traits >::upper_bound(), stx::btree_set< _Key, _Compare, _Traits >::value_comp(), and stx::btree_set< _Key, _Compare, _Traits >::verify().
1.5.6