Summed

template<typename Value, typename Extractor = ValueExtractor>
struct Summed

Summed mixin adds prefix sum support to a B++ tree in O(log N) time sum() returns the sum over the entire tree sum_inclusive(it) returns the sum up to and including the element pointed to by the iterator ‘it’ sum_exclusive(it) returns the sum up to but not including the element pointed to by the iterator ‘it’ If you want to sum between two iterators, do sum_exclusive(it2)-sum_exclusive(it1) sum_lower_bound(target) returns an iterator pointing to the first element for which sum_inclusive(it) >= target

Template Parameters:

• Value – the value type of the B++ tree

• Extractor – a class which implements operator()(Value) to return the value to be summed

Public Types

template<typename Parent>
using LeafNode = SummedLeafNode<Parent, SumType, Extractor>

template<typename Parent, auto internal_size>
using InternalNode = SummedInternalNode<Parent, SumType, internal_size>

template<typename Parent>
using NodeInfo = SummedNodeInfo<Parent, SumType>

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 Parent>
struct Shared : public Parent

Public Functions

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

inline Parent::iterator sum_lower_bound(SumType target)

Returns:

an iterator pointing to the first element such that sum_inclusive(it) >= target

inline Parent::const_iterator sum_lower_bound_const(SumType target) const

Returns:

a const_iterator pointing to the first element such that sum_inclusive(it) >= target

inline Parent::const_iterator sum_lower_bound(SumType target) const

Returns:

a const_iterator pointing to the first element such that sum_inclusive(it) >= target

inline SumType sum() const

Returns:

the sum of all elements in the tree

template<typename It>
inline SumType sum_inclusive(It const &it) const

Returns:

the sum of all elements up to and including the element pointed to by the iterator it

template<typename It>
inline SumType sum_exclusive(It const &it) const

Returns:

the sum of all elements up to but not including the element pointed to by the iterator it

template<typename Parent>
struct Transient : public Parent

Public Functions

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