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