tlx
btree_multimap.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * tlx/container/btree_multimap.hpp
3 *
4 * Part of tlx - http://panthema.net/tlx
5 *
6 * Copyright (C) 2008-2017 Timo Bingmann <tb@panthema.net>
7 *
8 * All rights reserved. Published under the Boost Software License, Version 1.0
9 ******************************************************************************/
10
11#ifndef TLX_CONTAINER_BTREE_MULTIMAP_HEADER
12#define TLX_CONTAINER_BTREE_MULTIMAP_HEADER
13
14#include <functional>
15#include <memory>
16#include <utility>
17
19
20namespace tlx {
21
22//! \addtogroup tlx_container_btree
23//! \{
24
25/*!
26 * Specialized B+ tree template class implementing STL's multimap container.
27 *
28 * Implements the STL multimap using a B+ tree. It can be used as a drop-in
29 * replacement for std::multimap. Not all asymptotic time requirements are met
30 * in theory. The class has a traits class defining B+ tree properties like
31 * slots and self-verification. Furthermore an allocator can be specified for
32 * tree nodes.
33 */
34template <typename Key_, typename Data_,
35 typename Compare_ = std::less<Key_>,
36 typename Traits_ =
37 btree_default_traits<Key_, std::pair<Key_, Data_> >,
38 typename Alloc_ = std::allocator<std::pair<Key_, Data_> > >
40{
41public:
42 //! \name Template Parameter Types
43 //! \{
44
45 //! First template parameter: The key type of the btree. This is stored in
46 //! inner nodes.
47 typedef Key_ key_type;
48
49 //! Second template parameter: The data type associated with each
50 //! key. Stored in the B+ tree's leaves
51 typedef Data_ data_type;
52
53 //! Third template parameter: Key comparison function object
54 typedef Compare_ key_compare;
55
56 //! Fourth template parameter: Traits object used to define more parameters
57 //! of the B+ tree
58 typedef Traits_ traits;
59
60 //! Fifth template parameter: STL allocator
61 typedef Alloc_ allocator_type;
62
63 //! \}
64
65 // The macro TLX_BTREE_FRIENDS can be used by outside class to access the B+
66 // tree internals. This was added for wxBTreeDemo to be able to draw the
67 // tree.
69
70public:
71 //! \name Constructed Types
72 //! \{
73
74 //! Typedef of our own type
75 typedef btree_multimap<
77
78 //! Construct the STL-required value_type as a composition pair of key and
79 //! data types
80 typedef std::pair<key_type, data_type> value_type;
81
82 //! Key Extractor Struct
83 struct key_of_value {
84 //! pull first out of pair
85 static const key_type& get(const value_type& v) { return v.first; }
86 };
87
88 //! Implementation type of the btree_base
89 typedef BTree<key_type, value_type, key_of_value, key_compare,
91
92 //! Function class comparing two value_type pairs.
93 typedef typename btree_impl::value_compare value_compare;
94
95 //! Size type used to count keys
97
98 //! Small structure containing statistics about the tree
99 typedef typename btree_impl::tree_stats tree_stats;
100
101 //! \}
102
103public:
104 //! \name Static Constant Options and Values of the B+ Tree
105 //! \{
106
107 //! Base B+ tree parameter: The number of key/data slots in each leaf
108 static const unsigned short leaf_slotmax = btree_impl::leaf_slotmax;
109
110 //! Base B+ tree parameter: The number of key slots in each inner node,
111 //! this can differ from slots in each leaf.
112 static const unsigned short inner_slotmax = btree_impl::inner_slotmax;
113
114 //! Computed B+ tree parameter: The minimum number of key/data slots used
115 //! in a leaf. If fewer slots are used, the leaf will be merged or slots
116 //! shifted from it's siblings.
117 static const unsigned short leaf_slotmin = btree_impl::leaf_slotmin;
118
119 //! Computed B+ tree parameter: The minimum number of key slots used
120 //! in an inner node. If fewer slots are used, the inner node will be
121 //! merged or slots shifted from it's siblings.
122 static const unsigned short inner_slotmin = btree_impl::inner_slotmin;
123
124 //! Debug parameter: Enables expensive and thorough checking of the B+ tree
125 //! invariants after each insert/erase operation.
127
128 //! Debug parameter: Prints out lots of debug information about how the
129 //! algorithms change the tree. Requires the header file to be compiled with
130 //! TLX_BTREE_DEBUG and the key type must be std::ostream printable.
131 static const bool debug = btree_impl::debug;
132
133 //! Operational parameter: Allow duplicate keys in the btree.
135
136 //! \}
137
138public:
139 //! \name Iterators and Reverse Iterators
140 //! \{
141
142 //! STL-like iterator object for B+ tree items. The iterator points to a
143 //! specific slot number in a leaf.
144 typedef typename btree_impl::iterator iterator;
145
146 //! STL-like iterator object for B+ tree items. The iterator points to a
147 //! specific slot number in a leaf.
148 typedef typename btree_impl::const_iterator const_iterator;
149
150 //! create mutable reverse iterator by using STL magic
151 typedef typename btree_impl::reverse_iterator reverse_iterator;
152
153 //! create constant reverse iterator by using STL magic
154 typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
155
156 //! \}
157
158private:
159 //! \name Tree Implementation Object
160 //! \{
161
162 //! The contained implementation object
164
165 //! \}
166
167public:
168 //! \name Constructors and Destructor
169 //! \{
170
171 //! Default constructor initializing an empty B+ tree with the standard key
172 //! comparison function
174 : tree_(alloc)
175 { }
176
177 //! Constructor initializing an empty B+ tree with a special key comparison
178 //! object
179 explicit btree_multimap(const key_compare& kcf,
180 const allocator_type& alloc = allocator_type())
181 : tree_(kcf, alloc)
182 { }
183
184 //! Constructor initializing a B+ tree with the range [first,last)
185 template <class InputIterator>
186 btree_multimap(InputIterator first, InputIterator last,
187 const allocator_type& alloc = allocator_type())
188 : tree_(first, last, alloc)
189 { }
190
191 //! Constructor initializing a B+ tree with the range [first,last) and a
192 //! special key comparison object
193 template <class InputIterator>
194 btree_multimap(InputIterator first, InputIterator last,
195 const key_compare& kcf,
196 const allocator_type& alloc = allocator_type())
197 : tree_(first, last, kcf, alloc)
198 { }
199
200 //! Frees up all used B+ tree memory pages
202 { }
203
204 //! Fast swapping of two identical B+ tree objects.
205 void swap(btree_multimap& from) {
206 std::swap(tree_, from.tree_);
207 }
208
209 //! \}
210
211public:
212 //! \name Key and Value Comparison Function Objects
213 //! \{
214
215 //! Constant access to the key comparison object sorting the B+ tree
217 return tree_.key_comp();
218 }
219
220 //! Constant access to a constructed value_type comparison object. required
221 //! by the STL
223 return tree_.value_comp();
224 }
225
226 //! \}
227
228public:
229 //! \name Allocators
230 //! \{
231
232 //! Return the base node allocator provided during construction.
234 return tree_.get_allocator();
235 }
236
237 //! \}
238
239public:
240 //! \name Fast Destruction of the B+ Tree
241 //! \{
242
243 //! Frees all key/data pairs and all nodes of the tree
244 void clear() {
245 tree_.clear();
246 }
247
248 //! \}
249
250public:
251 //! \name STL Iterator Construction Functions
252 //! \{
253
254 //! Constructs a read/data-write iterator that points to the first slot in
255 //! the first leaf of the B+ tree.
257 return tree_.begin();
258 }
259
260 //! Constructs a read/data-write iterator that points to the first invalid
261 //! slot in the last leaf of the B+ tree.
263 return tree_.end();
264 }
265
266 //! Constructs a read-only constant iterator that points to the first slot
267 //! in the first leaf of the B+ tree.
269 return tree_.begin();
270 }
271
272 //! Constructs a read-only constant iterator that points to the first
273 //! invalid slot in the last leaf of the B+ tree.
275 return tree_.end();
276 }
277
278 //! Constructs a read/data-write reverse iterator that points to the first
279 //! invalid slot in the last leaf of the B+ tree. Uses STL magic.
281 return tree_.rbegin();
282 }
283
284 //! Constructs a read/data-write reverse iterator that points to the first
285 //! slot in the first leaf of the B+ tree. Uses STL magic.
287 return tree_.rend();
288 }
289
290 //! Constructs a read-only reverse iterator that points to the first
291 //! invalid slot in the last leaf of the B+ tree. Uses STL magic.
293 return tree_.rbegin();
294 }
295
296 //! Constructs a read-only reverse iterator that points to the first slot
297 //! in the first leaf of the B+ tree. Uses STL magic.
299 return tree_.rend();
300 }
301
302 //! \}
303
304public:
305 //! \name Access Functions to the Item Count
306 //! \{
307
308 //! Return the number of key/data pairs in the B+ tree
309 size_type size() const {
310 return tree_.size();
311 }
312
313 //! Returns true if there is at least one key/data pair in the B+ tree
314 bool empty() const {
315 return tree_.empty();
316 }
317
318 //! Returns the largest possible size of the B+ Tree. This is just a
319 //! function required by the STL standard, the B+ Tree can hold more items.
321 return tree_.max_size();
322 }
323
324 //! Return a const reference to the current statistics.
325 const tree_stats& get_stats() const {
326 return tree_.get_stats();
327 }
328
329 //! \}
330
331public:
332 //! \name STL Access Functions Querying the Tree by Descending to a Leaf
333 //! \{
334
335 //! Non-STL function checking whether a key is in the B+ tree. The same as
336 //! (find(k) != end()) or (count() != 0).
337 bool exists(const key_type& key) const {
338 return tree_.exists(key);
339 }
340
341 //! Tries to locate a key in the B+ tree and returns an iterator to the
342 //! key/data slot if found. If unsuccessful it returns end().
343 iterator find(const key_type& key) {
344 return tree_.find(key);
345 }
346
347 //! Tries to locate a key in the B+ tree and returns an constant iterator to
348 //! the key/data slot if found. If unsuccessful it returns end().
349 const_iterator find(const key_type& key) const {
350 return tree_.find(key);
351 }
352
353 //! Tries to locate a key in the B+ tree and returns the number of identical
354 //! key entries found.
355 size_type count(const key_type& key) const {
356 return tree_.count(key);
357 }
358
359 //! Searches the B+ tree and returns an iterator to the first pair equal to
360 //! or greater than key, or end() if all keys are smaller.
362 return tree_.lower_bound(key);
363 }
364
365 //! Searches the B+ tree and returns a constant iterator to the first pair
366 //! equal to or greater than key, or end() if all keys are smaller.
368 return tree_.lower_bound(key);
369 }
370
371 //! Searches the B+ tree and returns an iterator to the first pair greater
372 //! than key, or end() if all keys are smaller or equal.
374 return tree_.upper_bound(key);
375 }
376
377 //! Searches the B+ tree and returns a constant iterator to the first pair
378 //! greater than key, or end() if all keys are smaller or equal.
380 return tree_.upper_bound(key);
381 }
382
383 //! Searches the B+ tree and returns both lower_bound() and upper_bound().
384 std::pair<iterator, iterator> equal_range(const key_type& key) {
385 return tree_.equal_range(key);
386 }
387
388 //! Searches the B+ tree and returns both lower_bound() and upper_bound().
389 std::pair<const_iterator, const_iterator>
390 equal_range(const key_type& key) const {
391 return tree_.equal_range(key);
392 }
393
394 //! \}
395
396public:
397 //! \name B+ Tree Object Comparison Functions
398 //! \{
399
400 //! Equality relation of B+ trees of the same type. B+ trees of the same
401 //! size and equal elements (both key and data) are considered equal. Beware
402 //! of the random ordering of duplicate keys.
403 bool operator == (const btree_multimap& other) const {
404 return (tree_ == other.tree_);
405 }
406
407 //! Inequality relation. Based on operator==.
408 bool operator != (const btree_multimap& other) const {
409 return (tree_ != other.tree_);
410 }
411
412 //! Total ordering relation of B+ trees of the same type. It uses
413 //! std::lexicographical_compare() for the actual comparison of elements.
414 bool operator < (const btree_multimap& other) const {
415 return (tree_ < other.tree_);
416 }
417
418 //! Greater relation. Based on operator<.
419 bool operator > (const btree_multimap& other) const {
420 return (tree_ > other.tree_);
421 }
422
423 //! Less-equal relation. Based on operator<.
424 bool operator <= (const btree_multimap& other) const {
425 return (tree_ <= other.tree_);
426 }
427
428 //! Greater-equal relation. Based on operator<.
429 bool operator >= (const btree_multimap& other) const {
430 return (tree_ >= other.tree_);
431 }
432
433 //! \}
434
435public:
436 //! \name Fast Copy: Assign Operator and Copy Constructors
437 //! \{
438
439 //! Assignment operator. All the key/data pairs are copied
441 if (this != &other)
442 tree_ = other.tree_;
443 return *this;
444 }
445
446 //! Copy constructor. The newly initialized B+ tree object will contain a
447 //! copy or all key/data pairs.
449 : tree_(other.tree_)
450 { }
451
452 //! \}
453
454public:
455 //! \name Public Insertion Functions
456 //! \{
457
458 //! Attempt to insert a key/data pair into the B+ tree. As this tree allows
459 //! duplicates, insertion never fails.
461 return tree_.insert(x).first;
462 }
463
464 //! Attempt to insert a key/data pair into the B+ tree. This function is the
465 //! same as the other insert. As this tree allows duplicates, insertion
466 //! never fails.
467 iterator insert2(const key_type& key, const data_type& data) {
468 return tree_.insert(value_type(key, data)).first;
469 }
470
471 //! Attempt to insert a key/data pair into the B+ tree. The iterator hint is
472 //! currently ignored by the B+ tree insertion routine.
474 return tree_.insert(hint, x);
475 }
476
477 //! Attempt to insert a key/data pair into the B+ tree. The iterator hint is
478 //! currently ignored by the B+ tree insertion routine.
480 const key_type& key, const data_type& data) {
481 return tree_.insert(hint, value_type(key, data));
482 }
483
484 //! Attempt to insert the range [first,last) of value_type pairs into the B+
485 //! tree. Each key/data pair is inserted individually.
486 template <typename InputIterator>
487 void insert(InputIterator first, InputIterator last) {
488 return tree_.insert(first, last);
489 }
490
491 //! Bulk load a sorted range [first,last). Loads items into leaves and
492 //! constructs a B-tree above them. The tree must be empty when calling this
493 //! function.
494 template <typename Iterator>
495 void bulk_load(Iterator first, Iterator last) {
496 return tree_.bulk_load(first, last);
497 }
498
499 //! \}
500
501public:
502 //! \name Public Erase Functions
503 //! \{
504
505 //! Erases one (the first) of the key/data pairs associated with the given
506 //! key.
507 bool erase_one(const key_type& key) {
508 return tree_.erase_one(key);
509 }
510
511 //! Erases all the key/data pairs associated with the given key. This is
512 //! implemented using erase_one() and thus not very efficient.
514 return tree_.erase(key);
515 }
516
517 //! Erase the key/data pair referenced by the iterator.
518 void erase(iterator iter) {
519 return tree_.erase(iter);
520 }
521
522#ifdef TLX_BTREE_TODO
523 //! Erase all key/data pairs in the range [first,last). This function is
524 //! currently not implemented by the B+ Tree.
525 void erase(iterator /* first */, iterator /* last */) {
526 abort();
527 }
528#endif
529
530 //! \}
531
532#ifdef TLX_BTREE_DEBUG
533
534public:
535 //! \name Debug Printing
536 //! \{
537
538 //! Print out the B+ tree structure with keys onto the given ostream. This
539 //! function requires that the header is compiled with TLX_BTREE_DEBUG and
540 //! that key_type is printable via std::ostream.
541 void print(std::ostream& os) const {
542 tree_.print(os);
543 }
544
545 //! Print out only the leaves via the double linked list.
546 void print_leaves(std::ostream& os) const {
547 tree_.print_leaves(os);
548 }
549
550 //! \}
551#endif
552
553public:
554 //! \name Verification of B+ Tree Invariants
555 //! \{
556
557 //! Run a thorough verification of all B+ tree invariants. The program
558 //! aborts via TLX_BTREE_ASSERT() if something is wrong.
559 void verify() const {
560 tree_.verify();
561 }
562
563 //! \}
564};
565
566//! \}
567
568} // namespace tlx
569
570#endif // !TLX_CONTAINER_BTREE_MULTIMAP_HEADER
571
572/******************************************************************************/
Basic class implementing a B+ tree data structure in memory.
Definition: btree.hpp:125
static const unsigned short inner_slotmax
Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...
Definition: btree.hpp:184
std::pair< iterator, bool > insert(const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree.hpp:1846
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,...
Definition: btree.hpp:1616
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
Definition: btree.hpp:2368
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
Definition: btree.hpp:2155
static const unsigned short inner_slotmin
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
Definition: btree.hpp:194
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...
Definition: btree.hpp:1656
static const bool allow_duplicates
Sixth template parameter: Allow duplicate keys in the B+ tree.
Definition: btree.hpp:150
static const unsigned short leaf_slotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
Definition: btree.hpp:180
size_type size() const
Return the number of key/data pairs in the B+ tree.
Definition: btree.hpp:1494
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
Definition: btree.hpp:203
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.
Definition: btree.hpp:1584
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
Definition: btree.hpp:1499
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
Definition: btree.hpp:1371
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Definition: btree.hpp:1232
const struct tree_stats & get_stats() const
Return a const reference to the current statistics.
Definition: btree.hpp:1510
static const bool self_verify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
Definition: btree.hpp:198
void verify() const
Run a thorough verification of all B+ tree invariants.
Definition: btree.hpp:3541
size_type max_size() const
Returns the largest possible size of the B+ Tree.
Definition: btree.hpp:1505
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.
Definition: btree.hpp:1542
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
Definition: btree.hpp:1522
static const unsigned short leaf_slotmin
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
Definition: btree.hpp:189
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
Definition: btree.hpp:1189
void clear()
Frees all key/data pairs and all nodes of the tree.
Definition: btree.hpp:1294
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
Definition: btree.hpp:1347
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
Definition: btree.hpp:1365
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition: btree.hpp:1695
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree.
Definition: btree.hpp:1341
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Definition: btree.hpp:2392
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
Definition: btree.hpp:1183
Specialized B+ tree template class implementing STL's multimap container.
static const unsigned short inner_slotmax
Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...
BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type > btree_impl
Implementation type of the btree_base.
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
create mutable reverse iterator by using STL magic
void swap(btree_multimap &from)
Fast swapping of two identical B+ tree objects.
btree_impl::size_type size_type
Size type used to count keys.
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
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
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
Operational parameter: Allow duplicate keys in the btree.
btree_impl::const_reverse_iterator const_reverse_iterator
create constant reverse iterator by using STL magic
static const unsigned short leaf_slotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
Alloc_ allocator_type
Fifth template parameter: STL allocator.
std::pair< key_type, data_type > value_type
Construct the STL-required value_type as a composition pair of key and data types.
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.
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
btree_impl::value_compare value_compare
Function class comparing two value_type pairs.
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
Small structure containing statistics about the tree.
const tree_stats & get_stats() const
Return a const reference to the current statistics.
static const bool self_verify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
void verify() const
Run a thorough verification of all B+ tree invariants.
bool operator!=(const btree_multimap &other) const
Inequality relation. Based on operator==.
btree_impl tree_
The contained implementation object.
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
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
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
STL-like iterator object for B+ tree items.
btree_impl::const_iterator const_iterator
STL-like iterator object for B+ tree items.
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
swap enclosed object with another counting pointer (no reference counts need change)
static const key_type & get(const value_type &v)
pull first out of pair