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