stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > Class Template Reference

The Hashtable containing all the elements. More...

Public Member Functions
hasher	hash_funct () const
key_equal	key_eq () const
allocator_type	get_allocator () const
	hashtable (size_type __n, const _HashFcn &__hf, const _EqualKey &__eql, const _ExtractKey &__ext, const allocator_type &__a=allocator_type())
	Constructs a hashtable with a specific number of buckets, a hasher, a comparison object, a key extractor functor and an allocator. More...
	hashtable (size_type __n, const _HashFcn &__hf, const _EqualKey &__eql, const allocator_type &__a=allocator_type())
	Constructs a hashtable with a specific number of buckets, a hasher, a comparison object, a key extractor functor and an allocator. More...
	hashtable (const hashtable &__ht)
hashtable &	operator= (const hashtable &__ht)
size_type	size () const
	Returns the number of elements in the container.
size_type	max_size () const
	Returns the maximum number of elements that can be held in the container.
bool	empty () const
	Returns whether the container is empty or not.
void	swap (hashtable &__ht)
	Exchange the content of the container with another one. More...
iterator	begin ()
iterator	end ()
const_iterator	begin () const
const_iterator	end () const
size_type	bucket_count () const
	Returns the number of buckets used by the container.
size_type	max_bucket_count () const
	Returns the maximum number of buckets that may be used by the container.
size_type	elems_in_bucket (size_type __bucket) const
	Returns the number of elements in a specific bucket.
std::pair< iterator, bool >	insert_unique (const value_type &__obj)
	Inserts a new element in the container. More...
iterator	insert_equal (const value_type &__obj)
	Inserts a new element in the container. If other elements with the same key already are in the container, it inserts the new element after the first element with the same key. More...
std::pair< iterator, bool >	insert_unique_noresize (const value_type &__obj)
	Inserts a new element in the container without resizing the buckets. More...
iterator	insert_equal_noresize (const value_type &__obj)
	Inserts a new element in the container without resizing the buckets. If other elements with the same key already are in the container, it inserts the new element after the first element with the same key. More...
template<class _InputIterator >
void	insert_unique (_InputIterator __f, _InputIterator __l)
	Inserts new elements in the container. More...
template<class _InputIterator >
void	insert_equal (_InputIterator __f, _InputIterator __l)
	Inserts a new element in the container. If other elements with the same key already are in the container, it inserts the new element after the first element with the same key. More...
template<class _InputIterator >
void	insert_unique (_InputIterator __f, _InputIterator __l, std::input_iterator_tag)
	Specialization of insert_unique for input iterators.
template<class _InputIterator >
void	insert_equal (_InputIterator __f, _InputIterator __l, std::input_iterator_tag)
	Specialization of insert_equal for input iterators.
template<class _ForwardIterator >
void	insert_unique (_ForwardIterator __f, _ForwardIterator __l, std::bidirectional_iterator_tag)
	Specialization of insert_unique for bidirectional iterators.
template<class _ForwardIterator >
void	insert_equal (_ForwardIterator __f, _ForwardIterator __l, std::bidirectional_iterator_tag)
	Specialization of insert_equal for bidirectional iterators.
void	insert_unique (const value_type *__f, const value_type *__l)
	Inserts new elements in the container. More...
void	insert_equal (const value_type *__f, const value_type *__l)
	Inserts a new element in the container. If other elements with the same key already are in the container, it inserts the new element after the first element with the same key. More...
void	insert_unique (const_iterator __f, const_iterator __l)
	Inserts new elements in the container. More...
void	insert_equal (const_iterator __f, const_iterator __l)
	Inserts a new element in the container. If other elements with the same key already are in the container, it inserts the new element after the first element with the same key. More...
reference	find_or_insert (const value_type &__obj)
	Returns a reference to a searched object. If the object was not found, inserts the object in the hashtable. More...
iterator	find (const key_type &__key)
	Search for a specific element in the container. More...
const_iterator	find (const key_type &__key) const
	Search for a specific element in the container. More...
size_type	count (const key_type &__key) const
	Returns the number of elements with the specified key. More...
std::pair< iterator, iterator >	equal_range (const key_type &__key)
	Return a range that includes all the elements with a specific key. More...
std::pair< const_iterator, const_iterator >	equal_range (const key_type &__key) const
	Return a range that includes all the elements with a specific key. More...
size_type	erase (const key_type &__key)
	Removes all elements with the specified key from the container. More...
void	erase (const iterator &__it)
	Removes an element pointed by an iterator from the container. More...
void	erase (iterator __first, iterator __last)
	Removes some elements pointed by an iterator from the container. More...
void	erase (const const_iterator &__it)
	Removes an element pointed by an iterator from the container. More...
void	erase (const_iterator __first, const_iterator __last)
	Removes some elements pointed by an iterator from the container. More...
void	resize (size_type __num_elements_hint)
	Increases the bucket count to at least __hint.
void	clear ()
	Removes all the elements from the container.
size_type	memory_size (void) const
	Returns the size in the memory used by the container.

Public Types
typedef _Key	key_type
typedef _Val	value_type
typedef _HashFcn	hasher
typedef _EqualKey	key_equal
typedef size_t	size_type
typedef ptrdiff_t	difference_type
typedef value_type *	pointer
typedef const value_type *	const_pointer
typedef value_type &	reference
typedef const value_type &	const_reference
typedef _Alloc	allocator_type
typedef _Hashtable_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >	iterator
typedef _Hashtable_const_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >	const_iterator

Protected Member Functions
_Node *	_M_get_node ()
void	_M_put_node (_Node *__p)
_Node_base **	_M_get_buckets (size_type __n)
void	_M_put_buckets (_Node_base **__p, size_type __n)
size_type	_M_next_size (size_type __n) const
	Returns the first prime number following a given number. More...
void	_M_initialize_buckets (size_type __n)
	Initializes a given number of buckets. It will initialize a prime number of buckets with _M_next_size(size_type __n). More...
size_type	_M_bkt_num_key (const key_type &__key) const
	Returns the index of the bucket where a particular element should be. More...
size_type	_M_bkt_num (const value_type &__obj) const
	Returns the index of the bucket where a particular element should be. More...
size_type	_M_bkt_num_key (const key_type &__key, size_t __n) const
	Returns the index of the bucket where a particular element should be. More...
size_type	_M_bkt_num (const value_type &__obj, size_t __n) const
	Returns the index of the bucket where a particular element should be. More...
_Node_base *	_M_new_node (const value_type &__obj)
	Initialize a new node for a given element. More...
void	_M_delete_node (_Node_base *__n)
	Deletes a node. More...
void	_M_delete_nodes (_Node_base **__p, size_type __num)
	Deletes a list of nodes. More...
_Node_base **	_M_new_buckets (const size_type __n)
	Increases the number of buckets by a specified integer. More...
void	_M_delete_buckets (_Node_base **__p, const size_type __n)
	Deletes a specified number of buckets. More...
void	_M_erase_bucket (const size_type __n, _Node_base *__first, _Node_base *__last)
	Removes all the elements in a range from a specific bucket. More...
void	_M_erase_bucket (const size_type __n, _Node_base *__last)
	Removes all the elements in a range from a specific bucket. More...
void	_M_copy_from (const hashtable &__ht)
	Copy all the elements from another hashtable. More...

Protected Types
typedef _Hashtable_node_base	_Node_base
typedef _Hashtable_node< _Val >	_Node
typedef allocator_type::template rebind< _Node >::other	_M_node_allocator_type
typedef _M_node_allocator_type::template rebind< _Node_base * >::other	_M_bucket_allocator_type

Protected Attributes
hasher	_M_hash
key_equal	_M_equals
_ExtractKey	_M_get_key
_Node_base **	_M_buckets
size_type	_M_num_buckets
size_type	_M_num_elements
_M_node_allocator_type	_M_node_allocator
_M_bucket_allocator_type	_M_bucket_allocator
_Node_base *	_M_end

Friends
struct	_Hashtable_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >
struct	_Hashtable_const_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >
template<class _Vl , class _Ky , class _HF , class _Ex , class _Eq , class _Al >
bool	operator== (const hashtable< _Vl, _Ky, _HF, _Ex, _Eq, _Al > &, const hashtable< _Vl, _Ky, _HF, _Ex, _Eq, _Al > &)

Detailed Description

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>
class stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >

The Hashtable containing all the elements.

[Changes made from SGI Hashtable:] [_Hashtable_node is now bidirectional.] [ – Operators added] [_Node** used rather than Vector<_Node*, alloc> for array of buckets] [_M_bucket_allocator used for bucket memory management] [Used in _M_delete/new_buckets functions]

Note

Hashtables handle allocators a bit differently than other containers do. If we're using standard-conforming allocators, then a hashtable unconditionally has a member variable to hold its allocator, even if it so happens that all instances of the allocator type are identical. This is because, for hashtables, this extra storage is negligible. Additionally, a base class wouldn't serve any other purposes; it wouldn't, for example, simplify the exception-handling code.

Template Parameters

_Val	The hashtable value type.
_Key	The hashtable's key type.
_HashFcn	The hash function used by the hashtable.
_ExtractKey	Functor that extracts the key from the data type.
_EqualKey	The key equality functor. Binary predicate used to compare key values of elements stored in the container for equality. The default equality functor is std::equal_to<_Key>.
_Alloc	The hashtable's allocator used for internal memory management. The default allocator is std::allocator<_Tp>.

Constructor & Destructor Documentation

hashtable() [1/2]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::hashtable	(	size_type	__n,
		const _HashFcn &	__hf,
		const _EqualKey &	__eql,
		const _ExtractKey &	__ext,
		const allocator_type &	__a = allocator_type()
	)

Constructs a hashtable with a specific number of buckets, a hasher, a comparison object, a key extractor functor and an allocator.

Parameters

__n	The number of buckets desired.
__hf	The hasher functor.
__eql	The comparison object.
__ext	The key extractor object.
__a	The allocator. By default a new one is constructed.

hashtable() [2/2]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::hashtable	(	size_type	__n,
		const _HashFcn &	__hf,
		const _EqualKey &	__eql,
		const allocator_type &	__a = allocator_type()
	)

Constructs a hashtable with a specific number of buckets, a hasher, a comparison object, a key extractor functor and an allocator.

Parameters

__n	The number of buckets desired.
__hf	The hasher functor.
__eql	The comparison object.
__a	The allocator. By default a new one is constructed.

Member Function Documentation

swap()

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

void stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::swap

(

hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > &

__ht

)

Exchange the content of the container with another one.

Parameters

__ht	The container which swaps elements of the same type.

insert_unique() [1/4]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

std::pair<iterator, bool> stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::insert_unique

(

const value_type &

__obj

)

Inserts a new element in the container.

Parameters

__obj

The element to be inserted.

Returns

A pair containing an iterator pointing to the element whose key is the same as the key of the element to insert, and a bool value that indicates whether the element was successfully inserted or not.

insert_equal() [1/4]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

iterator stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::insert_equal

(

const value_type &

__obj

)

Inserts a new element in the container. If other elements with the same key already are in the container, it inserts the new element after the first element with the same key.

Parameters

__obj

The element to be inserted.

Returns

An iterator pointing to the newly inserted element

insert_unique() [2/4]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

template<class _InputIterator >

void stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::insert_unique	(	_InputIterator	__f,
		_InputIterator	__l
	)

Inserts new elements in the container.

Parameters

__f,__l

Input iterators delimiting a range of elements to insert. The range of elements is [__f,__l).

insert_equal() [2/4]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

template<class _InputIterator >

void stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::insert_equal	(	_InputIterator	__f,
		_InputIterator	__l
	)

Inserts a new element in the container. If other elements with the same key already are in the container, it inserts the new element after the first element with the same key.

Parameters

__f,__l

Input iterators delimiting a range of elements to insert. The range of elements is [__f,__l).

insert_unique() [3/4]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

void stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::insert_unique	(	const value_type *	__f,
		const value_type *	__l
	)

Inserts new elements in the container.

Parameters

__f,__l

Pointers delimiting a range of elements to insert. The range of elements is [__f,__l).

insert_equal() [3/4]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

void stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::insert_equal	(	const value_type *	__f,
		const value_type *	__l
	)

Inserts a new element in the container. If other elements with the same key already are in the container, it inserts the new element after the first element with the same key.

Parameters

__f,__l

Pointers delimiting a range of elements to insert. The range of elements is [__f,__l).

insert_unique() [4/4]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

void stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::insert_unique	(	const_iterator	__f,
		const_iterator	__l
	)

Inserts new elements in the container.

Parameters

__f,__l

Input iterators delimiting a range of elements to insert. The range of elements is [__f,__l).

insert_equal() [4/4]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

void stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::insert_equal	(	const_iterator	__f,
		const_iterator	__l
	)

Inserts a new element in the container. If other elements with the same key already are in the container, it inserts the new element after the first element with the same key.

Parameters

__f,__l

Input iterators delimiting a range of elements to insert. The range of elements is [__f,__l).

find() [1/2]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

iterator stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::find

(

const key_type &

__key

)

Search for a specific element in the container.

Parameters

__key

The key indexing the element.

Returns

Iterator to the element, or to the end if no element is found.

find() [2/2]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

const_iterator stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::find

(

const key_type &

__key

)

const

Search for a specific element in the container.

Parameters

__key

The key indexing the element.

Returns

Iterator to the element, or to the end if no element is found.

count()

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

size_type stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::count

(

const key_type &

__key

)

const

Returns the number of elements with the specified key.

Parameters

__key

The key indexing the element.

_M_next_size()

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

size_type stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::_M_next_size ( size_type  __n ) const

protected

Returns the first prime number following a given number.

Parameters

__n	The current number.

_M_initialize_buckets()

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

void stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::_M_initialize_buckets ( size_type  __n )

protected

Initializes a given number of buckets. It will initialize a prime number of buckets with _M_next_size(size_type __n).

Parameters

__n	The desired number of buckets.

_M_bkt_num_key() [1/2]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

size_type stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::_M_bkt_num_key ( const key_type &  __key ) const

protected

Returns the index of the bucket where a particular element should be.

Parameters

__key

The key indexing the element.

_M_bkt_num() [1/2]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

size_type stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::_M_bkt_num ( const value_type &  __obj ) const

protected

Returns the index of the bucket where a particular element should be.

Parameters

__obj

The element.

_M_bkt_num_key() [2/2]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

size_type stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::_M_bkt_num_key ( const key_type &  __key, size_t  __n  ) const

protected

Returns the index of the bucket where a particular element should be.

Parameters

__key	The key indexing the element.
__n	The total number of buckets.

_M_bkt_num() [2/2]

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

size_type stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::_M_bkt_num ( const value_type &  __obj, size_t  __n  ) const

protected

Returns the index of the bucket where a particular element should be.

Parameters

__obj	The element.
__n	The total number of buckets.

_M_new_node()

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

_Node_base* stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::_M_new_node ( const value_type &  __obj )

protected

Initialize a new node for a given element.

Parameters

__obj

The element.

Returns

A pointer to the _Node_base containing the element

_M_delete_node()

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

void stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::_M_delete_node ( _Node_base *  __n )

protected

Deletes a node.

Parameters

__n	A pointer to the node to delete.

_M_delete_nodes()

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

void stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::_M_delete_nodes ( _Node_base **  __p, size_type  __num  )

protected

Deletes a list of nodes.

Parameters

__p	A pointer to the first _Node_base pointer.
__num	The size of the nodes' list.

_M_new_buckets()

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

_Node_base** stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::_M_new_buckets ( const size_type  __n )

protected

Increases the number of buckets by a specified integer.

Parameters

__n	The number of buckets to create.

_M_delete_buckets()

template<class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>

void stapl::hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc >::_M_delete_buckets ( _Node_base **  __p, const size_type  __n  )

protected

Deletes a specified number of buckets.

Parameters

__p	The pointer to the starting bucket to be deleted.
__n	The number of buckets to delete.

---

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

• stapl_hashtable_impl.h