STX B+ Tree Template Classes  0.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
btree_map.h
Go to the documentation of this file.
1 /** \file btree_map.h
2  * Contains the specialized B+ tree template class btree_map
3  */
4 
5 /*
6  * STX B+ Tree Template Classes v0.9
7  * Copyright (C) 2008-2013 Timo Bingmann <tb@panthema.net>
8  *
9  * Boost Software License - Version 1.0 - August 17th, 2003
10  *
11  * Permission is hereby granted, free of charge, to any person or organization
12  * obtaining a copy of the software and accompanying documentation covered by
13  * this license (the "Software") to use, reproduce, display, distribute,
14  * execute, and transmit the Software, and to prepare derivative works of the
15  * Software, and to permit third-parties to whom the Software is furnished to
16  * do so, all subject to the following:
17  *
18  * The copyright notices in the Software and this entire statement, including
19  * the above license grant, this restriction and the following disclaimer, must
20  * be included in all copies of the Software, in whole or in part, and all
21  * derivative works of the Software, unless such copies or derivative works are
22  * solely in the form of machine-executable object code generated by a source
23  * language processor.
24  *
25  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
26  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
27  * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
28  * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
29  * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
30  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
31  * DEALINGS IN THE SOFTWARE.
32  */
33 
34 #ifndef _STX_BTREE_MAP_H_
35 #define _STX_BTREE_MAP_H_
36 
37 #include <stx/btree.h>
38 
39 namespace stx {
40 
41 /** @brief Specialized B+ tree template class implementing STL's map container.
42  *
43  * Implements the STL map using a B+ tree. It can be used as a drop-in
44  * replacement for std::map. Not all asymptotic time requirements are met in
45  * theory. The class has a traits class defining B+ tree properties like slots
46  * and self-verification. Furthermore an allocator can be specified for tree
47  * nodes.
48  *
49  * Most noteworthy difference to the default red-black implementation of
50  * std::map is that the B+ tree does not hold key and data pair together in
51  * memory. Instead each B+ tree node has two arrays of keys and data
52  * values. This design directly generates many problems in implementing the
53  * iterator's operator's which return value_type composition pairs.
54  */
55 template <typename _Key, typename _Data,
56  typename _Compare = std::less<_Key>,
57  typename _Traits = btree_default_map_traits<_Key, _Data>,
58  typename _Alloc = std::allocator<std::pair<_Key, _Data> > >
59 class btree_map
60 {
61 public:
62  // *** Template Parameter Types
63 
64  /// First template parameter: The key type of the btree. This is stored in
65  /// inner nodes and leaves
66  typedef _Key key_type;
67 
68  /// Second template parameter: The data type associated with each
69  /// key. Stored in the B+ tree's leaves
70  typedef _Data data_type;
71 
72  /// Third template parameter: Key comparison function object
73  typedef _Compare key_compare;
74 
75  /// Fourth template parameter: Traits object used to define more parameters
76  /// of the B+ tree
77  typedef _Traits traits;
78 
79  /// Fifth template parameter: STL allocator
80  typedef _Alloc allocator_type;
81 
82  // The macro BTREE_FRIENDS can be used by outside class to access the B+
83  // tree internals. This was added for wxBTreeDemo to be able to draw the
84  // tree.
86 
87 public:
88  // *** Constructed Types
89 
90  /// Typedef of our own type
92 
93  /// Construct the STL-required value_type as a composition pair of key and
94  /// data types
95  typedef std::pair<key_type, data_type> value_type;
96 
97  /// Implementation type of the btree_base
99  traits, false, allocator_type, false> btree_impl;
100 
101  /// Function class comparing two value_type pairs.
102  typedef typename btree_impl::value_compare value_compare;
103 
104  /// Size type used to count keys
106 
107  /// Small structure containing statistics about the tree
108  typedef typename btree_impl::tree_stats tree_stats;
109 
110 public:
111  // *** Static Constant Options and Values of the B+ Tree
112 
113  /// Base B+ tree parameter: The number of key/data slots in each leaf
114  static const unsigned short leafslotmax = btree_impl::leafslotmax;
115 
116  /// Base B+ tree parameter: The number of key slots in each inner node,
117  /// this can differ from slots in each leaf.
118  static const unsigned short innerslotmax = btree_impl::innerslotmax;
119 
120  /// Computed B+ tree parameter: The minimum number of key/data slots used
121  /// in a leaf. If fewer slots are used, the leaf will be merged or slots
122  /// shifted from it's siblings.
123  static const unsigned short minleafslots = btree_impl::minleafslots;
124 
125  /// Computed B+ tree parameter: The minimum number of key slots used
126  /// in an inner node. If fewer slots are used, the inner node will be
127  /// merged or slots shifted from it's siblings.
128  static const unsigned short mininnerslots = btree_impl::mininnerslots;
129 
130  /// Debug parameter: Enables expensive and thorough checking of the B+ tree
131  /// invariants after each insert/erase operation.
132  static const bool selfverify = btree_impl::selfverify;
133 
134  /// Debug parameter: Prints out lots of debug information about how the
135  /// algorithms change the tree. Requires the header file to be compiled
136  /// with BTREE_DEBUG and the key type must be std::ostream printable.
137  static const bool debug = btree_impl::debug;
138 
139  /// Operational parameter: Allow duplicate keys in the btree.
141 
142 public:
143  // *** Iterators and Reverse Iterators
144 
145  /// STL-like iterator object for B+ tree items. The iterator points to a
146  /// specific slot number in a leaf.
147  typedef typename btree_impl::iterator iterator;
148 
149  /// STL-like iterator object for B+ tree items. The iterator points to a
150  /// specific slot number in a leaf.
151  typedef typename btree_impl::const_iterator const_iterator;
152 
153  /// create mutable reverse iterator by using STL magic
154  typedef typename btree_impl::reverse_iterator reverse_iterator;
155 
156  /// create constant reverse iterator by using STL magic
157  typedef typename btree_impl::const_reverse_iterator const_reverse_iterator;
158 
159 private:
160  // *** Tree Implementation Object
161 
162  /// The contained implementation object
164 
165 public:
166  // *** Constructors and Destructor
167 
168  /// Default constructor initializing an empty B+ tree with the standard key
169  /// comparison function
170  explicit inline btree_map(const allocator_type &alloc = allocator_type())
171  : tree(alloc)
172  {
173  }
174 
175  /// Constructor initializing an empty B+ tree with a special key
176  /// comparison object
177  explicit inline btree_map(const key_compare &kcf,
178  const allocator_type &alloc = allocator_type())
179  : tree(kcf, alloc)
180  {
181  }
182 
183  /// Constructor initializing a B+ tree with the range [first,last)
184  template <class InputIterator>
185  inline btree_map(InputIterator first, InputIterator last,
186  const allocator_type &alloc = allocator_type())
187  : tree(first, last, alloc)
188  {
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  inline 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 
200  /// Frees up all used B+ tree memory pages
201  inline ~btree_map()
202  {
203  }
204 
205  /// Fast swapping of two identical B+ tree objects.
206  void swap(self& from)
207  {
208  std::swap(tree, from.tree);
209  }
210 
211 public:
212  // *** Key and Value Comparison Function Objects
213 
214  /// Constant access to the key comparison object sorting the B+ tree
215  inline key_compare key_comp() const
216  {
217  return tree.key_comp();
218  }
219 
220  /// Constant access to a constructed value_type comparison object. required
221  /// by the STL
222  inline value_compare value_comp() const
223  {
224  return tree.value_comp();
225  }
226 
227 public:
228  // *** Allocators
229 
230  /// Return the base node allocator provided during construction.
232  {
233  return tree.get_allocator();
234  }
235 
236 public:
237  // *** Fast Destruction of the B+ Tree
238 
239  /// Frees all key/data pairs and all nodes of the tree
240  void clear()
241  {
242  tree.clear();
243  }
244 
245 public:
246  // *** STL Iterator Construction Functions
247 
248  /// Constructs a read/data-write iterator that points to the first slot in
249  /// the first leaf of the B+ tree.
250  inline iterator begin()
251  {
252  return tree.begin();
253  }
254 
255  /// Constructs a read/data-write iterator that points to the first invalid
256  /// slot in the last leaf of the B+ tree.
257  inline iterator end()
258  {
259  return tree.end();
260  }
261 
262  /// Constructs a read-only constant iterator that points to the first slot
263  /// in the first leaf of the B+ tree.
264  inline const_iterator begin() const
265  {
266  return tree.begin();
267  }
268 
269  /// Constructs a read-only constant iterator that points to the first
270  /// invalid slot in the last leaf of the B+ tree.
271  inline const_iterator end() const
272  {
273  return tree.end();
274  }
275 
276  /// Constructs a read/data-write reverse iterator that points to the first
277  /// invalid slot in the last leaf of the B+ tree. Uses STL magic.
279  {
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  {
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  {
294  return tree.rbegin();
295  }
296 
297  /// Constructs a read-only reverse iterator that points to the first slot
298  /// in the first leaf of the B+ tree. Uses STL magic.
300  {
301  return tree.rend();
302  }
303 
304 public:
305  // *** Access Functions to the Item Count
306 
307  /// Return the number of key/data pairs in the B+ tree
308  inline size_type size() const
309  {
310  return tree.size();
311  }
312 
313  /// Returns true if there is at least one key/data pair in the B+ tree
314  inline bool empty() const
315  {
316  return tree.empty();
317  }
318 
319  /// Returns the largest possible size of the B+ Tree. This is just a
320  /// function required by the STL standard, the B+ Tree can hold more items.
321  inline size_type max_size() const
322  {
323  return tree.max_size();
324  }
325 
326  /// Return a const reference to the current statistics.
327  inline const tree_stats& get_stats() const
328  {
329  return tree.get_stats();
330  }
331 
332 public:
333  // *** Standard Access Functions Querying the Tree by Descending to a Leaf
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  {
339  return tree.exists(key);
340  }
341 
342  /// Tries to locate a key in the B+ tree and returns an iterator to the
343  /// key/data slot if found. If unsuccessful it returns end().
344  iterator find(const key_type &key)
345  {
346  return tree.find(key);
347  }
348 
349  /// Tries to locate a key in the B+ tree and returns an constant iterator
350  /// to the key/data slot if found. If unsuccessful it returns end().
351  const_iterator find(const key_type &key) const
352  {
353  return tree.find(key);
354  }
355 
356  /// Tries to locate a key in the B+ tree and returns the number of
357  /// identical key entries found. Since this is a unique map, count()
358  /// returns either 0 or 1.
359  size_type count(const key_type &key) const
360  {
361  return tree.count(key);
362  }
363 
364  /// Searches the B+ tree and returns an iterator to the first pair
365  /// equal to or greater than key, or end() if all keys are smaller.
367  {
368  return tree.lower_bound(key);
369  }
370 
371  /// Searches the B+ tree and returns a constant iterator to the
372  /// first pair equal to or greater than key, or end() if all keys
373  /// are smaller.
375  {
376  return tree.lower_bound(key);
377  }
378 
379  /// Searches the B+ tree and returns an iterator to the first pair
380  /// greater than key, or end() if all keys are smaller or equal.
382  {
383  return tree.upper_bound(key);
384  }
385 
386  /// Searches the B+ tree and returns a constant iterator to the
387  /// first pair greater than key, or end() if all keys are smaller
388  /// or equal.
390  {
391  return tree.upper_bound(key);
392  }
393 
394  /// Searches the B+ tree and returns both lower_bound() and upper_bound().
395  inline std::pair<iterator, iterator> equal_range(const key_type& key)
396  {
397  return tree.equal_range(key);
398  }
399 
400  /// Searches the B+ tree and returns both lower_bound() and upper_bound().
401  inline std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
402  {
403  return tree.equal_range(key);
404  }
405 
406 public:
407  // *** B+ Tree Object Comparison Functions
408 
409  /// Equality relation of B+ trees of the same type. B+ trees of the same
410  /// size and equal elements (both key and data) are considered
411  /// equal.
412  inline bool operator==(const self &other) const
413  {
414  return (tree == other.tree);
415  }
416 
417  /// Inequality relation. Based on operator==.
418  inline bool operator!=(const self &other) const
419  {
420  return (tree != other.tree);
421  }
422 
423  /// Total ordering relation of B+ trees of the same type. It uses
424  /// std::lexicographical_compare() for the actual comparison of elements.
425  inline bool operator<(const self &other) const
426  {
427  return (tree < other.tree);
428  }
429 
430  /// Greater relation. Based on operator<.
431  inline bool operator>(const self &other) const
432  {
433  return (tree > other.tree);
434  }
435 
436  /// Less-equal relation. Based on operator<.
437  inline bool operator<=(const self &other) const
438  {
439  return (tree <= other.tree);
440  }
441 
442  /// Greater-equal relation. Based on operator<.
443  inline bool operator>=(const self &other) const
444  {
445  return (tree >= other.tree);
446  }
447 
448 public:
449  /// *** Fast Copy: Assign Operator and Copy Constructors
450 
451  /// Assignment operator. All the key/data pairs are copied
452  inline self& operator= (const self &other)
453  {
454  if (this != &other)
455  {
456  tree = other.tree;
457  }
458  return *this;
459  }
460 
461  /// Copy constructor. The newly initialized B+ tree object will contain a
462  /// copy of all key/data pairs.
463  inline btree_map(const self &other)
464  : tree(other.tree)
465  {
466  }
467 
468 public:
469  // *** Public Insertion Functions
470 
471  /// Attempt to insert a key/data pair into the B+ tree. Fails if the pair
472  /// is already present.
473  inline std::pair<iterator, bool> insert(const value_type& x)
474  {
475  return tree.insert2(x.first, x.second);
476  }
477 
478  /// Attempt to insert a key/data pair into the B+ tree. Beware that if
479  /// key_type == data_type, then the template iterator insert() is called
480  /// instead. Fails if the inserted pair is already present.
481  inline std::pair<iterator, bool> insert(const key_type& key, const data_type& data)
482  {
483  return tree.insert2(key, data);
484  }
485 
486  /// Attempt to insert a key/data pair into the B+ tree. This function is the
487  /// same as the other insert, however if key_type == data_type then the
488  /// non-template function cannot be called. Fails if the inserted pair is
489  /// already present.
490  inline std::pair<iterator, bool> insert2(const key_type& key, const data_type& data)
491  {
492  return tree.insert2(key, data);
493  }
494 
495  /// Attempt to insert a key/data pair into the B+ tree. The iterator hint
496  /// is currently ignored by the B+ tree insertion routine.
497  inline iterator insert(iterator hint, const value_type &x)
498  {
499  return tree.insert2(hint, x.first, x.second);
500  }
501 
502  /// Attempt to insert a key/data pair into the B+ tree. The iterator hint is
503  /// currently ignored by the B+ tree insertion routine.
504  inline iterator insert2(iterator hint, const key_type& key, const data_type& data)
505  {
506  return tree.insert2(hint, key, data);
507  }
508 
509  /// Returns a reference to the object that is associated with a particular
510  /// key. If the map does not already contain such an object, operator[]
511  /// inserts the default object data_type().
512  inline data_type& operator[](const key_type& key)
513  {
514  iterator i = insert( value_type(key, data_type()) ).first;
515  return i.data();
516  }
517 
518  /// Attempt to insert the range [first,last) of value_type pairs into the B+
519  /// tree. Each key/data pair is inserted individually.
520  template <typename InputIterator>
521  inline void insert(InputIterator first, InputIterator last)
522  {
523  return tree.insert(first, last);
524  }
525 
526  /// Bulk load a sorted range [first,last). Loads items into leaves and
527  /// constructs a B-tree above them. The tree must be empty when calling
528  /// this function.
529  template <typename Iterator>
530  inline void bulk_load(Iterator first, Iterator last)
531  {
532  return tree.bulk_load(first, last);
533  }
534 
535 public:
536  // *** Public Erase Functions
537 
538  /// Erases the key/data pairs associated with the given key. For this
539  /// unique-associative map there is no difference to erase().
540  bool erase_one(const key_type &key)
541  {
542  return tree.erase_one(key);
543  }
544 
545  /// Erases all the key/data pairs associated with the given key. This is
546  /// implemented using erase_one().
548  {
549  return tree.erase(key);
550  }
551 
552  /// Erase the key/data pair referenced by the iterator.
553  void erase(iterator iter)
554  {
555  return tree.erase(iter);
556  }
557 
558 #ifdef BTREE_TODO
559  /// Erase all key/data pairs in the range [first,last). This function is
560  /// currently not implemented by the B+ Tree.
561  void erase(iterator /* first */, iterator /* last */)
562  {
563  abort();
564  }
565 #endif
566 
567 #ifdef BTREE_DEBUG
568 public:
569  // *** Debug Printing
570 
571  /// Print out the B+ tree structure with keys onto the given ostream. This function
572  /// requires that the header is compiled with BTREE_DEBUG and that key_type
573  /// is printable via std::ostream.
574  void print(std::ostream &os) const
575  {
576  tree.print(os);
577  }
578 
579  /// Print out only the leaves via the double linked list.
580  void print_leaves(std::ostream &os) const
581  {
582  tree.print_leaves(os);
583  }
584 #endif
585 
586 public:
587  // *** Verification of B+ Tree Invariants
588 
589  /// Run a thorough verification of all B+ tree invariants. The program
590  /// aborts via BTREE_ASSERT() if something is wrong.
591  void verify() const
592  {
593  tree.verify();
594  }
595 
596 public:
597 
598  /// Dump the contents of the B+ tree out onto an ostream as a binary
599  /// image. The image contains memory pointers which will be fixed when the
600  /// image is restored. For this to work your key_type and data_type must be
601  /// integral types and contain no pointers or references.
602  void dump(std::ostream &os) const
603  {
604  tree.dump(os);
605  }
606 
607  /// Restore a binary image of a dumped B+ tree from an istream. The B+ tree
608  /// pointers are fixed using the dump order. For dump and restore to work
609  /// your key_type and data_type must be integral types and contain no
610  /// pointers or references. Returns true if the restore was successful.
611  bool restore(std::istream &is)
612  {
613  return tree.restore(is);
614  }
615 };
616 
617 } // namespace stx
618 
619 #endif // _STX_BTREE_MAP_H_
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_map.h:366
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
Definition: btree_map.h:337
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
Definition: btree_map.h:285
static const bool selfverify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
Definition: btree.h:243
~btree_map()
Frees up all used B+ tree memory pages.
Definition: btree_map.h:201
bool operator<=(const self &other) const
Less-equal relation. Based on operator<.
Definition: btree_map.h:437
static const bool selfverify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
Definition: btree_map.h:132
size_type size() const
Return the number of key/data pairs in the B+ tree.
Definition: btree.h:1728
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...
Definition: btree_map.h:351
const tree_stats & get_stats() const
Return a const reference to the current statistics.
Definition: btree_map.h:327
iterator insert2(iterator hint, const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree_map.h:504
size_type max_size() const
Returns the largest possible size of the B+ Tree.
Definition: btree_map.h:321
self & operator=(const self &other)
*** Fast Copy: Assign Operator and Copy Constructors
Definition: btree_map.h:452
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_map.h:292
btree_map(const key_compare &kcf, const allocator_type &alloc=allocator_type())
Constructor initializing an empty B+ tree with a special key comparison object.
Definition: btree_map.h:177
btree_impl::const_reverse_iterator const_reverse_iterator
create constant reverse iterator by using STL magic
Definition: btree_map.h:157
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
Definition: btree.h:1402
void insert(InputIterator first, InputIterator last)
Attempt to insert the range [first,last) of value_type pairs into the B+ tree.
Definition: btree_map.h:521
void bulk_load(Iterator first, Iterator last)
Bulk load a sorted range [first,last).
Definition: btree_map.h:530
Basic class implementing a base B+ tree data structure in memory.
Definition: btree.h:163
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_map.h:344
void erase(iterator, iterator)
Erase all key/data pairs in the range [first,last).
Definition: btree_map.h:561
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Definition: btree.h:2619
bool operator>(const self &other) const
Greater relation. Based on operator<.
Definition: btree_map.h:431
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition: btree.h:1940
iterator insert(iterator hint, const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree_map.h:497
btree_impl::value_compare value_compare
Function class comparing two value_type pairs.
Definition: btree_map.h:102
void verify() const
Run a thorough verification of all B+ tree invariants.
Definition: btree_map.h:591
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree...
Definition: btree_map.h:137
size_type max_size() const
Returns the largest possible size of the B+ Tree.
Definition: btree.h:1741
void swap(self &from)
Fast swapping of two identical B+ tree objects.
Definition: btree_map.h:206
static const unsigned short mininnerslots
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
Definition: btree_map.h:128
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree...
Definition: btree.h:248
data_type & operator[](const key_type &key)
Returns a reference to the object that is associated with a particular key.
Definition: btree_map.h:512
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_map.h:299
void verify() const
Run a thorough verification of all B+ tree invariants.
Definition: btree.h:3630
iterator upper_bound(const key_type &key)
Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys...
Definition: btree.h:1898
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...
Definition: btree_map.h:250
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
Definition: btree.h:1608
btree_map(const self &other)
Copy constructor.
Definition: btree_map.h:463
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
Definition: btree.h:3860
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
Definition: btree_map.h:222
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
Definition: btree.h:2401
bool erase_one(const key_type &key)
Erases the key/data pairs associated with the given key.
Definition: btree_map.h:540
static const unsigned short leafslotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
Definition: btree.h:225
static const unsigned short mininnerslots
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
Definition: btree.h:239
_Alloc allocator_type
Fifth template parameter: STL allocator.
Definition: btree_map.h:80
#define BTREE_FRIENDS
The macro BTREE_FRIENDS can be used by outside class to access the B+ tree internals.
Definition: btree.h:77
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
Definition: btree.h:1395
size_type count(const key_type &key) const
Tries to locate a key in the B+ tree and returns the number of identical key entries found...
Definition: btree.h:1822
btree_impl tree
The contained implementation object.
Definition: btree_map.h:163
std::pair< iterator, bool > insert2(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree.h:2106
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
Definition: btree.h:1601
_Compare key_compare
Third template parameter: Key comparison function object.
Definition: btree_map.h:73
_Data data_type
Second template parameter: The data type associated with each key.
Definition: btree_map.h:70
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_map.h:381
Contains the main B+ tree implementation template class btree.
btree_impl::tree_stats tree_stats
Small structure containing statistics about the tree.
Definition: btree_map.h:108
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
Definition: btree_map.h:395
btree_impl::size_type size_type
Size type used to count keys.
Definition: btree_map.h:105
void clear()
Frees all key/data pairs and all nodes of the tree.
Definition: btree_map.h:240
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree...
Definition: btree.h:1573
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
Definition: btree.h:1734
btree_map(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function...
Definition: btree_map.h:170
bool restore(std::istream &is)
Restore a binary image of a dumped B+ tree from an istream.
Definition: btree_map.h:611
btree_impl::reverse_iterator reverse_iterator
create mutable reverse iterator by using STL magic
Definition: btree_map.h:154
iterator lower_bound(const key_type &key)
Searches the B+ tree and returns an iterator to the first pair equal to or greater than key...
Definition: btree.h:1855
std::pair< iterator, bool > insert(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree_map.h:481
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given key.
Definition: btree.h:2596
const struct tree_stats & get_stats() const
Return a const reference to the current statistics.
Definition: btree.h:1747
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.h:95
static const bool allow_duplicates
Sixth template parameter: Allow duplicate keys in the B+ tree.
Definition: btree.h:191
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_map.h:359
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
Definition: btree_map.h:257
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
Definition: btree.h:1757
std::pair< iterator, bool > insert(const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree_map.h:473
bool operator!=(const self &other) const
Inequality relation. Based on operator==.
Definition: btree_map.h:418
bool operator<(const self &other) const
Total ordering relation of B+ trees of the same type.
Definition: btree_map.h:425
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
Definition: btree_map.h:314
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...
Definition: btree_map.h:194
static const unsigned short innerslotmax
Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...
Definition: btree_map.h:118
iterator find(const key_type &key)
Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found...
Definition: btree.h:1778
void print_leaves(std::ostream &os) const
Print out only the leaves via the double linked list.
Definition: btree_map.h:580
void dump(std::ostream &os) const
Dump the contents of the B+ tree out onto an ostream as a binary image.
Definition: btree.h:3843
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
Definition: btree_map.h:215
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
Definition: btree.h:1580
stx::btree< key_type, data_type, value_type, key_compare, traits, false, allocator_type, false > btree_impl
Implementation type of the btree_base.
Definition: btree_map.h:99
size_type size() const
Return the number of key/data pairs in the B+ tree.
Definition: btree_map.h:308
btree_impl::const_iterator const_iterator
STL-like iterator object for B+ tree items.
Definition: btree_map.h:151
bool operator>=(const self &other) const
Greater-equal relation. Based on operator<.
Definition: btree_map.h:443
void print_leaves(std::ostream &os) const
Print out only the leaves via the double linked list.
Definition: btree.h:3564
static const bool allow_duplicates
Operational parameter: Allow duplicate keys in the btree.
Definition: btree_map.h:140
void erase(iterator iter)
Erase the key/data pair referenced by the iterator.
Definition: btree_map.h:553
std::pair< iterator, bool > insert2(const key_type &key, const data_type &data)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree_map.h:490
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_map.h:389
static const unsigned short minleafslots
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
Definition: btree.h:234
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_map.h:401
std::pair< iterator, bool > insert(const pair_type &x)
Attempt to insert a key/data pair into the B+ tree.
Definition: btree.h:2088
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Definition: btree_map.h:547
void dump(std::ostream &os) const
Dump the contents of the B+ tree out onto an ostream as a binary image.
Definition: btree_map.h:602
_Key key_type
First template parameter: The key type of the btree.
Definition: btree_map.h:66
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Definition: btree_map.h:231
void print(std::ostream &os) const
Print out the B+ tree structure with keys onto the given ostream.
Definition: btree_map.h:574
bool operator==(const self &other) const
Equality relation of B+ trees of the same type.
Definition: btree_map.h:412
void print(std::ostream &os) const
Print out the B+ tree structure with keys onto the given ostream.
Definition: btree.h:3556
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
Definition: btree_map.h:278
Specialized B+ tree template class implementing STL's map container.
Definition: btree_map.h:59
_Traits traits
Fourth template parameter: Traits object used to define more parameters of the B+ tree...
Definition: btree_map.h:77
btree_impl::iterator iterator
STL-like iterator object for B+ tree items.
Definition: btree_map.h:147
static const unsigned short innerslotmax
Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in eac...
Definition: btree.h:229
const_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_map.h:374
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_map.h:271
allocator_type get_allocator() const
Return the base node allocator provided during construction.
Definition: btree.h:1445
static const unsigned short minleafslots
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
Definition: btree_map.h:123
btree_map(InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())
Constructor initializing a B+ tree with the range [first,last)
Definition: btree_map.h:185
void clear()
Frees all key/data pairs and all nodes of the tree.
Definition: btree.h:1527
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_map.h:264
static const unsigned short leafslotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
Definition: btree_map.h:114