tlx
btree_multimap.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/container/btree_multimap.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_MULTIMAP_HEADER
12 #define TLX_CONTAINER_BTREE_MULTIMAP_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 multimap container.
27  *
28  * Implements the STL multimap using a B+ tree. It can be used as a drop-in
29  * replacement for std::multimap. Not all asymptotic time requirements are met
30  * in theory. The class has a traits class defining B+ tree properties like
31  * slots and self-verification. Furthermore an allocator can be specified for
32  * tree nodes.
33  */
34 template <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_> > >
39 class btree_multimap
40 {
41 public:
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 data type associated with each
50  //! key. 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 
70 public:
71  //! \name Constructed Types
72  //! \{
73 
74  //! Typedef of our own type
75  typedef btree_multimap<
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
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
96  typedef typename btree_impl::size_type size_type;
97 
98  //! Small structure containing statistics about the tree
99  typedef typename btree_impl::tree_stats tree_stats;
100 
101  //! \}
102 
103 public:
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.
126  static const bool self_verify = btree_impl::self_verify;
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 with
130  //! 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 
138 public:
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 
158 private:
159  //! \name Tree Implementation Object
160  //! \{
161 
162  //! The contained implementation object
164 
165  //! \}
166 
167 public:
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_multimap(const allocator_type& alloc = allocator_type())
174  : tree_(alloc)
175  { }
176 
177  //! Constructor initializing an empty B+ tree with a special key comparison
178  //! object
179  explicit btree_multimap(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_multimap(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_multimap(InputIterator first, InputIterator last,
195  const key_compare& kcf,
196  const allocator_type& alloc = allocator_type())
197  : tree_(first, last, kcf, alloc)
198  { }
199 
200  //! Frees up all used B+ tree memory pages
202  { }
203 
204  //! Fast swapping of two identical B+ tree objects.
205  void swap(btree_multimap& from) {
206  std::swap(tree_, from.tree_);
207  }
208 
209  //! \}
210 
211 public:
212  //! \name Key and Value Comparison Function Objects
213  //! \{
214 
215  //! Constant access to the key comparison object sorting the B+ tree
216  key_compare key_comp() const {
217  return tree_.key_comp();
218  }
219 
220  //! Constant access to a constructed value_type comparison object. required
221  //! by the STL
222  value_compare value_comp() const {
223  return tree_.value_comp();
224  }
225 
226  //! \}
227 
228 public:
229  //! \name Allocators
230  //! \{
231 
232  //! Return the base node allocator provided during construction.
233  allocator_type get_allocator() const {
234  return tree_.get_allocator();
235  }
236 
237  //! \}
238 
239 public:
240  //! \name Fast Destruction of the B+ Tree
241  //! \{
242 
243  //! Frees all key/data pairs and all nodes of the tree
244  void clear() {
245  tree_.clear();
246  }
247 
248  //! \}
249 
250 public:
251  //! \name STL Iterator Construction Functions
252  //! \{
253 
254  //! Constructs a read/data-write iterator that points to the first slot in
255  //! the first leaf of the B+ tree.
256  iterator begin() {
257  return tree_.begin();
258  }
259 
260  //! Constructs a read/data-write iterator that points to the first invalid
261  //! slot in the last leaf of the B+ tree.
262  iterator end() {
263  return tree_.end();
264  }
265 
266  //! Constructs a read-only constant iterator that points to the first slot
267  //! in the first leaf of the B+ tree.
268  const_iterator begin() const {
269  return tree_.begin();
270  }
271 
272  //! Constructs a read-only constant iterator that points to the first
273  //! invalid slot in the last leaf of the B+ tree.
274  const_iterator end() const {
275  return tree_.end();
276  }
277 
278  //! Constructs a read/data-write reverse iterator that points to the first
279  //! invalid slot in the last leaf of the B+ tree. Uses STL magic.
281  return tree_.rbegin();
282  }
283 
284  //! Constructs a read/data-write reverse iterator that points to the first
285  //! slot in the first leaf of the B+ tree. Uses STL magic.
287  return tree_.rend();
288  }
289 
290  //! Constructs a read-only reverse iterator that points to the first
291  //! invalid slot in the last leaf of the B+ tree. Uses STL magic.
293  return tree_.rbegin();
294  }
295 
296  //! Constructs a read-only reverse iterator that points to the first slot
297  //! in the first leaf of the B+ tree. Uses STL magic.
298  const_reverse_iterator rend() const {
299  return tree_.rend();
300  }
301 
302  //! \}
303 
304 public:
305  //! \name Access Functions to the Item Count
306  //! \{
307 
308  //! Return the number of key/data pairs in the B+ tree
309  size_type size() const {
310  return tree_.size();
311  }
312 
313  //! Returns true if there is at least one key/data pair in the B+ tree
314  bool empty() const {
315  return tree_.empty();
316  }
317 
318  //! Returns the largest possible size of the B+ Tree. This is just a
319  //! function required by the STL standard, the B+ Tree can hold more items.
320  size_type max_size() const {
321  return tree_.max_size();
322  }
323 
324  //! Return a const reference to the current statistics.
325  const tree_stats& get_stats() const {
326  return tree_.get_stats();
327  }
328 
329  //! \}
330 
331 public:
332  //! \name STL Access Functions Querying the Tree by Descending to a Leaf
333  //! \{
334 
335  //! Non-STL function checking whether a key is in the B+ tree. The same as
336  //! (find(k) != end()) or (count() != 0).
337  bool exists(const key_type& key) const {
338  return tree_.exists(key);
339  }
340 
341  //! Tries to locate a key in the B+ tree and returns an iterator to the
342  //! key/data slot if found. If unsuccessful it returns end().
343  iterator find(const key_type& key) {
344  return tree_.find(key);
345  }
346 
347  //! Tries to locate a key in the B+ tree and returns an constant iterator to
348  //! the key/data slot if found. If unsuccessful it returns end().
349  const_iterator find(const key_type& key) const {
350  return tree_.find(key);
351  }
352 
353  //! Tries to locate a key in the B+ tree and returns the number of identical
354  //! key entries found.
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.
361  iterator lower_bound(const key_type& key) {
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.
367  const_iterator lower_bound(const key_type& key) const {
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.
373  iterator upper_bound(const key_type& key) {
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.
379  const_iterator upper_bound(const key_type& key) const {
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 
396 public:
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. Beware
402  //! of the random ordering of duplicate keys.
403  bool operator == (const btree_multimap& other) const {
404  return (tree_ == other.tree_);
405  }
406 
407  //! Inequality relation. Based on operator==.
408  bool operator != (const btree_multimap& other) const {
409  return (tree_ != other.tree_);
410  }
411 
412  //! Total ordering relation of B+ trees of the same type. It uses
413  //! std::lexicographical_compare() for the actual comparison of elements.
414  bool operator < (const btree_multimap& other) const {
415  return (tree_ < other.tree_);
416  }
417 
418  //! Greater relation. Based on operator<.
419  bool operator > (const btree_multimap& other) const {
420  return (tree_ > other.tree_);
421  }
422 
423  //! Less-equal relation. Based on operator<.
424  bool operator <= (const btree_multimap& other) const {
425  return (tree_ <= other.tree_);
426  }
427 
428  //! Greater-equal relation. Based on operator<.
429  bool operator >= (const btree_multimap& other) const {
430  return (tree_ >= other.tree_);
431  }
432 
433  //! \}
434 
435 public:
436  //! \name Fast Copy: Assign Operator and Copy Constructors
437  //! \{
438 
439  //! Assignment operator. All the key/data pairs are copied
440  btree_multimap& operator = (const btree_multimap& other) {
441  if (this != &other)
442  tree_ = other.tree_;
443  return *this;
444  }
445 
446  //! Copy constructor. The newly initialized B+ tree object will contain a
447  //! copy or all key/data pairs.
449  : tree_(other.tree_)
450  { }
451 
452  //! \}
453 
454 public:
455  //! \name Public Insertion Functions
456  //! \{
457 
458  //! Attempt to insert a key/data pair into the B+ tree. As this tree allows
459  //! duplicates, insertion never fails.
460  iterator insert(const value_type& x) {
461  return tree_.insert(x).first;
462  }
463 
464  //! Attempt to insert a key/data pair into the B+ tree. This function is the
465  //! same as the other insert. As this tree allows duplicates, insertion
466  //! never fails.
467  iterator insert2(const key_type& key, const data_type& data) {
468  return tree_.insert(value_type(key, data)).first;
469  }
470 
471  //! Attempt to insert a key/data pair into the B+ tree. The iterator hint is
472  //! currently ignored by the B+ tree insertion routine.
473  iterator insert(iterator hint, const value_type& x) {
474  return tree_.insert(hint, x);
475  }
476 
477  //! Attempt to insert a key/data pair into the B+ tree. The iterator hint is
478  //! currently ignored by the B+ tree insertion routine.
480  const key_type& key, const data_type& data) {
481  return tree_.insert(hint, value_type(key, data));
482  }
483 
484  //! Attempt to insert the range [first,last) of value_type pairs into the B+
485  //! tree. Each key/data pair is inserted individually.
486  template <typename InputIterator>
487  void insert(InputIterator first, InputIterator last) {
488  return tree_.insert(first, last);
489  }
490 
491  //! Bulk load a sorted range [first,last). Loads items into leaves and
492  //! constructs a B-tree above them. The tree must be empty when calling this
493  //! function.
494  template <typename Iterator>
495  void bulk_load(Iterator first, Iterator last) {
496  return tree_.bulk_load(first, last);
497  }
498 
499  //! \}
500 
501 public:
502  //! \name Public Erase Functions
503  //! \{
504 
505  //! Erases one (the first) of the key/data pairs associated with the given
506  //! key.
507  bool erase_one(const key_type& key) {
508  return tree_.erase_one(key);
509  }
510 
511  //! Erases all the key/data pairs associated with the given key. This is
512  //! implemented using erase_one() and thus not very efficient.
513  size_type erase(const key_type& key) {
514  return tree_.erase(key);
515  }
516 
517  //! Erase the key/data pair referenced by the iterator.
518  void erase(iterator iter) {
519  return tree_.erase(iter);
520  }
521 
522 #ifdef TLX_BTREE_TODO
523  //! Erase all key/data pairs in the range [first,last). This function is
524  //! currently not implemented by the B+ Tree.
525  void erase(iterator /* first */, iterator /* last */) {
526  abort();
527  }
528 #endif
529 
530  //! \}
531 
532 #ifdef TLX_BTREE_DEBUG
533 
534 public:
535  //! \name Debug Printing
536  //! \{
537 
538  //! Print out the B+ tree structure with keys onto the given ostream. This
539  //! function requires that the header is compiled with TLX_BTREE_DEBUG and
540  //! that key_type is printable via std::ostream.
541  void print(std::ostream& os) const {
542  tree_.print(os);
543  }
544 
545  //! Print out only the leaves via the double linked list.
546  void print_leaves(std::ostream& os) const {
547  tree_.print_leaves(os);
548  }
549 
550  //! \}
551 #endif
552 
553 public:
554  //! \name Verification of B+ Tree Invariants
555  //! \{
556 
557  //! Run a thorough verification of all B+ tree invariants. The program
558  //! aborts via TLX_BTREE_ASSERT() if something is wrong.
559  void verify() const {
560  tree_.verify();
561  }
562 
563  //! \}
564 };
565 
566 //! \}
567 
568 } // namespace tlx
569 
570 #endif // !TLX_CONTAINER_BTREE_MULTIMAP_HEADER
571 
572 /******************************************************************************/
tlx::btree_multimap::tree_stats
btree_impl::tree_stats tree_stats
Small structure containing statistics about the tree.
Definition: btree_multimap.hpp:107
tlx::BTree::verify
void verify() const
Run a thorough verification of all B+ tree invariants.
Definition: btree.hpp:3549
tlx::btree_multimap::value_comp
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
Definition: btree_multimap.hpp:230
tlx::btree_multimap::get_allocator
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Definition: btree_multimap.hpp:241
tlx::btree_multimap::key_type
Key_ key_type
First template parameter: The key type of the btree.
Definition: btree_multimap.hpp:55
tlx::btree_multimap::btree_multimap
btree_multimap(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function.
Definition: btree_multimap.hpp:181
tlx::btree_multimap::operator<
bool operator<(const btree_multimap &other) const
Total ordering relation of B+ trees of the same type.
Definition: btree_multimap.hpp:422
tlx::BTree::get_stats
const struct tree_stats & get_stats() const
Return a const reference to the current statistics.
Definition: btree.hpp:1518
tlx::btree_multimap::erase_one
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
Definition: btree_multimap.hpp:515
tlx::btree_multimap::begin
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree.
Definition: btree_multimap.hpp:264
tlx::BTree::clear
void clear()
Frees all key/data pairs and all nodes of the tree.
Definition: btree.hpp:1302
tlx::btree_multimap::bulk_load
void bulk_load(Iterator first, Iterator last)
Bulk load a sorted range [first,last).
Definition: btree_multimap.hpp:503
tlx::btree_multimap::upper_bound
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_multimap.hpp:381
tlx::BTree::bulk_load
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
Definition: btree.hpp:2163
tlx::btree_multimap::rbegin
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
Definition: btree_multimap.hpp:288
tlx::btree_multimap::allow_duplicates
static const bool allow_duplicates
Operational parameter: Allow duplicate keys in the btree.
Definition: btree_multimap.hpp:142
tlx::btree_multimap::operator!=
bool operator!=(const btree_multimap &other) const
Inequality relation. Based on operator==.
Definition: btree_multimap.hpp:416
tlx::btree_multimap::inner_slotmin
static const unsigned short inner_slotmin
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
Definition: btree_multimap.hpp:130
tlx::BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::debug
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
Definition: btree.hpp:211
tlx::btree_multimap::insert
iterator insert(const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree_multimap.hpp:468
tlx::btree_multimap::value_compare
btree_impl::value_compare value_compare
Function class comparing two value_type pairs.
Definition: btree_multimap.hpp:101
tlx::BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::inner_slotmax
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:192
tlx::btree_multimap::~btree_multimap
~btree_multimap()
Frees up all used B+ tree memory pages.
Definition: btree_multimap.hpp:209
tlx::btree_multimap::allocator_type
Alloc_ allocator_type
Fifth template parameter: STL allocator.
Definition: btree_multimap.hpp:69
tlx::btree_multimap::btree_impl
BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type > btree_impl
Implementation type of the btree_base.
Definition: btree_multimap.hpp:98
tlx::BTree::count
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:1592
tlx::btree_multimap::traits
Traits_ traits
Fourth template parameter: Traits object used to define more parameters of the B+ tree.
Definition: btree_multimap.hpp:66
tlx::BTree::insert
std::pair< iterator, bool > insert(const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree.hpp:1854
tlx::btree_multimap::max_size
size_type max_size() const
Returns the largest possible size of the B+ Tree.
Definition: btree_multimap.hpp:328
tlx::btree_multimap::get_stats
const tree_stats & get_stats() const
Return a const reference to the current statistics.
Definition: btree_multimap.hpp:333
tlx::btree_multimap::btree_multimap
btree_multimap(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last)
Definition: btree_multimap.hpp:194
tlx::BTree::max_size
size_type max_size() const
Returns the largest possible size of the B+ Tree.
Definition: btree.hpp:1513
tlx::btree_multimap::reverse_iterator
btree_impl::reverse_iterator reverse_iterator
create mutable reverse iterator by using STL magic
Definition: btree_multimap.hpp:159
tlx::btree_multimap::data_type
Data_ data_type
Second template parameter: The data type associated with each key.
Definition: btree_multimap.hpp:59
tlx::btree_multimap::debug
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
Definition: btree_multimap.hpp:139
tlx::btree_multimap::key_of_value
Key Extractor Struct.
Definition: btree_multimap.hpp:91
tlx::BTree::erase_one
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
Definition: btree.hpp:2376
tlx::btree_multimap::verify
void verify() const
Run a thorough verification of all B+ tree invariants.
Definition: btree_multimap.hpp:567
tlx::btree_multimap::rend
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
Definition: btree_multimap.hpp:294
tlx::btree_multimap::operator==
bool operator==(const btree_multimap &other) const
Equality relation of B+ trees of the same type.
Definition: btree_multimap.hpp:411
tlx::btree_multimap::equal_range
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition: btree_multimap.hpp:392
tlx::BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::inner_slotmin
static const unsigned short inner_slotmin
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
Definition: btree.hpp:202
tlx::BTree::key_comp
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
Definition: btree.hpp:1191
tlx::btree_multimap::insert2
iterator insert2(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree_multimap.hpp:475
tlx::btree_multimap::key_comp
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
Definition: btree_multimap.hpp:224
tlx::btree_multimap::key_compare
Compare_ key_compare
Third template parameter: Key comparison function object.
Definition: btree_multimap.hpp:62
tlx
Definition: exclusive_scan.hpp:17
tlx::BTree::equal_range
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:1703
tlx::BTree::get_allocator
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Definition: btree.hpp:1240
tlx::btree_multimap::end
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
Definition: btree_multimap.hpp:270
tlx::btree_multimap::empty
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
Definition: btree_multimap.hpp:322
tlx::BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::self_verify
static const bool self_verify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
Definition: btree.hpp:206
tlx::BTree::value_comp
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
Definition: btree.hpp:1197
tlx::BTree::size
size_type size() const
Return the number of key/data pairs in the B+ tree.
Definition: btree.hpp:1502
tlx::btree_multimap::const_iterator
btree_impl::const_iterator const_iterator
STL-like iterator object for B+ tree items.
Definition: btree_multimap.hpp:156
tlx::BTree::lower_bound
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:1624
tlx::btree_multimap::swap
void swap(btree_multimap &from)
Fast swapping of two identical B+ tree objects.
Definition: btree_multimap.hpp:213
tlx::btree_multimap
Specialized B+ tree template class implementing STL's multimap container.
Definition: btree_multimap.hpp:47
tlx::BTree::rend
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:1379
tlx::BTree::erase
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Definition: btree.hpp:2400
tlx::swap
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
swap enclosed object with another counting pointer (no reference counts need change)
Definition: counting_ptr.hpp:328
tlx::btree_multimap::clear
void clear()
Frees all key/data pairs and all nodes of the tree.
Definition: btree_multimap.hpp:252
tlx::BTree::find
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:1550
tlx::btree_multimap::find
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_multimap.hpp:351
tlx::BTree
Basic class implementing a B+ tree data structure in memory.
Definition: btree.hpp:132
tlx::btree_multimap::key_of_value::get
static const key_type & get(const value_type &v)
pull first out of pair
Definition: btree_multimap.hpp:93
tlx::btree_multimap::value_type
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_multimap.hpp:88
tlx::BTree::end
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:1355
tlx::btree_multimap::operator>=
bool operator>=(const btree_multimap &other) const
Greater-equal relation. Based on operator<.
Definition: btree_multimap.hpp:437
tlx::btree_multimap::leaf_slotmax
static const unsigned short leaf_slotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
Definition: btree_multimap.hpp:116
tlx::BTree::empty
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
Definition: btree.hpp:1507
tlx::BTree::exists
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
Definition: btree.hpp:1530
tlx::btree_multimap::leaf_slotmin
static const unsigned short leaf_slotmin
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
Definition: btree_multimap.hpp:125
tlx::btree_multimap::operator>
bool operator>(const btree_multimap &other) const
Greater relation. Based on operator<.
Definition: btree_multimap.hpp:427
tlx::btree_multimap::inner_slotmax
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_multimap.hpp:120
tlx::btree_multimap::operator<=
bool operator<=(const btree_multimap &other) const
Less-equal relation. Based on operator<.
Definition: btree_multimap.hpp:432
btree.hpp
tlx::BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::leaf_slotmin
static const unsigned short leaf_slotmin
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
Definition: btree.hpp:197
tlx::BTree::begin
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:1349
tlx::btree_multimap::lower_bound
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_multimap.hpp:369
tlx::btree_multimap::operator=
btree_multimap & operator=(const btree_multimap &other)
Assignment operator. All the key/data pairs are copied.
Definition: btree_multimap.hpp:448
tlx::btree_multimap::exists
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
Definition: btree_multimap.hpp:345
tlx::btree_multimap::size_type
btree_impl::size_type size_type
Size type used to count keys.
Definition: btree_multimap.hpp:104
tlx::btree_multimap::count
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_multimap.hpp:363
tlx::btree_multimap::size
size_type size() const
Return the number of key/data pairs in the B+ tree.
Definition: btree_multimap.hpp:317
tlx::BTree::upper_bound
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:1664
tlx::BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::allow_duplicates
static const bool allow_duplicates
Sixth template parameter: Allow duplicate keys in the B+ tree.
Definition: btree.hpp:158
tlx::btree_multimap::self_verify
static const bool self_verify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
Definition: btree_multimap.hpp:134
tlx::btree_multimap::tree_
btree_impl tree_
The contained implementation object.
Definition: btree_multimap.hpp:171
tlx::btree_multimap::const_reverse_iterator
btree_impl::const_reverse_iterator const_reverse_iterator
create constant reverse iterator by using STL magic
Definition: btree_multimap.hpp:162
tlx::btree_multimap::TLX_BTREE_FRIENDS
TLX_BTREE_FRIENDS
Definition: btree_multimap.hpp:76
tlx::BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::size_type
size_t size_type
Size type used to count keys.
Definition: btree.hpp:179
tlx::BTree::rbegin
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
Definition: btree.hpp:1373
tlx::BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::leaf_slotmax
static const unsigned short leaf_slotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
Definition: btree.hpp:188
tlx::btree_multimap::erase
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Definition: btree_multimap.hpp:521
tlx::btree_multimap::iterator
btree_impl::iterator iterator
STL-like iterator object for B+ tree items.
Definition: btree_multimap.hpp:152