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