#include <btree_map.h>
Public Types | |
| typedef _Key | key_type |
| First template parameter: The key type of the btree. | |
| typedef _Data | data_type |
| Second template parameter: The data type associated with each key. | |
| typedef _Compare | key_compare |
| Third template parameter: Key comparison function object. | |
| typedef _Traits | traits |
| Fourth template parameter: Traits object used to define more parameters of the B+ tree. | |
| typedef btree_map< key_type, data_type, key_compare, traits > | self |
| Typedef of our own type. | |
| typedef std::pair< key_type, data_type > | value_type |
| Construct the STL-required value_type as a composition pair of key and data types. | |
| 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 pairs. | |
| 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_map () | |
| Default constructor initializing an empty B+ tree with the standard key comparison function. | |
| btree_map (const key_compare &kcf) | |
| Constructor initializing an empty B+ tree with a special key comparison object. | |
| template<class InputIterator> | |
| btree_map (InputIterator first, InputIterator last) | |
| Constructor initializing a B+ tree with the range [first,last). | |
| template<class InputIterator> | |
| btree_map (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_map () | |
| 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 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. | |
| 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/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 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 key/data pairs are copied. | |
| btree_map (const self &other) | |
| Copy constructor. | |
| std::pair< iterator, bool > | insert (const value_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 hint, const value_type &x) |
| Attempt to insert a key/data pair into the B+ tree. | |
| iterator | insert2 (iterator hint, const key_type &key, const data_type &data) |
| Attempt to insert a key/data pair into the B+ tree. | |
| data_type & | operator[] (const key_type &key) |
| Returns a reference to the object that is associated with a particular key. | |
| 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 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 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/data 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. | |
Implements the STL map using a B+ tree. It can be used as a drop-in replacement for std::map. 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.
Most noteworthy difference to the default red-black implementation of std::map is that the B+ tree does not hold key and data pair together in memory. Instead each B+ tree node has two arrays of keys and data values. This design directly generates many problems in implementing the iterator's operator's which return value_type composition pairs.
Definition at line 48 of file btree_map.h.
| typedef _Key stx::btree_map< _Key, _Data, _Compare, _Traits >::key_type |
First template parameter: The key type of the btree.
This is stored in inner nodes and leaves
Definition at line 55 of file btree_map.h.
| typedef _Data stx::btree_map< _Key, _Data, _Compare, _Traits >::data_type |
Second template parameter: The data type associated with each key.
Stored in the B+ tree's leaves
Definition at line 59 of file btree_map.h.
| typedef _Compare stx::btree_map< _Key, _Data, _Compare, _Traits >::key_compare |
Third template parameter: Key comparison function object.
Definition at line 62 of file btree_map.h.
| typedef _Traits stx::btree_map< _Key, _Data, _Compare, _Traits >::traits |
Fourth template parameter: Traits object used to define more parameters of the B+ tree.
Definition at line 66 of file btree_map.h.
| typedef btree_map<key_type, data_type, key_compare, traits> stx::btree_map< _Key, _Data, _Compare, _Traits >::self |
| typedef std::pair<key_type, data_type> stx::btree_map< _Key, _Data, _Compare, _Traits >::value_type |
Construct the STL-required value_type as a composition pair of key and data types.
Definition at line 81 of file btree_map.h.
| typedef stx::btree<key_type, data_type, value_type, key_compare, traits, false> stx::btree_map< _Key, _Data, _Compare, _Traits >::btree_impl |
| typedef btree_impl::value_compare stx::btree_map< _Key, _Data, _Compare, _Traits >::value_compare |
| typedef btree_impl::size_type stx::btree_map< _Key, _Data, _Compare, _Traits >::size_type |
| typedef btree_impl::tree_stats stx::btree_map< _Key, _Data, _Compare, _Traits >::tree_stats |
| typedef btree_impl::iterator stx::btree_map< _Key, _Data, _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 132 of file btree_map.h.
| typedef btree_impl::const_iterator stx::btree_map< _Key, _Data, _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 136 of file btree_map.h.
| typedef btree_impl::reverse_iterator stx::btree_map< _Key, _Data, _Compare, _Traits >::reverse_iterator |
| typedef btree_impl::const_reverse_iterator stx::btree_map< _Key, _Data, _Compare, _Traits >::const_reverse_iterator |
| stx::btree_map< _Key, _Data, _Compare, _Traits >::btree_map | ( | ) | [inline] |
Default constructor initializing an empty B+ tree with the standard key comparison function.
Definition at line 155 of file btree_map.h.
| stx::btree_map< _Key, _Data, _Compare, _Traits >::btree_map | ( | const key_compare & | kcf | ) | [inline] |
Constructor initializing an empty B+ tree with a special key comparison object.
Definition at line 162 of file btree_map.h.
| stx::btree_map< _Key, _Data, _Compare, _Traits >::btree_map | ( | InputIterator | first, | |
| InputIterator | last | |||
| ) | [inline] |
Constructor initializing a B+ tree with the range [first,last).
Definition at line 169 of file btree_map.h.
| stx::btree_map< _Key, _Data, _Compare, _Traits >::btree_map | ( | 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 177 of file btree_map.h.
| stx::btree_map< _Key, _Data, _Compare, _Traits >::~btree_map | ( | ) | [inline] |
| stx::btree_map< _Key, _Data, _Compare, _Traits >::btree_map | ( | const self & | other | ) | [inline] |
Copy constructor.
The newly initialized B+ tree object will contain a copy of all key/data pairs.
Definition at line 434 of file btree_map.h.
| void stx::btree_map< _Key, _Data, _Compare, _Traits >::swap | ( | self & | from | ) | [inline] |
Fast swapping of two identical B+ tree objects.
Definition at line 188 of file btree_map.h.
References stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| key_compare stx::btree_map< _Key, _Data, _Compare, _Traits >::key_comp | ( | ) | const [inline] |
Constant access to the key comparison object sorting the B+ tree.
Definition at line 197 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::key_comp(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| value_compare stx::btree_map< _Key, _Data, _Compare, _Traits >::value_comp | ( | ) | const [inline] |
Constant access to a constructed value_type comparison object.
required by the STL
Definition at line 204 of file btree_map.h.
References stx::btree_map< _Key, _Data, _Compare, _Traits >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::value_comp().
| void stx::btree_map< _Key, _Data, _Compare, _Traits >::clear | ( | ) | [inline] |
Frees all key/data pairs and all nodes of the tree.
Definition at line 213 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::clear(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| iterator stx::btree_map< _Key, _Data, _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 223 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::begin(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| iterator stx::btree_map< _Key, _Data, _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 230 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| const_iterator stx::btree_map< _Key, _Data, _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 237 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::begin(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| const_iterator stx::btree_map< _Key, _Data, _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 244 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::end(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| reverse_iterator stx::btree_map< _Key, _Data, _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 251 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rbegin(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| reverse_iterator stx::btree_map< _Key, _Data, _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 258 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rend(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| const_reverse_iterator stx::btree_map< _Key, _Data, _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 265 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rbegin(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| const_reverse_iterator stx::btree_map< _Key, _Data, _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 272 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::rend(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| size_type stx::btree_map< _Key, _Data, _Compare, _Traits >::size | ( | ) | const [inline] |
Return the number of key/data pairs in the B+ tree.
Definition at line 281 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::size(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| bool stx::btree_map< _Key, _Data, _Compare, _Traits >::empty | ( | ) | const [inline] |
Returns true if there is at least one key/data pair in the B+ tree.
Definition at line 287 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::empty(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| size_type stx::btree_map< _Key, _Data, _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 294 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::max_size(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| const tree_stats& stx::btree_map< _Key, _Data, _Compare, _Traits >::get_stats | ( | ) | const [inline] |
Return a const reference to the current statistics.
Definition at line 300 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::get_stats(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| bool stx::btree_map< _Key, _Data, _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 310 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::exists(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| iterator stx::btree_map< _Key, _Data, _Compare, _Traits >::find | ( | const key_type & | key | ) | [inline] |
Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found.
If unsuccessful it returns end().
Definition at line 317 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::find(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| const_iterator stx::btree_map< _Key, _Data, _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/data slot if found.
If unsuccessful it returns end().
Definition at line 324 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::find(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| size_type stx::btree_map< _Key, _Data, _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.
Since this is a unique map, count() returns either 0 or 1.
Definition at line 332 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::count(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| iterator stx::btree_map< _Key, _Data, _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 339 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::lower_bound(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| const_iterator stx::btree_map< _Key, _Data, _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 346 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::lower_bound(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| iterator stx::btree_map< _Key, _Data, _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 353 of file btree_map.h.
References stx::btree_map< _Key, _Data, _Compare, _Traits >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::upper_bound().
| const_iterator stx::btree_map< _Key, _Data, _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 360 of file btree_map.h.
References stx::btree_map< _Key, _Data, _Compare, _Traits >::tree, and stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::upper_bound().
| std::pair<iterator, iterator> stx::btree_map< _Key, _Data, _Compare, _Traits >::equal_range | ( | const key_type & | key | ) | [inline] |
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition at line 366 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::equal_range(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| std::pair<const_iterator, const_iterator> stx::btree_map< _Key, _Data, _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 372 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::equal_range(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| bool stx::btree_map< _Key, _Data, _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 (both key and data) are considered equal.
Definition at line 383 of file btree_map.h.
References stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| bool stx::btree_map< _Key, _Data, _Compare, _Traits >::operator!= | ( | const self & | other | ) | const [inline] |
Inequality relation. Based on operator==.
Definition at line 389 of file btree_map.h.
References stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| bool stx::btree_map< _Key, _Data, _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 396 of file btree_map.h.
References stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| bool stx::btree_map< _Key, _Data, _Compare, _Traits >::operator> | ( | const self & | other | ) | const [inline] |
Greater relation. Based on operator<.
Definition at line 402 of file btree_map.h.
References stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| bool stx::btree_map< _Key, _Data, _Compare, _Traits >::operator<= | ( | const self & | other | ) | const [inline] |
Less-equal relation. Based on operator<.
Definition at line 408 of file btree_map.h.
References stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| bool stx::btree_map< _Key, _Data, _Compare, _Traits >::operator>= | ( | const self & | other | ) | const [inline] |
Greater-equal relation. Based on operator<.
Definition at line 414 of file btree_map.h.
References stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| self& stx::btree_map< _Key, _Data, _Compare, _Traits >::operator= | ( | const self & | other | ) | [inline] |
Assignment operator. All the key/data pairs are copied.
Definition at line 423 of file btree_map.h.
References stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| std::pair<iterator, bool> stx::btree_map< _Key, _Data, _Compare, _Traits >::insert | ( | const value_type & | x | ) | [inline] |
Attempt to insert a key/data pair into the B+ tree.
Fails if the pair is already present.
Definition at line 444 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert2(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
Referenced by stx::btree_map< _Key, _Data, _Compare, _Traits >::operator[]().
| std::pair<iterator, bool> stx::btree_map< _Key, _Data, _Compare, _Traits >::insert | ( | const key_type & | key, | |
| const data_type & | data | |||
| ) | [inline] |
Attempt to insert a key/data pair into the B+ tree.
Beware that if key_type == data_type, then the template iterator insert() is called instead. Fails if the inserted pair is already present.
Definition at line 452 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert2(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| std::pair<iterator, bool> stx::btree_map< _Key, _Data, _Compare, _Traits >::insert2 | ( | const key_type & | key, | |
| const data_type & | data | |||
| ) | [inline] |
Attempt to insert a key/data pair into the B+ tree.
This function is the same as the other insert, however if key_type == data_type then the non-template function cannot be called. Fails if the inserted pair is already present.
Definition at line 461 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert2(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.
| iterator stx::btree_map< _Key, _Data, _Compare, _Traits >::insert | ( | iterator | hint, | |
| const value_type & | x | |||
| ) | [inline] |
Attempt to insert a key/data pair into the B+ tree.
The iterator hint is currently ignored by the B+ tree insertion routine.
Definition at line 468 of file btree_map.h.
References stx::btree< _Key, _Data, _Value, _Compare, _Traits, _Duplicates >::insert2(), and stx::btree_map< _Key, _Data, _Compare, _Traits >::tree.