Deque with Direct Access. More...

#include <hashtable_deque.hpp>

Classes
class	KeyPair
	A pair of keys for the implementation of a deque as a doubly-linked list. More...

Public Member Functions
	HashtableDeque (key_type initialSize=0)
	Constructor of a Deque with Direct Access. More...

	~HashtableDeque ()
	Destructor of a Deque with Direct Access. More...

bool	contains (const key_type &k) const noexcept
	Entry with given key contained. More...

void	pushToBack (const key_type &k)
	Add the key to the back of this deque. More...

void	pushToBack (key_type &&k)
	Add the key to the back of this deque (with move semantics) More...

void	popFromFront ()
	Removes the next key from this deque. More...

void	popFromFront (key_type &k)
	Removes the next key from this deque. More...

void	pushToFront (const key_type &k)
	Add the key to the front of this deque. More...

void	pushToFront (key_type &&k)
	Add the key to the front of this deque (with move semantics) More...

void	popFromBack ()
	Removes the next key from this deque. More...

void	popFromBack (key_type &k)
	Removes the next key from this deque. More...

void	remove (const key_type &k)
	Removes a specific key from this deque. More...

void	remove (key_type &&k)
	Removes a specific key from this deque (with move semantic) More...

void	insertBefore (const key_type &k, const key_type &ref)
	Add the key to before a reference key. More...

void	insertBefore (key_type &&k, key_type &&ref)
	Add the key to before a reference key. More...

void	insertAfter (const key_type &k, const key_type &ref)
	Add the key to after a reference key. More...

void	insertAfter (key_type &&k, key_type &&ref)
	Add the key to after a reference key. More...

void	getFront (key_type &k)
	Get the key at the front. More...

key_type	getFront ()
	Get the key at the front. More...

void	getBack (key_type &k)
	Get the key at the back. More...

key_type	getBack ()
	Get the key at the back. More...

void	getBefore (key_type &k, const key_type &ref)
	Get the key to before a reference key. More...

void	getBefore (key_type &k, key_type &&ref)
	Get the key to before a reference key. More...

key_type	getBefore (const key_type &ref)
	Get the key to before a reference key. More...

key_type	getBefore (key_type &&ref)
	Get the key to before a reference key. More...

void	getAfter (key_type &k, const key_type &ref)
	Get the key to after a reference key. More...

void	getAfter (key_type &k, key_type &&ref)
	Get the key to after a reference key. More...

key_type	getAfter (const key_type &ref)

key_type	getAfter (key_type &&ref)

uint64_t	length () const noexcept
	Number of entries in this deque. More...

Private Attributes
std::unique_ptr< std::unordered_map< key_type, KeyPair > >	_directAccessDeque
	Maps from keys to their deque entry. More...

key_type	_back
	Element at the back. More...

key_type	_front
	Element at the front. More...

Detailed Description

template<class key_type, key_type invalid_key>
class zero::hashtable_deque::HashtableDeque< key_type, invalid_key >

Deque with Direct Access.

Represents a deque of keys with direct access using the keys. It offers the usual deque semantics where entries are inserted either at the back or the front of the deque and where entries are removed either from the front or from the back of it. But it also offers the possibility to remove a specified element from somewhere within the deque. The data type of the entries is specified using a template parameter. Each value contained in the deque needs to be unique and inserts of duplicate keys are prevented. The computational complexity of the direct access as well as removal and insertion with deque semantics depends on the implementation of std::unordered_map, as this class is used for that. The space complexity also depends on the implementation of std::unordered_map where key has a size of the key template parameter and where T has double the size of the key template parameter.

Note: Could also be implemented using Boost.MultiIndex .

Template Parameters

key_type	The data type of the entries stored in this data structure.
invalid_key	This specifies an invalid `key` which can be used to mark that an element in the deque does not have a previous or next element. It can also be used to mark that there is no back or front of the deque when there is no deque. This should have the semantics of `null` for the specified `key` template parameter therefore a natural choice for the case that `key` is a pointer would be `nullptr` .

Author: Max Gilbert

Constructor & Destructor Documentation

§ HashtableDeque()

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::HashtableDeque ( key_type initialSize = 0 )

inline

Constructor of a Deque with Direct Access.

Creates a new Deque with Direct Access with an optional maximum size. If the initialSize is greater 0, the memory required for the specified number of keys is allocated during the creation to reduce the overhead due to allocation of memory.

Parameters

initialSize The maximum number of keys that can be managed by this Deque with Direct Access, or 0 (default) for a Deque with Direct Access with an unlimited capacity (depends on the number of unique key values).

§ ~HashtableDeque()

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::~HashtableDeque ( )

inline

Destructor of a Deque with Direct Access.

Destructs this Deque with Direct Access including the dynamically allocated memory used for the data.

Member Function Documentation

§ contains()

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::contains ( const key_type & k ) const

inlinenoexcept

Entry with given key contained.

Searches this deque for the given key and the return value gives information about if the key could be found.

Parameters

k	The key that should be searched for in this deque.

Returns: true if this deque contains an entry with k as key, false else.

§ getAfter() [1/4]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::getAfter	(	key_type &	k,
		const key_type &	ref
	)

inline

Get the key to after a reference key.

Returns an entry right after (closer to the back of the deque) a given reference key already contained in this deque.

Parameters

[out]	k	The key after the reference key.
	ref	The already contained key given as position.

Exceptions

HashtableDequeNotContainedException	Thrown if the reference key was not already contained in this deque.
HashtableDequeAlreadyAtTheBackException	Thrown if the reference key was already at the back of this deque.

Returns an entry right after (closer to the back of the deque) a given reference key already contained in this deque.

Returns: The key after the reference key.

Parameters

ref	The already contained key given as position.

Exceptions

HashtableDequeNotContainedException	Thrown if the reference key was not already contained in this deque.
HashtableDequeAlreadyAtTheBackException	Thrown if the reference key was already at the back of this deque.

§ getAfter() [2/4]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::getAfter	(	key_type &	k,
		key_type &&	ref
	)

inline

Get the key to after a reference key.

Returns an entry right after (closer to the back of the deque) a given reference key already contained in this deque.

Parameters

[out]	k	The key after the reference key.
	ref	The already contained key given as position.

Exceptions

HashtableDequeNotContainedException	Thrown if the reference key was not already contained in this deque.
HashtableDequeAlreadyAtTheBackException	Thrown if the reference key was already at the back of this deque.

Returns an entry right after (closer to the back of the deque) a given reference key already contained in this deque.

Returns: The key after the reference key.

Parameters

ref	The already contained key given as position.

Exceptions

HashtableDequeNotContainedException	Thrown if the reference key was not already contained in this deque.
HashtableDequeAlreadyAtTheBackException	Thrown if the reference key was already at the back of this deque.

§ getAfter() [3/4]

template<class key_type, key_type invalid_key>

key_type zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::getAfter ( const key_type & ref )

inline

§ getAfter() [4/4]

template<class key_type, key_type invalid_key>

key_type zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::getAfter ( key_type && ref )

inline

§ getBack() [1/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::getBack ( key_type & k )

inline

Get the key at the back.

Returns the entry at the back of this deque.

Parameters

[out] k The key at the back.

Exceptions

HashtableDequeEmptyException Thrown if this deque is empty.

§ getBack() [2/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::getBack ( )

inline

Get the key at the back.

Returns the entry at the back of this deque.

Returns: The key at the back.

Exceptions

HashtableDequeEmptyException Thrown if this deque is empty.

§ getBefore() [1/4]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::getBefore	(	key_type &	k,
		const key_type &	ref
	)

inline

Get the key to before a reference key.

Returns an entry right before (closer to the front of the deque) a given reference key already contained in this deque.

Parameters

[out]	k	The key before the reference key.
	ref	The already contained key given as position.

Exceptions

HashtableDequeNotContainedException	Thrown if the reference key was not already contained in this deque.
HashtableDequeAlreadyAtTheFrontException	Thrown if the reference key was already at the front of this deque.

§ getBefore() [2/4]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::getBefore	(	key_type &	k,
		key_type &&	ref
	)

inline

Get the key to before a reference key.

Returns an entry right before (closer to the front of the deque) a given reference key already contained in this deque.

Parameters

[out]	k	The key before the reference key.
	ref	The already contained key given as position.

Exceptions

HashtableDequeNotContainedException	Thrown if the reference key was not already contained in this deque.
HashtableDequeAlreadyAtTheFrontException	Thrown if the reference key was already at the front of this deque.

§ getBefore() [3/4]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::getBefore ( const key_type & ref )

inline

Get the key to before a reference key.

Returns an entry right before (closer to the front of the deque) a given reference key already contained in this deque.

Returns: The key before the reference key.

Parameters

ref	The already contained key given as position.

Exceptions

HashtableDequeNotContainedException	Thrown if the reference key was not already contained in this deque.
HashtableDequeAlreadyAtTheFrontException	Thrown if the reference key was already at the front of this deque.

§ getBefore() [4/4]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::getBefore ( key_type && ref )

inline

Get the key to before a reference key.

Returns an entry right before (closer to the front of the deque) a given reference key already contained in this deque.

Returns: The key before the reference key.

Parameters

ref	The already contained key given as position.

Exceptions

HashtableDequeNotContainedException	Thrown if the reference key was not already contained in this deque.
HashtableDequeAlreadyAtTheFrontException	Thrown if the reference key was already at the front of this deque.

§ getFront() [1/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::getFront ( key_type & k )

inline

Get the key at the front.

Returns the entry at the front of this deque.

Parameters

[out] k The key at the front.

Exceptions

HashtableDequeEmptyException Thrown if this deque is empty.

§ getFront() [2/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::getFront ( )

inline

Get the key at the front.

Returns the entry at the front of this deque.

Returns: The key at the front.

Exceptions

HashtableDequeEmptyException Thrown if this deque is empty.

§ insertAfter() [1/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::insertAfter	(	const key_type &	k,
		const key_type &	ref
	)

inline

Add the key to after a reference key.

Adds an entry right after (closer to the back of the deque) a given reference key already contained in this deque.

Parameters

k	The key that is added to this deque.
ref	The already contained key given as position for the insert.

Exceptions

HashtableDequeNotContainedException	Thrown if the reference key was not already contained in this deque.
HashtableDequeAlreadyContainsException	Thrown if the key was already contained in this deque.

§ insertAfter() [2/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::insertAfter	(	key_type &&	k,
		key_type &&	ref
	)

inline

Add the key to after a reference key.

Adds an entry right after (closer to the back of the deque) a given reference key already contained in this deque.

Parameters

k	The key that is added to this deque.
ref	The already contained key given as position for the insert.

Exceptions

HashtableDequeNotContainedException	Thrown if the reference key was not already contained in this deque.
HashtableDequeAlreadyContainsException	Thrown if the key was already contained in this deque.

§ insertBefore() [1/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::insertBefore	(	const key_type &	k,
		const key_type &	ref
	)

inline

Add the key to before a reference key.

Adds an entry right before (closer to the front of the deque) a given reference key already contained in this deque.

Parameters

k	The key that is added to this deque.
ref	The already contained key given as position for the insert.

Exceptions

HashtableDequeNotContainedException	Thrown if the reference key was not already contained in this deque.
HashtableDequeAlreadyContainsException	Thrown if the key was already contained in this deque.

§ insertBefore() [2/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::insertBefore	(	key_type &&	k,
		key_type &&	ref
	)

inline

Add the key to before a reference key.

Adds an entry right before (closer to the front of the deque) a given reference key already contained in this deque.

Parameters

k	The key that is added to this deque.
ref	The already contained key given as position for the insert.

Exceptions

HashtableDequeNotContainedException	Thrown if the reference key was not already contained in this deque.
HashtableDequeAlreadyContainsException	Thrown if the key was already contained in this deque.

§ length()

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::length ( ) const

inlinenoexcept

Number of entries in this deque.

Returns the number of entries (keys) that are contained in this deque.

Returns: The number of entries contained in this deque.

§ popFromBack() [1/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::popFromBack ( )

inline

Removes the next key from this deque.

Removes an entry from the back of this deque.

Exceptions

HashtableDequeEmptyException Thrown if this deque was already empty.

§ popFromBack() [2/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::popFromBack ( key_type & k )

inline

Removes the next key from this deque.

Removes an entry from the back of this deque.

Parameters

[out] k The key that was removed from the front of this queue.

Exceptions

HashtableDequeEmptyException Thrown if this deque was already empty.

§ popFromFront() [1/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::popFromFront ( )

inline

Removes the next key from this deque.

Removes an entry from the front of this deque.

Exceptions

HashtableDequeEmptyException Thrown if this deque was already empty.

§ popFromFront() [2/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::popFromFront ( key_type & k )

inline

Removes the next key from this deque.

Removes an entry from the front of this deque.

Parameters

[out] k The key that was removed from the front of this queue.

Exceptions

HashtableDequeEmptyException Thrown if this deque was already empty.

§ pushToBack() [1/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::pushToBack ( const key_type & k )

inline

Add the key to the back of this deque.

Adds an entry to the back of this deque.

Parameters

k	The key that is added to this deque.

Exceptions

HashtableDequeAlreadyContainsException Thrown if the key was already contained in this deque.

§ pushToBack() [2/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::pushToBack ( key_type && k )

inline

Add the key to the back of this deque (with move semantics)

Adds an entry to the back of this deque using move semantics.

Parameters

k	The key that is added to this deque.

Exceptions

HashtableDequeAlreadyContainsException Thrown if the key was already contained in this deque.

§ pushToFront() [1/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::pushToFront ( const key_type & k )

inline

Add the key to the front of this deque.

Adds an entry to the front of this deque.

Parameters

k	The key that is added to this deque.

Exceptions

HashtableDequeAlreadyContainsException Thrown if the key was already contained in this deque.

§ pushToFront() [2/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::pushToFront ( key_type && k )

inline

Add the key to the front of this deque (with move semantics)

Adds an entry to the front of this deque using move semantics.

Parameters

k	The key that is added to this deque.

Exceptions

HashtableDequeAlreadyContainsException Thrown if the key was already contained in this deque.

§ remove() [1/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::remove ( const key_type & k )

inline

Removes a specific key from this deque.

Removes the specified key k from this deque using the hash table over the deque entries, if the key k was contained in this deque.

Parameters

k	The key to remove from this deque.

Exceptions

HashtableDequeNotContainedException Thrown if the key was not contained in this deque.

§ remove() [2/2]

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::remove ( key_type && k )

inline

Removes a specific key from this deque (with move semantic)

Removes the specified key k from this deque using the hash table over the deque entries and move semantics, if the key k was contained in this deque.

Parameters

k	The key to remove from this deque.

Exceptions

HashtableDequeNotContainedException Thrown if the key was not contained in this deque.

Member Data Documentation

§ _back

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::_back

private

Element at the back.

Stores the key of the element at the back of the deque. This element does not have a next element but the previous element can be accesses using _directAccessDeque .

§ _directAccessDeque

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::_directAccessDeque

private

Maps from keys to their deque entry.

Allows direct access to specific elements of the deque and stores the inner deque elements. Every access on deque elements happens through the interface of this data structure but this does not directly support the access with deque semantics. The key represents an deque entry and the keyPair which is mapped to that key stores the information about previous and next key in the deque.

See also: keyPair

§ _front

template<class key_type, key_type invalid_key>

zero::hashtable_deque::HashtableDeque< key_type, invalid_key >::_front

private

Element at the front.

Stores the key of the element at the front of the deque. This element does not have a previous element but the next element can be accesses using _directAccessDeque .

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

src/common/hashtable_deque.hpp

Classes

Public Member Functions

Private Attributes

Detailed Description

template<class key_type, key_type invalid_key> class zero::hashtable_deque::HashtableDeque< key_type, invalid_key >

Constructor & Destructor Documentation

§ HashtableDeque()

§ ~HashtableDeque()

Member Function Documentation

§ contains()

§ getAfter() [1/4]

§ getAfter() [2/4]

§ getAfter() [3/4]

§ getAfter() [4/4]

§ getBack() [1/2]

§ getBack() [2/2]

§ getBefore() [1/4]

§ getBefore() [2/4]

§ getBefore() [3/4]

§ getBefore() [4/4]

§ getFront() [1/2]

§ getFront() [2/2]

§ insertAfter() [1/2]

§ insertAfter() [2/2]

§ insertBefore() [1/2]

§ insertBefore() [2/2]

§ length()

§ popFromBack() [1/2]

§ popFromBack() [2/2]

§ popFromFront() [1/2]

§ popFromFront() [2/2]

§ pushToBack() [1/2]

§ pushToBack() [2/2]

§ pushToFront() [1/2]

§ pushToFront() [2/2]

§ remove() [1/2]

§ remove() [2/2]

Member Data Documentation

§ _back

§ _directAccessDeque

§ _front

template<class key_type, key_type invalid_key>
class zero::hashtable_deque::HashtableDeque< key_type, invalid_key >