Template Class LinkedHashSet

• Defined in File LinkedHashSet.h

Class Documentation

template<class T, class H = std::hash<T>>
class LinkedHashSet

a set on a hash table whose foreach follows the order of insertion: a LIST keeps the items in that order and the table maps each item to its position, so insert(), remove() and contains() take O( 1 ) expected time and forEach() O( n ) (exercise 8.9)

Public Types

using Item = T

the type of the items

using value_type = T

using size_type = std::size_t

using difference_type = std::ptrdiff_t

using reference = const T&

using const_reference = const T&

using const_iterator = typename List<T>::const_iterator

using iterator = const_iterator

Public Functions

LinkedHashSet(void)

LinkedHashSet(const LinkedHashSet &o)

a copy, with positions into its own list

LinkedHashSet &operator=(const LinkedHashSet&) = delete

std::size_t size(void) const

bool empty(void) const

bool contains(const T &x) const

void insert(const T &x)

a new item goes to the end of the order; an item already there keeps its place

Post:

x is in the set

void remove(const T &x)

Post:

x is not in the set

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

f( x ) on the items in the order of insertion, O( n ) time

inline const_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const