Ordered

Most of the time when using Ordered you will want the value type to be a std::pair. Ordered can support other value types, such as std::tuple (using KeyValueExtractor = TupleExtractor) and even arbitrary user defined classes, but they require a carefully crafted KeyValueExtractor to work properly.

template<typename KeyValue, typename KeyValueExtractor = PairExtractor<0>, typename LessThan = MinComparator, typename BinarySearch = std::false_type>
struct Ordered

Ordered mixin adds lookup by key into a B++ tree. Values in the B++ tree must be ordered by key to use Ordered. Supports lookup, lower_bound, upper_bound, assign, insert, update, and erase by key in O(log N) time

Template Parameters:

• KeyValue – the element type of the B++ tree

• KeyValueExtractor – a class which implements functions to get a key from a KeyValue, get a value from a KeyValue, or forward a key and value to another function in the correct order

• LessThan – a class which implements operator()(A const& a, B const& b) to return true if a < b and false otherwise

• BinarySearch – std::true_type to use binary search within internal and leaf nodes, std::false_type to use linear search. linear search is typically faster for value types, but binary search is likely to be faster if comparing two keys requires an indirection or if the nodes are exceptionally large.

Public Types

template<typename Parent>
using LeafNode = typename Detail::template LeafNode<Parent>

template<typename Parent, auto internal_size>
using InternalNode = typename Detail::template InternalNode<Parent, internal_size>

template<typename Parent>
using NodeInfo = typename Detail::template NodeInfo<Parent>

Public Static Functions

static inline constexpr size_t sizeof_hint()

template<typename Parent>
struct Persistent : public Parent

Public Types

using SelfType = typename Parent::SelfType

Public Functions

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

template<typename ...Args>
inline SelfType insert_v(Args&&... args) const

template<typename ...Args>
inline SelfType assign_v(Args&&... args) const

template<typename ...Args>
inline SelfType insert_or_assign(Args&&... args) const

inline SelfType erase_key(Key const &key) const

template<typename U>
inline SelfType update_key(Key const &key, U &&updater) const

inline GetValue operator[](Key const &key) const

template<typename Parent>
struct Shared : public Parent

Public Functions

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

inline decltype(auto) at_key(Key const &key) const

inline Parent::iterator find(Key const &key)

Returns:

an iterator pointing to the element with key ‘key’

inline Parent::const_iterator find_const(Key const &key) const

Returns:

a const_iterator pointing to the element with key ‘key’

inline Parent::const_iterator find(Key const &key) const

Returns:

a const_iterator pointing to the element with key ‘key’

inline Parent::iterator lower_bound(Key const &key)

Returns:

an iterator pointing to the first element with a key >= ‘key’

inline Parent::const_iterator lower_bound_const(Key const &key) const

Returns:

a const_iterator pointing to the first element with a key >= ‘key’

inline Parent::const_iterator lower_bound(Key const &key) const

Returns:

a const_iterator pointing to the first element with a key >= ‘key’

inline Parent::iterator upper_bound(Key const &key)

Returns:

an iterator pointing to the first element with a key >= ‘key’

inline Parent::const_iterator upper_bound_const(Key const &key) const

Returns:

a const_iterator pointing to the first element with a key > ‘key’

inline Parent::const_iterator upper_bound(Key const &key) const

Returns:

a const_iterator pointing to the first element with a key > ‘key’

inline bool contains(Key const &key) const

Returns:

true if this tree contains an element with key ‘key’, false otherwise

template<typename Parent>
struct Transient : public Parent

Public Functions

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

template<typename ...Args>
inline void insert_v(Args&&... args)

template<typename ...Args>
inline void assign_v(Args&&... args)

inline void erase_key(Key const &key)

template<typename U>
inline void update_key(Key const &key, U &&updater)

template<typename ...Args>
inline void insert_or_assign(Args&&... args)

inline ProxyRef operator[](Key const &key)

inline GetValue operator[](Key const &key) const

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

Public Functions

inline ProxyRef(Transient &tree, Key const &key)

~ProxyRef() = default

template<typename V>
inline ProxyRef &operator=(V &&value)

inline void check_key([[maybe_unused]] KeyValue const &key_value)

inline ProxyRef &operator=(KeyValue &value)

inline ProxyRef &operator=(KeyValue const &value)

inline ProxyRef &operator=(KeyValue &&value)

inline operator GetValue() const

inline GetValue get() const