STX B+ Tree Template Classes  0.9
btree_multiset.h
Go to the documentation of this file.
1 /** \file btree_multiset.h
2  * Contains the specialized B+ tree template class btree_multiset
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_MULTISET_H_
35 #define _STX_BTREE_MULTISET_H_
36 
37 #include <stx/btree.h>
38 
39 namespace stx {
40 
41 /** @brief Specialized B+ tree template class implementing STL's multiset
42  * container.
43  *
44  * Implements the STL multiset using a B+ tree. It can be used as a drop-in
45  * replacement for std::multiset. 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  * It is somewhat inefficient to implement a multiset using a B+ tree, a plain
51  * B tree would hold fewer copies of the keys.
52  *
53  * The set class is derived from the base implementation class btree by
54  * specifying an empty struct as data_type. All function are adapted to provide
55  * the inner class with placeholder objects. Most tricky to get right were the
56  * return type's of iterators which as value_type should be the same as
57  * key_type, and not a pair of key and dummy-struct. This is taken case of
58  * using some template magic in the btree class.
59  */
60 template <typename _Key,
61  typename _Compare = std::less<_Key>,
62  typename _Traits = btree_default_set_traits<_Key>,
63  typename _Alloc = std::allocator<_Key> >
65 {
66 public:
67  // *** Template Parameter Types
68 
69  /// First template parameter: The key type of the btree. This is stored in
70  /// inner nodes and leaves
71  typedef _Key key_type;
72 
73  /// Second template parameter: Key comparison function object
74  typedef _Compare key_compare;
75 
76  /// Third template parameter: Traits object used to define more parameters
77  /// of the B+ tree
78  typedef _Traits traits;
79 
80  /// Fourth 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 private:
89  // *** The Data_Type
90 
91  /// The empty struct used as a placeholder for the data_type.
92  struct empty_struct
93  {
94  };
95 
96 public:
97  // *** Constructed Types
98 
99  /// The empty data_type
100  typedef struct empty_struct data_type;
101 
102  /// Construct the set value_type: the key_type.
103  typedef key_type value_type;
104 
105  /// Typedef of our own type
107 
108  /// Implementation type of the btree_base
111 
112  /// Function class comparing two value_type keys.
113  typedef typename btree_impl::value_compare value_compare;
114 
115  /// Size type used to count keys
117 
118  /// Small structure containing statistics about the tree
119  typedef typename btree_impl::tree_stats tree_stats;
120 
121 public:
122  // *** Static Constant Options and Values of the B+ Tree
123 
124  /// Base B+ tree parameter: The number of key/data slots in each leaf
125  static const unsigned short leafslotmax = btree_impl::leafslotmax;
126 
127  /// Base B+ tree parameter: The number of key slots in each inner node,
128  /// this can differ from slots in each leaf.
129  static const unsigned short innerslotmax = btree_impl::innerslotmax;
130 
131  /// Computed B+ tree parameter: The minimum number of key slots used in a
132  /// leaf. If fewer slots are used, the leaf will be merged or slots shifted
133  /// from it's siblings.
134  static const unsigned short minleafslots = btree_impl::minleafslots;
135 
136  /// Computed B+ tree parameter: The minimum number of key slots used
137  /// in an inner node. If fewer slots are used, the inner node will be
138  /// merged or slots shifted from it's siblings.
139  static const unsigned short mininnerslots = btree_impl::mininnerslots;
140 
141  /// Debug parameter: Enables expensive and thorough checking of the B+ tree
142  /// invariants after each insert/erase operation.
143  static const bool selfverify = btree_impl::selfverify;
144 
145  /// Debug parameter: Prints out lots of debug information about how the
146  /// algorithms change the tree. Requires the header file to be compiled
147  /// with BTREE_DEBUG and the key type must be std::ostream printable.
148  static const bool debug = btree_impl::debug;
149 
150  /// Operational parameter: Allow duplicate keys in the btree.
152 
153 public:
154  // *** Iterators and Reverse Iterators
155 
156  /// STL-like iterator object for B+ tree items. The iterator points to a
157  /// specific slot number in a leaf.
158  typedef typename btree_impl::iterator iterator;
159 
160  /// STL-like iterator object for B+ tree items. The iterator points to a
161  /// specific slot number in a leaf.
162  typedef typename btree_impl::const_iterator const_iterator;
163 
164  /// create mutable reverse iterator by using STL magic
165  typedef typename btree_impl::reverse_iterator reverse_iterator;
166 
167  /// create constant reverse iterator by using STL magic
168  typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
169 
170 private:
171  // *** Tree Implementation Object
172 
173  /// The contained implementation object
174  btree_impl tree;
175 
176 public:
177  // *** Constructors and Destructor
178 
179  /// Default constructor initializing an empty B+ tree with the standard key
180  /// comparison function
181  explicit inline btree_multiset(const allocator_type &alloc = allocator_type())
182  : tree(alloc)
183  {
184  }
185 
186  /// Constructor initializing an empty B+ tree with a special key
187  /// comparison object
188  explicit inline btree_multiset(const key_compare &kcf,
189  const allocator_type &alloc = allocator_type())
190  : tree(kcf, alloc)
191  {
192  }
193 
194  /// Constructor initializing a B+ tree with the range [first,last)
195  template <class InputIterator>
196  inline btree_multiset(InputIterator first, InputIterator last,
197  const allocator_type &alloc = allocator_type())
198  : tree(alloc)
199  {
200  insert(first, last);
201  }
202 
203  /// Constructor initializing a B+ tree with the range [first,last) and a
204  /// special key comparison object
205  template <class InputIterator>
206  inline btree_multiset(InputIterator first, InputIterator last, const key_compare &kcf,
207  const allocator_type &alloc = allocator_type())
208  : tree(kcf, alloc)
209  {
210  insert(first, last);
211  }
212 
213  /// Frees up all used B+ tree memory pages
215  {
216  }
217 
218  /// Fast swapping of two identical B+ tree objects.
219  void swap(self& from)
220  {
221  std::swap(tree, from.tree);
222  }
223 
224 public:
225  // *** Key and Value Comparison Function Objects
226 
227  /// Constant access to the key comparison object sorting the B+ tree
228  inline key_compare key_comp() const
229  {
230  return tree.key_comp();
231  }
232 
233  /// Constant access to a constructed value_type comparison object. Required
234  /// by the STL
235  inline value_compare value_comp() const
236  {
237  return tree.value_comp();
238  }
239 
240 public:
241  // *** Allocators
242 
243  /// Return the base node allocator provided during construction.
244  allocator_type get_allocator() const
245  {
246  return tree.get_allocator();
247  }
248 
249 public:
250  // *** Fast Destruction of the B+ Tree
251 
252  /// Frees all keys and all nodes of the tree
253  void clear()
254  {
255  tree.clear();
256  }
257 
258 public:
259  // *** STL Iterator Construction Functions
260 
261  /// Constructs a read/data-write iterator that points to the first slot in
262  /// the first leaf of the B+ tree.
263  inline iterator begin()
264  {
265  return tree.begin();
266  }
267 
268  /// Constructs a read/data-write iterator that points to the first invalid
269  /// slot in the last leaf of the B+ tree.
270  inline iterator end()
271  {
272  return tree.end();
273  }
274 
275  /// Constructs a read-only constant iterator that points to the first slot
276  /// in the first leaf of the B+ tree.
277  inline const_iterator begin() const
278  {
279  return tree.begin();
280  }
281 
282  /// Constructs a read-only constant iterator that points to the first
283  /// invalid slot in the last leaf of the B+ tree.
284  inline const_iterator end() const
285  {
286  return tree.end();
287  }
288 
289  /// Constructs a read/data-write reverse iterator that points to the first
290  /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
291  inline reverse_iterator rbegin()
292  {
293  return tree.rbegin();
294  }
295 
296  /// Constructs a read/data-write reverse iterator that points to the first
297  /// slot in the first leaf of the B+ tree. Uses STL magic.
298  inline reverse_iterator rend()
299  {
300  return tree.rend();
301  }
302 
303  /// Constructs a read-only reverse iterator that points to the first
304  /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
305  inline const_reverse_iterator rbegin() const
306  {
307  return tree.rbegin();
308  }
309 
310  /// Constructs a read-only reverse iterator that points to the first slot
311  /// in the first leaf of the B+ tree. Uses STL magic.
312  inline const_reverse_iterator rend() const
313  {
314  return tree.rend();
315  }
316 
317 public:
318  // *** Access Functions to the Item Count
319 
320  /// Return the number of keys in the B+ tree
321  inline size_type size() const
322  {
323  return tree.size();
324  }
325 
326  /// Returns true if there is at least one key in the B+ tree
327  inline bool empty() const
328  {
329  return tree.empty();
330  }
331 
332  /// Returns the largest possible size of the B+ Tree. This is just a
333  /// function required by the STL standard, the B+ Tree can hold more items.
334  inline size_type max_size() const
335  {
336  return tree.max_size();
337  }
338 
339  /// Return a const reference to the current statistics.
340  inline const tree_stats& get_stats() const
341  {
342  return tree.get_stats();
343  }
344 
345 public:
346  // *** Standard Access Functions Querying the Tree by Descending to a Leaf
347 
348  /// Non-STL function checking whether a key is in the B+ tree. The same as
349  /// (find(k) != end()) or (count() != 0).
350  bool exists(const key_type &key) const
351  {
352  return tree.exists(key);
353  }
354 
355  /// Tries to locate a key in the B+ tree and returns an iterator to the
356  /// key slot if found. If unsuccessful it returns end().
357  iterator find(const key_type &key)
358  {
359  return tree.find(key);
360  }
361 
362  /// Tries to locate a key in the B+ tree and returns an constant iterator
363  /// to the key slot if found. If unsuccessful it returns end().
364  const_iterator find(const key_type &key) const
365  {
366  return tree.find(key);
367  }
368 
369  /// Tries to locate a key in the B+ tree and returns the number of
370  /// identical key entries found.
371  size_type count(const key_type &key) const
372  {
373  return tree.count(key);
374  }
375 
376  /// Searches the B+ tree and returns an iterator to the first pair
377  /// equal to or greater than key, or end() if all keys are smaller.
378  iterator lower_bound(const key_type& key)
379  {
380  return tree.lower_bound(key);
381  }
382 
383  /// Searches the B+ tree and returns a constant iterator to the
384  /// first pair equal to or greater than key, or end() if all keys
385  /// are smaller.
386  const_iterator lower_bound(const key_type& key) const
387  {
388  return tree.lower_bound(key);
389  }
390 
391  /// Searches the B+ tree and returns an iterator to the first pair
392  /// greater than key, or end() if all keys are smaller or equal.
393  iterator upper_bound(const key_type& key)
394  {
395  return tree.upper_bound(key);
396  }
397 
398  /// Searches the B+ tree and returns a constant iterator to the
399  /// first pair greater than key, or end() if all keys are smaller
400  /// or equal.
401  const_iterator upper_bound(const key_type& key) const
402  {
403  return tree.upper_bound(key);
404  }
405 
406  /// Searches the B+ tree and returns both lower_bound() and upper_bound().
407  inline std::pair<iterator, iterator> equal_range(const key_type& key)
408  {
409  return tree.equal_range(key);
410  }
411 
412  /// Searches the B+ tree and returns both lower_bound() and upper_bound().
413  inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
414  {
415  return tree.equal_range(key);
416  }
417 
418 public:
419  // *** B+ Tree Object Comparison Functions
420 
421  /// Equality relation of B+ trees of the same type. B+ trees of the same
422  /// size and equal key (counts) are considered equal.
423  inline bool operator==(const self &other) const
424  {
425  return (tree == other.tree);
426  }
427 
428  /// Inequality relation. Based on operator==.
429  inline bool operator!=(const self &other) const
430  {
431  return (tree != other.tree);
432  }
433 
434  /// Total ordering relation of B+ trees of the same type. It uses
435  /// std::lexicographical_compare() for the actual comparison of elements.
436  inline bool operator<(const self &other) const
437  {
438  return (tree < other.tree);
439  }
440 
441  /// Greater relation. Based on operator<.
442  inline bool operator>(const self &other) const
443  {
444  return (tree > other.tree);
445  }
446 
447  /// Less-equal relation. Based on operator<.
448  inline bool operator<=(const self &other) const
449  {
450  return (tree <= other.tree);
451  }
452 
453  /// Greater-equal relation. Based on operator<.
454  inline bool operator>=(const self &other) const
455  {
456  return (tree >= other.tree);
457  }
458 
459 public:
460  /// *** Fast Copy: Assign Operator and Copy Constructors
461 
462  /// Assignment operator. All the keys are copied
463  inline self& operator= (const self &other)
464  {
465  if (this != &other)
466  {
467  tree = other.tree;
468  }
469  return *this;
470  }
471 
472  /// Copy constructor. The newly initialized B+ tree object will contain a
473  /// copy of all keys.
474  inline btree_multiset(const self &other)
475  : tree(other.tree)
476  {
477  }
478 
479 public:
480  // *** Public Insertion Functions
481 
482  /// Attempt to insert a key into the B+ tree. As this set allows
483  /// duplicates, this function never fails.
484  inline iterator insert(const key_type& x)
485  {
486  return tree.insert2(x, data_type()).first;
487  }
488 
489  /// Attempt to insert a key into the B+ tree. The iterator hint is
490  /// currently ignored by the B+ tree insertion routine.
491  inline iterator insert(iterator hint, const key_type &x)
492  {
493  return tree.insert2(hint, x, data_type());
494  }
495 
496  /// Attempt to insert the range [first,last) of key_type into the B+
497  /// tree. Each key is inserted individually.
498  template <typename InputIterator>
499  inline void insert(InputIterator first, InputIterator last)
500  {
501  InputIterator iter = first;
502  while(iter != last)
503  {
504  insert(*iter);
505  ++iter;
506  }
507  }
508 
509  /// Bulk load a sorted range [first,last). Loads items into leaves and
510  /// constructs a B-tree above them. The tree must be empty when calling
511  /// this function.
512  template <typename Iterator>
513  inline void bulk_load(Iterator first, Iterator last)
514  {
515  return tree.bulk_load(first, last);
516  }
517 
518 public:
519  // *** Public Erase Functions
520 
521  /// Erases one (the first) entry of the given key.
522  bool erase_one(const key_type &key)
523  {
524  return tree.erase_one(key);
525  }
526 
527  /// Erases all the entries of the given key. This is implemented using
528  /// erase_one() and thus not very efficient.
529  size_type erase(const key_type &key)
530  {
531  return tree.erase(key);
532  }
533 
534  /// Erase the key/data pair referenced by the iterator.
535  void erase(iterator iter)
536  {
537  return tree.erase(iter);
538  }
539 
540 #ifdef BTREE_TODO
541  /// Erase all keys in the range [first,last). This function is currently
542  /// not implemented by the B+ Tree.
543  void erase(iterator /* first */, iterator /* last */)
544  {
545  abort();
546  }
547 #endif
548 
549 #ifdef BTREE_DEBUG
550 public:
551  // *** Debug Printing
552 
553  /// Print out the B+ tree structure with keys onto the given ostream. This function
554  /// requires that the header is compiled with BTREE_DEBUG and that key_type
555  /// is printable via std::ostream.
556  void print(std::ostream &os) const
557  {
558  tree.print(os);
559  }
560 
561  /// Print out only the leaves via the double linked list.
562  void print_leaves(std::ostream &os) const
563  {
564  tree.print_leaves(os);
565  }
566 #endif
567 
568 public:
569  // *** Verification of B+ Tree Invariants
570 
571  /// Run a thorough verification of all B+ tree invariants. The program
572  /// aborts via BTREE_ASSERT() if something is wrong.
573  void verify() const
574  {
575  tree.verify();
576  }
577 
578 public:
579 
580  /// Dump the contents of the B+ tree out onto an ostream as a binary
581  /// image. The image contains memory pointers which will be fixed when the
582  /// image is restored. For this to work your key_type must be an integral
583  /// type and contain no pointers or references.
584  void dump(std::ostream &os) const
585  {
586  tree.dump(os);
587  }
588 
589  /// Restore a binary image of a dumped B+ tree from an istream. The B+ tree
590  /// pointers are fixed using the dump order. For dump and restore to work
591  /// your key_type must be an integral type and contain no pointers or
592  /// references. Returns true if the restore was successful.
593  bool restore(std::istream &is)
594  {
595  return tree.restore(is);
596  }
597 };
598 
599 } // namespace stx
600 
601 #endif // _STX_BTREE_MULTISET_H_
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 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 count(const key_type &key) const
Tries to locate a key in the B+ tree and returns the number of identical key entries found...
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree...
Definition: btree.h:248
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
void verify() const
Run a thorough verification of all B+ tree invariants.
Definition: btree.h:3630
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
void print(std::ostream &os) const
Print out the B+ tree structure with keys onto the given ostream.
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
size_type erase(const key_type &key)
Erases all the entries of the given key.
bool operator>=(const self &other) const
Greater-equal relation. Based on operator<.
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
Contains the main B+ tree implementation template class btree.
void erase(iterator, iterator)
Erase all keys in the range [first,last).
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
Definition: btree.h:3860
static const bool allow_duplicates
Sixth template parameter: Allow duplicate keys in the B+ tree.
Definition: btree.h:191
btree_impl::const_iterator const_iterator
STL-like iterator object for B+ tree items.
btree_impl::value_compare value_compare
Function class comparing two value_type keys.
_Compare key_compare
Second template parameter: Key comparison function object.
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
bool operator<=(const self &other) const
Less-equal relation. Based on operator<.
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Definition: btree.h:1445
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().
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
btree_multiset(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function...
void print_leaves(std::ostream &os) const
Print out only the leaves via the double linked list.
bool operator==(const self &other) const
Equality relation of B+ trees of the same type.
void clear()
Frees all keys and all nodes of the tree.
btree_multiset(const self &other)
Copy constructor.
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
self & operator=(const self &other)
*** Fast Copy: Assign Operator and Copy Constructors
btree_multiset(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last)
~btree_multiset()
Frees up all used B+ tree memory pages.
bool empty() const
Returns true if there is at least one key in the B+ tree.
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
allocator_type get_allocator() const
Return the base node allocator provided during construction.
static const unsigned short minleafslots
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
Definition: btree.h:234
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...
btree_impl::iterator iterator
STL-like iterator object for B+ tree items.
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
bool erase_one(const key_type &key)
Erases one (the first) entry of the given key.
static const unsigned short leafslotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
stx::btree< key_type, data_type, value_type, key_compare, traits, true, allocator_type, true > btree_impl
Implementation type of the btree_base.
void insert(InputIterator first, InputIterator last)
Attempt to insert the range [first,last) of key_type into the B+ tree.
static const unsigned short minleafslots
Computed B+ tree parameter: The minimum number of key slots used in a leaf.
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...
void print_leaves(std::ostream &os) const
Print out only the leaves via the double linked list.
Definition: btree.h:3564
_Traits traits
Third template parameter: Traits object used to define more parameters of the B+ tree.
bool operator>(const self &other) const
Greater relation. Based on operator<.
The empty struct used as a placeholder for the data_type.
static const bool allow_duplicates
Operational parameter: Allow duplicate keys in the btree.
void dump(std::ostream &os) const
Dump the contents of the B+ tree out onto an ostream as a binary image.
iterator insert(iterator hint, const key_type &x)
Attempt to insert a key into the B+ tree.
size_type size() const
Return the number of keys in 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
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...
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 unsigned short innerslotmax
Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...
void verify() const
Run a thorough verification of all B+ tree invariants.
btree_impl::const_reverse_iterator const_reverse_iterator
create constant reverse iterator by using STL magic
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
size_type max_size() const
Returns the largest possible size of the B+ Tree.
void erase(iterator iter)
Erase the key/data pair referenced by the iterator.
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...
void bulk_load(Iterator first, Iterator last)
Bulk load a sorted range [first,last).
static const unsigned short mininnerslots
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
Definition: btree.h:239
#define BTREE_FRIENDS
The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.
Definition: btree.h:77
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
Definition: btree.h:1395
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
bool operator!=(const self &other) const
Inequality relation. Based on operator==.
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
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.
STX - Some Template Extensions namespace.
Definition: btree.h:81
size_type max_size() const
Returns the largest possible size of the B+ Tree.
Definition: btree.h:1741
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
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...
const_iterator end() const
Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of th...
const_reverse_iterator rbegin() const
Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the...
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
void swap(self &from)
Fast swapping of two identical B+ tree objects.
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
btree_impl tree
The contained implementation object.
static const bool selfverify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
const struct tree_stats & get_stats() const
Return a const reference to the current statistics.
Definition: btree.h:1747
_Alloc allocator_type
Fourth template parameter: STL allocator.
void clear()
Frees all key/data pairs and all nodes of the tree.
Definition: btree.h:1527
btree_impl::size_type size_type
Size type used to count keys.
static const unsigned short leafslotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
Definition: btree.h:225
iterator insert(const key_type &x)
Attempt to insert a key into the B+ tree.
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 exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
Definition: btree.h:1757
btree_impl::reverse_iterator reverse_iterator
create mutable reverse iterator by using STL magic
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Definition: btree.h:2619
bool operator<(const self &other) const
Total ordering relation of B+ trees of the same type.
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
_Key key_type
First template parameter: The key type of the btree.
static const bool selfverify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
Definition: btree.h:243
size_type size() const
Return the number of key/data pairs in the B+ tree.
Definition: btree.h:1728
btree_multiset(const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing an empty B+ tree with a special key comparison object.
btree_impl::tree_stats tree_stats
Small structure containing statistics about the tree.
key_type value_type
Construct the set value_type: the key_type.
const tree_stats & get_stats() const
Return a const reference to the current statistics.
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
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
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
Definition: btree.h:1734
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.
Definition: btree.h:1402
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...
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
Definition: btree.h:2401
Basic class implementing a base B+ tree data structure in memory.
Definition: btree.h:163
struct empty_struct data_type
The empty data_type.
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
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree...
Specialized B+ tree template class implementing STL&#39;s multiset container.
static const unsigned short mininnerslots
Computed B+ tree parameter: The minimum number of key slots used in an inner node.