An object of this class is a set that combines the lookup speed of an unordered_set<> and ordering and iterator stability capabilities of an std::list<>. More...

#include <linked_hash_set.hpp>

Public Types
using	Value = Key
	Short-hand for values, which in this case are simply the keys.

using	size_type = std::size_t
	Type for index into array of items, where items are all applicable objects including `Value`s and `Key`s.

using	difference_type = std::ptrdiff_t
	Type for difference of `size_type`s.

using	Const_iterator = typename Value_list::const_iterator
	Type for iterator pointing into an immutable structure of this type.

using	Iterator = Const_iterator
	Type for iterator pointing into a mutable structure of this type but actually that is not possible; so alias to Const_iterator. More...

using	Const_reverse_iterator = typename Value_list::const_reverse_iterator
	Type for reverse iterator pointing into an immutable structure of this type.

using	Reverse_iterator = Const_reverse_iterator
	Type for reverse iterator pointing into a mutable structure of this type but actually that is not possible; so alias to Const_reverse_iterator. More...

using	key_type = Key
	For container compliance (hence the irregular capitalization): `Key` type.

using	value_type = Value
	For container compliance (hence the irregular capitalization): `Value` type.

using	hasher = Hash
	For container compliance (hence the irregular capitalization): `Hash` type.

using	key_equal = Pred
	For container compliance (hence the irregular capitalization): `Pred` type.

using	pointer = Value *
	For container compliance (hence the irregular capitalization): pointer to `Key` type.

using	const_pointer = Value const *
	For container compliance (hence the irregular capitalization): pointer to `const Key` type.

using	reference = Value &
	For container compliance (hence the irregular capitalization): reference to `Key` type.

using	const_reference = Value const &
	For container compliance (hence the irregular capitalization): reference to `const Key` type.

using	iterator = Iterator
	For container compliance (hence the irregular capitalization): `Iterator` type.

using	const_iterator = Const_iterator
	For container compliance (hence the irregular capitalization): `Const_iterator` type.

Public Member Functions
	Linked_hash_set (size_type n_buckets=size_type(-1), Hash const &hasher_instance=Hash(), Pred const &key_equal_instance=Pred())
	Constructs empty structure with some basic parameters. More...

	Linked_hash_set (std::initializer_list< Value > values, size_type n_buckets=size_type(-1), Hash const &hasher_instance=Hash(), Pred const &key_equal_instance=Pred())
	Constructs structure with some basic parameters, and values initialized from initializer list. More...

	Linked_hash_set (Linked_hash_set const &src)
	Constructs object that is a copy of the given source. More...

	Linked_hash_set (Linked_hash_set &&src)
	Constructs object by making it equal to the given source, while the given source becomes as-if default-cted. More...

Linked_hash_set &	operator= (Linked_hash_set const &src)
	Overwrites this object with a copy of the given source. More...

Linked_hash_set &	operator= (Linked_hash_set &&src)
	Overwrites this object making it equal to the given source, while the given source becomes as-if default-cted. More...

std::pair< Iterator, bool >	insert (Value const &key)
	Attempts to insert the given key into the set. More...

Const_iterator	find (Key const &key) const
	Attempts to find the given key in the set. More...

size_type	count (Key const &key) const
	Returns the number of times a key is equivalent to the given one is present in the hash: either 1 or 0. More...

Value const &	const_front () const
	Returns reference to immutable front ("newest") element in the structure; formally equivalent to `*(this->const_newest())`. More...

Value const &	const_back () const
	Returns reference to immutable back ("oldest") element in the structure; formally equivalent to `*(--this->const_past_oldest())`. More...

void	touch (Const_iterator const &it)
	Given a valid iterator into the structure, makes the pointed to element "newest" by moving it from wherever it is to be first in the iteration order. More...

bool	touch (Key const &key)
	Given a key into the structure, makes the corresponding element "newest" by moving it from wherever it is to be first in the iteration order; or does nothing if no such key. More...

Iterator	erase (Const_iterator const &it)
	Erases the element pointed to by the given valid iterator. More...

Iterator	erase (Const_iterator const &it_newest, Const_iterator const &it_past_oldest)
	Erases all elements in the range [`it_newest`, `it_past_oldest`). More...

size_type	erase (Key const &key)
	Erases the element with the given key, if it exists. More...

void	pop_front ()
	Queue-style pop (erase) of the front – a/k/a newest – element. Behavior undefined if empty().

void	pop_back ()
	Queue-style pop (erase) of the back – a/k/a oldest – element. Behavior undefined if empty().

void	clear ()
	Makes it so that `size() == 0`.

void	swap (Linked_hash_set &other)
	Swaps the contents of this structure and `other`. More...

Iterator	begin () const
	Synonym of newest(). More...

Iterator	newest () const
	Returns first, a/k/a "newest," element's iterator (to immutable element, due to nature of this type). More...

Iterator	end () const
	Synonym of past_oldest(). More...

Iterator	past_oldest () const
	Returns one past last, a/k/a "oldest," element's iterator (to immutable element, due to nature of this type). More...

Const_iterator	cbegin () const
	Synonym of const_newest(). More...

Const_iterator	const_newest () const
	Returns first, a/k/a "newest," element's iterator (to immutable element). More...

Const_iterator	cend () const
	Synonym of const_past_oldest(). More...

Const_iterator	const_past_oldest () const
	Returns one past last, a/k/a "oldest," element's iterator (to immutable element). More...

Reverse_iterator	rbegin () const
	Synonym of oldest(). More...

Reverse_iterator	oldest () const
	Returns first, a/k/a "oldest," element's reverse iterator (to immutable element, due to nature of this type). More...

Reverse_iterator	rend () const
	Synonym of past_newest(). More...

Reverse_iterator	past_newest () const
	Returns one past last, a/k/a "newest," element's reverse iterator (to immutable element, due to nature of this type). More...

Const_reverse_iterator	crbegin () const
	Synonym of const_oldest(). More...

Const_reverse_iterator	const_oldest () const
	Returns first, a/k/a "oldest," element's reverse iterator (to immutable element). More...

Const_reverse_iterator	crend () const
	Synonym of const_past_newest(). More...

Const_reverse_iterator	const_past_newest () const
	Returns one past last, a/k/a "newest," element's reverse iterator (to immutable element). More...

bool	empty () const
	Returns `true` if and only if container is empty. More...

size_type	size () const
	Returns number of elements stored. More...

size_type	max_size () const
	Returns max number of elements that can be stored. More...

Related Functions
(Note that these are not member functions.)
template<typename Key , typename Hash , typename Pred >
void	swap (Linked_hash_set< Key, Hash, Pred > &val1, Linked_hash_set< Key, Hash, Pred > &val2)
	Equivalent to `val1.swap(val2)`. More...

Detailed Description

template<typename Key, typename Hash, typename Pred>
class flow::util::Linked_hash_set< Key, Hash, Pred >

An object of this class is a set that combines the lookup speed of an unordered_set<> and ordering and iterator stability capabilities of an std::list<>.

This is just like Linked_hash_map, except it only stores keys – no mapped values. All comments, except for self-explanatory differences, from Linked_hash_map apply here. Thus I will only speak of differences below to avoid duplication of this header.

See also: class Linked_hash_map.

Template Parameters

Key	Key type. Same as for Linked_hash_map.
Hash	Hasher type. Same as for Linked_hash_map.
Pred	Equality functor type. Same as for Linked_hash_map.

Member Typedef Documentation

◆ Iterator

template<typename Key , typename Hash , typename Pred >

using flow::util::Linked_hash_set< Key, Hash, Pred >::Iterator = Const_iterator

Type for iterator pointing into a mutable structure of this type but actually that is not possible; so alias to Const_iterator.

Note these are standard semantics (see std::set, etc.).

◆ Reverse_iterator

template<typename Key , typename Hash , typename Pred >

using flow::util::Linked_hash_set< Key, Hash, Pred >::Reverse_iterator = Const_reverse_iterator

Type for reverse iterator pointing into a mutable structure of this type but actually that is not possible; so alias to Const_reverse_iterator.

Note these are standard semantics (see std::set, etc.).

Constructor & Destructor Documentation

◆ Linked_hash_set() [1/4]

template<typename Key , typename Hash , typename Pred >

flow::util::Linked_hash_set< Key, Hash, Pred >::Linked_hash_set	(	size_type	n_buckets = `size_type(-1)`,
		Hash const &	hasher_instance = `Hash()`,
		Pred const &	key_equal_instance = `Pred()`
	)

explicit

Constructs empty structure with some basic parameters.

Parameters

n_buckets	Number of buckets for the unordered (hash) table. Special value -1 (default) will cause us to use whatever `unordered_set<>` would use by default.
hasher_instance	Instance of the hash function type (`hasher_instance(Key k)` should be `size_type`d hash of key `k`).
key_equal_instance	Instance of the equality function type (`key_equal_instance(Key k1, Key k2)` should return `true` if and only if `k1` equals `k2`).

◆ Linked_hash_set() [2/4]

template<typename Key , typename Hash , typename Pred >

flow::util::Linked_hash_set< Key, Hash, Pred >::Linked_hash_set	(	std::initializer_list< Value >	values,
		size_type	n_buckets = `size_type(-1)`,
		Hash const &	hasher_instance = `Hash()`,
		Pred const &	key_equal_instance = `Pred()`
	)

explicit

Constructs structure with some basic parameters, and values initialized from initializer list.

The values are inserted as if insert(v) was called for each pair v in values in reverse order. Since the canonical ordering places the newest (last inserted/touch()ed) element at the front of the ordering, that means that forward iteration through the set (right after this constructor runs) will yield values in the same order as in initializer list values.

Parameters

values	Values with which to fill the structure after initializing it. Typically you'd provide a series of keys like this: `{ key1, key2, ... }`. They will appear in iterated sequence in the same order as they appear in this list.
n_buckets	See other constructor.
hasher_instance	See other constructor.
key_equal_instance	See other constructor.

◆ Linked_hash_set() [3/4]

template<typename Key , typename Hash , typename Pred >

flow::util::Linked_hash_set< Key, Hash, Pred >::Linked_hash_set ( Linked_hash_set< Key, Hash, Pred > const & src )

Constructs object that is a copy of the given source.

Equivalent to operator=(src).

Parameters

src	Source object.

◆ Linked_hash_set() [4/4]

template<typename Key , typename Hash , typename Pred >

flow::util::Linked_hash_set< Key, Hash, Pred >::Linked_hash_set ( Linked_hash_set< Key, Hash, Pred > && src )

Constructs object by making it equal to the given source, while the given source becomes as-if default-cted.

Parameters

src	Source object which is emptied.

Member Function Documentation

◆ begin()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Iterator flow::util::Linked_hash_set< Key, Hash, Pred >::begin

Synonym of newest().

Returns: See newest().

◆ cbegin()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Const_iterator flow::util::Linked_hash_set< Key, Hash, Pred >::cbegin

Synonym of const_newest().

Exists as standard container method (hence the odd formatting).

Returns: See const_newest().

◆ cend()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Const_iterator flow::util::Linked_hash_set< Key, Hash, Pred >::cend

Synonym of const_past_oldest().

Exists as standard container method (hence the odd formatting).

Returns: See const_past_oldest().

◆ const_back()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Value const & flow::util::Linked_hash_set< Key, Hash, Pred >::const_back

Returns reference to immutable back ("oldest") element in the structure; formally equivalent to *(--this->const_past_oldest()).

All other comments for const_front() apply analogously.

Returns: Reference to immutable Key (a/k/a Value) directly inside data structure; or to undefined location if currently empty().

◆ const_front()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Value const & flow::util::Linked_hash_set< Key, Hash, Pred >::const_front

Returns reference to immutable front ("newest") element in the structure; formally equivalent to *(this->const_newest()).

OK to call when empty(); but behavior undefined if you attempt to access the result in any way if either empty() when this was called; or if !empty() at that time, but the underlying element is erased at time of access. If not empty() when this was called, then resulting reference continues to be valid as long as the underlying element is not erased; however, in the future the reference (while referring to the same element) might not refer to front ("newest") element any longer. (Informally, most uses would only call const_front() when !empty(), and would access it immediately and but once. However, I'm listing the corner cases above.)

Returns: Reference to immutable Key (a/k/a Value) directly inside data structure; or to undefined location if currently empty().

◆ const_newest()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Const_iterator flow::util::Linked_hash_set< Key, Hash, Pred >::const_newest

Returns first, a/k/a "newest," element's iterator (to immutable element).

Returns: Ditto.

◆ const_oldest()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Const_reverse_iterator flow::util::Linked_hash_set< Key, Hash, Pred >::const_oldest

Returns first, a/k/a "oldest," element's reverse iterator (to immutable element).

Returns: Ditto.

◆ const_past_newest()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Const_reverse_iterator flow::util::Linked_hash_set< Key, Hash, Pred >::const_past_newest

Returns one past last, a/k/a "newest," element's reverse iterator (to immutable element).

Returns: Ditto.

◆ const_past_oldest()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Const_iterator flow::util::Linked_hash_set< Key, Hash, Pred >::const_past_oldest

Returns one past last, a/k/a "oldest," element's iterator (to immutable element).

Returns: Ditto.

◆ count()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::size_type flow::util::Linked_hash_set< Key, Hash, Pred >::count ( Key const & key ) const

Returns the number of times a key is equivalent to the given one is present in the hash: either 1 or 0.

Parameters

key	Key whose equal to find.

Returns: 0 or 1.

◆ crbegin()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Const_reverse_iterator flow::util::Linked_hash_set< Key, Hash, Pred >::crbegin

Synonym of const_oldest().

Returns: See const_oldest().

◆ crend()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Const_reverse_iterator flow::util::Linked_hash_set< Key, Hash, Pred >::crend

Synonym of const_past_newest().

Exists as standard container method.

Returns: See const_past_newest().

◆ empty()

template<typename Key , typename Hash , typename Pred >

bool flow::util::Linked_hash_set< Key, Hash, Pred >::empty

Returns true if and only if container is empty.

Same performance as of unordered_map<>.

Returns: Ditto.

◆ end()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Iterator flow::util::Linked_hash_set< Key, Hash, Pred >::end

Synonym of past_oldest().

Exists as standard container method.

Returns: See past_oldest().

◆ erase() [1/3]

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Iterator flow::util::Linked_hash_set< Key, Hash, Pred >::erase ( Const_iterator const & it )

Erases the element pointed to by the given valid iterator.

Behavior undefined if it is not valid. it becomes invalid.

Parameters

it	Iterator of element to erase.

Returns: Iterator one position past (i.e., "older") than it, before *it was removed.

◆ erase() [2/3]

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Iterator flow::util::Linked_hash_set< Key, Hash, Pred >::erase	(	Const_iterator const &	it_newest,
		Const_iterator const &	it_past_oldest
	)

Erases all elements in the range [it_newest, it_past_oldest).

Behavior undefined if given iterator is invalid. it_newest becomes invalid.

Parameters

it_newest	Iterator of first ("newest") element to erase.
it_past_oldest	Iterator of one past last ("oldest") element to erase.

Returns: it_past_oldest copy.

◆ erase() [3/3]

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::size_type flow::util::Linked_hash_set< Key, Hash, Pred >::erase ( Key const & key )

Erases the element with the given key, if it exists.

Return value indicates various info of interest about what occurred or did not occur.

Parameters

key	Key such that its equal's (if found) element will be erased.

Returns: Number of elements erased (0 or 1).

◆ find()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Const_iterator flow::util::Linked_hash_set< Key, Hash, Pred >::find ( Key const & key ) const

Attempts to find the given key in the set.

Key presence is determined according to the Pred template parameter which determines equality of 2 given keys; and via the Hash template parameter that enables efficient hash-based lookup. The returned iterator (if valid) cannot be used to mutate the elements stored in the map.

As long as the key is not removed from the map, the iterator will continue to be valid.

Note: Let r be the returned value. Since no key-associated value beyond key itself is stored in the structure, the fact that *r == key is not valuable: you already had key after all! It is only useful in pin-pointing the relative location in the chronological ordering; in being used as an argument to various erasing methods; and in checking for presence of the key in the set. For the latter, I recommend the following utility:

See also: util::key_exists(), which uses this method to more concisely check for the presence of a key.

Parameters

key	Key whose equal to find.

Returns: If found, iterator to the equivalent key; else this->const_past_oldest().

◆ insert()

template<typename Key , typename Hash , typename Pred >

std::pair< typename Linked_hash_set< Key, Hash, Pred >::Iterator, bool > flow::util::Linked_hash_set< Key, Hash, Pred >::insert ( Value const & key )

Attempts to insert the given key into the set.

If the key is already present in the set, does nothing. Return value indicates various info of interest about what occurred or did not occur. Key presence is determined according to the Pred template parameter which determines equality of 2 given keys; and via the Hash template parameter that enables efficient hash-based lookup. If inserted, the new element is considered "newest," as if by touch(). If not inserted, the existing element location is not affected.

Parameters

key	The key to attempt to insert. This value is copied, and the copy is inserted.

Returns: A pair whose second element is true if and only if the insertion occurred; and whose first element is an iterator pointing to either the newly inserted element or already present one equal to key.

◆ max_size()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::size_type flow::util::Linked_hash_set< Key, Hash, Pred >::max_size

Returns max number of elements that can be stored.

Same performance as of unordered_map<> + list<>.

Returns: Ditto.

◆ newest()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Iterator flow::util::Linked_hash_set< Key, Hash, Pred >::newest

Returns first, a/k/a "newest," element's iterator (to immutable element, due to nature of this type).

Returns: Ditto.

◆ oldest()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Reverse_iterator flow::util::Linked_hash_set< Key, Hash, Pred >::oldest

Returns first, a/k/a "oldest," element's reverse iterator (to immutable element, due to nature of this type).

Returns: Ditto.

◆ operator=() [1/2]

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred > & flow::util::Linked_hash_set< Key, Hash, Pred >::operator= ( Linked_hash_set< Key, Hash, Pred > && src )

Overwrites this object making it equal to the given source, while the given source becomes as-if default-cted.

Parameters

src	Source object which is emptied (unless it is `*this`; then no-op).

Returns: *this.

◆ operator=() [2/2]

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred > & flow::util::Linked_hash_set< Key, Hash, Pred >::operator= ( Linked_hash_set< Key, Hash, Pred > const & src )

Overwrites this object with a copy of the given source.

We become equal to src but independent of it to the max extent possible (if you've got pointers stored in there, for example, the pointers are copied, not the values at those pointers). In addition, the hasher instance and equality predicate are copied from src. Finally, a reasonable attempt is made to also make the internal structure of the hash set to be similar to that of src.

Parameters

src	Source object.

Returns: *this.

◆ past_newest()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Reverse_iterator flow::util::Linked_hash_set< Key, Hash, Pred >::past_newest

Returns one past last, a/k/a "newest," element's reverse iterator (to immutable element, due to nature of this type).

Returns: Ditto.

◆ past_oldest()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Iterator flow::util::Linked_hash_set< Key, Hash, Pred >::past_oldest

Returns one past last, a/k/a "oldest," element's iterator (to immutable element, due to nature of this type).

Returns: Ditto.

◆ rbegin()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Reverse_iterator flow::util::Linked_hash_set< Key, Hash, Pred >::rbegin

Synonym of oldest().

Returns: See oldest().

◆ rend()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::Reverse_iterator flow::util::Linked_hash_set< Key, Hash, Pred >::rend

Synonym of past_newest().

Exists as standard container method.

Returns: See past_newest().

◆ size()

template<typename Key , typename Hash , typename Pred >

Linked_hash_set< Key, Hash, Pred >::size_type flow::util::Linked_hash_set< Key, Hash, Pred >::size

Returns number of elements stored.

Same performance as of unordered_map<>.

Returns: Ditto.

◆ swap()

template<typename Key , typename Hash , typename Pred >

void flow::util::Linked_hash_set< Key, Hash, Pred >::swap ( Linked_hash_set< Key, Hash, Pred > & other )

Swaps the contents of this structure and other.

This is a constant-time operation.

Parameters

other The other structure.

◆ touch() [1/2]

template<typename Key , typename Hash , typename Pred >

void flow::util::Linked_hash_set< Key, Hash, Pred >::touch ( Const_iterator const & it )

Given a valid iterator into the structure, makes the pointed to element "newest" by moving it from wherever it is to be first in the iteration order.

Behavior undefined if iterator invalid.

The iterator continues to be valid.

Parameters

it	Iterator to an element of the structure.

◆ touch() [2/2]

template<typename Key , typename Hash , typename Pred >

bool flow::util::Linked_hash_set< Key, Hash, Pred >::touch ( Key const & key )

Given a key into the structure, makes the corresponding element "newest" by moving it from wherever it is to be first in the iteration order; or does nothing if no such key.

Return value indicates various info of interest about what occurred or did not occur.

Parameters

key	Key whose equal to find.

Returns: true if the key was found (even if it was already "newest"); false if not found.

Friends And Related Function Documentation

◆ swap()

template<typename Key , typename Hash , typename Pred >

void swap	(	Linked_hash_set< Key, Hash, Pred > &	val1,
		Linked_hash_set< Key, Hash, Pred > &	val2
	)

Parameters

val1	Object.
val2	Object.

The documentation for this class was generated from the following files:

util/linked_hash_set.hpp
util/util_fwd.hpp

Public Types

Public Member Functions

Related Functions

Detailed Description

Member Typedef Documentation

◆ Iterator

◆ Reverse_iterator

Constructor & Destructor Documentation

◆ Linked_hash_set() [1/4]

◆ Linked_hash_set() [2/4]

◆ Linked_hash_set() [3/4]

◆ Linked_hash_set() [4/4]

Member Function Documentation

◆ begin()

◆ cbegin()

◆ cend()

◆ const_back()

◆ const_front()

◆ const_newest()

◆ const_oldest()

◆ const_past_newest()

◆ const_past_oldest()

◆ count()

◆ crbegin()

◆ crend()

◆ empty()

◆ end()

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ find()

◆ insert()

◆ max_size()

◆ newest()

◆ oldest()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ past_newest()

◆ past_oldest()

◆ rbegin()

◆ rend()

◆ size()

◆ swap()

◆ touch() [1/2]

◆ touch() [2/2]

Friends And Related Function Documentation

◆ swap()