#include <btree_multiset.h>
Public Types | |
| typedef _Key | key_type |
| First template parameter: The key type of the btree. | |
| 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 empty_struct | data_type |
| The empty data_type. | |
| typedef key_type | value_type |
| Construct the set value_type: the key_type. | |
| typedef btree_multiset< key_type, key_compare, traits > | self |
| Typedef of our own type. | |
| typedef stx::btree< key_type, data_type, value_type, key_compare, traits, true > | 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_multiset () | |
| Default constructor initializing an empty B+ tree with the standard key comparison function. | |
| btree_multiset (const key_compare &kcf) | |
| Constructor initializing an empty B+ tree with a special key comparison object. | |
| template<class InputIterator> | |
| btree_multiset (InputIterator first, InputIterator last) | |
| Constructor initializing a B+ tree with the range [first,last). | |
| template<class InputIterator> | |
| btree_multiset (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_multiset () | |
| 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) |
| Assignment operator. All the keys are copied. | |
| btree_multiset (const self &other) | |
| Copy constructor. | |
| iterator | 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 key_type into the B+ tree. | |
| bool | erase_one (const key_type &key) |
| Erases one (the first) entry of the given key. | |
| size_type | erase (const key_type &key) |
| Erases all the entries of the given key. | |
| void | erase (iterator iter) |
| Erase the key referenced by the iterator. | |
| void | erase (iterator, iterator) |
| Erase all keys 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 unsigned short | leafslotmax = btree_impl::leafslotmax |
| Base B+ tree parameter: The number of key/data slots in each leaf. | |
| static const unsigned short | innerslotmax = btree_impl::innerslotmax |
| Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in each leaf. | |
| static const unsigned short | minleafslots = btree_impl::minleafslots |
| Computed B+ tree parameter: The minimum number of key 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. | |
Classes | |
| struct | empty_struct |
Implements the STL multiset using a B+ tree. It can be used as a drop-in replacement for std::multiset. 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 multiset 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 53 of file btree_multiset.h.
| typedef _Key stx::btree_multiset< _Key, _Compare, _Traits >::key_type |
First template parameter: The key type of the btree.
This is stored in inner nodes and leaves
Definition at line 60 of file btree_multiset.h.
| typedef _Compare stx::btree_multiset< _Key, _Compare, _Traits >::key_compare |
Second template parameter: Key comparison function object.
Definition at line 63 of file btree_multiset.h.
| typedef _Traits stx::btree_multiset< _Key, _Compare, _Traits >::traits |
Third template parameter: Traits object used to define more parameters of the B+ tree.
Definition at line 67 of file btree_multiset.h.
typedef struct empty_struct stx::btree_multiset< _Key, _Compare, _Traits >::data_type [read] |
| typedef key_type stx::btree_multiset< _Key, _Compare, _Traits >::value_type |
| typedef btree_multiset<key_type, key_compare, traits> stx::btree_multiset< _Key, _Compare, _Traits >::self |
| typedef stx::btree<key_type, data_type, value_type, key_compare, traits, true> stx::btree_multiset< _Key, _Compare, _Traits >::btree_impl |
| typedef btree_impl::value_compare stx::btree_multiset< _Key, _Compare, _Traits >::value_compare |
| typedef btree_impl::size_type stx::btree_multiset< _Key, _Compare, _Traits >::size_type |
| typedef btree_impl::tree_stats stx::btree_multiset< _Key, _Compare, _Traits >::tree_stats |
Small structure containing statistics about the tree.
Definition at line 99 of file btree_multiset.h.
| typedef btree_impl::iterator stx::btree_multiset< _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 138 of file btree_multiset.h.
| typedef btree_impl::const_iterator stx::btree_multiset< _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 142 of file btree_multiset.h.
| typedef btree_impl::reverse_iterator stx::btree_multiset< _Key, _Compare, _Traits >::reverse_iterator |
| typedef btree_impl::const_reverse_iterator stx::btree_multiset< _Key, _Compare, _Traits >::const_reverse_iterator |
create constant reverse iterator by using STL magic
Definition at line 148 of file btree_multiset.h.
| stx::btree_multiset< _Key, _Compare, _Traits >::btree_multiset | ( | ) | [inline] |
Default constructor initializing an empty B+ tree with the standard key comparison function.
Definition at line 161 of file btree_multiset.h.
| stx::btree_multiset< _Key, _Compare, _Traits >::btree_multiset | ( | const key_compare & | kcf | ) | [inline] |
Constructor initializing an empty B+ tree with a special key comparison object.
Definition at line 168 of file btree_multiset.h.
| stx::btree_multiset< _Key, _Compare, _Traits >::btree_multiset | ( | InputIterator | first, | |
| InputIterator | last | |||
| ) | [inline] |
Constructor initializing a B+ tree with the range [first,last).
Definition at line 175 of file btree_multiset.h.
References stx::btree_multiset< _Key, _Compare, _Traits >::insert().
| stx::btree_multiset< _Key, _Compare, _Traits >::btree_multiset | ( | 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 184 of file btree_multiset.h.
References stx::btree_multiset< _Key, _Compare, _Traits >::insert().
| stx::btree_multiset< _Key, _Compare, _Traits >::~btree_multiset | ( | ) | [inline] |
| stx::btree_multiset< _Key, _Compare, _Traits >::btree_multiset | ( | const self & | other | ) | [inline] |
Copy constructor.
The newly initialized B+ tree object will contain a copy of all keys.
Definition at line 440 of file btree_multiset.h.
| void stx::btree_multiset< _Key, _Compare, _Traits >::swap | ( | self & | from | ) | [inline] |
Fast swapping of two identical B+ tree objects.
Definition at line 196 of file btree_multiset.h.
References stx::btree_multiset< _Key, _Compare, _Traits >::tree.
| key_compare stx::btree_multiset< _Key, _Compare, _Traits >::key_comp | ( | ) | const [inline] |
Constant access to the key comparison object sorting the B+ tree.
Definition at line 205 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::key_comp().
| value_compare stx::btree_multiset< _Key, _Compare, _Traits >::value_comp | ( | ) | const [inline] |
Constant access to a constructed value_type comparison object.
Required by the STL
Definition at line 212 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::value_comp().
| void stx::btree_multiset< _Key, _Compare, _Traits >::clear | ( | ) | [inline] |
Frees all keys and all nodes of the tree.
Definition at line 221 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::clear().
| iterator stx::btree_multiset< _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 231 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::begin().
| iterator stx::btree_multiset< _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 238 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end().
| const_iterator stx::btree_multiset< _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 245 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::begin().
| const_iterator stx::btree_multiset< _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 252 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end().
| reverse_iterator stx::btree_multiset< _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 259 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rbegin().
| reverse_iterator stx::btree_multiset< _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 266 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rend().
| const_reverse_iterator stx::btree_multiset< _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 273 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rbegin().
| const_reverse_iterator stx::btree_multiset< _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 280 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rend().
| size_type stx::btree_multiset< _Key, _Compare, _Traits >::size | ( | ) | const [inline] |
Return the number of keys in the B+ tree.
Definition at line 289 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::size().
| bool stx::btree_multiset< _Key, _Compare, _Traits >::empty | ( | ) | const [inline] |
Returns true if there is at least one key in the B+ tree.
Definition at line 295 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::empty().
| size_type stx::btree_multiset< _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 302 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::max_size().
| const tree_stats& stx::btree_multiset< _Key, _Compare, _Traits >::get_stats | ( | ) | const [inline] |
Return a const reference to the current statistics.
Definition at line 308 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::get_stats().
| bool stx::btree_multiset< _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 318 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::exists().
| iterator stx::btree_multiset< _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 325 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::find().
| const_iterator stx::btree_multiset< _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 332 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::find().
| size_type stx::btree_multiset< _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.
Definition at line 339 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::count().
| iterator stx::btree_multiset< _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 346 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::lower_bound().
| const_iterator stx::btree_multiset< _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 353 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::lower_bound().
| iterator stx::btree_multiset< _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 360 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::upper_bound().
| const_iterator stx::btree_multiset< _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 367 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::upper_bound().
| std::pair<iterator, iterator> stx::btree_multiset< _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 373 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::equal_range().
| std::pair<const_iterator, const_iterator> stx::btree_multiset< _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 379 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::equal_range().
| bool stx::btree_multiset< _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 key (counts) are considered equal.
Definition at line 389 of file btree_multiset.h.
References stx::btree_multiset< _Key, _Compare, _Traits >::tree.
| bool stx::btree_multiset< _Key, _Compare, _Traits >::operator!= | ( | const self & | other | ) | const [inline] |
Inequality relation. Based on operator==.
Definition at line 395 of file btree_multiset.h.
References stx::btree_multiset< _Key, _Compare, _Traits >::tree.
| bool stx::btree_multiset< _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 402 of file btree_multiset.h.
References stx::btree_multiset< _Key, _Compare, _Traits >::tree.
| bool stx::btree_multiset< _Key, _Compare, _Traits >::operator> | ( | const self & | other | ) | const [inline] |
Greater relation. Based on operator<.
Definition at line 408 of file btree_multiset.h.
References stx::btree_multiset< _Key, _Compare, _Traits >::tree.
| bool stx::btree_multiset< _Key, _Compare, _Traits >::operator<= | ( | const self & | other | ) | const [inline] |
Less-equal relation. Based on operator<.
Definition at line 414 of file btree_multiset.h.
References stx::btree_multiset< _Key, _Compare, _Traits >::tree.
| bool stx::btree_multiset< _Key, _Compare, _Traits >::operator>= | ( | const self & | other | ) | const [inline] |
Greater-equal relation. Based on operator<.
Definition at line 420 of file btree_multiset.h.
References stx::btree_multiset< _Key, _Compare, _Traits >::tree.
| self& stx::btree_multiset< _Key, _Compare, _Traits >::operator= | ( | const self & | other | ) | [inline] |
Assignment operator. All the keys are copied.
Definition at line 429 of file btree_multiset.h.
References stx::btree_multiset< _Key, _Compare, _Traits >::tree.
| iterator stx::btree_multiset< _Key, _Compare, _Traits >::insert | ( | const key_type & | x | ) | [inline] |
Attempt to insert a key into the B+ tree.
As this set allows duplicates, this function never fails.
Definition at line 450 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert2().
Referenced by stx::btree_multiset< _Key, _Compare, _Traits >::btree_multiset(), and stx::btree_multiset< _Key, _Compare, _Traits >::insert().
| iterator stx::btree_multiset< _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 457 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert2().
| void stx::btree_multiset< _Key, _Compare, _Traits >::insert | ( | InputIterator | first, | |
| InputIterator | last | |||
| ) | [inline] |
Attempt to insert the range [first,last) of key_type into the B+ tree.
Each key is inserted individually.
Definition at line 465 of file btree_multiset.h.
References stx::btree_multiset< _Key, _Compare, _Traits >::insert().
| bool stx::btree_multiset< _Key, _Compare, _Traits >::erase_one | ( | const key_type & | key | ) | [inline] |
Erases one (the first) entry of the given key.
Definition at line 479 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase_one().
| size_type stx::btree_multiset< _Key, _Compare, _Traits >::erase | ( | const key_type & | key | ) | [inline] |
Erases all the entries of the given key.
This is implemented using erase_one() and thus not very efficient.
Definition at line 486 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::erase().
| void stx::btree_multiset< _Key, _Compare, _Traits >::erase | ( | iterator | iter | ) | [inline] |
| void stx::btree_multiset< _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 502 of file btree_multiset.h.
| void stx::btree_multiset< _Key, _Compare, _Traits >::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 514 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::print().
| void stx::btree_multiset< _Key, _Compare, _Traits >::print_leaves | ( | ) | const [inline] |
Print out only the leaves via the double linked list.
Definition at line 520 of file btree_multiset.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::print_leaves().