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

#include <SetVector.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 const DataT &	const_reference

typedef VectorType::const_reverse_iterator	const_reverse_iterator

typedef SetVector< DataT, HashT >	ContainerType

typedef HashTable< DataT, size_t, HashT >	HashType

typedef VectorType::iterator	iterator

typedef VectorType::reverse_iterator	reverse_iterator

typedef size_t	size_type

typedef DataT	value_type

typedef Vector< DataT >	VectorType

Public Member Functions
	SetVector ()
	Constructor.

	SetVector (const ContainerType &other)
	Copy constructor.

	~SetVector ()
	Destructor.

DataT &	at (size_t index)
	Access an element in the vector using an index.

const DataT &	at (size_t index) const
	Access an element in the vector using an index.

DataT &	back ()

const DataT &	back () const

iterator	begin ()

const_iterator	begin () const

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

template<typename T2 >
bool	contains (const T2 &key) const
	Hash search for the data in the container.

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

iterator	end ()

const_iterator	end () const

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

template<typename T2 >
bool	erase (const T2 &key)
	Erase an element from the container.

template<typename T2 >
iterator	find (const T2 &key)
	Perform a hash search for a given key.

template<typename T2 >
const_iterator	find (const T2 &key) const
	Perform a hash search for a given key.

DataT &	front ()

const DataT &	front () const

template<typename T2 >
iterator	insert (const T2 &data)
	Insert a data element in to the end of the container.

ContainerType &	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 T2 >
iterator	push_back (const T2 &data)
	Insert a data element in to the end of the container.

reverse_iterator	rbegin ()

const_reverse_iterator	rbegin () const

reverse_iterator	rend ()

const_reverse_iterator	rend () const

template<typename OldDataT , typename NewDataT >
iterator	replace (const OldDataT &oldData, const NewDataT &newData)
	Replace data in set 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 DataT, typename HashT = HashFn<DataT>>
class agx::SetVector< 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.

Definition at line 37 of file SetVector.h.

Member Typedef Documentation

◆ const_iterator

template<typename DataT , typename HashT = HashFn<DataT>>

typedef VectorType::const_iterator agx::SetVector< DataT, HashT >::const_iterator

Definition at line 63 of file SetVector.h.

◆ const_reference

template<typename DataT , typename HashT = HashFn<DataT>>

typedef const DataT& agx::SetVector< DataT, HashT >::const_reference

Definition at line 42 of file SetVector.h.

◆ const_reverse_iterator

template<typename DataT , typename HashT = HashFn<DataT>>

typedef VectorType::const_reverse_iterator agx::SetVector< DataT, HashT >::const_reverse_iterator

Definition at line 65 of file SetVector.h.

◆ ContainerType

template<typename DataT , typename HashT = HashFn<DataT>>

typedef SetVector<DataT, HashT> agx::SetVector< DataT, HashT >::ContainerType

Definition at line 44 of file SetVector.h.

◆ HashType

template<typename DataT , typename HashT = HashFn<DataT>>

typedef HashTable<DataT, size_t, HashT> agx::SetVector< DataT, HashT >::HashType

Definition at line 46 of file SetVector.h.

◆ iterator

template<typename DataT , typename HashT = HashFn<DataT>>

typedef VectorType::iterator agx::SetVector< DataT, HashT >::iterator

Definition at line 62 of file SetVector.h.

◆ reverse_iterator

template<typename DataT , typename HashT = HashFn<DataT>>

typedef VectorType::reverse_iterator agx::SetVector< DataT, HashT >::reverse_iterator

Definition at line 64 of file SetVector.h.

◆ size_type

template<typename DataT , typename HashT = HashFn<DataT>>

typedef size_t agx::SetVector< DataT, HashT >::size_type

Definition at line 43 of file SetVector.h.

◆ value_type

template<typename DataT , typename HashT = HashFn<DataT>>

typedef DataT agx::SetVector< DataT, HashT >::value_type

Definition at line 41 of file SetVector.h.

◆ VectorType

template<typename DataT , typename HashT = HashFn<DataT>>

typedef Vector<DataT> agx::SetVector< DataT, HashT >::VectorType

Definition at line 45 of file SetVector.h.

Member Enumeration Documentation

◆ ClearPolicy

template<typename DataT , typename HashT = HashFn<DataT>>

enum agx::SetVector::ClearPolicy

Enumerator
SHRINK_BUFFER
SHRINK_BUFFER_AVERAGED
MAINTAIN_BUFFER

Definition at line 54 of file SetVector.h.

Constructor & Destructor Documentation

◆ SetVector() [1/2]

template<typename DataT , typename HashT = HashFn<DataT>>

agx::SetVector< DataT, HashT >::SetVector ( )

inline

Constructor.

Definition at line 69 of file SetVector.h.

◆ SetVector() [2/2]

template<typename DataT , typename HashT = HashFn<DataT>>

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

inline

Copy constructor.

Definition at line 73 of file SetVector.h.

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

◆ ~SetVector()

template<typename DataT , typename HashT = HashFn<DataT>>

agx::SetVector< DataT, HashT >::~SetVector ( )

inline

Destructor.

Definition at line 93 of file SetVector.h.

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

Member Function Documentation

◆ at() [1/2]

template<typename DataT , typename HashT = HashFn<DataT>>

DataT & agx::SetVector< DataT, HashT >::at ( size_t index )

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 499 of file SetVector.h.

References agx::Vector< T, Allocator >::at().

◆ at() [2/2]

template<typename DataT , typename HashT = HashFn<DataT>>

const DataT & agx::SetVector< DataT, HashT >::at ( size_t index ) const

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 488 of file SetVector.h.

References agx::Vector< T, Allocator >::at().

◆ back() [1/2]

template<typename DataT , typename HashT = HashFn<DataT>>

DataT & agx::SetVector< DataT, HashT >::back ( )

inline

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

Definition at line 371 of file SetVector.h.

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

◆ back() [2/2]

template<typename DataT , typename HashT = HashFn<DataT>>

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

inline

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

Definition at line 380 of file SetVector.h.

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

◆ begin() [1/2]

template<typename DataT , typename HashT = HashFn<DataT>>

iterator agx::SetVector< DataT, HashT >::begin ( )

inline

Returns: iterator to first element in the vector container

Definition at line 276 of file SetVector.h.

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

Referenced by agxWire::WireController::getBeginWireIterator(), and agx::SetVector< DataT, HashT >::replace().

◆ begin() [2/2]

template<typename DataT , typename HashT = HashFn<DataT>>

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

inline

Returns: const_iterator to first element in the vector container

Definition at line 286 of file SetVector.h.

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

◆ clear()

template<typename DataT , typename HashT = HashFn<DataT>>

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

inline

Remove all elements.

Parameters

policy - specifies the erase policy.

Definition at line 446 of file SetVector.h.

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

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

◆ contains()

template<typename DataT , typename HashT = HashFn<DataT>>

template<typename T2 >

bool agx::SetVector< DataT, HashT >::contains ( const T2 & key ) const

inline

Hash search for the data in the container.

Complexity: O(HashTable::contains())

Returns: true if key exists in the container.

Definition at line 225 of file SetVector.h.

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

Referenced by agxCollide::Space::canCollide(), and agxSDK::matchFilter().

◆ empty()

template<typename DataT , typename HashT = HashFn<DataT>>

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

inline

Return true if the container is empty.

Definition at line 128 of file SetVector.h.

References agx::Container::empty().

Referenced by agx::Frame::hasChildren(), and agx::SetVector< DataT, HashT >::purge().

◆ end() [1/2]

template<typename DataT , typename HashT = HashFn<DataT>>

iterator agx::SetVector< DataT, HashT >::end ( )

inline

Returns: iterator marking end of the vector container

Definition at line 316 of file SetVector.h.

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

Referenced by agx::SetVector< DataT, HashT >::erase(), agx::SetVector< DataT, HashT >::find(), agx::SetVector< DataT, HashT >::push_back(), and agx::SetVector< DataT, HashT >::replace().

◆ end() [2/2]

template<typename DataT , typename HashT = HashFn<DataT>>

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

inline

Returns: const_iterator marking end of the vector container

Definition at line 326 of file SetVector.h.

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

◆ erase() [1/2]

template<typename DataT , typename HashT = HashFn<DataT>>

bool agx::SetVector< DataT, HashT >::erase ( const iterator & it )

inline

Erase an element using an iterator.

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: true if erasing the element referred by it was successful. False if it==end()

Definition at line 422 of file SetVector.h.

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

◆ erase() [2/2]

template<typename DataT , typename HashT = HashFn<DataT>>

template<typename T2 >

bool agx::SetVector< DataT, HashT >::erase ( const T2 & 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 397 of file SetVector.h.

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

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

◆ find() [1/2]

template<typename DataT , typename HashT = HashFn<DataT>>

template<typename T2 >

iterator agx::SetVector< DataT, HashT >::find ( const T2 & 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 241 of file SetVector.h.

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

◆ find() [2/2]

template<typename DataT , typename HashT = HashFn<DataT>>

template<typename T2 >

const_iterator agx::SetVector< DataT, HashT >::find ( const T2 & 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 260 of file SetVector.h.

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

◆ front() [1/2]

template<typename DataT , typename HashT = HashFn<DataT>>

DataT & agx::SetVector< DataT, HashT >::front ( )

inline

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

Definition at line 353 of file SetVector.h.

References agxAssert.

◆ front() [2/2]

template<typename DataT , typename HashT = HashFn<DataT>>

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

inline

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

Definition at line 362 of file SetVector.h.

References agxAssert.

◆ insert()

template<typename DataT , typename HashT = HashFn<DataT>>

template<typename T2 >

iterator agx::SetVector< DataT, HashT >::insert ( const T2 & data )

inline

Insert a data element 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 182 of file SetVector.h.

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

◆ operator=()

template<typename DataT , typename HashT = HashFn<DataT>>

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

inline

Assignment operator.

Definition at line 80 of file SetVector.h.

◆ operator[]() [1/2]

template<typename DataT , typename HashT = HashFn<DataT>>

DataT & agx::SetVector< 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 462 of file SetVector.h.

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

◆ operator[]() [2/2]

template<typename DataT , typename HashT = HashFn<DataT>>

const DataT & agx::SetVector< 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 474 of file SetVector.h.

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

◆ purge()

template<typename DataT , typename HashT = HashFn<DataT>>

template<typename T >

size_t agx::SetVector< 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 - size of container, 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 T1& a, const T2& b) { return a > b; } };

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 545 of file SetVector.h.

References agx::Vector< T, Allocator >::begin(), agx::Vector< T, Allocator >::clear(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::clear(), agx::SetVector< DataT, HashT >::empty(), agx::Vector< T, Allocator >::end(), agx::SetVector< 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 DataT , typename HashT = HashFn<DataT>>

template<typename T2 >

iterator agx::SetVector< DataT, HashT >::push_back ( const T2 & data )

inline

Insert a data element 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 data 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 148 of file SetVector.h.

References agxAssert, agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::end(), agx::SetVector< DataT, HashT >::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::SetVector< DataT, HashT >::insert().

◆ rbegin() [1/2]

template<typename DataT , typename HashT = HashFn<DataT>>

reverse_iterator agx::SetVector< DataT, HashT >::rbegin ( )

inline

Returns: reverse iterator to first element in the vector container

Definition at line 296 of file SetVector.h.

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

◆ rbegin() [2/2]

template<typename DataT , typename HashT = HashFn<DataT>>

const_reverse_iterator agx::SetVector< DataT, HashT >::rbegin ( ) const

inline

Returns: reverse const_iterator to first element in the vector container

Definition at line 306 of file SetVector.h.

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

◆ rend() [1/2]

template<typename DataT , typename HashT = HashFn<DataT>>

reverse_iterator agx::SetVector< DataT, HashT >::rend ( )

inline

Returns: reverse iterator marking end of the vector container

Definition at line 335 of file SetVector.h.

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

◆ rend() [2/2]

template<typename DataT , typename HashT = HashFn<DataT>>

const_reverse_iterator agx::SetVector< DataT, HashT >::rend ( ) const

inline

Returns: reverse const_iterator marking end of the vector container

Definition at line 344 of file SetVector.h.

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

◆ replace()

template<typename DataT , typename HashT = HashFn<DataT>>

template<typename OldDataT , typename NewDataT >

iterator agx::SetVector< DataT, HashT >::replace	(	const OldDataT &	oldData,
		const NewDataT &	newData
	)

inline

Replace data in set vector.

Similar to erase + insert but preserve iteration order.

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

Parameters

oldData	- old key (fails if not present in this hash vector)
newData	- new key for data

Returns: iterator to the inserted data

Definition at line 200 of file SetVector.h.

References agxAssert, agx::SetVector< DataT, HashT >::begin(), agx::LinearProbingHashTableImplementation< KeyT, ValueT, HashT, AllocatorT >::end(), agx::SetVector< DataT, HashT >::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 DataT , typename HashT = HashFn<DataT>>

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

inline

Reserve capacity in the hash table.

Parameters

size	- reserve size elements

Definition at line 509 of file SetVector.h.

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

◆ size()

template<typename DataT , typename HashT = HashFn<DataT>>

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

inline

Return the number of inserted elements.

Definition at line 118 of file SetVector.h.

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

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

◆ table()

template<typename DataT , typename HashT = HashFn<DataT>>

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

inline

Returns: the hash table containing vector indices for existing elements

Definition at line 110 of file SetVector.h.

◆ vector()

template<typename DataT , typename HashT = HashFn<DataT>>

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

inline

Returns: the elements

Definition at line 102 of file SetVector.h.

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

SetVector.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_reference

◆ const_reverse_iterator

◆ ContainerType

◆ HashType

◆ iterator

◆ reverse_iterator

◆ size_type

◆ value_type

◆ VectorType

Member Enumeration Documentation

◆ ClearPolicy

Constructor & Destructor Documentation

◆ SetVector() [1/2]

◆ SetVector() [2/2]

◆ ~SetVector()

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ 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]

◆ insert()

◆ operator=()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ purge()

◆ push_back()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ replace()

◆ reserve()

◆ size()

◆ table()

◆ vector()