Go to the documentation of this file.
11 #ifndef TLX_CONTAINER_BTREE_SET_HEADER
12 #define TLX_CONTAINER_BTREE_SET_HEADER
37 template <
typename Key_,
38 typename Compare_ = std::less<Key_>,
39 typename Traits_ = btree_default_traits<Key_, Key_>,
40 typename Alloc_ = std::allocator<Key_> >
95 typedef typename btree_impl::tree_stats
tree_stats;
140 typedef typename btree_impl::iterator
iterator;
181 template <
class InputIterator>
182 btree_set(InputIterator first, InputIterator last,
190 template <
class InputIterator>
193 :
tree_(kcf, alloc) {
387 std::pair<const_iterator, const_iterator>
equal_range(
401 return (
tree_ == other.tree_);
406 return (
tree_ != other.tree_);
412 return (
tree_ < other.tree_);
417 return (
tree_ > other.tree_);
422 return (
tree_ <= other.tree_);
427 return (
tree_ >= other.tree_);
468 template <
typename InputIterator>
469 void insert(InputIterator first, InputIterator last) {
470 InputIterator iter = first;
481 template <
typename Iterator>
482 void bulk_load(Iterator first, Iterator last) {
508 #ifdef TLX_BTREE_TODO
518 #ifdef TLX_BTREE_DEBUG
527 void print(std::ostream& os)
const {
532 void print_leaves(std::ostream& os)
const {
533 tree_.print_leaves(os);
556 #endif // !TLX_CONTAINER_BTREE_SET_HEADER
btree_impl::tree_stats tree_stats
Small structure containing statistics about the tree.
btree_impl tree_
The contained implementation object.
void verify() const
Run a thorough verification of all B+ tree invariants.
Specialized B+ tree template class implementing STL's set container.
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
iterator begin()
Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree.
const struct tree_stats & get_stats() const
Return a const reference to the current statistics.
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
Traits_ traits
Third template parameter: Traits object used to define more parameters of the B+ tree.
void clear()
Frees all key/data pairs and all nodes of the tree.
Compare_ key_compare
Second template parameter: Key comparison function object.
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...
btree_impl::size_type size_type
Size type used to count keys.
void bulk_load(Iterator ibegin, Iterator iend)
Bulk load a sorted range.
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
btree_impl::reverse_iterator reverse_iterator
create mutable reverse iterator by using STL magic
const tree_stats & get_stats() const
Return a const reference to the current statistics.
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
BTree< key_type, value_type, key_of_value, key_compare, traits, false, allocator_type > btree_impl
Implementation type of the btree_base.
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...
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.
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
void clear()
Frees all keys and all nodes of the tree.
std::pair< iterator, bool > insert(const value_type &x)
Attempt to insert a key/data pair into the B+ tree.
bool operator>=(const btree_set &other) const
Greater-equal relation. Based on operator<.
bool operator>(const btree_set &other) const
Greater relation. Based on operator<.
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
size_type max_size() const
Returns the largest possible size of the B+ Tree.
static const bool allow_duplicates
Operational parameter: Allow duplicate keys in the btree.
void swap(btree_set &from)
Fast swapping of two identical B+ tree objects.
bool erase_one(const key_type &key)
Erases the key from the set.
iterator find(const key_type &key)
Tries to locate a key in the B+ tree and returns an iterator to the key slot if found.
void bulk_load(Iterator first, Iterator last)
Bulk load a sorted range [first,last).
size_type max_size() const
Returns the largest possible size of the B+ Tree.
bool erase_one(const key_type &key)
Erases one (the first) of the key/data pairs associated with the given 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...
bool operator<(const btree_set &other) const
Total ordering relation of B+ trees of the same type.
btree_impl::const_iterator const_iterator
STL-like iterator object for B+ tree items.
static const unsigned short inner_slotmin
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
bool empty() const
Returns true if there is at least one key in the B+ tree.
btree_impl::value_compare value_compare
Function class comparing two value_type keys.
~btree_set()
Frees up all used B+ tree memory pages.
static const bool debug
Debug parameter: Prints out lots of debug information about how the algorithms change the tree.
std::pair< iterator, iterator > equal_range(const key_type &key)
Searches the B+ tree and returns both lower_bound() and upper_bound().
allocator_type get_allocator() const
Return the base node allocator provided during construction.
TLX_BTREE_FRIENDS
The macro TLX_BTREE_FRIENDS can be used by outside class to access the B+ tree internals.
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,...
btree_impl::iterator iterator
STL-like iterator object for B+ tree items.
static const bool self_verify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
btree_impl::const_reverse_iterator const_reverse_iterator
create constant reverse iterator by using STL magic
value_compare value_comp() const
Constant access to a constructed value_type comparison object.
size_type size() const
Return the number of key/data pairs in the B+ tree.
key_type value_type
Construct the set value_type: the key_type.
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,...
key_compare key_comp() const
Constant access to the key comparison object sorting the B+ tree.
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
static const bool self_verify
Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/...
btree_set(const allocator_type &alloc=allocator_type())
Default constructor initializing an empty B+ tree with the standard key comparison function.
reverse_iterator rend()
Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the ...
allocator_type get_allocator() const
Return the base node allocator provided during construction.
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given key.
Key_ key_type
First template parameter: The key type of the B+ tree.
static const key_type & get(const value_type &v)
pull first out of pair
size_type size() const
Return the number of keys in the B+ tree.
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
swap enclosed object with another counting pointer (no reference counts need change)
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.
Basic class implementing a B+ tree data structure in memory.
iterator end()
Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B...
Alloc_ allocator_type
Fourth template parameter: STL allocator.
void verify() const
Run a thorough verification of all B+ tree invariants.
static const unsigned short leaf_slotmin
Computed B+ tree parameter: The minimum number of key slots used in a leaf.
bool empty() const
Returns true if there is at least one key/data pair in the B+ tree.
bool exists(const key_type &key) const
Non-STL function checking whether a key is in the B+ tree.
bool operator!=(const btree_set &other) const
Inequality relation. Based on operator==.
static const unsigned short leaf_slotmin
Computed B+ tree parameter: The minimum number of key/data slots used in a leaf.
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_set &other) const
Less-equal relation. Based on operator<.
size_type erase(const key_type &key)
Erases all the key/data pairs associated with the given 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...
static const bool allow_duplicates
Sixth template parameter: Allow duplicate keys in the B+ tree.
static const unsigned short inner_slotmin
Computed B+ tree parameter: The minimum number of key slots used in an inner node.
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.
static const unsigned short leaf_slotmax
Base B+ tree parameter: The number of key slots in each leaf.
std::pair< iterator, bool > insert(const key_type &x)
Attempt to insert a key into the B+ tree.
size_t size_type
Size type used to count keys.
reverse_iterator rbegin()
Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf ...
bool operator==(const btree_set &other) const
Equality relation of B+ trees of the same type.
static const unsigned short leaf_slotmax
Base B+ tree parameter: The number of key/data slots in each leaf.
btree_set & operator=(const btree_set &other)
Assignment operator. All the keys are copied.