tlx
Loading...
Searching...
No Matches
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
19
20namespace 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 */
37template <typename Key_,
38 typename Compare_ = std::less<Key_>,
39 typename Traits_ = btree_default_traits<Key_, Key_>,
40 typename Alloc_ = std::allocator<Key_> >
42{
43public:
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
68public:
69 //! \name Constructed Types
70 //! \{
71
72 //! Construct the set value_type: the key_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
85 typedef BTree<key_type, value_type, key_of_value, key_compare,
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
93
94 //! Small structure containing statistics about the tree
95 typedef typename btree_impl::tree_stats tree_stats;
96
97 //! \}
98
99public:
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
134public:
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
154private:
155 //! \name Tree Implementation Object
156 //! \{
157
158 //! The contained implementation object
160
161 //! \}
162
163public:
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
208public:
209 //! \name Key and Value Comparison Function Objects
210 //! \{
211
212 //! Constant access to the key comparison object sorting the B+ tree
214 return tree_.key_comp();
215 }
216
217 //! Constant access to a constructed value_type comparison object. required
218 //! by the STL
220 return tree_.value_comp();
221 }
222
223 //! \}
224
225public:
226 //! \name Allocators
227 //! \{
228
229 //! Return the base node allocator provided during construction.
231 return tree_.get_allocator();
232 }
233
234 //! \}
235
236public:
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
247public:
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.
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.
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.
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.
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.
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.
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.
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.
296 return tree_.rend();
297 }
298
299 //! \}
300
301public:
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.
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
328public:
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.
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.
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.
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.
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
394public:
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
432public:
433 //! \name Fast Copy: Assign Operator and Copy Constructors
434 //! \{
435
436 //! Assignment operator. All the keys are copied
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
451public:
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.
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
489public:
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.
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
521public:
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
540public:
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/******************************************************************************/
Basic class implementing a B+ tree data structure in memory.
Definition: btree.hpp:125
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
std::pair< iterator, bool > insert(const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree.hpp:1846
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
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
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
Definition: btree.hpp:2155
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
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
static const bool allow_duplicates
Sixth template parameter: Allow duplicate keys in the B+ tree.
Definition: btree.hpp:150
static const unsigned short leaf_slotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
Definition: btree.hpp:180
size_type size() const
Return the number of key/data pairs in the B+ tree.
Definition: btree.hpp:1494
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
Definition: btree.hpp:203
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
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
Definition: btree.hpp:1499
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
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Definition: btree.hpp:1232
const struct tree_stats & get_stats() const
Return a const reference to the current statistics.
Definition: btree.hpp:1510
static const bool self_verify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
Definition: btree.hpp:198
void verify() const
Run a thorough verification of all B+ tree invariants.
Definition: btree.hpp:3541
size_type max_size() const
Returns the largest possible size of the B+ Tree.
Definition: btree.hpp:1505
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
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
Definition: btree.hpp:1522
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
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
Definition: btree.hpp:1189
void clear()
Frees all key/data pairs and all nodes of the tree.
Definition: btree.hpp:1294
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
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
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
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
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Definition: btree.hpp:2392
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
Definition: btree.hpp:1183
Specialized B+ tree template class implementing STL's set container.
Definition: btree_set.hpp:42
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
std::pair< iterator, bool > insert(const key_type &x)
Attempt to insert a key into the B+ tree.
Definition: btree_set.hpp:457
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
btree_impl::reverse_iterator reverse_iterator
create mutable reverse iterator by using STL magic
Definition: btree_set.hpp:147
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 operator!=(const btree_set &other) const
Inequality relation. Based on operator==.
Definition: btree_set.hpp:405
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
btree_impl::size_type size_type
Size type used to count keys.
Definition: btree_set.hpp:92
iterator insert(iterator hint, const key_type &x)
Attempt to insert a key into the B+ tree.
Definition: btree_set.hpp: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.hpp:265
key_type value_type
Construct the set value_type: the key_type.
Definition: btree_set.hpp:73
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
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
bool erase_one(const key_type &key)
Erases the key from the set.
Definition: btree_set.hpp:495
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
void swap(btree_set &from)
Fast swapping of two identical B+ tree objects.
Definition: btree_set.hpp:202
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
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
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 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
static const unsigned short leaf_slotmax
Base B+ tree parameter: The number of key slots in each leaf.
Definition: btree_set.hpp:104
Alloc_ allocator_type
Fourth template parameter: STL allocator.
Definition: btree_set.hpp:59
bool operator<(const btree_set &other) const
Total ordering relation of B+ trees of the same type.
Definition: btree_set.hpp:411
size_type size() const
Return the number of keys in the B+ tree.
Definition: btree_set.hpp:306
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
Definition: btree_set.hpp:127
btree_impl::value_compare value_compare
Function class comparing two value_type keys.
Definition: btree_set.hpp:89
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
bool empty() const
Returns true if there is at least one key in the B+ tree.
Definition: btree_set.hpp:311
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
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
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Definition: btree_set.hpp:230
bool operator>=(const btree_set &other) const
Greater-equal relation. Based on operator<.
Definition: btree_set.hpp:426
Compare_ key_compare
Second template parameter: Key comparison function object.
Definition: btree_set.hpp:52
btree_impl::tree_stats tree_stats
Small structure containing statistics about the tree.
Definition: btree_set.hpp:95
const tree_stats & get_stats() const
Return a const reference to the current statistics.
Definition: btree_set.hpp:322
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 & operator=(const btree_set &other)
Assignment operator. All the keys are copied.
Definition: btree_set.hpp:437
bool operator==(const btree_set &other) const
Equality relation of B+ trees of the same type.
Definition: btree_set.hpp:400
void verify() const
Run a thorough verification of all B+ tree invariants.
Definition: btree_set.hpp:546
btree_impl tree_
The contained implementation object.
Definition: btree_set.hpp:159
size_type max_size() const
Returns the largest possible size of the B+ Tree.
Definition: btree_set.hpp:317
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
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
btree_set< key_type, key_compare, traits, allocator_type > self
Typedef of our own type.
Definition: btree_set.hpp:76
bool operator>(const btree_set &other) const
Greater relation. Based on operator<.
Definition: btree_set.hpp:416
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
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
Definition: btree_set.hpp:334
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
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
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
Definition: btree_set.hpp:219
void clear()
Frees all keys and all nodes of the tree.
Definition: btree_set.hpp:241
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
Key_ key_type
First template parameter: The key type of the B+ tree.
Definition: btree_set.hpp:49
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
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
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
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
Traits_ traits
Third template parameter: Traits object used to define more parameters of the B+ tree.
Definition: btree_set.hpp:56
~btree_set()
Frees up all used B+ tree memory pages.
Definition: btree_set.hpp:198
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Definition: btree_set.hpp:500
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
Definition: btree_set.hpp:213
bool operator<=(const btree_set &other) const
Less-equal relation. Based on operator<.
Definition: btree_set.hpp:421
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
btree_set(const btree_set &other)
Copy constructor.
Definition: btree_set.hpp:445
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
void erase(iterator iter)
Erase the key/data pair referenced by the iterator.
Definition: btree_set.hpp:505
void bulk_load(Iterator first, Iterator last)
Bulk load a sorted range [first,last).
Definition: btree_set.hpp:483
btree_impl::iterator iterator
STL-like iterator object for B+ tree items.
Definition: btree_set.hpp:140
btree_impl::const_iterator const_iterator
STL-like iterator object for B+ tree items.
Definition: btree_set.hpp:144
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
Key Extractor Struct.
Definition: btree_set.hpp:79
static const key_type & get(const value_type &v)
pull first out of pair
Definition: btree_set.hpp:81