34 #ifndef _STX_BTREE_MULTIMAP_H_ 35 #define _STX_BTREE_MULTIMAP_H_ 56 template <
typename _Key,
typename _Data,
57 typename _Compare = std::less<_Key>,
58 typename _Traits = btree_default_map_traits<_Key, _Data>,
59 typename _Alloc = std::allocator<std::pair<_Key, _Data> > >
185 template <
class InputIterator>
188 : tree(first, last, alloc)
194 template <
class InputIterator>
195 inline btree_multimap(InputIterator first, InputIterator last,
const key_compare &kcf,
197 : tree(first, last, kcf, alloc)
209 std::swap(tree, from.tree);
272 inline const_iterator
end()
const 293 inline const_reverse_iterator
rbegin()
const 300 inline const_reverse_iterator
rend()
const 345 iterator
find(
const key_type &key)
347 return tree.
find(key);
352 const_iterator
find(
const key_type &key)
const 354 return tree.
find(key);
359 size_type
count(
const key_type &key)
const 361 return tree.
count(key);
395 inline std::pair<iterator, iterator>
equal_range(
const key_type& key)
401 inline std::pair<const_iterator, const_iterator>
equal_range(
const key_type& key)
const 414 return (tree == other.tree);
420 return (tree != other.tree);
427 return (tree < other.tree);
433 return (tree > other.tree);
439 return (tree <= other.tree);
445 return (tree >= other.tree);
473 inline iterator
insert(
const value_type& x)
475 return tree.
insert2(x.first, x.second).first;
481 inline iterator
insert(
const key_type& key,
const data_type& data)
483 return tree.
insert2(key, data).first;
490 inline iterator
insert2(
const key_type& key,
const data_type& data)
492 return tree.
insert2(key, data).first;
497 inline iterator
insert(iterator hint,
const value_type &x)
499 return tree.
insert2(hint, x.first, x.second);
504 inline iterator
insert2(iterator hint,
const key_type& key,
const data_type& data)
506 return tree.
insert2(hint, key, data);
511 template <
typename InputIterator>
512 inline void insert(InputIterator first, InputIterator last)
514 return tree.
insert(first, last);
520 template <
typename Iterator>
538 size_type
erase(
const key_type &key)
540 return tree.
erase(key);
546 return tree.
erase(iter);
593 void dump(std::ostream &os)
const 610 #endif // _STX_BTREE_MULTIMAP_H_ size_type size() const
Return the number of key/data pairs in the B+ tree.
const_iterator upper_bound(const key_type &key) const
Searches the B+ tree and returns a constant iterator to the first pair greater than key...
void bulk_load(Iterator first, Iterator last)
Bulk load a sorted range [first,last).
void dump(std::ostream &os) const
Dump the contents of the B+ tree out onto an ostream as a binary image.
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree...
static const unsigned short leafslotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
const_iterator begin() const
Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tr...
void verify() const
Run a thorough verification of all B+ tree invariants.
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
void clear()
Frees all key/data pairs and all nodes of the tree.
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
bool operator>(const self &other) const
Greater relation. Based on operator<.
void swap(self &from)
Fast swapping of two identical B+ tree objects.
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
Contains the main B+ tree implementation template class btree.
iterator lower_bound(const key_type &key)
Searches the B+ tree and returns an iterator to the first pair equal to or greater than key...
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
static const bool allow_duplicates
Sixth template parameter: Allow duplicate keys in the B+ tree.
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
static const unsigned short innerslotmax
Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...
void print_leaves(std::ostream &os) const
Print out only the leaves via the double linked list.
allocator_type get_allocator() const
Return the base node allocator provided during construction.
bool exists(const key_type &key) const
Non-STL function checking whether a key is in 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 th...
btree_impl::tree_stats tree_stats
Small structure containing statistics about the tree.
iterator insert(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
iterator lower_bound(const key_type &key)
Searches the B+ tree and returns an iterator to the first pair equal to or greater than key...
iterator insert(const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
_Key key_type
First template parameter: The key type of the btree.
_Compare key_compare
Third template parameter: Key comparison function object.
btree_impl tree
The contained implementation object.
const tree_stats & get_stats() const
Return a const reference to the current statistics.
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree...
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
void dump(std::ostream &os) const
Dump the contents of the B+ tree out onto an ostream as a binary image.
Specialized B+ tree template class implementing STL's multimap container.
static const unsigned short minleafslots
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
btree_impl::reverse_iterator reverse_iterator
create mutable reverse iterator by using STL magic
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...
void print(std::ostream &os) const
Print out the B+ tree structure with keys onto the given ostream.
bool operator<=(const self &other) const
Less-equal relation. Based on operator<.
std::pair< iterator, bool > insert(const pair_type &x)
Attempt to insert a key/data pair into the B+ tree.
btree_impl::const_reverse_iterator const_reverse_iterator
create constant reverse iterator by using STL magic
~btree_multimap()
Frees up all used B+ tree memory pages.
void print_leaves(std::ostream &os) const
Print out only the leaves via the double linked list.
bool operator!=(const self &other) const
Inequality relation. Based on operator==.
bool operator>=(const self &other) const
Greater-equal relation. Based on operator<.
void print(std::ostream &os) const
Print out the B+ tree structure with keys onto the given ostream.
_Alloc allocator_type
Fifth template parameter: STL allocator.
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...
iterator upper_bound(const key_type &key)
Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys...
const_iterator lower_bound(const key_type &key) const
Searches the B+ tree and returns a constant iterator to the first pair equal to or greater than key...
const_reverse_iterator rbegin() const
Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the...
static const unsigned short mininnerslots
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
#define BTREE_FRIENDS
The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.
const_reverse_iterator rend() const
Constructs a read-only reverse iterator that points to the first slot in the first leaf of the B+ tre...
self & operator=(const self &other)
*** Fast Copy: Assign Operator and Copy Constructors
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
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...
btree_impl::value_compare value_compare
Function class comparing two value_type pairs.
btree_multimap(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function...
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...
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
static const unsigned short innerslotmax
Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
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...
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
STX - Some Template Extensions namespace.
void verify() const
Run a thorough verification of all B+ tree invariants.
size_type max_size() const
Returns the largest possible size of the B+ Tree.
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().
const struct tree_stats & get_stats() const
Return a const reference to the current statistics.
static const unsigned short mininnerslots
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
void clear()
Frees all key/data pairs and all nodes of the tree.
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
static const unsigned short leafslotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
stx::btree< key_type, data_type, value_type, key_compare, traits, true, allocator_type, false > btree_impl
Implementation type of the btree_base.
btree_multimap(const self &other)
Copy constructor.
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
std::pair< iterator, bool > insert2(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
static const bool selfverify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
std::pair< key_type, data_type > value_type
Construct the STL-required value_type as a composition pair of key and data types.
size_type size() const
Return the number of key/data pairs in the B+ tree.
allocator_type get_allocator() const
Return the base node allocator provided during construction.
iterator insert2(iterator hint, const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
size_type max_size() const
Returns the largest possible size of the B+ Tree.
void insert(InputIterator first, InputIterator last)
Attempt to insert the range [first,last) of value_type pairs into the B+ tree.
iterator insert(iterator hint, const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
_Data data_type
Second template parameter: The data type associated with each key.
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
iterator upper_bound(const key_type &key)
Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys...
size_t size_type
Size type used to count keys.
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...
void erase(iterator iter)
Erase the key/data pair referenced by the iterator.
bool empty() const
Returns true if there is at least one key/data pair in 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 ...
btree_multimap(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last)
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
static const bool allow_duplicates
Operational parameter: Allow duplicate keys in the btree.
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
Basic class implementing a base B+ tree data structure in memory.
iterator insert2(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
btree_impl::iterator iterator
STL-like iterator object for B+ tree items.
btree_impl::const_iterator const_iterator
STL-like iterator object for B+ tree items.
btree_multimap(InputIterator first, InputIterator last, const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last) and a special key comparison object...
bool operator<(const self &other) const
Total ordering relation of B+ trees of the same type.
void erase(iterator, iterator)
Erase all key/data pairs in the range [first,last).
_Traits traits
Fourth template parameter: Traits object used to define more parameters of the B+ tree...
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
btree_impl::size_type size_type
Size type used to count keys.
btree_multimap(const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing an empty B+ tree with a special key comparison object.
bool operator==(const self &other) const
Equality relation of B+ trees of the same type.
static const unsigned short minleafslots
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
static const bool selfverify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...