Indexed

template<typename Value, typename SizeType = size_t> struct Indexed

Indexed mixin adds support for indexing into a B++ tree by an integer index Supports lookup, assign, insert, update, and erase by index in O(log N) time Also supports getting the index of an element from an iterator Given two iterators a and b from an indexed tree, a-b is O(log N) (it is O(N) for non-indexed trees)

Template Parameters:

Value – value type of tree
SizeType – type to use for index

Public Types

template<typename Parent> using LeafNode = IndexedLeafNode<Parent, Value, SizeType>

template<typename Parent, auto internal_size> using InternalNode = IndexedInternalNode<Parent, Value, SizeType, internal_size>

template<typename Parent> using NodeInfo = IndexedNodeInfo<Parent, SizeType>

Public Static Functions

static inline constexpr size_t sizeof_hint()

template<typename Parent> struct Persistent : public Parent 

Public Functions

template<typename ...Us> inline explicit Persistent(Us&&... us)

template<typename ...Args> inline auto insert_index(SizeType index, Args&&... args) const

Makes a transient copy of tree, calls insert_index on it with index and args, makes a persistent copy of the transient tree, and returns it.

Returns:: A copy of this tree that has been modified by calling insert_index with index and args

template<typename ...Args> inline auto assign_index(SizeType index, Args&&... args) const

Makes a transient copy of tree, calls assign_index on it with index and args, makes a persistent copy of the transient tree, and returns it.

Returns:: A copy of this tree that has been modified by calling assign_index with index and args

inline auto erase_index(SizeType index) const

Makes a transient copy of tree, calls erase_index on it with index, makes a persistent copy of the transient tree, and returns it.

Returns:: A copy of this tree that has been modified by calling erase_index with index

template<typename U> inline auto update_index(SizeType index, U &&updater) const

Makes a transient copy of tree, calls update_index on it with index and updater, makes a persistent copy of the transient tree, and returns it.

Returns:: A copy of this tree that has been modified by calling update_index with index and updater

inline Value const &operator[](SizeType const &index) const

Returns:: a const reference to the value at index

template<typename Parent> struct Shared : public Parent 

Public Functions

template<typename ...Us> inline explicit Shared(Us&&... us)

inline Value const &at_index(SizeType index) const

Returns:: a const reference to the value at index

inline Parent::iterator find_index(SizeType index)

Returns:: a forward iterator pointing to the element at index

inline Parent::const_iterator find_index_const(SizeType index) const

Returns:: a forward const_iterator pointing to the element at index

inline Parent::const_iterator find_index(SizeType index) const

Returns:: a forward const_iterator pointing to the element at index

template<typename It> inline SizeType order(It const &it) const

Template Parameters:: It – the type of iterator (supports const and non-const iterators as well as forward and reverse)
Parameters:: it – an iterator of type It
Returns:: the index of the element pointed to by the iterator

template<typename Parent> struct Transient : public Parent 

Public Functions

template<typename ...Us> inline explicit Transient(Us&&... us)

template<typename ...Args> inline void insert_index(SizeType index, Args&&... args): Constructs an element in place at index using args, moving all elements starting from index back by one

template<typename ...Args> inline void assign_index(SizeType index, Args&&... args): Constructs and element in place at index using args, replacing the element that is currently there

inline void erase_index(SizeType index): Erases the element at index, moving all elements after it forward by one

template<typename U> inline void update_index(SizeType index, U &&updater)

Apply updater function to element at index, and overwrites the element at index with the returned result

Parameters:: updater – function that takes a Value const& and returns a Value (or something convertible to a Value)

inline ProxyRef operator[](SizeType const &index)

Returns:: a ProxyRef to the value at index which supports assignment, compound assignment, pre- and post- increment and decrement, all binary operators, and implicit conversion to const reference to Value.

inline Value const &operator[](SizeType const &index) const

Returns:: a const reference to the value at index

struct ProxyRef : public bpptree::detail::ProxyOperators<ProxyRef>

Public Functions

inline ProxyRef(Transient &tree, SizeType const &index)

~ProxyRef() = default

inline ProxyRef &operator=(Value const &value)

inline operator Value const&() const

inline Value const &get() const