11#ifndef TLX_CONTAINER_BTREE_MULTIMAP_HEADER
12#define TLX_CONTAINER_BTREE_MULTIMAP_HEADER
34template <
typename Key_,
typename Data_,
35 typename Compare_ = std::less<Key_>,
38 typename Alloc_ = std::allocator<std::pair<Key_, Data_> > >
185 template <
class InputIterator>
188 :
tree_(first, last, alloc)
193 template <
class InputIterator>
197 :
tree_(first, last, kcf, alloc)
217 return tree_.key_comp();
223 return tree_.value_comp();
234 return tree_.get_allocator();
257 return tree_.begin();
269 return tree_.begin();
281 return tree_.rbegin();
293 return tree_.rbegin();
315 return tree_.empty();
321 return tree_.max_size();
326 return tree_.get_stats();
338 return tree_.exists(key);
344 return tree_.find(key);
350 return tree_.find(key);
356 return tree_.count(key);
362 return tree_.lower_bound(key);
368 return tree_.lower_bound(key);
374 return tree_.upper_bound(key);
380 return tree_.upper_bound(key);
385 return tree_.equal_range(key);
389 std::pair<const_iterator, const_iterator>
391 return tree_.equal_range(key);
461 return tree_.insert(x).first;
474 return tree_.insert(hint, x);
486 template <
typename InputIterator>
487 void insert(InputIterator first, InputIterator last) {
488 return tree_.insert(first, last);
494 template <
typename Iterator>
496 return tree_.bulk_load(first, last);
508 return tree_.erase_one(key);
514 return tree_.erase(key);
519 return tree_.erase(iter);
532#ifdef TLX_BTREE_DEBUG
541 void print(std::ostream& os)
const {
546 void print_leaves(std::ostream& os)
const {
547 tree_.print_leaves(os);
Basic class implementing a B+ tree data structure in memory.
static const unsigned short inner_slotmax
static const unsigned short inner_slotmin
static const bool allow_duplicates
static const unsigned short leaf_slotmax
static const bool self_verify
static const unsigned short leaf_slotmin
static const unsigned short inner_slotmax
BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type > btree_impl
btree_multimap(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function.
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...
btree_impl::reverse_iterator reverse_iterator
void swap(btree_multimap &from)
Fast swapping of two identical B+ tree objects.
btree_impl::size_type size_type
bool operator>(const btree_multimap &other) const
Greater relation. Based on operator<.
iterator insert2(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into 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+ tr...
Data_ data_type
Second template parameter: The data type associated with each key.
btree_multimap & operator=(const btree_multimap &other)
Assignment operator. All the key/data pairs are copied.
btree_multimap< key_type, data_type, key_compare, traits, allocator_type > self
Typedef of our own type.
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 erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
iterator insert(iterator hint, const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
static const unsigned short inner_slotmin
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,...
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...
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().
static const bool allow_duplicates
btree_impl::const_reverse_iterator const_reverse_iterator
static const unsigned short leaf_slotmax
Alloc_ allocator_type
Fifth template parameter: STL allocator.
std::pair< key_type, data_type > value_type
bool operator<(const btree_multimap &other) const
Total ordering relation of B+ trees of the same type.
size_type size() const
Return the number of key/data pairs in the B+ tree.
btree_impl::value_compare value_compare
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.
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 ...
bool operator==(const btree_multimap &other) const
Equality relation of B+ trees of the same type.
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Compare_ key_compare
Third template parameter: Key comparison function object.
btree_multimap(const btree_multimap &other)
Copy constructor.
btree_impl::tree_stats tree_stats
const tree_stats & get_stats() const
Return a const reference to the current statistics.
static const bool self_verify
void verify() const
Run a thorough verification of all B+ tree invariants.
bool operator!=(const btree_multimap &other) const
Inequality relation. Based on operator==.
size_type max_size() const
Returns the largest possible size of 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.
iterator insert(const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
bool operator>=(const btree_multimap &other) const
Greater-equal relation. Based on operator<.
~btree_multimap()
Frees up all used B+ tree memory pages.
bool operator<=(const btree_multimap &other) const
Less-equal relation. Based on operator<.
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.
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,...
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
static const unsigned short leaf_slotmin
iterator insert2(iterator hint, const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
void insert(InputIterator first, InputIterator last)
Attempt to insert the range [first,last) of value_type pairs into 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 end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
Key_ key_type
First template parameter: The key type of the btree.
const_iterator end() const
Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of th...
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree.
Traits_ traits
Fourth template parameter: Traits object used to define more parameters of the B+ tree.
btree_multimap(const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing an empty B+ tree with a special key comparison object.
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
key_compare key_comp() const
Constant access to the key comparison object sorting 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...
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.
btree_multimap(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last)
void erase(iterator iter)
Erase the key/data pair referenced by the iterator.
void bulk_load(Iterator first, Iterator last)
Bulk load a sorted range [first,last).
btree_impl::iterator iterator
btree_impl::const_iterator const_iterator
Generates default traits for a B+ tree used as a set or map.
static const key_type & get(const value_type &v)
pull first out of pair