Template Class SPlusTree

Defined in File StaticSearch.h

Nested Relationships

Nested Types

Struct SPlusTree::Free

Class Documentation

template<class T, class Less = std::less<T>, std::size_t Bytes = 64> class SPlusTree

the static B+-tree of Slotin on a sorted array, by the order less()

Public Types

using Item = T : the type of the items

Public Functions

SPlusTree(void) = default

explicit SPlusTree(const std::vector<T> &A, Less less = Less())

the tree on the sorted items of A

Pre:: A is sorted (an audit)

SPlusTree(const SPlusTree &o)

SPlusTree(SPlusTree &&o) noexcept = default

SPlusTree &operator=(SPlusTree o) noexcept

std::size_t lowerBound(const T &v) const: the first place of an item not smaller than v, size() if none

std::size_t upperBound(const T &v) const: the first place of an item larger than v, size() if none

bool contains(const T &v) const

const T &operator[](std::size_t i) const: the item of place i, in the sorted order

std::size_t size(void) const

bool empty(void) const

int height(void) const: the levels, the leaves included

Public Static Attributes

static constexpr std::size_t B = sizeof(T) <= Bytes ? std::max<std::size_t>(Bytes / sizeof(T), 2) : 2: the items of a node, a line of cache