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