#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]</ |