Template Class SkipList

• Defined in File SkipList.h

Nested Relationships

Nested Types

• Struct SkipList::Node

• Class SkipList::const_iterator

Class Documentation

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

a DICTIONARY on a skip list

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 iterator = const_iterator

Public Functions

explicit SkipList(std::uint64_t seed = 1)

SkipList(const SkipList&) = delete

SkipList &operator=(const SkipList&) = delete

SkipList(SkipList &&other) noexcept

the nodes of other, which is left empty

~SkipList()

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

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

Post:

k has the value v

void remove(const K &k)

Post:

k is not there

bool contains(const K &k) const

std::size_t size(void) const

int levels(void) const

the number of levels in use

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

class const_iterator

Public Types

using reference = std::pair<const K&, const V&>

using value_type = reference

using difference_type = std::ptrdiff_t

using iterator_concept = std::forward_iterator_tag

using iterator_category = std::input_iterator_tag

Public Functions

const_iterator(void) = default

inline explicit const_iterator(const Node *x)

inline reference operator*(void) const

inline const_iterator &operator++(void)

inline const_iterator operator++(int)

bool operator==(const const_iterator &o) const = default