Template Class SplayTree

• Defined in File SplayTree.h

Nested Relationships

Nested Types

• Struct SplayTree::Node

• Struct SplayTree::Shape

Class Documentation

template<std::totally_ordered K, class V>
class SplayTree

a DICTIONARY on a splay tree

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 const_iterator = PathIterator<SplayTree, Shape>

using iterator = const_iterator

Public Functions

SplayTree(void) = default

SplayTree(const SplayTree&) = delete

SplayTree &operator=(const SplayTree&) = delete

SplayTree(SplayTree &&other) noexcept

the nodes of other, which is left empty

~SplayTree()

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

the value of k, or nothing; k, or the last node on its path, goes to the root

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

Post:

k has the value v, at the root

void remove(const K &k)

Post:

k is not there

std::size_t size(void) const

std::optional<K> root(void) const

the key at the root, if any

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

f( k , v ) on the pairs by increasing keys

inline const_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const

struct Shape

the shape of the tree, for PathIterator

Public Static Functions

static inline auto root(const auto &o)

static inline auto left(const auto *n)

static inline auto right(const auto *n)

static inline auto read(const auto *n)