Template Class BTreeMap

• Defined in File BTreeMap.h

Nested Relationships

Nested Types

• Struct BTreeMap::Inner

• Struct BTreeMap::Leaf

• Struct BTreeMap::None

• Struct BTreeMap::Step

• Class BTreeMap::const_iterator

Class Documentation

template<class K, class V, class Less = std::less<K>, std::size_t B = 512, bool R = false>
class BTreeMap

an ordered map on a B+-tree of nodes of B bytes, by the order less(), with the counts of the pairs below each child if R (the ranks)

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 BTreeMap(Less less = Less())

BTreeMap(const BTreeMap &o)

BTreeMap(BTreeMap &&o) noexcept

BTreeMap &operator=(BTreeMap o) noexcept

~BTreeMap()

std::optional<V> lookup(const K &k) const

the value of k, if there

const V *find(const K &k) const

the value of k, to change in place, or nullptr

V *find(const K &k)

bool insert(const K &k, const V &v)

gives k the value v; true if k was not there

bool remove(const K &k)

removes k; true if it was there

bool contains(const K &k) const

std::size_t size(void) const

bool empty(void) const

int height(void) const

the levels of the tree, 0 if empty, 1 if a single leaf

void clear(void)

template<std::input_iterator It>
void build(It first, It last)

replaces the pairs with those of [ first , last ), pairs ( key , value ) by strictly increasing keys, all the nodes full

Pre:

the keys are strictly increasing (an audit)

template<class F>
void forEach(F &&f) const

f( key , value ) on each pair, by increasing keys

template<class F>
void forRange(const K &lo, const K &hi, F &&f) const

f( key , value ) on each pair of key in [ lo , hi ), by increasing keys

void swap(BTreeMap &o) noexcept

const_iterator begin(void) const

const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const

const_iterator lowerBound(const K &k) const

the first pair whose key is not smaller than k

const_iterator upperBound(const K &k) const

the first pair whose key is larger than k

const_iterator erase(const_iterator it)

removes the pair of it, and gives the one after it

std::size_t rank(const K &k) const

the pairs whose key is smaller than k, O( ( L + I ) log n ) time

const_iterator select(std::size_t i) const

the pair of rank i (from 0), end() if i >= size()

Public Static Attributes

static constexpr std::size_t L = std::clamp<std::size_t>(B / (sizeof(K) + sizeof(V)), 4, 255)

the pairs of a leaf

static constexpr std::size_t I = std::clamp<std::size_t>(B / (sizeof(K) + sizeof(void*)), 4, 255)

the keys of an internal node

class const_iterator

Public Types

using value_type = std::pair<const K&, const V&>

using reference = value_type

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 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