STX B+ Tree Template Classes  0.9
btree_set.h
Go to the documentation of this file.
1 /** \file btree_set.h
2  * Contains the specialized B+ tree template class btree_set
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_SET_H_
35 #define _STX_BTREE_SET_H_
36 
37 #include <stx/btree.h>
38 
39 namespace stx {
40 
41 /** @brief Specialized B+ tree template class implementing STL's set container.
42  *
43  * Implements the STL set using a B+ tree. It can be used as a drop-in
44  * replacement for std::set. Not all asymptotic time requirements are met in
45  * theory. The class has a traits class defining B+ tree properties like slots
46  * and self-verification. Furthermore an allocator can be specified for tree
47  * nodes.
48  *
49  * It is somewhat inefficient to implement a set using a B+ tree, a plain B
50  * tree would hold fewer copies of the keys.
51  *
52  * The set class is derived from the base implementation class btree by
53  * specifying an empty struct as data_type. All function are adapted to provide
54  * the inner class with placeholder objects. Most tricky to get right were the
55  * return type's of iterators which as value_type should be the same as
56  * key_type, and not a pair of key and dummy-struct. This is taken case of
57  * using some template magic in the btree class.
58  */
59 template <typename _Key,
60  typename _Compare = std::less<_Key>,
61  typename _Traits = btree_default_set_traits<_Key>,
62  typename _Alloc = std::allocator<_Key> >
63 class btree_set
64 {
65 public:
66  // *** Template Parameter Types
67 
68  /// First template parameter: The key type of the B+ tree. This is stored
69  /// in inner nodes and leaves
70  typedef _Key key_type;
71 
72  /// Second template parameter: Key comparison function object
73  typedef _Compare key_compare;
74 
75  /// Third template parameter: Traits object used to define more parameters
76  /// of the B+ tree
77  typedef _Traits traits;
78 
79  /// Fourth template parameter: STL allocator
80  typedef _Alloc allocator_type;
81 
82  /// The macro BTREE_FRIENDS can be used by outside class to access the B+
83  /// tree internals. This was added for wxBTreeDemo to be able to draw the
84  /// tree.
86 
87 private:
88  // *** The data_type
89 
90  /// \internal The empty struct used as a placeholder for the data_type
91  struct empty_struct
92  {
93  };
94 
95 public:
96  // *** Constructed Types
97 
98  /// The empty data_type
99  typedef struct empty_struct data_type;
100 
101  /// Construct the set value_type: the key_type.
102  typedef key_type value_type;
103 
104  /// Typedef of our own type
106 
107  /// Implementation type of the btree_base
110 
111  /// Function class comparing two value_type keys.
112  typedef typename btree_impl::value_compare value_compare;
113 
114  /// Size type used to count keys
116 
117  /// Small structure containing statistics about the tree
118  typedef typename btree_impl::tree_stats tree_stats;
119 
120 public:
121  // *** Static Constant Options and Values of the B+ Tree
122 
123  /// Base B+ tree parameter: The number of key slots in each leaf
124  static const unsigned short leafslotmax = btree_impl::leafslotmax;
125 
126  /// Base B+ tree parameter: The number of key slots in each inner node,
127  /// this can differ from slots in each leaf.
128  static const unsigned short innerslotmax = btree_impl::innerslotmax;
129 
130  /// Computed B+ tree parameter: The minimum number of key slots used in a
131  /// leaf. If fewer slots are used, the leaf will be merged or slots shifted
132  /// from it's siblings.
133  static const unsigned short minleafslots = btree_impl::minleafslots;
134 
135  /// Computed B+ tree parameter: The minimum number of key slots used
136  /// in an inner node. If fewer slots are used, the inner node will be
137  /// merged or slots shifted from it's siblings.
138  static const unsigned short mininnerslots = btree_impl::mininnerslots;
139 
140  /// Debug parameter: Enables expensive and thorough checking of the B+ tree
141  /// invariants after each insert/erase operation.
142  static const bool selfverify = btree_impl::selfverify;
143 
144  /// Debug parameter: Prints out lots of debug information about how the
145  /// algorithms change the tree. Requires the header file to be compiled
146  /// with BTREE_DEBUG and the key type must be std::ostream printable.
147  static const bool debug = btree_impl::debug;
148 
149  /// Operational parameter: Allow duplicate keys in the btree.
151 
152 public:
153  // *** Iterators and Reverse Iterators
154 
155  /// STL-like iterator object for B+ tree items. The iterator points to a
156  /// specific slot number in a leaf.
157  typedef typename btree_impl::iterator iterator;
158 
159  /// STL-like iterator object for B+ tree items. The iterator points to a
160  /// specific slot number in a leaf.
161  typedef typename btree_impl::const_iterator const_iterator;
162 
163  /// create mutable reverse iterator by using STL magic
164  typedef typename btree_impl::reverse_iterator reverse_iterator;
165 
166  /// create constant reverse iterator by using STL magic
167  typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
168 
169 private:
170  // *** Tree Implementation Object
171 
172  /// The contained implementation object
173  btree_impl tree;
174 
175 public:
176  // *** Constructors and Destructor
177 
178  /// Default constructor initializing an empty B+ tree with the standard key
179  /// comparison function
180  explicit inline btree_set(const allocator_type &alloc = allocator_type())
181  : tree(alloc)
182  {
183  }
184 
185  /// Constructor initializing an empty B+ tree with a special key
186  /// comparison object
187  explicit inline btree_set(const key_compare &kcf,
188  const allocator_type &alloc = allocator_type())
189  : tree(kcf, alloc)
190  {
191  }
192 
193  /// Constructor initializing a B+ tree with the range [first,last)
194  template <class InputIterator>
195  inline btree_set(InputIterator first, InputIterator last,
196  const allocator_type &alloc = allocator_type())
197  : tree(alloc)
198  {
199  insert(first, last);
200  }
201 
202  /// Constructor initializing a B+ tree with the range [first,last) and a
203  /// special key comparison object
204  template <class InputIterator>
205  inline btree_set(InputIterator first, InputIterator last, const key_compare &kcf,
206  const allocator_type &alloc = allocator_type())
207  : tree(kcf, alloc)
208  {
209  insert(first, last);
210  }
211 
212  /// Frees up all used B+ tree memory pages
213  inline ~btree_set()
214  {
215  }
216 
217  /// Fast swapping of two identical B+ tree objects.
218  void swap(self& from)
219  {
220  std::swap(tree, from.tree);
221  }
222 
223 public:
224  // *** Key and Value Comparison Function Objects
225 
226  /// Constant access to the key comparison object sorting the B+ tree
227  inline key_compare key_comp() const
228  {
229  return tree.key_comp();
230  }
231 
232  /// Constant access to a constructed value_type comparison object. required
233  /// by the STL
234  inline value_compare value_comp() const
235  {
236  return tree.value_comp();
237  }
238 
239 public:
240  // *** Allocators
241 
242  /// Return the base node allocator provided during construction.
243  allocator_type get_allocator() const
244  {
245  return tree.get_allocator();
246  }
247 
248 public:
249  // *** Fast Destruction of the B+ Tree
250 
251  /// Frees all keys and all nodes of the tree
252  void clear()
253  {
254  tree.clear();
255  }
256 
257 public:
258  // *** STL Iterator Construction Functions
259 
260  /// Constructs a read/data-write iterator that points to the first slot in
261  /// the first leaf of the B+ tree.
262  inline iterator begin()
263  {
264  return tree.begin();
265  }
266 
267  /// Constructs a read/data-write iterator that points to the first invalid
268  /// slot in the last leaf of the B+ tree.
269  inline iterator end()
270  {
271  return tree.end();
272  }
273 
274  /// Constructs a read-only constant iterator that points to the first slot
275  /// in the first leaf of the B+ tree.
276  inline const_iterator begin() const
277  {
278  return tree.begin();
279  }
280 
281  /// Constructs a read-only constant iterator that points to the first
282  /// invalid slot in the last leaf of the B+ tree.
283  inline const_iterator end() const
284  {
285  return tree.end();
286  }
287 
288  /// Constructs a read/data-write reverse iterator that points to the first
289  /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
290  inline reverse_iterator rbegin()
291  {
292  return tree.rbegin();
293  }
294 
295  /// Constructs a read/data-write reverse iterator that points to the first
296  /// slot in the first leaf of the B+ tree. Uses STL magic.
297  inline reverse_iterator rend()
298  {
299  return tree.rend();
300  }
301 
302  /// Constructs a read-only reverse iterator that points to the first
303  /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
304  inline const_reverse_iterator rbegin() const
305  {
306  return tree.rbegin();
307  }
308 
309  /// Constructs a read-only reverse iterator that points to the first slot
310  /// in the first leaf of the B+ tree. Uses STL magic.
311  inline const_reverse_iterator rend() const
312  {
313  return tree.rend();
314  }
315 
316 public:
317  // *** Access Functions to the Item Count
318 
319  /// Return the number of keys in the B+ tree
320  inline size_type size() const
321  {
322  return tree.size();
323  }
324 
325  /// Returns true if there is at least one key in the B+ tree
326  inline bool empty() const
327  {
328  return tree.empty();
329  }
330 
331  /// Returns the largest possible size of the B+ Tree. This is just a
332  /// function required by the STL standard, the B+ Tree can hold more items.
333  inline size_type max_size() const
334  {
335  return tree.max_size();
336  }
337 
338  /// Return a const reference to the current statistics.
339  inline const tree_stats& get_stats() const
340  {
341  return tree.get_stats();
342  }
343 
344 public:
345  // *** Standard Access Functions Querying the Tree by Descending to a Leaf
346 
347  /// Non-STL function checking whether a key is in the B+ tree. The same as
348  /// (find(k) != end()) or (count() != 0).
349  bool exists(const key_type &key) const
350  {
351  return tree.exists(key);
352  }
353 
354  /// Tries to locate a key in the B+ tree and returns an iterator to the
355  /// key slot if found. If unsuccessful it returns end().
356  iterator find(const key_type &key)
357  {
358  return tree.find(key);
359  }
360 
361  /// Tries to locate a key in the B+ tree and returns an constant iterator
362  /// to the key slot if found. If unsuccessful it returns end().
363  const_iterator find(const key_type &key) const
364  {
365  return tree.find(key);
366  }
367 
368  /// Tries to locate a key in the B+ tree and returns the number of
369  /// identical key entries found. As this is a unique set, count() returns
370  /// either 0 or 1.
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 elements 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_set(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. The insert will fail if it is
483  /// already present.
484  inline std::pair<iterator, bool> insert(const key_type& x)
485  {
486  return tree.insert2(x, data_type());
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 iterators dereferencing to
497  /// key_type into the B+ tree. Each key/data pair 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 the key from the set. As this is a unique set, there is no
522  /// difference to erase().
523  bool erase_one(const key_type &key)
524  {
525  return tree.erase_one(key);
526  }
527 
528  /// Erases all the key/data pairs associated with the given key.
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 
567 #endif
568 
569 public:
570  // *** Verification of B+ Tree Invariants
571 
572  /// Run a thorough verification of all B+ tree invariants. The program
573  /// aborts via BTREE_ASSERT() if something is wrong.
574  void verify() const
575  {
576  tree.verify();
577  }
578 
579 public:
580 
581  /// Dump the contents of the B+ tree out onto an ostream as a binary
582  /// image. The image contains memory pointers which will be fixed when the
583  /// image is restored. For this to work your key_type must be an integral
584  /// type and contain no pointers or references.
585  void dump(std::ostream &os) const
586  {
587  tree.dump(os);
588  }
589 
590  /// Restore a binary image of a dumped B+ tree from an istream. The B+ tree
591  /// pointers are fixed using the dump order. For dump and restore to work
592  /// your key_type must be an integral type and contain no pointers or
593  /// references. Returns true if the restore was successful.
594  bool restore(std::istream &is)
595  {
596  return tree.restore(is);
597  }
598 };
599 
600 } // namespace stx
601 
602 #endif // _STX_BTREE_SET_H_
bool erase_one(const key_type &key)
Erases the key from the set.
Definition: btree_set.h:523
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...
Definition: btree_set.h:262
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
iterator insert(iterator hint, const key_type &x)
Attempt to insert a key into the B+ tree.
Definition: btree_set.h:491
void print_leaves(std::ostream &os) const
Print out only the leaves via the double linked list.
Definition: btree_set.h:562
bool operator>(const self &other) const
Greater relation. Based on operator<.
Definition: btree_set.h:442
self & operator=(const self &other)
*** Fast Copy: Assign Operator and Copy Constructors
Definition: btree_set.h:463
const_iterator begin() const
Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tr...
Definition: btree_set.h:276
const_iterator end() const
Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of th...
Definition: btree_set.h:283
void erase(iterator iter)
Erase the key/data pair referenced by the iterator.
Definition: btree_set.h:535
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
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_set.h:128
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 operator!=(const self &other) const
Inequality relation. Based on operator==.
Definition: btree_set.h:429
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_set.h:413
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
Definition: btree.h:1757
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
void erase(iterator, iterator)
Erase all keys in the range [first,last).
Definition: btree_set.h:543
std::pair< iterator, bool > insert(const key_type &x)
Attempt to insert a key into the B+ tree.
Definition: btree_set.h:484
btree_set(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...
Definition: btree_set.h:205
bool operator<=(const self &other) const
Less-equal relation. Based on operator<.
Definition: btree_set.h:448
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
Definition: btree_set.h:349
btree_set(const self &other)
Copy constructor.
Definition: btree_set.h:474
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_set.h:371
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
Definition: btree.h:3860
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
Definition: btree_set.h:234
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Definition: btree.h:2619
static const unsigned short mininnerslots
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
Definition: btree_set.h:138
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
bool operator<(const self &other) const
Total ordering relation of B+ trees of the same type.
Definition: btree_set.h:436
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
Definition: btree_set.h:297
static const bool selfverify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
Definition: btree_set.h:142
size_type size() const
Return the number of keys in the B+ tree.
Definition: btree_set.h:320
const tree_stats & get_stats() const
Return a const reference to the current statistics.
Definition: btree_set.h:339
btree_impl::size_type size_type
Size type used to count keys.
Definition: btree_set.h:115
STX - Some Template Extensions namespace.
Definition: btree.h:81
static const bool allow_duplicates
Operational parameter: Allow duplicate keys in the btree.
Definition: btree_set.h:150
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
Definition: btree_set.h:594
static const bool selfverify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
Definition: btree.h:243
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...
Definition: btree_set.h:401
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
stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, true > btree_impl
Implementation type of the btree_base.
Definition: btree_set.h:109
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
struct empty_struct data_type
The empty data_type.
Definition: btree_set.h:99
The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.
Definition: btree_set.h:91
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
Definition: btree_set.h:290
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
Definition: btree.h:2401
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
_Compare key_compare
Second template parameter: Key comparison function object.
Definition: btree_set.h:73
static const unsigned short leafslotmax
Base B+ tree parameter: The number of key slots in each leaf.
Definition: btree_set.h:124
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
btree_impl tree
The contained implementation object.
Definition: btree_set.h:173
Specialized B+ tree template class implementing STL&#39;s set container.
Definition: btree_set.h:63
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...
Definition: btree_set.h:311
bool operator==(const self &other) const
Equality relation of B+ trees of the same type.
Definition: btree_set.h:423
~btree_set()
Frees up all used B+ tree memory pages.
Definition: btree_set.h:213
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Definition: btree_set.h:529
void dump(std::ostream &os) const
Dump the contents of the B+ tree out onto an ostream as a binary image.
Definition: btree_set.h:585
_Alloc allocator_type
Fourth template parameter: STL allocator.
Definition: btree_set.h:80
void print(std::ostream &os) const
Print out the B+ tree structure with keys onto the given ostream.
Definition: btree_set.h:556
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
btree_set(const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing an empty B+ tree with a special key comparison object.
Definition: btree_set.h:187
void clear()
Frees all keys and all nodes of the tree.
Definition: btree_set.h:252
btree_impl::const_reverse_iterator const_reverse_iterator
create constant reverse iterator by using STL magic
Definition: btree_set.h:167
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Definition: btree_set.h:243
static const bool allow_duplicates
Sixth template parameter: Allow duplicate keys in the B+ tree.
Definition: btree.h:191
_Traits traits
Third template parameter: Traits object used to define more parameters of the B+ tree.
Definition: btree_set.h:77
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_set.h:393
btree_set(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function...
Definition: btree_set.h:180
void print(std::ostream &os) const
Print out the B+ tree structure with keys onto the given ostream.
Definition: btree.h:3556
bool operator>=(const self &other) const
Greater-equal relation. Based on operator<.
Definition: btree_set.h:454
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_set.h:378
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
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree...
Definition: btree_set.h:147
key_type value_type
Construct the set value_type: the key_type.
Definition: btree_set.h:102
size_type max_size() const
Returns the largest possible size of the B+ Tree.
Definition: btree_set.h:333
void insert(InputIterator first, InputIterator last)
Attempt to insert the range [first,last) of iterators dereferencing to key_type into the B+ tree...
Definition: btree_set.h:499
void swap(self &from)
Fast swapping of two identical B+ tree objects.
Definition: btree_set.h:218
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
void bulk_load(Iterator first, Iterator last)
Bulk load a sorted range [first,last).
Definition: btree_set.h:513
_Key key_type
First template parameter: The key type of the B+ tree.
Definition: btree_set.h:70
btree_impl::reverse_iterator reverse_iterator
create mutable reverse iterator by using STL magic
Definition: btree_set.h:164
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
const_reverse_iterator rbegin() const
Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the...
Definition: btree_set.h:304
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...
Definition: btree_set.h:386
void verify() const
Run a thorough verification of all B+ tree invariants.
Definition: btree.h:3630
btree_impl::value_compare value_compare
Function class comparing two value_type keys.
Definition: btree_set.h:112
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.
Definition: btree_set.h:356
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
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition: btree_set.h:407
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Definition: btree.h:1445
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...
Definition: btree_set.h:363
bool empty() const
Returns true if there is at least one key in the B+ tree.
Definition: btree_set.h:326
static const unsigned short minleafslots
Computed B+ tree parameter: The minimum number of key slots used in a leaf.
Definition: btree_set.h:133
btree_set(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last)
Definition: btree_set.h:195
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
void verify() const
Run a thorough verification of all B+ tree invariants.
Definition: btree_set.h:574
static const unsigned short minleafslots
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
Definition: btree.h:234
btree_impl::tree_stats tree_stats
Small structure containing statistics about the tree.
Definition: btree_set.h:118
btree_impl::iterator iterator
STL-like iterator object for B+ tree items.
Definition: btree_set.h:157
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
Definition: btree_set.h:227
btree_impl::const_iterator const_iterator
STL-like iterator object for B+ tree items.
Definition: btree_set.h:161
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
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
Definition: btree_set.h:269
Contains the main B+ tree implementation template class btree.