#include <hash_table.h>

Classes
struct	ConvertFromValue

Public Types
typedef Traits	traits_type

typedef Traits::key_type	key_type

typedef Traits::key_equal	key_equal

typedef Traits::hasher	hasher

typedef Traits::allocator_type	allocator_type

typedef storage_type::list_type	list_type

typedef list_type::size_type	size_type

typedef list_type::difference_type	difference_type

typedef list_type::pointer	pointer

typedef list_type::const_pointer	const_pointer

typedef list_type::reference	reference

typedef list_type::const_reference	const_reference

typedef list_type::iterator	iterator

typedef list_type::const_iterator	const_iterator

typedef list_type::reverse_iterator	reverse_iterator

typedef list_type::const_reverse_iterator	const_reverse_iterator

typedef list_type::value_type	value_type

typedef iterator	local_iterator

typedef const_iterator	const_local_iterator

typedef storage_type::vector_value_type	vector_value_type

typedef storage_type::vector_type	vector_type

typedef AZStd::pair< iterator, bool >	pair_iter_bool

typedef AZStd::pair< iterator, iterator >	pair_iter_iter

typedef AZStd::pair< const_iterator, const_iterator >	pair_citer_citer

typedef list_type::node_type	list_node_type

typedef vector_type::node_type	vector_node_type

typedef hash_node_destructor< allocator_type, list_node_type >	node_deleter

Public Member Functions
AZ_FORCE_INLINE	hash_table (const hasher &hash, const key_equal &keyEqual, const allocator_type &alloc=allocator_type())

AZ_FORCE_INLINE	hash_table (const value_type first, const value_type last, const hasher &hash, const key_equal &keyEqual, const allocator_type &alloc)

	hash_table (const hash_table &rhs)

	hash_table (const hash_table &rhs, const type_identity_t< allocator_type > &alloc)

	hash_table (hash_table &&rhs)

	hash_table (hash_table &&rhs, const type_identity_t< allocator_type > &alloc)

this_type &	operator= (this_type &&rhs)

AZ_FORCE_INLINE this_type &	operator= (const this_type &rhs)

AZ_FORCE_INLINE iterator	begin ()

AZ_FORCE_INLINE const_iterator	begin () const

AZ_FORCE_INLINE iterator	end ()

AZ_FORCE_INLINE const_iterator	end () const

AZ_FORCE_INLINE local_iterator	begin (size_type bucket)

AZ_FORCE_INLINE const_local_iterator	begin (size_type bucket) const

AZ_FORCE_INLINE local_iterator	end (size_type bucket)

AZ_FORCE_INLINE const_local_iterator	end (size_type bucket) const

AZ_FORCE_INLINE reverse_iterator	rbegin ()

AZ_FORCE_INLINE const_reverse_iterator	rbegin () const

AZ_FORCE_INLINE reverse_iterator	rend ()

AZ_FORCE_INLINE const_reverse_iterator	rend () const

AZ_FORCE_INLINE size_type	size () const

AZ_FORCE_INLINE size_type	max_size () const

AZ_FORCE_INLINE bool	empty () const

AZ_FORCE_INLINE key_equal	key_eq () const

AZ_FORCE_INLINE hasher	get_hasher () const

AZ_FORCE_INLINE size_type	bucket_count () const

AZ_FORCE_INLINE size_type	max_bucket_count () const

AZ_FORCE_INLINE size_type	bucket (const key_type &keyValue) const

AZ_INLINE size_type	bucket_size (size_type bucket) const

AZ_FORCE_INLINE float	load_factor () const

AZ_FORCE_INLINE float	max_load_factor () const

AZ_FORCE_INLINE void	max_load_factor (float newMaxLoadFactor)

AZ_FORCE_INLINE pair_iter_bool	insert (const value_type &value)

AZ_FORCE_INLINE iterator	insert (const_iterator, const value_type &value)

AZ_FORCE_INLINE pair_iter_bool	insert (value_type &&value)

AZ_FORCE_INLINE iterator	insert (const_iterator, value_type &&value)

template<typename... Args>
AZ_FORCE_INLINE pair_iter_bool	emplace (Args &&... arguments)

AZ_FORCE_INLINE void	insert (std::initializer_list< value_type > list)

template<class Iterator >
auto	insert (Iterator first, Iterator last) -> enable_if_t< input_iterator< Iterator > &&!is_convertible_v< Iterator, size_type > >

template<class R >
auto	insert_range (R &&rg) -> enable_if_t< Internal::container_compatible_range< R, value_type > >

template<class InsertReturnType , class NodeHandle >
InsertReturnType	node_handle_insert (NodeHandle &&nodeHandle)

template<class NodeHandle >
auto	node_handle_insert (const_iterator hint, NodeHandle &&nodeHandle) -> iterator

template<class NodeHandle >
NodeHandle	node_handle_extract (const key_type &key)

template<class NodeHandle >
NodeHandle	node_handle_extract (const_iterator it)

AZ_FORCE_INLINE void	reserve (size_type numBucketsMin)

AZ_FORCE_INLINE void	rehash (size_type numBucketsMin)

iterator	erase (const_iterator erasePos)

size_type	erase (const key_type &keyValue)

iterator	erase (const_iterator first, const_iterator last)

AZ_FORCE_INLINE void	clear ()

template<class ComparableToKey >
auto	find (const ComparableToKey &key) -> enable_if_t<(Internal::is_transparent< key_equal, ComparableToKey >::value &&Internal::is_transparent< hasher, ComparableToKey >::value)\|\|AZStd::is_convertible_v< ComparableToKey, key_type >, iterator >

template<class ComparableToKey >
auto	find (const ComparableToKey &key) const -> enable_if_t<(Internal::is_transparent< key_equal, ComparableToKey >::value &&Internal::is_transparent< hasher, ComparableToKey >::value)\|\|AZStd::is_convertible_v< ComparableToKey, key_type >, const_iterator >

template<class ComparableToKey >
auto	contains (const ComparableToKey &key) const -> enable_if_t<(Internal::is_transparent< key_equal, ComparableToKey >::value &&Internal::is_transparent< hasher, ComparableToKey >::value)\|\|AZStd::is_convertible_v< ComparableToKey, key_type >, bool >

template<class ComparableToKey >
auto	count (const ComparableToKey &key) const -> enable_if_t<(Internal::is_transparent< key_equal, ComparableToKey >::value &&Internal::is_transparent< hasher, ComparableToKey >::value)\|\|AZStd::is_convertible_v< ComparableToKey, key_type >, size_type >

template<class ComparableToKey >
auto	lower_bound (const ComparableToKey &key) -> enable_if_t<(Internal::is_transparent< key_equal, ComparableToKey >::value &&Internal::is_transparent< hasher, ComparableToKey >::value)\|\|AZStd::is_convertible_v< ComparableToKey, key_type >, iterator >

template<class ComparableToKey >
auto	lower_bound (const ComparableToKey &key) const -> enable_if_t<(Internal::is_transparent< key_equal, ComparableToKey >::value &&Internal::is_transparent< hasher, ComparableToKey >::value)\|\|AZStd::is_convertible_v< ComparableToKey, key_type >, const_iterator >

template<class ComparableToKey >
auto	upper_bound (const ComparableToKey &key) -> enable_if_t<(Internal::is_transparent< key_equal, ComparableToKey >::value &&Internal::is_transparent< hasher, ComparableToKey >::value)\|\|AZStd::is_convertible_v< ComparableToKey, key_type >, iterator >

template<class ComparableToKey >
auto	upper_bound (const ComparableToKey &key) const -> enable_if_t<(Internal::is_transparent< key_equal, ComparableToKey >::value &&Internal::is_transparent< hasher, ComparableToKey >::value)\|\|AZStd::is_convertible_v< ComparableToKey, key_type >, const_iterator >

template<class ComparableToKey >
auto	equal_range (const ComparableToKey &key) -> enable_if_t<(Internal::is_transparent< key_equal, ComparableToKey >::value &&Internal::is_transparent< hasher, ComparableToKey >::value)\|\|AZStd::is_convertible_v< ComparableToKey, key_type >, AZStd::pair< iterator, iterator > >

template<class ComparableToKey >
auto	equal_range (const ComparableToKey &key) const -> enable_if_t<(Internal::is_transparent< key_equal, ComparableToKey >::value &&Internal::is_transparent< hasher, ComparableToKey >::value)\|\|AZStd::is_convertible_v< ComparableToKey, key_type >, AZStd::pair< const_iterator, const_iterator > >

AZ_INLINE void	swap (this_type &rhs)

template<typename ComparableToKey , typename... Args>
auto	try_emplace_transparent (ComparableToKey &&key, Args &&... arguments) -> pair_iter_bool

template<typename ComparableToKey , typename... Args>
auto	try_emplace_transparent (const_iterator, ComparableToKey &&key, Args &&... arguments) -> iterator

template<typename ComparableToKey , typename MappedType >
auto	insert_or_assign_transparent (ComparableToKey &&key, MappedType &&value) -> pair_iter_bool

template<typename ComparableToKey , typename MappedType >
auto	insert_or_assign_transparent (const_iterator, ComparableToKey &&key, MappedType &&value) -> iterator

Extensions

AZ_FORCE_INLINE allocator_type &	get_allocator ()

AZ_FORCE_INLINE const allocator_type &	get_allocator () const

void	set_allocator (const allocator_type &allocator)

template<class ComparableToKey , class Hasher , class KeyEqual >
iterator	find_as (const ComparableToKey &keyCmp, const Hasher &hash, const KeyEqual &keyEq)

template<class ComparableToKey , class Hasher , class KeyEqual >
const_iterator	find_as (const ComparableToKey &keyCmp, const Hasher &hash, const KeyEqual &keyEq) const

template<class U , class Converter , class Hasher , class KeyEqual >
pair_iter_bool	insert_from (const U &userValue, const Converter &convert, const Hasher &hash, const KeyEqual &keyEq)

bool	validate () const

int	validate_iterator (const iterator &iter) const
	Validates an iter iterator. Returns a combination of iterator_status_flag.

int	validate_iterator (const const_iterator &iter) const

void	leak_and_reset ()

Protected Member Functions
AZ_FORCE_INLINE size_type	bucket_from_hash (const size_type key) const

void	copy (const this_type &rhs)

void	assign_rv (this_type &&rhs)

template<class ComparableToKey , class KeyEq >
bool	find_insert_position (const ComparableToKey &keyCmp, const KeyEq &keyEq, iterator &insertIter, size_type numElements, const true_type &)

template<class ComparableToKey , class KeyEq >
bool	find_insert_position (const ComparableToKey &keyCmp, const KeyEq &keyEq, iterator &insertIter, size_type numElements, const false_type &)

template<typename T >
pair_iter_bool	insert_impl (T &&value)

template<typename... Args>
pair_iter_bool	insert_impl_emplace (Args &&... arguments)

template<typename ComparableToKey , typename... Args>
pair_iter_bool	try_emplace_transparent (ComparableToKey &&key, Args &&... arguments)

template<typename ComparableToKey , typename... Args>
iterator	try_emplace_transparent (const_iterator hint, ComparableToKey &&key, Args &&... arguments)

template<typename ComparableToKey , typename MappedType >
pair_iter_bool	insert_or_assign_transparent (ComparableToKey &&key, MappedType &&value)

template<typename ComparableToKey , typename MappedType >
iterator	insert_or_assign_transparent (const_iterator hint, ComparableToKey &&key, MappedType &&value)

Protected Attributes
storage_type	m_data

key_equal	m_keyEqual

hasher	m_hasher

Detailed Description

template<class Traits>
class AZStd::hash_table< Traits >

Hash table is internal container used as a base class for all unordered associative containers. It provides functionality for the unordered container in CTR1. (6.3.4). In addition we introduce the following extensions.

Traits should have the following members typedef xxx key_type; typedef xxx key_equal; typedef xxx hasher; typedef xxx value_type; typedef xxx allocator_type; enum { max_load_factor = xxx, // What should the max load factor before we grow the map. Load factor is the average num of elements per bucket. min_buckets = xxx, // Min num of buckets to be allocated. has_multi_elements = true or false, is_dynamic = true or false, // true if we have fixed container. If we do so we will need to se fixed_num_buckets and fixed_num_elements. fixed_num_buckets = xxx, // Number of buckets to pre-allocate. For hashing purposes it will be good to be a prime number. We we get better bucket distribution. // It should be aprox. 1/3 - 1/4 (max_load_factor 3 or 4) of the number of elements, otherwise we will have too much liear searches. fixed_num_elements = xxx, // Number of elements to pre-allocate. }

static inline key_type key_from_value(const value_type& value);

Member Function Documentation

◆ find_as()

template<class Traits >

template<class ComparableToKey , class Hasher , class KeyEqual >

iterator AZStd::hash_table< Traits >::find_as	(	const ComparableToKey &	keyCmp,
		const Hasher &	hash,
		const KeyEqual &	keyEq
	)

inline

This is similar to lazy_find in this paper C14IDEAS. The idea is to be able to customize the search. For non key_type objects.

◆ insert_from()

template<class Traits >

template<class U , class Converter , class Hasher , class KeyEqual >

pair_iter_bool AZStd::hash_table< Traits >::insert_from	(	const U &	userValue,
		const Converter &	convert,
		const Hasher &	hash,
		const KeyEqual &	keyEq
	)

inline

Inserts from a value and converter object. Converter object has the following interface struct MyConverter { typedef Map::key_type or CompareableToKeyType key_type; const key_type& to_key(const& MyValue) const; Map::value_type to_value(const& MyValue) const; } This allow us to convert any "userValue" (U parameter) to a key, check if we can add it to the list, if so, we call to_value function to create (to_key(userValue), to_value(userValue)) and add it to the hash table. This is similar to lazy_insert in this paper C14IDEAS. There is an example why it's beneficial, you can check AZStdExamples. The main idea is that you don't to create unnecessary expensive temporaries.

◆ leak_and_reset()

template<class Traits >

void AZStd::hash_table< Traits >::leak_and_reset ( )

inline

Resets the container without deallocating any memory or calling any destructor. This function should be used when we need very quick tear down. Generally it's used for temporary vectors and we can just nuke them that way. In addition the provided Allocators, has leak and reset flag which will enable automatically this behavior. So this function should be used in special cases AZStdExamples.

Note: This function is added to the vector for consistency. In the vector case we have only one allocation, and if the allocator allows memory leaks it can just leave deallocate function empty, which performance wise will be the same. For more complex containers this will make big difference.

◆ node_handle_extract() [1/2]

template<class Traits >

template<class NodeHandle >

NodeHandle AZStd::hash_table< Traits >::node_handle_extract ( const key_type & key )

inline

Searches for an element which matches the value of key and extracts it from the hash_table

Returns: A NodeHandle which can be used to insert the an element between unique and non-unique containers of the same type i.e a NodeHandle from an unordered_map can be used to insert a node into an unordered_multimap, but not a std::map

◆ node_handle_extract() [2/2]

template<class Traits >

template<class NodeHandle >

NodeHandle AZStd::hash_table< Traits >::node_handle_extract ( const_iterator it )

inline

Finds an element within the hash_table that is represented by the supplied iterator and extracts it

Returns: A NodeHandle which can be used to insert the an element between unique and non-unique containers of the same type

◆ node_handle_insert()

template<class Traits >

template<class InsertReturnType , class NodeHandle >

InsertReturnType AZStd::hash_table< Traits >::node_handle_insert ( NodeHandle && nodeHandle )

Returns an insert_return_type with the members initialized as follows: if nh is empty, inserted is false, position is end(), and node is empty. Otherwise if the insertion took place, inserted is true, position points to the inserted element, and node is empty. If the insertion failed, inserted is false, node has the previous value of nh, and position points to an element with a key equivalent to nh.key().

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

Code/Framework/AzCore/AzCore/std/containers/node_handle.h
Code/Framework/AzCore/AzCore/std/hash_table.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Function Documentation

◆ find_as()

◆ insert_from()

◆ leak_and_reset()

◆ node_handle_extract() [1/2]

◆ node_handle_extract() [2/2]

◆ node_handle_insert()