STX B+ Tree Template Classes  0.9
btree_multimap.h
Go to the documentation of this file.
1 /** \file btree_multimap.h
2  * Contains the specialized B+ tree template class btree_multimap
3  */
4 
5 /*
6  * STX B+ Tree Template Classes v0.9
7  * Copyright (C) 2008-2013 Timo Bingmann
8  *
9  * Boost Software License - Version 1.0 - August 17th, 2003
10  *
11  * Permission is hereby granted, free of charge, to any person or organization
12  * obtaining a copy of the software and accompanying documentation covered by
13  * this license (the "Software") to use, reproduce, display, distribute,
14  * execute, and transmit the Software, and to prepare derivative works of the
15  * Software, and to permit third-parties to whom the Software is furnished to
16  * do so, all subject to the following:
17  *
18  * The copyright notices in the Software and this entire statement, including
19  * the above license grant, this restriction and the following disclaimer, must
20  * be included in all copies of the Software, in whole or in part, and all
21  * derivative works of the Software, unless such copies or derivative works are
22  * solely in the form of machine-executable object code generated by a source
23  * language processor.
24  *
25  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
26  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
27  * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
28  * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
29  * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
30  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
31  * DEALINGS IN THE SOFTWARE.
32  */
33 
34 #ifndef _STX_BTREE_MULTIMAP_H_
35 #define _STX_BTREE_MULTIMAP_H_
36 
37 #include <stx/btree.h>
38 
39 namespace stx {
40 
41 /** @brief Specialized B+ tree template class implementing STL's multimap
42  * container.
43  *
44  * Implements the STL multimap using a B+ tree. It can be used as a drop-in
45  * replacement for std::multimap. Not all asymptotic time requirements are met
46  * in theory. The class has a traits class defining B+ tree properties like
47  * slots and self-verification. Furthermore an allocator can be specified for
48  * tree nodes.
49  *
50  * Most noteworthy difference to the default red-black implementation of
51  * std::multimap is that the B+ tree does not hold key and data pair together
52  * in memory. Instead each B+ tree node has two arrays of keys and data
53  * values. This design directly generates many problems in implementing the
54  * iterator's operator's which return value_type composition pairs.
55  */
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> > >
61 {
62 public:
63  // *** Template Parameter Types
64 
65  /// First template parameter: The key type of the btree. This is stored in
66  /// inner nodes and leaves
67  typedef _Key key_type;
68 
69  /// Second template parameter: The data type associated with each
70  /// key. Stored in the B+ tree's leaves
71  typedef _Data data_type;
72 
73  /// Third template parameter: Key comparison function object
74  typedef _Compare key_compare;
75 
76  /// Fourth template parameter: Traits object used to define more parameters
77  /// of the B+ tree
78  typedef _Traits traits;
79 
80  /// Fifth template parameter: STL allocator
81  typedef _Alloc allocator_type;
82 
83  // The macro BTREE_FRIENDS can be used by outside class to access the B+
84  // tree internals. This was added for wxBTreeDemo to be able to draw the
85  // tree.
87 
88 public:
89  // *** Constructed Types
90 
91  /// Typedef of our own type
93 
94  /// Construct the STL-required value_type as a composition pair of key and
95  /// data types
96  typedef std::pair<key_type, data_type> value_type;
97 
98  /// Implementation type of the btree_base
101 
102  /// Function class comparing two value_type pairs.
103  typedef typename btree_impl::value_compare value_compare;
104 
105  /// Size type used to count keys
107 
108  /// Small structure containing statistics about the tree
109  typedef typename btree_impl::tree_stats tree_stats;
110 
111 public:
112  // *** Static Constant Options and Values of the B+ Tree
113 
114  /// Base B+ tree parameter: The number of key/data slots in each leaf
115  static const unsigned short leafslotmax = btree_impl::leafslotmax;
116 
117  /// Base B+ tree parameter: The number of key slots in each inner node,
118  /// this can differ from slots in each leaf.
119  static const unsigned short innerslotmax = btree_impl::innerslotmax;
120 
121  /// Computed B+ tree parameter: The minimum number of key/data slots used
122  /// in a leaf. If fewer slots are used, the leaf will be merged or slots
123  /// shifted from it's siblings.
124  static const unsigned short minleafslots = btree_impl::minleafslots;
125 
126  /// Computed B+ tree parameter: The minimum number of key slots used
127  /// in an inner node. If fewer slots are used, the inner node will be
128  /// merged or slots shifted from it's siblings.
129  static const unsigned short mininnerslots = btree_impl::mininnerslots;
130 
131  /// Debug parameter: Enables expensive and thorough checking of the B+ tree
132  /// invariants after each insert/erase operation.
133  static const bool selfverify = btree_impl::selfverify;
134 
135  /// Debug parameter: Prints out lots of debug information about how the
136  /// algorithms change the tree. Requires the header file to be compiled
137  /// with BTREE_DEBUG and the key type must be std::ostream printable.
138  static const bool debug = btree_impl::debug;
139 
140  /// Operational parameter: Allow duplicate keys in the btree.
142 
143 public:
144  // *** Iterators and Reverse Iterators
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::iterator iterator;
149 
150  /// STL-like iterator object for B+ tree items. The iterator points to a
151  /// specific slot number in a leaf.
152  typedef typename btree_impl::const_iterator const_iterator;
153 
154  /// create mutable reverse iterator by using STL magic
155  typedef typename btree_impl::reverse_iterator reverse_iterator;
156 
157  /// create constant reverse iterator by using STL magic
158  typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
159 
160 private:
161  // *** Tree Implementation Object
162 
163  /// The contained implementation object
164  btree_impl tree;
165 
166 public:
167  // *** Constructors and Destructor
168 
169  /// Default constructor initializing an empty B+ tree with the standard key
170  /// comparison function
171  explicit inline btree_multimap(const allocator_type &alloc = allocator_type())
172  : tree(alloc)
173  {
174  }
175 
176  /// Constructor initializing an empty B+ tree with a special key
177  /// comparison object
178  explicit inline btree_multimap(const key_compare &kcf,
179  const allocator_type &alloc = allocator_type())
180  : tree(kcf, alloc)
181  {
182  }
183 
184  /// Constructor initializing a B+ tree with the range [first,last)
185  template <class InputIterator>
186  inline btree_multimap(InputIterator first, InputIterator last,
187  const allocator_type &alloc = allocator_type())
188  : tree(first, last, alloc)
189  {
190  }
191 
192  /// Constructor initializing a B+ tree with the range [first,last) and a
193  /// special key comparison object
194  template <class InputIterator>
195  inline btree_multimap(InputIterator first, InputIterator last, const key_compare &kcf,
196  const allocator_type &alloc = allocator_type())
197  : tree(first, last, kcf, alloc)
198  {
199  }
200 
201  /// Frees up all used B+ tree memory pages
203  {
204  }
205 
206  /// Fast swapping of two identical B+ tree objects.
207  void swap(self& from)
208  {
209  std::swap(tree, from.tree);
210  }
211 
212 public:
213  // *** Key and Value Comparison Function Objects
214 
215  /// Constant access to the key comparison object sorting the B+ tree
216  inline key_compare key_comp() const
217  {
218  return tree.key_comp();
219  }
220 
221  /// Constant access to a constructed value_type comparison object. required
222  /// by the STL
223  inline value_compare value_comp() const
224  {
225  return tree.value_comp();
226  }
227 
228 public:
229  // *** Allocators
230 
231  /// Return the base node allocator provided during construction.
232  allocator_type get_allocator() const
233  {
234  return tree.get_allocator();
235  }
236 
237 public:
238  // *** Fast Destruction of the B+ Tree
239 
240  /// Frees all key/data pairs and all nodes of the tree
241  void clear()
242  {
243  tree.clear();
244  }
245 
246 public:
247  // *** STL Iterator Construction Functions
248 
249  /// Constructs a read/data-write iterator that points to the first slot in
250  /// the first leaf of the B+ tree.
251  inline iterator begin()
252  {
253  return tree.begin();
254  }
255 
256  /// Constructs a read/data-write iterator that points to the first invalid
257  /// slot in the last leaf of the B+ tree.
258  inline iterator end()
259  {
260  return tree.end();
261  }
262 
263  /// Constructs a read-only constant iterator that points to the first slot
264  /// in the first leaf of the B+ tree.
265  inline const_iterator begin() const
266  {
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  inline const_iterator end() const
273  {
274  return tree.end();
275  }
276 
277  /// Constructs a read/data-write reverse iterator that points to the first
278  /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
279  inline reverse_iterator rbegin()
280  {
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.
286  inline reverse_iterator rend()
287  {
288  return tree.rend();
289  }
290 
291  /// Constructs a read-only reverse iterator that points to the first
292  /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
293  inline const_reverse_iterator rbegin() const
294  {
295  return tree.rbegin();
296  }
297 
298  /// Constructs a read-only reverse iterator that points to the first slot
299  /// in the first leaf of the B+ tree. Uses STL magic.
300  inline const_reverse_iterator rend() const
301  {
302  return tree.rend();
303  }
304 
305 public:
306  // *** Access Functions to the Item Count
307 
308  /// Return the number of key/data pairs in the B+ tree
309  inline size_type size() const
310  {
311  return tree.size();
312  }
313 
314  /// Returns true if there is at least one key/data pair in the B+ tree
315  inline bool empty() const
316  {
317  return tree.empty();
318  }
319 
320  /// Returns the largest possible size of the B+ Tree. This is just a
321  /// function required by the STL standard, the B+ Tree can hold more items.
322  inline size_type max_size() const
323  {
324  return tree.max_size();
325  }
326 
327  /// Return a const reference to the current statistics.
328  inline const tree_stats& get_stats() const
329  {
330  return tree.get_stats();
331  }
332 
333 public:
334  // *** Standard Access Functions Querying the Tree by Descending to a Leaf
335 
336  /// Non-STL function checking whether a key is in the B+ tree. The same as
337  /// (find(k) != end()) or (count() != 0).
338  bool exists(const key_type &key) const
339  {
340  return tree.exists(key);
341  }
342 
343  /// Tries to locate a key in the B+ tree and returns an iterator to the
344  /// key/data slot if found. If unsuccessful it returns end().
345  iterator find(const key_type &key)
346  {
347  return tree.find(key);
348  }
349 
350  /// Tries to locate a key in the B+ tree and returns an constant iterator
351  /// to the key/data slot if found. If unsuccessful it returns end().
352  const_iterator find(const key_type &key) const
353  {
354  return tree.find(key);
355  }
356 
357  /// Tries to locate a key in the B+ tree and returns the number of
358  /// identical key entries found.
359  size_type count(const key_type &key) const
360  {
361  return tree.count(key);
362  }
363 
364  /// Searches the B+ tree and returns an iterator to the first pair
365  /// equal to or greater than key, or end() if all keys are smaller.
366  iterator lower_bound(const key_type& key)
367  {
368  return tree.lower_bound(key);
369  }
370 
371  /// Searches the B+ tree and returns a constant iterator to the
372  /// first pair equal to or greater than key, or end() if all keys
373  /// are smaller.
374  const_iterator lower_bound(const key_type& key) const
375  {
376  return tree.lower_bound(key);
377  }
378 
379  /// Searches the B+ tree and returns an iterator to the first pair
380  /// greater than key, or end() if all keys are smaller or equal.
381  iterator upper_bound(const key_type& key)
382  {
383  return tree.upper_bound(key);
384  }
385 
386  /// Searches the B+ tree and returns a constant iterator to the
387  /// first pair greater than key, or end() if all keys are smaller
388  /// or equal.
389  const_iterator upper_bound(const key_type& key) const
390  {
391  return tree.upper_bound(key);
392  }
393 
394  /// Searches the B+ tree and returns both lower_bound() and upper_bound().
395  inline std::pair<iterator, iterator> equal_range(const key_type& key)
396  {
397  return tree.equal_range(key);
398  }
399 
400  /// Searches the B+ tree and returns both lower_bound() and upper_bound().
401  inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
402  {
403  return tree.equal_range(key);
404  }
405 
406 public:
407  // *** B+ Tree Object Comparison Functions
408 
409  /// Equality relation of B+ trees of the same type. B+ trees of the same
410  /// size and equal elements (both key and data) are considered
411  /// equal. Beware of the random ordering of duplicate keys.
412  inline bool operator==(const self &other) const
413  {
414  return (tree == other.tree);
415  }
416 
417  /// Inequality relation. Based on operator==.
418  inline bool operator!=(const self &other) const
419  {
420  return (tree != other.tree);
421  }
422 
423  /// Total ordering relation of B+ trees of the same type. It uses
424  /// std::lexicographical_compare() for the actual comparison of elements.
425  inline bool operator<(const self &other) const
426  {
427  return (tree < other.tree);
428  }
429 
430  /// Greater relation. Based on operator<.
431  inline bool operator>(const self &other) const
432  {
433  return (tree > other.tree);
434  }
435 
436  /// Less-equal relation. Based on operator<.
437  inline bool operator<=(const self &other) const
438  {
439  return (tree <= other.tree);
440  }
441 
442  /// Greater-equal relation. Based on operator<.
443  inline bool operator>=(const self &other) const
444  {
445  return (tree >= other.tree);
446  }
447 
448 public:
449  /// *** Fast Copy: Assign Operator and Copy Constructors
450 
451  /// Assignment operator. All the key/data pairs are copied
452  inline self& operator= (const self &other)
453  {
454  if (this != &other)
455  {
456  tree = other.tree;
457  }
458  return *this;
459  }
460 
461  /// Copy constructor. The newly initialized B+ tree object will contain a
462  /// copy or all key/data pairs.
463  inline btree_multimap(const self &other)
464  : tree(other.tree)
465  {
466  }
467 
468 public:
469  // *** Public Insertion Functions
470 
471  /// Attempt to insert a key/data pair into the B+ tree. As this tree allows
472  /// duplicates insertion never fails.
473  inline iterator insert(const value_type& x)
474  {
475  return tree.insert2(x.first, x.second).first;
476  }
477 
478  /// Attempt to insert a key/data pair into the B+ tree. Beware that if
479  /// key_type == data_type, then the template iterator insert() is called
480  /// instead. As this tree allows duplicates insertion never fails.
481  inline iterator insert(const key_type& key, const data_type& data)
482  {
483  return tree.insert2(key, data).first;
484  }
485 
486  /// Attempt to insert a key/data pair into the B+ tree. This function is the
487  /// same as the other insert, however if key_type == data_type then the
488  /// non-template function cannot be called. As this tree allows duplicates
489  /// insertion never fails.
490  inline iterator insert2(const key_type& key, const data_type& data)
491  {
492  return tree.insert2(key, data).first;
493  }
494 
495  /// Attempt to insert a key/data pair into the B+ tree. The iterator hint
496  /// is currently ignored by the B+ tree insertion routine.
497  inline iterator insert(iterator hint, const value_type &x)
498  {
499  return tree.insert2(hint, x.first, x.second);
500  }
501 
502  /// Attempt to insert a key/data pair into the B+ tree. The iterator hint is
503  /// currently ignored by the B+ tree insertion routine.
504  inline iterator insert2(iterator hint, const key_type& key, const data_type& data)
505  {
506  return tree.insert2(hint, key, data);
507  }
508 
509  /// Attempt to insert the range [first,last) of value_type pairs into the B+
510  /// tree. Each key/data pair is inserted individually.
511  template <typename InputIterator>
512  inline void insert(InputIterator first, InputIterator last)
513  {
514  return tree.insert(first, last);
515  }
516 
517  /// Bulk load a sorted range [first,last). Loads items into leaves and
518  /// constructs a B-tree above them. The tree must be empty when calling
519  /// this function.
520  template <typename Iterator>
521  inline void bulk_load(Iterator first, Iterator last)
522  {
523  return tree.bulk_load(first, last);
524  }
525 
526 public:
527  // *** Public Erase Functions
528 
529  /// Erases one (the first) of the key/data pairs associated with the given
530  /// key.
531  bool erase_one(const key_type &key)
532  {
533  return tree.erase_one(key);
534  }
535 
536  /// Erases all the key/data pairs associated with the given key. This is
537  /// implemented using erase_one() and thus not very efficient.
538  size_type erase(const key_type &key)
539  {
540  return tree.erase(key);
541  }
542 
543  /// Erase the key/data pair referenced by the iterator.
544  void erase(iterator iter)
545  {
546  return tree.erase(iter);
547  }
548 
549 #ifdef BTREE_TODO
550  /// Erase all key/data pairs in the range [first,last). This function is
551  /// currently not implemented by the B+ Tree.
552  void erase(iterator /* first */, iterator /* last */)
553  {
554  abort();
555  }
556 #endif
557 
558 #ifdef BTREE_DEBUG
559 public:
560  // *** Debug Printing
561 
562  /// Print out the B+ tree structure with keys onto the given ostream. This function
563  /// requires that the header is compiled with BTREE_DEBUG and that key_type
564  /// is printable via std::ostream.
565  void print(std::ostream &os) const
566  {
567  tree.print(os);
568  }
569 
570  /// Print out only the leaves via the double linked list.
571  void print_leaves(std::ostream &os) const
572  {
573  tree.print_leaves(os);
574  }
575 #endif
576 
577 public:
578  // *** Verification of B+ Tree Invariants
579 
580  /// Run a thorough verification of all B+ tree invariants. The program
581  /// aborts via BTREE_ASSERT() if something is wrong.
582  void verify() const
583  {
584  tree.verify();
585  }
586 
587 public:
588 
589  /// Dump the contents of the B+ tree out onto an ostream as a binary
590  /// image. The image contains memory pointers which will be fixed when the
591  /// image is restored. For this to work your key_type and data_type must be
592  /// integral types and contain no pointers or references.
593  void dump(std::ostream &os) const
594  {
595  tree.dump(os);
596  }
597 
598  /// Restore a binary image of a dumped B+ tree from an istream. The B+ tree
599  /// pointers are fixed using the dump order. For dump and restore to work
600  /// your key_type and data_type must be integral types and contain no
601  /// pointers or references. Returns true if the restore was successful.
602  bool restore(std::istream &is)
603  {
604  return tree.restore(is);
605  }
606 };
607 
608 } // namespace stx
609 
610 #endif // _STX_BTREE_MULTIMAP_H_
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...
Definition: btree.h:1573
void dump(std::ostream &os) const
Dump the contents of the B+ tree out onto an ostream as a binary image.
Definition: btree.h:3843
size_type max_size() const
Returns the largest possible size of the B+ Tree.
static const unsigned short minleafslots
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
btree_impl::reverse_iterator reverse_iterator
create mutable reverse iterator by using STL magic
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
Definition: btree.h:1580
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.h:1898
btree_impl::const_iterator const_iterator
STL-like iterator object for B+ tree items.
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
Definition: btree.h:1757
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 struct tree_stats & get_stats() const
Return a const reference to the current statistics.
Definition: btree.h:1747
static const unsigned short leafslotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
Definition: btree.h:225
Basic class implementing a base B+ tree data structure in memory.
Definition: btree.h:163
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
Definition: btree.h:1734
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
allocator_type get_allocator() const
Return the base node allocator provided during construction.
_Alloc allocator_type
Fifth template parameter: STL allocator.
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
Definition: btree.h:3860
iterator insert2(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Definition: btree.h:2619
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
Definition: btree.h:2596
btree_impl::const_reverse_iterator const_reverse_iterator
create constant reverse iterator by using STL magic
void erase(iterator iter)
Erase the key/data pair referenced by the iterator.
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
bool operator<(const self &other) const
Total ordering relation of B+ trees of the same type.
STX - Some Template Extensions namespace.
Definition: btree.h:81
static const bool selfverify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
Definition: btree.h:243
const tree_stats & get_stats() const
Return a const reference to the current statistics.
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...
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition: btree.h:1940
void dump(std::ostream &os) const
Dump the contents of the B+ tree out onto an ostream as a binary image.
size_type size() const
Return the number of key/data pairs in 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...
Definition: btree.h:1822
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
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...
static const unsigned short leafslotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
void bulk_load(Iterator first, Iterator last)
Bulk load a sorted range [first,last).
bool operator!=(const self &other) const
Inequality relation. Based on operator==.
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...
const_reverse_iterator rbegin() const
Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the...
iterator insert(const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
bool operator==(const self &other) const
Equality relation of B+ trees of the same type.
btree_impl::tree_stats tree_stats
Small structure containing statistics about the tree.
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
Definition: btree.h:2401
btree_impl::value_compare value_compare
Function class comparing two value_type pairs.
_Compare key_compare
Third template parameter: Key comparison function object.
void clear()
Frees all key/data pairs and all nodes of the tree.
Definition: btree.h:1527
#define BTREE_FRIENDS
The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.
Definition: btree.h:77
btree_multimap(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last)
size_type max_size() const
Returns the largest possible size of the B+ Tree.
Definition: btree.h:1741
static const unsigned short mininnerslots
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
Definition: btree.h:239
void print(std::ostream &os) const
Print out the B+ tree structure with keys onto the given ostream.
iterator insert2(iterator hint, const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
_Key key_type
First template parameter: The key type of the btree.
void swap(self &from)
Fast swapping of two identical B+ tree objects.
btree_multimap(const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing an empty B+ tree with a special key comparison object.
_Data data_type
Second template parameter: The data type associated with each key.
std::pair< iterator, bool > insert(const pair_type &x)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree.h:2088
static const unsigned short mininnerslots
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
btree_impl tree
The contained implementation object.
void erase(iterator, iterator)
Erase all key/data pairs in the range [first,last).
iterator insert(iterator hint, const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
Definition: btree.h:1395
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
Definition: btree.h:1402
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...
void clear()
Frees all key/data pairs and all nodes of the tree.
btree_impl::iterator iterator
STL-like iterator object for B+ tree items.
static const bool allow_duplicates
Sixth template parameter: Allow duplicate keys in the B+ tree.
Definition: btree.h:191
btree_multimap(const self &other)
Copy constructor.
bool operator<=(const self &other) const
Less-equal relation. Based on operator<.
const_iterator end() const
Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of th...
iterator insert(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
void print(std::ostream &os) const
Print out the B+ tree structure with keys onto the given ostream.
Definition: btree.h:3556
void verify() const
Run a thorough verification of all B+ tree invariants.
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...
const_iterator begin() const
Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tr...
static const bool selfverify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
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.h:1778
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
void print_leaves(std::ostream &os) const
Print out only the leaves via the double linked list.
Definition: btree.h:3564
size_type size() const
Return the number of key/data pairs in the B+ tree.
Definition: btree.h:1728
self & operator=(const self &other)
*** Fast Copy: Assign Operator and Copy Constructors
static const bool allow_duplicates
Operational parameter: Allow duplicate keys in the btree.
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...
bool operator>(const self &other) const
Greater relation. Based on operator<.
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree...
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
Definition: btree.h:1601
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree...
Definition: btree.h:248
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...
Definition: btree.h:229
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
void verify() const
Run a thorough verification of all B+ tree invariants.
Definition: btree.h:3630
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...
bool operator>=(const self &other) const
Greater-equal relation. Based on operator<.
void insert(InputIterator first, InputIterator last)
Attempt to insert the range [first,last) of value_type pairs into the B+ tree.
std::pair< iterator, bool > insert2(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree.h:2106
_Traits traits
Fourth template parameter: Traits object used to define more parameters of the B+ tree...
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf 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.
Specialized B+ tree template class implementing STL&#39;s multimap container.
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Definition: btree.h:1445
btree_multimap(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function...
stx::btree< key_type, data_type, value_type, key_compare, traits, true, allocator_type, false > btree_impl
Implementation type of the btree_base.
std::pair< key_type, data_type > value_type
Construct the STL-required value_type as a composition pair of key and data types.
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
Definition: btree.h:1608
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
static const unsigned short minleafslots
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
Definition: btree.h:234
void print_leaves(std::ostream &os) const
Print out only the leaves via the double linked list.
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...
~btree_multimap()
Frees up all used B+ tree memory pages.
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().
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...
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.h:1855
Contains the main B+ tree implementation template class btree.