A cache-friendly hash set with open addressing, linear probing and power-of-two capacity. More...

#include <LinearProbingHashSet.h>

Inheritance diagram for agx::LinearProbingHashSetImplementation< KeyT, HashT >:

Classes
class	const_iterator

class	iterator

Public Types
using	const_reference = const KeyT &

using	reference = KeyT &

using	size_type = size_t

using	value_type = KeyT

Public Member Functions
	LinearProbingHashSetImplementation ()=default

	LinearProbingHashSetImplementation (const LinearProbingHashSetImplementation &other)

	LinearProbingHashSetImplementation (LinearProbingHashSetImplementation &&other)

	~LinearProbingHashSetImplementation ()

iterator	begin ()

const_iterator	begin () const

void	clear ()

bool	contains (const KeyT &k) const

size_t	count (const KeyT &k) const

template<class... Args>
iterator	emplace (Args &&... args)

bool	empty () const

iterator	end ()

const_iterator	end () const

bool	erase (const KeyT &key)

iterator	erase (iterator it)

iterator	find (const KeyT &key)

const_iterator	find (const KeyT &key) const

iterator	insert (const KeyT &key)

void	insert (const_iterator begin, const_iterator end)

iterator	insert (KeyT &&key)

void	insert_unique (KeyT &&key)

LinearProbingHashSetImplementation &	operator= (const LinearProbingHashSetImplementation &other)

LinearProbingHashSetImplementation &	operator= (LinearProbingHashSetImplementation &&other)

void	reserve (size_t num_elems)

size_t	size () const

void	swap (LinearProbingHashSetImplementation &other)

Protected Member Functions
void	erase_bucket (size_t bucket)

template<typename T2 >
size_t	find_filled_bucket (const T2 &key) const

Detailed Description

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

A cache-friendly hash set with open addressing, linear probing and power-of-two capacity.

Definition at line 43 of file LinearProbingHashSet.h.

Member Typedef Documentation

◆ const_reference

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

using agx::LinearProbingHashSetImplementation< KeyT, HashT >::const_reference = const KeyT&

Definition at line 58 of file LinearProbingHashSet.h.

◆ reference

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

using agx::LinearProbingHashSetImplementation< KeyT, HashT >::reference = KeyT&

Definition at line 57 of file LinearProbingHashSet.h.

◆ size_type

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

using agx::LinearProbingHashSetImplementation< KeyT, HashT >::size_type = size_t

Definition at line 55 of file LinearProbingHashSet.h.

◆ value_type

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

using agx::LinearProbingHashSetImplementation< KeyT, HashT >::value_type = KeyT

Definition at line 56 of file LinearProbingHashSet.h.

Constructor & Destructor Documentation

◆ LinearProbingHashSetImplementation() [1/3]

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

agx::LinearProbingHashSetImplementation< KeyT, HashT >::LinearProbingHashSetImplementation ( )

default

◆ LinearProbingHashSetImplementation() [2/3]

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

agx::LinearProbingHashSetImplementation< KeyT, HashT >::LinearProbingHashSetImplementation ( const LinearProbingHashSetImplementation< KeyT, HashT > & other )

inline

Definition at line 204 of file LinearProbingHashSet.h.

References agx::cbegin(), agx::cend(), agx::LinearProbingHashSetImplementation< KeyT, HashT >::insert(), agx::LinearProbingHashSetImplementation< KeyT, HashT >::reserve(), and agx::LinearProbingHashSetImplementation< KeyT, HashT >::size().

◆ LinearProbingHashSetImplementation() [3/3]

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

agx::LinearProbingHashSetImplementation< KeyT, HashT >::LinearProbingHashSetImplementation ( LinearProbingHashSetImplementation< KeyT, HashT > && other )

inline

Definition at line 210 of file LinearProbingHashSet.h.

◆ ~LinearProbingHashSetImplementation()

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

agx::LinearProbingHashSetImplementation< KeyT, HashT >::~LinearProbingHashSetImplementation ( )

inline

Definition at line 233 of file LinearProbingHashSet.h.

Member Function Documentation

◆ begin() [1/2]

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

iterator agx::LinearProbingHashSetImplementation< KeyT, HashT >::begin ( )

inline

Definition at line 257 of file LinearProbingHashSet.h.

Referenced by agx::begin(), agx::cbegin(), and agx::LinearProbingHashSetImplementation< KeyT, HashT >::insert().

◆ begin() [2/2]

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

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

inline

Definition at line 266 of file LinearProbingHashSet.h.

◆ clear()

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

void agx::LinearProbingHashSetImplementation< KeyT, HashT >::clear ( )

inline

Definition at line 415 of file LinearProbingHashSet.h.

References agx::LinearProbingHashSetImplementation< KeyT, HashT >::empty().

Referenced by agx::LinearProbingHashSetImplementation< KeyT, HashT >::operator=().

◆ contains()

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

bool agx::LinearProbingHashSetImplementation< KeyT, HashT >::contains ( const KeyT & k ) const

inline

Definition at line 311 of file LinearProbingHashSet.h.

References agx::LinearProbingHashSetImplementation< KeyT, HashT >::find_filled_bucket().

Referenced by agx::LinearProbingHashSetImplementation< KeyT, HashT >::insert_unique().

◆ count()

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

size_t agx::LinearProbingHashSetImplementation< KeyT, HashT >::count ( const KeyT & k ) const

inline

Definition at line 316 of file LinearProbingHashSet.h.

References agx::LinearProbingHashSetImplementation< KeyT, HashT >::find_filled_bucket().

◆ emplace()

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

template<class... Args>

iterator agx::LinearProbingHashSetImplementation< KeyT, HashT >::emplace ( Args &&... args )

inline

Definition at line 366 of file LinearProbingHashSet.h.

References agx::LinearProbingHashSetImplementation< KeyT, HashT >::insert().

◆ empty()

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

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

inline

Definition at line 286 of file LinearProbingHashSet.h.

Referenced by agx::LinearProbingHashSetImplementation< KeyT, HashT >::clear(), and agx::LinearProbingHashSetImplementation< KeyT, HashT >::find_filled_bucket().

◆ end() [1/2]

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

iterator agx::LinearProbingHashSetImplementation< KeyT, HashT >::end ( )

inline

Definition at line 275 of file LinearProbingHashSet.h.

Referenced by agx::cend(), agx::end(), agx::LinearProbingHashSetImplementation< KeyT, HashT >::find(), agx::LinearProbingHashSet< agx::ref_ptr< KeyT >, HashT >::find(), and agx::LinearProbingHashSetImplementation< KeyT, HashT >::insert().

◆ end() [2/2]

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

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

inline

Definition at line 278 of file LinearProbingHashSet.h.

◆ erase() [1/2]

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

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

inline

Definition at line 393 of file LinearProbingHashSet.h.

References agx::LinearProbingHashSetImplementation< KeyT, HashT >::erase_bucket(), and agx::LinearProbingHashSetImplementation< KeyT, HashT >::find_filled_bucket().

◆ erase() [2/2]

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

iterator agx::LinearProbingHashSetImplementation< KeyT, HashT >::erase ( iterator it )

inline

Definition at line 406 of file LinearProbingHashSet.h.

References agx::LinearProbingHashSetImplementation< KeyT, HashT >::iterator::_bucket, agx::LinearProbingHashSetImplementation< KeyT, HashT >::iterator::_set, agxAssert, and agx::LinearProbingHashSetImplementation< KeyT, HashT >::erase_bucket().

◆ erase_bucket()

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

void agx::LinearProbingHashSetImplementation< KeyT, HashT >::erase_bucket ( size_t bucket )

inlineprotected

Definition at line 505 of file LinearProbingHashSet.h.

Referenced by agx::LinearProbingHashSetImplementation< KeyT, HashT >::erase(), and agx::LinearProbingHashSet< agx::ref_ptr< KeyT >, HashT >::erase().

◆ find() [1/2]

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

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

inline

Definition at line 293 of file LinearProbingHashSet.h.

References agx::LinearProbingHashSetImplementation< KeyT, HashT >::end(), and agx::LinearProbingHashSetImplementation< KeyT, HashT >::find_filled_bucket().

◆ find() [2/2]

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

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

inline

Definition at line 302 of file LinearProbingHashSet.h.

References agx::LinearProbingHashSetImplementation< KeyT, HashT >::end(), and agx::LinearProbingHashSetImplementation< KeyT, HashT >::find_filled_bucket().

◆ find_filled_bucket()

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

template<typename T2 >

size_t agx::LinearProbingHashSetImplementation< KeyT, HashT >::find_filled_bucket ( const T2 & key ) const

inlineprotected

Definition at line 488 of file LinearProbingHashSet.h.

References agx::LinearProbingHashSetImplementation< KeyT, HashT >::empty(), and agx::hashKeyEqual().

Referenced by agx::LinearProbingHashSetImplementation< KeyT, HashT >::contains(), agx::LinearProbingHashSet< agx::ref_ptr< KeyT >, HashT >::contains(), agx::LinearProbingHashSetImplementation< KeyT, HashT >::count(), agx::LinearProbingHashSetImplementation< KeyT, HashT >::erase(), agx::LinearProbingHashSet< agx::ref_ptr< KeyT >, HashT >::erase(), agx::LinearProbingHashSetImplementation< KeyT, HashT >::find(), and agx::LinearProbingHashSet< agx::ref_ptr< KeyT >, HashT >::find().

◆ insert() [1/3]

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

iterator agx::LinearProbingHashSetImplementation< KeyT, HashT >::insert ( const KeyT & key )

inline

Definition at line 327 of file LinearProbingHashSet.h.

Referenced by agx::LinearProbingHashSetImplementation< KeyT, HashT >::LinearProbingHashSetImplementation(), agx::LinearProbingHashSetImplementation< KeyT, HashT >::emplace(), agx::LinearProbingHashSetImplementation< KeyT, HashT >::insert(), and agx::LinearProbingHashSetImplementation< KeyT, HashT >::operator=().

◆ insert() [2/3]

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

void agx::LinearProbingHashSetImplementation< KeyT, HashT >::insert	(	const_iterator	begin,
		const_iterator	end
	)

inline

Definition at line 371 of file LinearProbingHashSet.h.

References agx::LinearProbingHashSetImplementation< KeyT, HashT >::begin(), agx::LinearProbingHashSetImplementation< KeyT, HashT >::end(), and agx::LinearProbingHashSetImplementation< KeyT, HashT >::insert().

◆ insert() [3/3]

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

iterator agx::LinearProbingHashSetImplementation< KeyT, HashT >::insert ( KeyT && key )

inline

Definition at line 348 of file LinearProbingHashSet.h.

◆ insert_unique()

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

void agx::LinearProbingHashSetImplementation< KeyT, HashT >::insert_unique ( KeyT && key )

inline

Definition at line 379 of file LinearProbingHashSet.h.

References agxAssert, and agx::LinearProbingHashSetImplementation< KeyT, HashT >::contains().

◆ operator=() [1/2]

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

LinearProbingHashSetImplementation & agx::LinearProbingHashSetImplementation< KeyT, HashT >::operator= ( const LinearProbingHashSetImplementation< KeyT, HashT > & other )

inline

Definition at line 215 of file LinearProbingHashSet.h.

References agx::cbegin(), agx::cend(), agx::LinearProbingHashSetImplementation< KeyT, HashT >::clear(), agx::LinearProbingHashSetImplementation< KeyT, HashT >::insert(), agx::LinearProbingHashSetImplementation< KeyT, HashT >::reserve(), and agx::LinearProbingHashSetImplementation< KeyT, HashT >::size().

◆ operator=() [2/2]

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

LinearProbingHashSetImplementation & agx::LinearProbingHashSetImplementation< KeyT, HashT >::operator= ( LinearProbingHashSetImplementation< KeyT, HashT > && other )

inline

Definition at line 227 of file LinearProbingHashSet.h.

References agx::LinearProbingHashSetImplementation< KeyT, HashT >::swap().

◆ reserve()

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

void agx::LinearProbingHashSetImplementation< KeyT, HashT >::reserve ( size_t num_elems )

inline

Definition at line 431 of file LinearProbingHashSet.h.

References agxAssert.

Referenced by agx::LinearProbingHashSetImplementation< KeyT, HashT >::LinearProbingHashSetImplementation(), and agx::LinearProbingHashSetImplementation< KeyT, HashT >::operator=().

◆ size()

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

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

inline

Definition at line 281 of file LinearProbingHashSet.h.

Referenced by agx::LinearProbingHashSetImplementation< KeyT, HashT >::LinearProbingHashSetImplementation(), and agx::LinearProbingHashSetImplementation< KeyT, HashT >::operator=().

◆ swap()

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

void agx::LinearProbingHashSetImplementation< KeyT, HashT >::swap ( LinearProbingHashSetImplementation< KeyT, HashT > & other )

inline

Definition at line 244 of file LinearProbingHashSet.h.

References std::swap().

Referenced by agx::LinearProbingHashSetImplementation< KeyT, HashT >::operator=().

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

LinearProbingHashSet.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Detailed Description

Member Typedef Documentation

◆ const_reference

◆ reference

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ LinearProbingHashSetImplementation() [1/3]

◆ LinearProbingHashSetImplementation() [2/3]

◆ LinearProbingHashSetImplementation() [3/3]

◆ ~LinearProbingHashSetImplementation()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ clear()

◆ contains()

◆ count()

◆ emplace()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ erase_bucket()

◆ find() [1/2]

◆ find() [2/2]

◆ find_filled_bucket()

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ insert_unique()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ reserve()

◆ size()

◆ swap()