Template Class BPlusTree

Nested Relationships

Nested Types

Class Documentation

template<std::totally_ordered K, class V>
class BPlusTree

a B+-tree of order m, without the removal

Public Types

using Key = K

the type of the keys

using Value = V

the type of the values

using value_type = std::pair<const K&, const V&>
using size_type = std::size_t
using difference_type = std::ptrdiff_t
using reference = value_type
using const_reference = value_type
using iterator = const_iterator

Public Functions

explicit BPlusTree(int m)

an empty B+-tree of order m > 2, the root a leaf

BPlusTree(const BPlusTree&) = delete
BPlusTree &operator=(const BPlusTree&) = delete
~BPlusTree()
std::optional<V> lookup(const K &x) const

the value of the key x, or nothing

void insert(const K &x, const V &v)

associates the value v to the key x

std::size_t size(void) const
int order(void) const

the order m

std::vector<std::pair<K, V>> range(const K &A, const K &B) const

the pairs with keys in [ A , B ], read along the list of the leaves

std::vector<std::vector<std::vector<K>>> levels(void) const

the keys of the nodes, level by level from the root, each level from left to right: the shape of the tree, as in Figura 6.7

void check(void) const

checks the shape [see shaped()] whatever the level of the contracts; it throws contract_violation if it fails

inline const_iterator begin(void) const
inline const_iterator end(void) const
inline const_iterator cbegin(void) const
inline const_iterator cend(void) const
class const_iterator

Public Types

using reference = std::pair<const K&, const V&>
using value_type = reference
using difference_type = std::ptrdiff_t
using iterator_concept = std::bidirectional_iterator_tag
using iterator_category = std::input_iterator_tag

Public Functions

const_iterator(void) = default
inline const_iterator(const BPlusTree *t, const Node *f, std::size_t i)
inline reference operator*(void) const
inline const_iterator &operator++(void)
inline const_iterator &operator--(void)
inline const_iterator operator++(int)
inline const_iterator operator--(int)
inline bool operator==(const const_iterator &o) const