This class is a combined container which has the find complexity of a HashTable, deterministic iteration of a Vector (using begin(), end()). More...

#include <HashVector.h>

Public Types
enum	ClearPolicy { SHRINK_BUFFER =VectorType::SHRINK_BUFFER , SHRINK_BUFFER_AVERAGED =VectorType::SHRINK_BUFFER_AVERAGED , MAINTAIN_BUFFER =VectorType::MAINTAIN_BUFFER }

typedef VectorType::const_iterator	const_iterator

typedef HashVector< KeyT, DataT, HashT >	ContainerType

typedef HashTable< KeyT, size_t, HashT >	HashType

typedef VectorType::iterator	iterator

typedef DataT	value_type

typedef Vector< std::pair< KeyT, DataT > >	VectorType

Public Member Functions
	HashVector ()
	Constructor.

	HashVector (const ContainerType &other)
	Copy constructor.

	~HashVector ()
	Destructor.

DataT &	back ()

const DataT &	back () const

iterator	begin ()

const_iterator	begin () const

void	clear (ClearPolicy policy=SHRINK_BUFFER_AVERAGED)
	Remove all elements.

bool	contains (const KeyT &key) const
	Hash search for the key in the container.

bool	empty () const
	Return true if the container is empty.

iterator	end ()

const_iterator	end () const

iterator	erase (const iterator &it)
	Erase an element using an iterator.

bool	erase (const KeyT &key)
	Erase an element from the container.

iterator	find (const KeyT &key)
	Perform a hash search for a given key.

const_iterator	find (const KeyT &key) const
	Perform a hash search for a given key.

DataT &	front ()

const DataT &	front () const

DataT &	getOrCreate (const KeyT &key)
	Returns value given key.

template<typename T >
iterator	insert (const KeyT &key, T &&data)
	Insert a key,data pair in to the end of the container.

HashVector< KeyT, DataT, HashT > &	operator= (const ContainerType &other)
	Assignment operator.

DataT &	operator[] (size_t i)
	Access an element in the vector using an index.

const DataT &	operator[] (size_t i) const
	Access an element in the vector using an index.

template<typename T >
size_t	purge (T purger)
	Purge the hash set.

template<typename T >
iterator	push_back (const KeyT &key, T &&data)
	Insert a key,data pair in to the end of the container.

iterator	replace (const KeyT &oldKey, const KeyT &newKey, const DataT &data)
	Replace data in hash vector.

void	reserve (size_t size)
	Reserve capacity in the hash table.

size_t	size () const
	Return the number of inserted elements.

const HashType &	table () const

const VectorType &	vector () const

Detailed Description

template<typename KeyT, typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>
class agx::HashVector< KeyT, DataT, HashT >

This class is a combined container which has the find complexity of a HashTable, deterministic iteration of a Vector (using begin(), end()).

The cost is storage requirement. Data is stored in a vector<pair<KeyT, DataT> >, which contains the Hash key and the data. A hash table in parallel store the index to the vector and the corresponding key.

Beware of accessing the iterator of the vector, and change the Key value (pair.first). This will effectively invalidate the data structure. Unfortunately, there is no easy way protecting this unless only a const_iterator is used for accessing the vector, which would reduce the practical functionality of the container.

The vector contains a std::pair<KeyT, DataT>, so the iterator is a pointer to such an object.

Definition at line 40 of file HashVector.h.

Member Typedef Documentation

◆ const_iterator

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

typedef VectorType::const_iterator agx::HashVector< KeyT, DataT, HashT >::const_iterator

Definition at line 65 of file HashVector.h.

◆ ContainerType

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

typedef HashVector<KeyT, DataT, HashT> agx::HashVector< KeyT, DataT, HashT >::ContainerType

Definition at line 45 of file HashVector.h.

◆ HashType

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

typedef HashTable<KeyT, size_t, HashT> agx::HashVector< KeyT, DataT, HashT >::HashType

Definition at line 48 of file HashVector.h.

◆ iterator

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

typedef VectorType::iterator agx::HashVector< KeyT, DataT, HashT >::iterator

Definition at line 64 of file HashVector.h.

◆ value_type

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

typedef DataT agx::HashVector< KeyT, DataT, HashT >::value_type

Definition at line 44 of file HashVector.h.

◆ VectorType

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

typedef Vector<std::pair<KeyT, DataT> > agx::HashVector< KeyT, DataT, HashT >::VectorType

Definition at line 47 of file HashVector.h.

Member Enumeration Documentation

◆ ClearPolicy

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

enum agx::HashVector::ClearPolicy

Enumerator
SHRINK_BUFFER
SHRINK_BUFFER_AVERAGED
MAINTAIN_BUFFER

Definition at line 57 of file HashVector.h.

Constructor & Destructor Documentation

◆ HashVector() [1/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

agx::HashVector< KeyT, DataT, HashT >::HashVector ( )

inline

Constructor.

Definition at line 69 of file HashVector.h.

◆ HashVector() [2/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

agx::HashVector< KeyT, DataT, HashT >::HashVector ( const ContainerType & other )

inline

Copy constructor.

Definition at line 73 of file HashVector.h.

References agx::HashVector< KeyT, DataT, HashT >::clear(), and agx::HashVector< KeyT, DataT, HashT >::SHRINK_BUFFER.

◆ ~HashVector()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

agx::HashVector< KeyT, DataT, HashT >::~HashVector ( )

inline

Destructor.

Definition at line 93 of file HashVector.h.

References agx::HashVector< KeyT, DataT, HashT >::clear(), and agx::HashVector< KeyT, DataT, HashT >::MAINTAIN_BUFFER.

Member Function Documentation

◆ back() [1/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

DataT & agx::HashVector< KeyT, DataT, HashT >::back ( )

inline

Returns: a reference to the last element in the vector container

Definition at line 321 of file HashVector.h.

References agxAssert, and agx::Container::size().

◆ back() [2/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

const DataT & agx::HashVector< KeyT, DataT, HashT >::back ( ) const

inline

Returns: a const reference to the last element in the vector container

Definition at line 330 of file HashVector.h.

References agxAssert, and agx::Container::size().

◆ begin() [1/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

iterator agx::HashVector< KeyT, DataT, HashT >::begin ( )

inline

Returns: iterator to first element in the vector container

Definition at line 265 of file HashVector.h.

References agxAssert, and agx::Vector< T, Allocator >::begin().

Referenced by agx::HashVector< KeyT, DataT, HashT >::replace().

◆ begin() [2/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

const_iterator agx::HashVector< KeyT, DataT, HashT >::begin ( ) const

inline

Returns: const_iterator to first element in the vector container

Definition at line 275 of file HashVector.h.

References agxAssert, and agx::Vector< T, Allocator >::begin().

◆ clear()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

void agx::HashVector< KeyT, DataT, HashT >::clear ( ClearPolicy policy = SHRINK_BUFFER_AVERAGED )

inline

Remove all elements.

Parameters

policy - specifies the erase policy.

Definition at line 399 of file HashVector.h.

References agxAssert, agx::Vector< T, Allocator >::clear(), and agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::clear().

Referenced by agx::HashVector< KeyT, DataT, HashT >::HashVector(), and agx::HashVector< KeyT, DataT, HashT >::~HashVector().

◆ contains()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

bool agx::HashVector< KeyT, DataT, HashT >::contains ( const KeyT & key ) const

inline

Hash search for the key in the container.

Complexity: O(HashTable::contains())

Returns: true if key exists in the container.

Definition at line 215 of file HashVector.h.

References agxAssert, and agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::contains().

◆ empty()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

bool agx::HashVector< KeyT, DataT, HashT >::empty ( ) const

inline

Return true if the container is empty.

Definition at line 122 of file HashVector.h.

References agx::Container::empty().

Referenced by agx::HashVector< KeyT, DataT, HashT >::purge().

◆ end() [1/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

iterator agx::HashVector< KeyT, DataT, HashT >::end ( )

inline

Returns: iterator marking end of the vector container

Definition at line 285 of file HashVector.h.

References agxAssert, and agx::Vector< T, Allocator >::end().

Referenced by agx::HashVector< KeyT, DataT, HashT >::erase(), agx::HashVector< KeyT, DataT, HashT >::find(), agx::HashVector< KeyT, DataT, HashT >::getOrCreate(), agx::HashVector< KeyT, DataT, HashT >::push_back(), agx::HashVector< KeyT, DataT, HashT >::replace(), and agxSensor::RtRegistry::storage().

◆ end() [2/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

const_iterator agx::HashVector< KeyT, DataT, HashT >::end ( ) const

inline

Returns: const_iterator marking end of the vector container

Definition at line 294 of file HashVector.h.

References agxAssert, and agx::Vector< T, Allocator >::end().

◆ erase() [1/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

iterator agx::HashVector< KeyT, DataT, HashT >::erase ( const iterator & it )

inline

Erase an element using an iterator.

This is a fastErase method where the erased element is replaced by the last elment.

This method assumes that it is a valid/existing iterator in the container. If it is not, there is a chance that the iterator is point at something we do not want to touch, hence could cause crash. it is checked to see if it is == end(), then the method will return false. For other invalid iterators, behavior is undefined.

Complexity: O(HashTable::find() + HashTable::erase() + Vector::fastErase() )

Parameters

it	- Iterator to the element to be removed.

Returns: the iterator to the position of the erased element where the last element is put if successful, otherwise end().

Definition at line 375 of file HashVector.h.

References agxAssert, agx::HashVector< KeyT, DataT, HashT >::end(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::end(), agx::HashVector< KeyT, DataT, HashT >::erase(), and agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::find().

◆ erase() [2/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

bool agx::HashVector< KeyT, DataT, HashT >::erase ( const KeyT & key )

inline

Erase an element from the container.

The elements in the vector CAN change order due to the use of Vector::fastErase, where the erased and the last element swap places.

Complexity: O(HashTable::find() + HashTable::erase() + Vector::fastErase() )

Returns: false if element was not found

Definition at line 347 of file HashVector.h.

References agxAssert, agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::end(), agx::HashVector< KeyT, DataT, HashT >::erase(), and agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::find().

Referenced by agx::HashVector< KeyT, DataT, HashT >::erase(), and agx::HashVector< KeyT, DataT, HashT >::purge().

◆ find() [1/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

iterator agx::HashVector< KeyT, DataT, HashT >::find ( const KeyT & key )

inline

Perform a hash search for a given key.

Complexity: O(HashTable::find())

Returns: iterator to the found element, end() if none is found.

Definition at line 230 of file HashVector.h.

References agxAssert, agx::HashVector< KeyT, DataT, HashT >::end(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::end(), and agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::find().

Referenced by agx::HashVector< KeyT, DataT, HashT >::getOrCreate().

◆ find() [2/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

const_iterator agx::HashVector< KeyT, DataT, HashT >::find ( const KeyT & key ) const

inline

Perform a hash search for a given key.

Complexity: O(HashTable::find())

Returns: const_iterator to the found element, end() if none is found.

Definition at line 248 of file HashVector.h.

References agxAssert, agx::HashVector< KeyT, DataT, HashT >::end(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::end(), and agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::find().

◆ front() [1/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

DataT & agx::HashVector< KeyT, DataT, HashT >::front ( )

inline

Returns: a reference to the first element in the vector container

Definition at line 303 of file HashVector.h.

References agxAssert.

◆ front() [2/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

const DataT & agx::HashVector< KeyT, DataT, HashT >::front ( ) const

inline

Returns: a const reference to the first element in the vector container

Definition at line 312 of file HashVector.h.

References agxAssert.

◆ getOrCreate()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

DataT & agx::HashVector< KeyT, DataT, HashT >::getOrCreate ( const KeyT & key )

inline

Returns value given key.

If the key doesn't exist, the key is inserted and the default value is returned.

Parameters

key - key

Returns: data for key

Definition at line 449 of file HashVector.h.

References agx::HashVector< KeyT, DataT, HashT >::end(), agx::HashVector< KeyT, DataT, HashT >::find(), and agx::HashVector< KeyT, DataT, HashT >::insert().

◆ insert()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

template<typename T >

iterator agx::HashVector< KeyT, DataT, HashT >::insert	(	const KeyT &	key,
		T &&	data
	)

inline

Insert a key,data pair in to the end of the container.

The element will end up at the end of the vector (analogue to a vector push_back!). What also happens is an insert into the hash table.

Identical to the push_back() method

Complexity: O(HashTable::find()+HashTable::insert()+Vector::push_back())

Returns: iterator to the inserted pair (at the end of the vector)

Definition at line 175 of file HashVector.h.

References agxAssert, and agx::HashVector< KeyT, DataT, HashT >::push_back().

Referenced by agx::HashVector< KeyT, DataT, HashT >::getOrCreate().

◆ operator=()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

HashVector< KeyT, DataT, HashT > & agx::HashVector< KeyT, DataT, HashT >::operator= ( const ContainerType & other )

inline

Assignment operator.

Definition at line 80 of file HashVector.h.

◆ operator[]() [1/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

DataT & agx::HashVector< KeyT, DataT, HashT >::operator[] ( size_t i )

inline

Access an element in the vector using an index.

Returns: reference to the Data in the i:th element in the vector

Definition at line 411 of file HashVector.h.

References agxAssert, and agx::Container::size().

◆ operator[]() [2/2]

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

const DataT & agx::HashVector< KeyT, DataT, HashT >::operator[] ( size_t i ) const

inline

Access an element in the vector using an index.

Returns: const reference to the Data in the i:th element in the vector

Definition at line 423 of file HashVector.h.

References agxAssert, and agx::Container::size().

◆ purge()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

template<typename T >

size_t agx::HashVector< KeyT, DataT, HashT >::purge ( T purger )

inline

Purge the hash set.

Good to use when removing multiple items, since iterators are invalidated after any modification. The purger should be a functor class which takes the key as parameter and return true if the entry should be removed from the hash set.

Complexity: n - number of purged elements O(n*HashTable::erase())

Example of a purger implementation:

template < typename T1, typename T2 > class MyPurger { public: MyPurger() {} inline bool operator()(const T& a) { return a==2; } };

Parameters

purger - An instance of a class with an bool () operator which when it returns true, the element will be removed from the container

Returns: number of purged elements

Definition at line 483 of file HashVector.h.

References agx::Vector< T, Allocator >::begin(), agx::Vector< T, Allocator >::clear(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::clear(), agx::HashVector< KeyT, DataT, HashT >::empty(), agx::Vector< T, Allocator >::end(), agx::HashVector< KeyT, DataT, HashT >::erase(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::insert(), agx::Vector< T, Allocator >::push_back(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::reserve(), agx::Vector< T, Allocator >::reserve(), agx::Container::SHRINK_BUFFER_AVERAGED, and agx::Container::size().

◆ push_back()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

template<typename T >

iterator agx::HashVector< KeyT, DataT, HashT >::push_back	(	const KeyT &	key,
		T &&	data
	)

inline

Insert a key,data pair in to the end of the container.

The element will end up at the end of the vector (analogue to a vector push_back!). What also happens is an insert into the hash table.

If the key already exists in the Container, it will analogue to the HashTable replace the already existing data element in the vector.

Identical to the insert() method

Complexity: O(HashTable::find()+HashTable::insert()+Vector::push_back())

Returns: iterator to the inserted pair (the last element if key did not exist before).

Definition at line 142 of file HashVector.h.

References agxAssert, agx::HashVector< KeyT, DataT, HashT >::end(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::end(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::find(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::insert(), agx::Vector< T, Allocator >::push_back(), and agx::Container::size().

Referenced by agx::HashVector< KeyT, DataT, HashT >::insert().

◆ replace()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

iterator agx::HashVector< KeyT, DataT, HashT >::replace	(	const KeyT &	oldKey,
		const KeyT &	newKey,
		const DataT &	data
	)

inline

Replace data in hash vector.

Similar to erase + insert but preserve iteration order.

Note: If oldKey doesn't exist, the operation is aborted and end() is returned.

Parameters

oldKey	- old key (fails if not present in this hash vector)
newKey	- new key for data
data	- data for `newKey`

Definition at line 192 of file HashVector.h.

References agxAssert, agx::HashVector< KeyT, DataT, HashT >::begin(), agx::HashVector< KeyT, DataT, HashT >::end(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::end(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::erase(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::find(), and agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::insert().

◆ reserve()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

void agx::HashVector< KeyT, DataT, HashT >::reserve ( size_t size )

inline

Reserve capacity in the hash table.

Parameters

size	- reserve size elements

Definition at line 435 of file HashVector.h.

References agxAssert, agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::reserve(), agx::Vector< T, Allocator >::reserve(), and agx::HashVector< KeyT, DataT, HashT >::size().

◆ size()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

size_t agx::HashVector< KeyT, DataT, HashT >::size ( ) const

inline

Return the number of inserted elements.

Definition at line 112 of file HashVector.h.

References agxAssert, and agx::Container::size().

Referenced by agx::HashVector< KeyT, DataT, HashT >::reserve().

◆ table()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

const HashType & agx::HashVector< KeyT, DataT, HashT >::table ( ) const

inline

Definition at line 104 of file HashVector.h.

◆ vector()

template<typename KeyT , typename DataT = KeyT, typename HashT = agx::HashFn<KeyT>>

const VectorType & agx::HashVector< KeyT, DataT, HashT >::vector ( ) const

inline

Definition at line 99 of file HashVector.h.

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

HashVector.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ ContainerType

◆ HashType

◆ iterator

◆ value_type

◆ VectorType

Member Enumeration Documentation

◆ ClearPolicy

Constructor & Destructor Documentation

◆ HashVector() [1/2]

◆ HashVector() [2/2]

◆ ~HashVector()

Member Function Documentation

◆ back() [1/2]

◆ back() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ clear()

◆ contains()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ find() [1/2]

◆ find() [2/2]

◆ front() [1/2]

◆ front() [2/2]

◆ getOrCreate()

◆ insert()

◆ operator=()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ purge()

◆ push_back()

◆ replace()

◆ reserve()

◆ size()

◆ table()

◆ vector()