ReactOS 0.4.15-dev-7942-gd23573b
Public Types | Public Member Functions | Protected Member Functions | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All > Class Template Reference

#include <_hashtable.h>

Collaboration diagram for hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >:
Collaboration graph
[legend]

Public Types

typedef _Key key_type
 
typedef _Val value_type
 
typedef _HF hasher
 
typedef _EqK key_equal
 
typedef size_t size_type
 
typedef ptrdiff_t difference_type
 
typedef _NonConstTraits::pointer pointer
 
typedef const value_type * const_pointer
 
typedef _NonConstTraits::reference reference
 
typedef const value_type & const_reference
 
typedef forward_iterator_tag _Iterator_category
 
typedef _STLP_PRIV _Ht_iterator< _ElemsIte, _NonConstTraits > iterator
 
typedef _STLP_PRIV _Ht_iterator< _ElemsIte, _ConstTraits > const_iterator
 
typedef _STLP_PRIV _Ht_iterator< _ElemsIte, _NonConstLocalTraits > local_iterator
 
typedef _STLP_PRIV _Ht_iterator< _ElemsIte, _ConstLocalTraits > const_local_iterator
 
typedef _All allocator_type
 
typedef _Key key_type
 
typedef _HF hasher
 
typedef _EqK key_equal
 
typedef _STLP_PRIV _DBG_iter< _Base, _STLP_PRIV _DbgTraits< _NonConstTraits > > iterator
 
typedef _STLP_PRIV _DBG_iter< _Base, _STLP_PRIV _DbgTraits< _ConstTraits > > const_iterator
 
typedef iterator local_iterator
 
typedef const_iterator const_local_iterator
 
typedef _Base::iterator _Base_iterator
 
typedef _Base::const_iterator _Base_const_iterator
 

Public Member Functions

hasher hash_funct () const
 
key_equal key_eq () const
 
allocator_type get_allocator () const
 
 hashtable (size_type __n, const _HF &__hf, const _EqK &__eql, const allocator_type &__a=allocator_type())
 
 hashtable (const _Self &__ht)
 
 hashtable (__move_source< _Self > src)
 
_Self & operator= (const _Self &__ht)
 
 ~hashtable ()
 
size_type size () const
 
size_type max_size () const
 
bool empty () const
 
void swap (_Self &__ht)
 
iterator begin ()
 
iterator end ()
 
local_iterator begin (size_type __n)
 
local_iterator end (size_type __n)
 
const_iterator begin () const
 
const_iterator end () const
 
const_local_iterator begin (size_type __n) const
 
const_local_iterator end (size_type __n) const
 
size_type bucket_count () const
 
size_type max_bucket_count () const
 
size_type elems_in_bucket (size_type __bucket) const
 
_STLP_TEMPLATE_FOR_CONT_EXT size_type bucket (const _KT &__k) const
 
float load_factor () const
 
float max_load_factor () const
 
void max_load_factor (float __z)
 
pair< iterator, bool > insert_unique (const value_type &__obj)
 
iterator insert_equal (const value_type &__obj)
 
pair< iterator, bool > insert_unique_noresize (const value_type &__obj)
 
iterator insert_equal_noresize (const value_type &__obj)
 
void insert_unique (const value_type *__f, const value_type *__l)
 
void insert_equal (const value_type *__f, const value_type *__l)
 
void insert_unique (const_iterator __f, const_iterator __l)
 
void insert_equal (const_iterator __f, const_iterator __l)
 
_STLP_TEMPLATE_FOR_CONT_EXT iterator find (const _KT &__key)
 
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator find (const _KT &__key) const
 
_STLP_TEMPLATE_FOR_CONT_EXT size_type count (const _KT &__key) const
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range (const _KT &__key)
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range (const _KT &__key) const
 
size_type erase (const key_type &__key)
 
void erase (const_iterator __it)
 
void erase (const_iterator __first, const_iterator __last)
 
void rehash (size_type __num_buckets_hint)
 
void resize (size_type __num_buckets_hint)
 
void clear ()
 
reference _M_insert (const value_type &__obj)
 
hasher hash_funct () const
 
key_equal key_eq () const
 
allocator_type get_allocator () const
 
 hashtable (size_type __n, const _HF &__hf, const _EqK &__eql, const _ExK &__ext, const allocator_type &__a=allocator_type())
 
 hashtable (size_type __n, const _HF &__hf, const _EqK &__eql, const allocator_type &__a=allocator_type())
 
 hashtable (const _Self &__ht)
 
 hashtable (__move_source< _Self > src)
 
size_type size () const
 
size_type max_size () const
 
bool empty () const
 
_Self & operator= (const _Self &__ht)
 
void swap (_Self &__ht)
 
iterator begin ()
 
iterator end ()
 
local_iterator begin (size_type __n)
 
local_iterator end (size_type __n)
 
const_iterator begin () const
 
const_iterator end () const
 
const_local_iterator begin (size_type __n) const
 
const_local_iterator end (size_type __n) const
 
pair< iterator, bool > insert_unique (const value_type &__obj)
 
iterator insert_equal (const value_type &__obj)
 
pair< iterator, bool > insert_unique_noresize (const value_type &__obj)
 
iterator insert_equal_noresize (const value_type &__obj)
 
void insert_unique (const value_type *__f, const value_type *__l)
 
void insert_equal (const value_type *__f, const value_type *__l)
 
void insert_unique (const_iterator __f, const_iterator __l)
 
void insert_equal (const_iterator __f, const_iterator __l)
 
_STLP_TEMPLATE_FOR_CONT_EXT iterator find (const _KT &__key)
 
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator find (const _KT &__key) const
 
_STLP_TEMPLATE_FOR_CONT_EXT size_type count (const _KT &__key) const
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range (const _KT &__key)
 
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range (const _KT &__key) const
 
size_type erase (const key_type &__key)
 
void erase (const const_iterator &__it)
 
void erase (const_iterator __first, const_iterator __last)
 
void rehash (size_type __num_buckets_hint)
 
void resize (size_type __num_elements_hint)
 
void clear ()
 
reference _M_insert (const value_type &__obj)
 
size_type bucket_count () const
 
size_type max_bucket_count () const
 
size_type elems_in_bucket (size_type __n) const
 
_STLP_TEMPLATE_FOR_CONT_EXT size_type bucket (const _KT &__k) const
 
float load_factor () const
 
float max_load_factor () const
 
void max_load_factor (float __z)
 

Protected Member Functions

iterator _M_insert_noresize (size_type __n, const value_type &__obj)
 

Private Types

typedef hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All > _Self
 
typedef _Traits::_NonConstTraits _NonConstTraits
 
typedef _Traits::_ConstTraits _ConstTraits
 
typedef _Traits::_NonConstLocalTraits _NonConstLocalTraits
 
typedef _Traits::_ConstLocalTraits _ConstLocalTraits
 
typedef slist< value_type, _All > _ElemsCont
 
typedef _ElemsCont::iterator _ElemsIte
 
typedef _ElemsCont::const_iterator _ElemsConstIte
 
typedef _STLP_PRIV _Slist_node_base _BucketType
 
typedef _Alloc_traits< _BucketType *, _All >::allocator_type _BucketAllocType
 
typedef vector< _BucketType *, _BucketAllocType > _BucketVector
 
typedef hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All > _Self
 
typedef _STLP_NON_DBG_HT _Base
 
typedef _Traits::_NonConstTraits _NonConstTraits
 
typedef _Traits::_ConstTraits _ConstTraits
 
typedef _Traits::_NonConstLocalTraits _NonConstLocalTraits
 
typedef _Traits::_ConstLocalTraits _ConstLocalTraits
 

Private Member Functions

_STLP_TEMPLATE_FOR_CONT_EXT _ElemsIte _M_find (const _KT &__key) const
 
void _M_enlarge (size_type __n)
 
void _M_reduce ()
 
void _M_resize ()
 
void _M_rehash (size_type __num_buckets)
 
iterator _M_before_begin (size_type &__n) const
 
void _M_initialize_buckets (size_type __n)
 
_STLP_TEMPLATE_FOR_CONT_EXT size_type _M_bkt_num_key (const _KT &__key) const
 
size_type _M_bkt_num (const value_type &__obj) const
 
_STLP_TEMPLATE_FOR_CONT_EXT size_type _M_bkt_num_key (const _KT &__key, size_type __n) const
 
size_type _M_bkt_num (const value_type &__obj, size_t __n) const
 
void _M_copy_from (const _Self &__ht)
 
void _Invalidate_iterator (const const_iterator &__it)
 
void _Invalidate_iterators (const const_iterator &__first, const const_iterator &__last)
 

Static Private Member Functions

static const key_type & _M_get_key (const value_type &__val)
 
static iterator _S_before_begin (const _ElemsCont &__elems, const _BucketVector &__buckets, size_type &__n)
 

Private Attributes

hasher _M_hash
 
key_equal _M_equals
 
_ElemsCont _M_elems
 
_BucketVector _M_buckets
 
size_type _M_num_elements
 
float _M_max_load_factor
 
_Base _M_non_dbg_impl
 
_STLP_PRIV __owned_list _M_iter_list
 

Detailed Description

template<class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
class hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >

Definition at line 91 of file _hashtable.h.

Member Typedef Documentation

◆ _Base

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _STLP_NON_DBG_HT hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_Base
private

Definition at line 93 of file _hashtable.h.

◆ _Base_const_iterator

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Base::const_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_Base_const_iterator

Definition at line 118 of file _hashtable.h.

◆ _Base_iterator

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Base::iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_Base_iterator

Definition at line 117 of file _hashtable.h.

◆ _BucketAllocType

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Alloc_traits<_BucketType*,_All>::allocator_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_BucketAllocType
private

Definition at line 259 of file _hashtable.h.

◆ _BucketType

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _STLP_PRIV _Slist_node_base hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_BucketType
private

Definition at line 258 of file _hashtable.h.

◆ _BucketVector

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef vector<_BucketType*, _BucketAllocType> hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_BucketVector
private

Definition at line 271 of file _hashtable.h.

◆ _ConstLocalTraits [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Traits::_ConstLocalTraits hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_ConstLocalTraits
private

Definition at line 230 of file _hashtable.h.

◆ _ConstLocalTraits [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Traits::_ConstLocalTraits hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_ConstLocalTraits
private

Definition at line 98 of file _hashtable.h.

◆ _ConstTraits [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Traits::_ConstTraits hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_ConstTraits
private

Definition at line 228 of file _hashtable.h.

◆ _ConstTraits [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Traits::_ConstTraits hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_ConstTraits
private

Definition at line 96 of file _hashtable.h.

◆ _ElemsConstIte

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _ElemsCont::const_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_ElemsConstIte
private

Definition at line 257 of file _hashtable.h.

◆ _ElemsCont

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef slist<value_type, _All> hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_ElemsCont
private

Definition at line 254 of file _hashtable.h.

◆ _ElemsIte

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _ElemsCont::iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_ElemsIte
private

Definition at line 256 of file _hashtable.h.

◆ _Iterator_category

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef forward_iterator_tag hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_Iterator_category

Definition at line 244 of file _hashtable.h.

◆ _NonConstLocalTraits [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Traits::_NonConstLocalTraits hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_NonConstLocalTraits
private

Definition at line 229 of file _hashtable.h.

◆ _NonConstLocalTraits [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Traits::_NonConstLocalTraits hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_NonConstLocalTraits
private

Definition at line 97 of file _hashtable.h.

◆ _NonConstTraits [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Traits::_NonConstTraits hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_NonConstTraits
private

Definition at line 227 of file _hashtable.h.

◆ _NonConstTraits [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Traits::_NonConstTraits hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_NonConstTraits
private

Definition at line 95 of file _hashtable.h.

◆ _Self [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_Self
private

Definition at line 226 of file _hashtable.h.

◆ _Self [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_Self
private

Definition at line 92 of file _hashtable.h.

◆ allocator_type

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _All hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::allocator_type

Definition at line 299 of file _hashtable.h.

◆ const_iterator [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstTraits> hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::const_iterator

Definition at line 288 of file _hashtable.h.

◆ const_iterator [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_ConstTraits> > hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::const_iterator

Definition at line 111 of file _hashtable.h.

◆ const_local_iterator [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstLocalTraits> hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::const_local_iterator

Definition at line 293 of file _hashtable.h.

◆ const_local_iterator [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef const_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::const_local_iterator

Definition at line 115 of file _hashtable.h.

◆ const_pointer

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef const value_type* hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::const_pointer

Definition at line 241 of file _hashtable.h.

◆ const_reference

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef const value_type& hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::const_reference

Definition at line 243 of file _hashtable.h.

◆ difference_type

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef ptrdiff_t hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::difference_type

Definition at line 239 of file _hashtable.h.

◆ hasher [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _HF hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hasher

Definition at line 235 of file _hashtable.h.

◆ hasher [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _HF hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hasher

Definition at line 105 of file _hashtable.h.

◆ iterator [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstTraits> hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::iterator

Definition at line 287 of file _hashtable.h.

◆ iterator [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_NonConstTraits> > hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::iterator

Definition at line 110 of file _hashtable.h.

◆ key_equal [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _EqK hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::key_equal

Definition at line 236 of file _hashtable.h.

◆ key_equal [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _EqK hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::key_equal

Definition at line 106 of file _hashtable.h.

◆ key_type [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Key hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::key_type

Definition at line 233 of file _hashtable.h.

◆ key_type [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Key hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::key_type

Definition at line 104 of file _hashtable.h.

◆ local_iterator [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstLocalTraits> hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::local_iterator

Definition at line 292 of file _hashtable.h.

◆ local_iterator [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::local_iterator

Definition at line 113 of file _hashtable.h.

◆ pointer

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _NonConstTraits::pointer hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::pointer

Definition at line 240 of file _hashtable.h.

◆ reference

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _NonConstTraits::reference hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::reference

Definition at line 242 of file _hashtable.h.

◆ size_type

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef size_t hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::size_type

Definition at line 238 of file _hashtable.h.

◆ value_type

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
typedef _Val hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::value_type

Definition at line 234 of file _hashtable.h.

Constructor & Destructor Documentation

◆ hashtable() [1/7]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hashtable ( size_type  __n,
const _HF &  __hf,
const _EqK &  __eql,
const allocator_type &  __a = allocator_type() 
)
inline

Definition at line 303 of file _hashtable.h.

311 : _M_hash(__hf),
312 _M_equals(__eql),
313 _M_elems(allocator_type()),
314 _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
315 _M_num_elements(0),
316 _M_max_load_factor(1.0f)
317 { _M_initialize_buckets(__n); }
318
319 hashtable(size_type __n,
320 const _HF& __hf,
321 const _EqK& __eql,
322 const allocator_type& __a)
323#endif
324 : _M_hash(__hf),
325 _M_equals(__eql),
326 _M_elems(__a),
327 _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
328 _M_num_elements(0),
329 _M_max_load_factor(1.0f)
330 { _M_initialize_buckets(__n); }
__n
return __n
Definition: _algo.h:75
_STLP_CONVERT_ALLOCATOR
#define _STLP_CONVERT_ALLOCATOR(__a, _Tp)
Definition: _alloc.h:183
hashtable::_M_hash
hasher _M_hash
Definition: _hashtable.h:274
hashtable::_M_max_load_factor
float _M_max_load_factor
Definition: _hashtable.h:279
hashtable::_M_num_elements
size_type _M_num_elements
Definition: _hashtable.h:278
hashtable::allocator_type
_All allocator_type
Definition: _hashtable.h:299
hashtable::_M_elems
_ElemsCont _M_elems
Definition: _hashtable.h:276
hashtable::_M_initialize_buckets
void _M_initialize_buckets(size_type __n)
Definition: _hashtable.h:595
hashtable::_M_buckets
_BucketVector _M_buckets
Definition: _hashtable.h:277
hashtable::_BucketType
_STLP_PRIV _Slist_node_base _BucketType
Definition: _hashtable.h:258
hashtable::_M_equals
key_equal _M_equals
Definition: _hashtable.h:275
hashtable::size_type
size_t size_type
Definition: _hashtable.h:238

◆ hashtable() [2/7]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hashtable ( const _Self &  __ht)
inline

Definition at line 332 of file _hashtable.h.

333 : _M_hash(__ht._M_hash),
334 _M_equals(__ht._M_equals),
335 _M_elems(__ht.get_allocator()),
336 _M_buckets(_STLP_CONVERT_ALLOCATOR(__ht.get_allocator(), _BucketType*)),
337 _M_num_elements(0),
338 _M_max_load_factor(1.0f)
339 { _M_copy_from(__ht); }
hashtable::_M_copy_from
void _M_copy_from(const _Self &__ht)
Definition: _hashtable.c:510

◆ hashtable() [3/7]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hashtable ( __move_source< _Self >  src)
inline

Definition at line 342 of file _hashtable.h.

343 : _M_hash(_STLP_PRIV _AsMoveSource(src.get()._M_hash)),
344 _M_equals(_STLP_PRIV _AsMoveSource(src.get()._M_equals)),
345 _M_elems(__move_source<_ElemsCont>(src.get()._M_elems)),
346 _M_buckets(__move_source<_BucketVector>(src.get()._M_buckets)),
347 _M_num_elements(src.get()._M_num_elements),
348 _M_max_load_factor(src.get()._M_max_load_factor) {}
_STLP_PRIV
#define _STLP_PRIV
Definition: _dm.h:70
_AsMoveSource
_STLP_TYPENAME_ON_RETURN_TYPE _MoveSourceTraits< _Tp >::_Type _AsMoveSource(_Tp &src)
Definition: _move_construct_fwk.h:101
__move_source
Definition: _move_construct_fwk.h:35
src
GLenum src
Definition: glext.h:6340

◆ ~hashtable()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::~hashtable ( )
inline

Definition at line 361 of file _hashtable.h.

361{ clear(); }
hashtable::clear
void clear()
Definition: _hashtable.c:501

◆ hashtable() [4/7]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hashtable ( size_type  __n,
const _HF &  __hf,
const _EqK &  __eql,
const _ExK &  __ext,
const allocator_type &  __a = allocator_type() 
)
inline

Definition at line 134 of file _hashtable.h.

139 : _M_non_dbg_impl(__n, __hf, __eql, __ext, __a),
140 _M_iter_list(&_M_non_dbg_impl) {}
hashtable::_M_non_dbg_impl
_Base _M_non_dbg_impl
Definition: _hashtable.h:100
hashtable::_M_iter_list
_STLP_PRIV __owned_list _M_iter_list
Definition: _hashtable.h:101

◆ hashtable() [5/7]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hashtable ( size_type  __n,
const _HF &  __hf,
const _EqK &  __eql,
const allocator_type &  __a = allocator_type() 
)
inline

Definition at line 142 of file _hashtable.h.

146 : _M_non_dbg_impl(__n, __hf, __eql, __a),
147 _M_iter_list(&_M_non_dbg_impl) {}

◆ hashtable() [6/7]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hashtable ( const _Self &  __ht)
inline

Definition at line 149 of file _hashtable.h.

150 : _M_non_dbg_impl(__ht._M_non_dbg_impl),
151 _M_iter_list(&_M_non_dbg_impl) {}

◆ hashtable() [7/7]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hashtable ( __move_source< _Self >  src)
inline

Definition at line 154 of file _hashtable.h.

155 : _M_non_dbg_impl(__move_source<_Base>(src.get()._M_non_dbg_impl)),
156 _M_iter_list(&_M_non_dbg_impl) {
157# if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL)
158 src.get()._M_iter_list._Invalidate_all();
159# else
160 src.get()._M_iter_list._Set_owner(_M_iter_list);
161# endif
162 }

Member Function Documentation

◆ _Invalidate_iterator()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_Invalidate_iterator ( const const_iterator &  __it)
inlineprivate

Definition at line 124 of file _hashtable.h.

125 { _STLP_PRIV __invalidate_iterator(&_M_iter_list, __it); }
__it
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::erase().

◆ _Invalidate_iterators()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_Invalidate_iterators ( const const_iterator &  __first,
const const_iterator &  __last 
)
inlineprivate

Definition at line 126 of file _hashtable.h.

127 { _STLP_PRIV __invalidate_range(&_M_iter_list, __first, __last); }
__last
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::clear(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::erase(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::operator=().

◆ _M_before_begin()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
__iterator__ hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_before_begin ( size_type &  __n) const
private

Definition at line 148 of file _hashtable.c.

148 {
149 return _S_before_begin(_M_elems, _M_buckets, __n);
150}
hashtable::_S_before_begin
static iterator _S_before_begin(const _ElemsCont &__elems, const _BucketVector &__buckets, size_type &__n)
Definition: _hashtable.c:156

◆ _M_bkt_num() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_bkt_num ( const value_type &  __obj) const
inlineprivate

Definition at line 605 of file _hashtable.h.

606 { return _M_bkt_num_key(_M_get_key(__obj)); }
hashtable::_M_get_key
static const key_type & _M_get_key(const value_type &__val)
Definition: _hashtable.h:282
hashtable::_M_bkt_num_key
_STLP_TEMPLATE_FOR_CONT_EXT size_type _M_bkt_num_key(const _KT &__key) const
Definition: _hashtable.h:602

◆ _M_bkt_num() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_bkt_num ( const value_type &  __obj,
size_t  __n 
) const
inlineprivate

Definition at line 612 of file _hashtable.h.

613 { return _M_bkt_num_key(_M_get_key(__obj), __n); }

◆ _M_bkt_num_key() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_bkt_num_key ( const _KT &  __key) const
inlineprivate

Definition at line 602 of file _hashtable.h.

603 { return _M_bkt_num_key(__key, bucket_count()); }
hashtable::bucket_count
size_type bucket_count() const
Definition: _hashtable.h:391

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_bkt_num(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_bkt_num_key(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_find(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::bucket(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::count(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::equal_range().

◆ _M_bkt_num_key() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_bkt_num_key ( const _KT &  __key,
size_type  __n 
) const
inlineprivate

Definition at line 609 of file _hashtable.h.

610 { return _M_hash(__key) % __n; }

◆ _M_copy_from()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_copy_from ( const _Self &  __ht)
private

Definition at line 510 of file _hashtable.c.

510 {
511 _M_elems.clear();
512 _M_elems.insert(_M_elems.end(), __ht._M_elems.begin(), __ht._M_elems.end());
513 _M_buckets.resize(__ht._M_buckets.size());
514 _ElemsConstIte __src(__ht._M_elems.begin()), __src_end(__ht._M_elems.end());
515 _ElemsIte __dst(_M_elems.begin());
516 typename _BucketVector::const_iterator __src_b(__ht._M_buckets.begin()),
517 __src_end_b(__ht._M_buckets.end());
518 typename _BucketVector::iterator __dst_b(_M_buckets.begin()), __dst_end_b(_M_buckets.end());
519 for (; __src != __src_end; ++__src, ++__dst) {
520 for (; __src_b != __src_end_b; ++__src_b, ++__dst_b) {
521 if (*__src_b == __src._M_node) {
522 *__dst_b = __dst._M_node;
523 }
524 else
525 break;
526 }
527 }
528 fill(__dst_b, __dst_end_b, __STATIC_CAST(_BucketType*, 0));
529 _M_num_elements = __ht._M_num_elements;
530 _M_max_load_factor = __ht._M_max_load_factor;
531}
fill
_STLP_MOVE_TO_STD_NAMESPACE void fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__val)
Definition: _algobase.h:449
hashtable::_ElemsIte
_ElemsCont::iterator _ElemsIte
Definition: _hashtable.h:256
hashtable::_ElemsConstIte
_ElemsCont::const_iterator _ElemsConstIte
Definition: _hashtable.h:257
slist::end
iterator end()
Definition: _slist.h:420
slist::clear
void clear()
Definition: _slist.h:691
slist::insert
iterator insert(iterator __pos, const value_type &__x=_Tp())
Definition: _slist.h:635
slist::begin
iterator begin()
Definition: _slist.h:416
__STATIC_CAST
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
vector::end
iterator end()
Definition: _vector.h:184
vector::resize
void resize(size_type __new_size, const _Tp &__x=_STLP_DEFAULT_CONSTRUCTED(_Tp))
Definition: _vector.h:639
vector::begin
iterator begin()
Definition: _vector.h:182

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hashtable(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::operator=().

◆ _M_enlarge()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_enlarge ( size_type  __n)
private

Definition at line 382 of file _hashtable.c.

382 {
383 size_type __num_buckets = bucket_count();
384 size_type __num_buckets_hint = (size_type)((float)__to_size / max_load_factor());
385 if (__num_buckets_hint <= __num_buckets) {
386 return;
387 }
388 __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint);
389
390 _M_rehash(__num_buckets);
391}
_Stl_prime::_S_next_size
static size_t _STLP_CALL _S_next_size(size_t)
hashtable::_M_rehash
void _M_rehash(size_type __num_buckets)
Definition: _hashtable.c:454
hashtable::max_load_factor
float max_load_factor() const
Definition: _hashtable.h:401

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique().

◆ _M_find()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT _ElemsIte hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_find ( const _KT &  __key) const
inlineprivate

Definition at line 498 of file _hashtable.h.

498 {
499 size_type __n = _M_bkt_num_key(__key);
500 _ElemsIte __first(_M_buckets[__n]);
501 _ElemsIte __last(_M_buckets[__n + 1]);
502 for ( ; (__first != __last) && !_M_equals(_M_get_key(*__first), __key); ++__first);
503 if (__first != __last)
504 return __first;
505 else
506 return __CONST_CAST(_ElemsCont&, _M_elems).end();
507 }
hashtable::_ElemsCont
slist< value_type, _All > _ElemsCont
Definition: _hashtable.h:254
__CONST_CAST
#define __CONST_CAST(__x, __y)
Definition: features.h:584

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::find().

◆ _M_get_key()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
static const key_type & hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_get_key ( const value_type &  __val)
inlinestaticprivate

Definition at line 282 of file _hashtable.h.

282 {
283 _ExK k;
284 return k(__val);
285 }
__val
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
k
int k
Definition: mpi.c:3369

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_bkt_num(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_find(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::count(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::equal_range().

◆ _M_initialize_buckets()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_initialize_buckets ( size_type  __n)
inlineprivate

Definition at line 595 of file _hashtable.h.

595 {
596 const size_type __n_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__n) + 1;
597 _M_buckets.reserve(__n_buckets);
598 _M_buckets.assign(__n_buckets, __STATIC_CAST(_BucketType*, 0));
599 }
vector::reserve
void reserve(size_type __n)
Definition: _vector.c:62
vector::assign
void assign(size_type __n, const _Tp &__val)
Definition: _vector.h:318

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hashtable().

◆ _M_insert() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
__reference__ hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_insert ( const value_type &  __obj)

Definition at line 254 of file _hashtable.c.

254 {
255 _M_enlarge(_M_num_elements + 1);
256 return *insert_unique_noresize(__obj).first;
257}
hashtable::_M_enlarge
void _M_enlarge(size_type __n)
Definition: _hashtable.c:382
hashtable::insert_unique_noresize
pair< iterator, bool > insert_unique_noresize(const value_type &__obj)
Definition: _hashtable.c:199

Referenced by hash_map< _Key, _Tp,,, >::operator[](), and unordered_map< _Key, _Tp,,, >::operator[]().

◆ _M_insert() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
reference hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_insert ( const value_type &  __obj)
inline

Definition at line 313 of file _hashtable.h.

313{ return _M_non_dbg_impl._M_insert(__obj); }

◆ _M_insert_noresize()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
__iterator__ hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_insert_noresize ( size_type  __n,
const value_type &  __obj 
)
protected

Definition at line 183 of file _hashtable.c.

183 {
184 //We always insert this element as 1st in the bucket to not break
185 //the elements order as equal elements must be kept next to each other.
186 size_type __prev = __n;
187 _ElemsIte __pos = _M_before_begin(__prev)._M_ite;
188
189 fill(_M_buckets.begin() + __prev, _M_buckets.begin() + __n + 1,
190 _M_elems.insert_after(__pos, __obj)._M_node);
191 ++_M_num_elements;
192 return iterator(_ElemsIte(_M_buckets[__n]));
193}
hashtable::iterator
_STLP_PRIV _Ht_iterator< _ElemsIte, _NonConstTraits > iterator
Definition: _hashtable.h:287
hashtable::_M_before_begin
iterator _M_before_begin(size_type &__n) const
Definition: _hashtable.c:148
slist::insert_after
iterator insert_after(iterator __pos, const value_type &__x=_Tp())
Definition: _slist.h:601

◆ _M_reduce()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_reduce
private

Definition at line 396 of file _hashtable.c.

396 {
397 size_type __num_buckets = bucket_count();
398 // We only try to reduce the hashtable if the theorical load factor
399 // is lower than a fraction of the max load factor:
400 // 4 factor is coming from the fact that prime number list is almost a
401 // geometrical suite with reason 2, as we try to jump 2 levels is means
402 // a 4 factor.
403 if ((float)size() / (float)__num_buckets > max_load_factor() / 4.0f)
404 return;
405
406 const size_type *__first;
407 const size_type *__prev;
408 _STLP_PRIV _Stl_prime_type::_S_prev_sizes(__num_buckets, __first, __prev);
409
410 /* We are only going to reduce number of buckets if moving to yet the previous number
411 * of buckets in the prime numbers would respect the load rule. Otherwise algorithm
412 * successively removing and adding an element would each time perform an expensive
413 * rehash operation. */
414 const size_type *__prev_prev = __prev;
415 if (__prev_prev != __first) {
416 --__prev_prev;
417 if ((float)size() / (float)*__prev_prev > max_load_factor())
418 return;
419 }
420 else {
421 if (*__prev >= __num_buckets)
422 return;
423 }
424
425 // Can we reduce further:
426 while (__prev_prev != __first) {
427 --__prev_prev;
428 if ((float)size() / (float)*__prev_prev > max_load_factor())
429 // We cannot reduce further.
430 break;
431 --__prev;
432 }
433
434 _M_rehash(*__prev);
435}
_Stl_prime::_S_prev_sizes
static void _STLP_CALL _S_prev_sizes(size_t __hint, const size_t *&__begin, const size_t *&__end)
hashtable::size
size_type size() const
Definition: _hashtable.h:363

◆ _M_rehash()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_rehash ( size_type  __num_buckets)
private

Definition at line 454 of file _hashtable.c.

454 {
455#if defined (_STLP_DEBUG)
456 _M_check();
457#endif
458 _ElemsCont __tmp_elems(_M_elems.get_allocator());
459 _BucketVector __tmp(__num_buckets + 1, __STATIC_CAST(_BucketType*, 0), _M_buckets.get_allocator());
460 _ElemsIte __cur, __last(_M_elems.end());
461 while (!_M_elems.empty()) {
462 __cur = _M_elems.begin();
463 size_type __new_bucket = _M_bkt_num(*__cur, __num_buckets);
464 _ElemsIte __ite(__cur), __before_ite(__cur);
465 for (++__ite;
466 __ite != __last && _M_equals(_M_get_key(*__cur), _M_get_key(*__ite));
467 ++__ite, ++__before_ite);
468 size_type __prev_bucket = __new_bucket;
469 _ElemsIte __prev = _S_before_begin(__tmp_elems, __tmp, __prev_bucket)._M_ite;
470 __tmp_elems.splice_after(__prev, _M_elems, _M_elems.before_begin(), __before_ite);
471 fill(__tmp.begin() + __prev_bucket, __tmp.begin() + __new_bucket + 1, __cur._M_node);
472 }
473 _M_elems.swap(__tmp_elems);
474 _M_buckets.swap(__tmp);
475}
hashtable::_M_bkt_num
size_type _M_bkt_num(const value_type &__obj) const
Definition: _hashtable.h:605
hashtable::_BucketVector
vector< _BucketType *, _BucketAllocType > _BucketVector
Definition: _hashtable.h:271
slist::swap
void swap(_Self &__x)
Definition: _slist.h:430
slist::before_begin
iterator before_begin()
Definition: _slist.h:412
slist::get_allocator
allocator_type get_allocator() const
Definition: _slist.h:277
slist::empty
bool empty() const
Definition: _slist.h:428
vector::swap
void swap(_Self &__x)
Definition: _vector.h:404
vector::get_allocator
allocator_type get_allocator() const
Definition: _vector.h:135

◆ _M_resize()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_resize
private

Definition at line 440 of file _hashtable.c.

440 {
441 if (load_factor() > max_load_factor()) {
442 // We have to enlarge
443 _M_enlarge(size());
444 }
445 else {
446 // We can try to reduce size:
447 _M_reduce();
448 }
449}
hashtable::_M_reduce
void _M_reduce()
Definition: _hashtable.c:396
hashtable::load_factor
float load_factor() const
Definition: _hashtable.h:400

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::max_load_factor().

◆ _S_before_begin()

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
__iterator__ hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_S_before_begin ( const _ElemsCont &  __elems,
const _BucketVector &  __buckets,
size_type &  __n 
)
staticprivate

Definition at line 156 of file _hashtable.c.

157 {
158 _ElemsCont &__mutable_elems = __CONST_CAST(_ElemsCont&, __elems);
159 typename _BucketVector::const_iterator __bpos(__buckets.begin() + __n);
160
161 _ElemsIte __pos(*__bpos);
162 if (__pos == __mutable_elems.begin()) {
163 __n = 0;
164 return __mutable_elems.before_begin();
165 }
166
167 typename _BucketVector::const_iterator __bcur(__bpos);
168 _BucketType *__pos_node = __pos._M_node;
169 for (--__bcur; __pos_node == *__bcur; --__bcur);
170
171 __n = __bcur - __buckets.begin() + 1;
172 _ElemsIte __cur(*__bcur);
173 _ElemsIte __prev = __cur++;
174 for (; __cur != __pos; ++__prev, ++__cur);
175 return __prev;
176}

◆ begin() [1/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::begin ( )
inline

Definition at line 376 of file _hashtable.h.

376{ return _M_elems.begin(); }

Referenced by hash_map< _Key, _Tp,,, >::begin(), hash_multimap< _Key, _Tp,,, >::begin(), hash_set< _Value,,, >::begin(), hash_multiset< _Value,,, >::begin(), unordered_map< _Key, _Tp,,, >::begin(), unordered_multimap< _Key, _Tp,,, >::begin(), unordered_set< _Value,,, >::begin(), unordered_multiset< _Value,,, >::begin(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::clear(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::erase(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::operator=().

◆ begin() [2/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::begin ( )
inline

Definition at line 183 of file _hashtable.h.

183{ return iterator(&_M_iter_list, _M_non_dbg_impl.begin()); }

◆ begin() [3/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
const_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::begin ( ) const
inline

Definition at line 381 of file _hashtable.h.

381{ return __CONST_CAST(_ElemsCont&, _M_elems).begin(); }

◆ begin() [4/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
const_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::begin ( ) const
inline

Definition at line 196 of file _hashtable.h.

196{ return const_iterator(&_M_iter_list, _M_non_dbg_impl.begin()); }
hashtable::const_iterator
_STLP_PRIV _Ht_iterator< _ElemsIte, _ConstTraits > const_iterator
Definition: _hashtable.h:288

◆ begin() [5/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
local_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::begin ( size_type  __n)
inline

Definition at line 378 of file _hashtable.h.

378{ return _ElemsIte(_M_buckets[__n]); }

◆ begin() [6/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
local_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::begin ( size_type  __n)
inline

Definition at line 185 of file _hashtable.h.

185 {
186 //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
187 _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
188 return local_iterator(&_M_iter_list, _M_non_dbg_impl.begin(__n));
189 }
_STLP_VERBOSE_ASSERT
#define _STLP_VERBOSE_ASSERT(expr, diagnostic)
Definition: _debug.h:439
hashtable::local_iterator
_STLP_PRIV _Ht_iterator< _ElemsIte, _NonConstLocalTraits > local_iterator
Definition: _hashtable.h:292

◆ begin() [7/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
const_local_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::begin ( size_type  __n) const
inline

Definition at line 383 of file _hashtable.h.

383{ return _ElemsIte(_M_buckets[__n]); }

◆ begin() [8/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
const_local_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::begin ( size_type  __n) const
inline

Definition at line 198 of file _hashtable.h.

198 {
199 //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
200 _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
201 return const_local_iterator(&_M_iter_list, _M_non_dbg_impl.begin(__n));
202 }
hashtable::const_local_iterator
_STLP_PRIV _Ht_iterator< _ElemsIte, _ConstLocalTraits > const_local_iterator
Definition: _hashtable.h:293

◆ bucket() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::bucket ( const _KT &  __k) const
inline

Definition at line 397 of file _hashtable.h.

397{ return _M_bkt_num_key(__k); }

Referenced by unordered_map< _Key, _Tp,,, >::bucket(), unordered_multimap< _Key, _Tp,,, >::bucket(), unordered_set< _Value,,, >::bucket(), and unordered_multiset< _Value,,, >::bucket().

◆ bucket() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::bucket ( const _KT &  __k) const
inline

Definition at line 322 of file _hashtable.h.

322{ return _M_non_dbg_impl.bucket(__k); }

◆ bucket_count() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::bucket_count ( ) const
inline

Definition at line 391 of file _hashtable.h.

391{ return _M_buckets.size() - 1; }
vector::size
size_type size() const
Definition: _vector.h:192

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_bkt_num_key(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::begin(), hash_map< _Key, _Tp,,, >::bucket_count(), hash_multimap< _Key, _Tp,,, >::bucket_count(), hash_set< _Value,,, >::bucket_count(), hash_multiset< _Value,,, >::bucket_count(), unordered_map< _Key, _Tp,,, >::bucket_count(), unordered_multimap< _Key, _Tp,,, >::bucket_count(), unordered_set< _Value,,, >::bucket_count(), unordered_multiset< _Value,,, >::bucket_count(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::elems_in_bucket(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::end(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::load_factor().

◆ bucket_count() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::bucket_count ( ) const
inline

Definition at line 315 of file _hashtable.h.

315{ return _M_non_dbg_impl.bucket_count(); }

◆ clear() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::clear

Definition at line 501 of file _hashtable.c.

501 {
502 _M_elems.clear();
503 _M_buckets.assign(_M_buckets.size(), __STATIC_CAST(_BucketType*, 0));
504 _M_num_elements = 0;
505}

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_copy_from(), hash_map< _Key, _Tp,,, >::clear(), hash_multimap< _Key, _Tp,,, >::clear(), hash_set< _Value,,, >::clear(), hash_multiset< _Value,,, >::clear(), unordered_map< _Key, _Tp,,, >::clear(), unordered_multimap< _Key, _Tp,,, >::clear(), unordered_set< _Value,,, >::clear(), unordered_multiset< _Value,,, >::clear(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::operator=(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::~hashtable().

◆ clear() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::clear ( )
inline

Definition at line 308 of file _hashtable.h.

308 {
309 _Invalidate_iterators(begin(), end());
310 _M_non_dbg_impl.clear();
311 }
hashtable::_Invalidate_iterators
void _Invalidate_iterators(const const_iterator &__first, const const_iterator &__last)
Definition: _hashtable.h:126
hashtable::end
iterator end()
Definition: _hashtable.h:377
hashtable::begin
iterator begin()
Definition: _hashtable.h:376

◆ count() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::count ( const _KT &  __key) const
inline

Definition at line 516 of file _hashtable.h.

516 {
517 const size_type __n = _M_bkt_num_key(__key);
518
519 _ElemsIte __cur(_M_buckets[__n]);
520 _ElemsIte __last(_M_buckets[__n + 1]);
521 for (; __cur != __last; ++__cur) {
522 if (_M_equals(_M_get_key(*__cur), __key)) {
523 size_type __result = 1;
524 for (++__cur;
525 __cur != __last && _M_equals(_M_get_key(*__cur), __key);
526 ++__result, ++__cur);
527 return __result;
528 }
529 }
530 return 0;
531 }

Referenced by hash_map< _Key, _Tp,,, >::count(), hash_multimap< _Key, _Tp,,, >::count(), hash_set< _Value,,, >::count(), hash_multiset< _Value,,, >::count(), unordered_map< _Key, _Tp,,, >::count(), unordered_multimap< _Key, _Tp,,, >::count(), unordered_set< _Value,,, >::count(), and unordered_multiset< _Value,,, >::count().

◆ count() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::count ( const _KT &  __key) const
inline

Definition at line 268 of file _hashtable.h.

268{ return _M_non_dbg_impl.count(__key); }

◆ elems_in_bucket() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::elems_in_bucket ( size_type  __bucket) const
inline

Definition at line 393 of file _hashtable.h.

394 { return _STLP_STD::distance(_ElemsIte(_M_buckets[__bucket]), _ElemsIte(_M_buckets[__bucket + 1])); }

Referenced by unordered_map< _Key, _Tp,,, >::bucket_size(), unordered_multimap< _Key, _Tp,,, >::bucket_size(), unordered_set< _Value,,, >::bucket_size(), unordered_multiset< _Value,,, >::bucket_size(), hash_map< _Key, _Tp,,, >::elems_in_bucket(), hash_multimap< _Key, _Tp,,, >::elems_in_bucket(), hash_set< _Value,,, >::elems_in_bucket(), and hash_multiset< _Value,,, >::elems_in_bucket().

◆ elems_in_bucket() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::elems_in_bucket ( size_type  __n) const
inline

Definition at line 317 of file _hashtable.h.

317 {
318 _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
319 return _M_non_dbg_impl.elems_in_bucket(__n);
320 }

◆ empty() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
bool hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::empty ( ) const
inline

Definition at line 365 of file _hashtable.h.

365{ return size() == 0; }

Referenced by hash_map< _Key, _Tp,,, >::empty(), hash_multimap< _Key, _Tp,,, >::empty(), hash_set< _Value,,, >::empty(), hash_multiset< _Value,,, >::empty(), unordered_map< _Key, _Tp,,, >::empty(), unordered_multimap< _Key, _Tp,,, >::empty(), unordered_set< _Value,,, >::empty(), and unordered_multiset< _Value,,, >::empty().

◆ empty() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
bool hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::empty ( ) const
inline

Definition at line 167 of file _hashtable.h.

167{ return _M_non_dbg_impl.empty(); }

◆ end() [1/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::end ( )
inline

Definition at line 377 of file _hashtable.h.

377{ return _M_elems.end(); }

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::clear(), hash_map< _Key, _Tp,,, >::end(), hash_multimap< _Key, _Tp,,, >::end(), hash_set< _Value,,, >::end(), hash_multiset< _Value,,, >::end(), unordered_map< _Key, _Tp,,, >::end(), unordered_multimap< _Key, _Tp,,, >::end(), unordered_set< _Value,,, >::end(), unordered_multiset< _Value,,, >::end(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::equal_range(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::erase(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::operator=(), hash_map< _Key, _Tp,,, >::operator[](), and unordered_map< _Key, _Tp,,, >::operator[]().

◆ end() [2/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::end ( )
inline

Definition at line 184 of file _hashtable.h.

184{ return iterator(&_M_iter_list, _M_non_dbg_impl.end()); }

◆ end() [3/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
const_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::end ( ) const
inline

Definition at line 382 of file _hashtable.h.

382{ return __CONST_CAST(_ElemsCont&, _M_elems).end(); }

◆ end() [4/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
const_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::end ( ) const
inline

Definition at line 197 of file _hashtable.h.

197{ return const_iterator(&_M_iter_list, _M_non_dbg_impl.end()); }

◆ end() [5/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
local_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::end ( size_type  __n)
inline

Definition at line 379 of file _hashtable.h.

379{ return _ElemsIte(_M_buckets[__n + 1]); }

◆ end() [6/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
local_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::end ( size_type  __n)
inline

Definition at line 190 of file _hashtable.h.

190 {
191 //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
192 _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
193 return local_iterator(&_M_iter_list, _M_non_dbg_impl.end(__n));
194 }

◆ end() [7/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
const_local_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::end ( size_type  __n) const
inline

Definition at line 384 of file _hashtable.h.

384{ return _ElemsIte(_M_buckets[__n + 1]); }

◆ end() [8/8]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
const_local_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::end ( size_type  __n) const
inline

Definition at line 203 of file _hashtable.h.

203 {
204 //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
205 _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
206 return const_local_iterator(&_M_iter_list, _M_non_dbg_impl.end(__n));
207 }

◆ equal_range() [1/4]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::equal_range ( const _KT &  __key)
inline

Definition at line 534 of file _hashtable.h.

534 {
535 typedef pair<iterator, iterator> _Pii;
536 const size_type __n = _M_bkt_num_key(__key);
537
538 for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
539 __first != __last; ++__first) {
540 if (_M_equals(_M_get_key(*__first), __key)) {
541 _ElemsIte __cur(__first);
542 for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
543 return _Pii(__first, __cur);
544 }
545 }
546 return _Pii(end(), end());
547 }
pair
Definition: _pair.h:47

Referenced by hash_map< _Key, _Tp,,, >::equal_range(), hash_multimap< _Key, _Tp,,, >::equal_range(), hash_set< _Value,,, >::equal_range(), hash_multiset< _Value,,, >::equal_range(), unordered_map< _Key, _Tp,,, >::equal_range(), unordered_multimap< _Key, _Tp,,, >::equal_range(), unordered_set< _Value,,, >::equal_range(), unordered_multiset< _Value,,, >::equal_range(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::erase().

◆ equal_range() [2/4]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::equal_range ( const _KT &  __key)
inline

Definition at line 271 of file _hashtable.h.

271 {
272 pair<_Base_iterator, _Base_iterator> __res = _M_non_dbg_impl.equal_range(__key);
273 return pair<iterator,iterator> (iterator(&_M_iter_list,__res.first),
274 iterator(&_M_iter_list,__res.second));
275 }
pair::second
_T2 second
Definition: _pair.h:52
pair::first
_T1 first
Definition: _pair.h:51

◆ equal_range() [3/4]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::equal_range ( const _KT &  __key) const
inline

Definition at line 550 of file _hashtable.h.

550 {
551 typedef pair<const_iterator, const_iterator> _Pii;
552 const size_type __n = _M_bkt_num_key(__key);
553
554 for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
555 __first != __last; ++__first) {
556 if (_M_equals(_M_get_key(*__first), __key)) {
557 _ElemsIte __cur(__first);
558 for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
559 return _Pii(__first, __cur);
560 }
561 }
562 return _Pii(end(), end());
563 }

◆ equal_range() [4/4]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::equal_range ( const _KT &  __key) const
inline

Definition at line 278 of file _hashtable.h.

278 {
279 pair <_Base_const_iterator, _Base_const_iterator> __res = _M_non_dbg_impl.equal_range(__key);
280 return pair<const_iterator,const_iterator> (const_iterator(&_M_iter_list,__res.first),
281 const_iterator(&_M_iter_list,__res.second));
282 }

◆ erase() [1/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::erase ( const const_iterator &  __it)
inline

Definition at line 292 of file _hashtable.h.

292 {
293 _STLP_DEBUG_CHECK(_STLP_PRIV _Dereferenceable(__it))
294 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __it))
295 _Invalidate_iterator(__it);
296 _M_non_dbg_impl.erase(__it._M_iterator);
297 }
_STLP_DEBUG_CHECK
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440
hashtable::_Invalidate_iterator
void _Invalidate_iterator(const const_iterator &__it)
Definition: _hashtable.h:124
_Dereferenceable
bool _Dereferenceable(const _Iterator &__it)
Definition: _iterator.h:93

◆ erase() [2/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
__size_type__ hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::erase ( const key_type &  __key)

Definition at line 263 of file _hashtable.c.

263 {
264 const size_type __n = _M_bkt_num_key(__key);
265
266 _ElemsIte __cur(_M_buckets[__n]);
267 _ElemsIte __last(_M_buckets[__n + 1]);
268 if (__cur == __last)
269 return 0;
270
271 size_type __erased = 0;
272 if (_M_equals(_M_get_key(*__cur), __key)) {
273 //We look for the pos before __cur:
274 size_type __prev_b = __n;
275 _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
276 do {
277 __cur = _M_elems.erase_after(__prev);
278 ++__erased;
279 } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
280 fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1, __cur._M_node);
281 }
282 else {
283 _ElemsIte __prev = __cur++;
284 for (; __cur != __last; ++__prev, ++__cur) {
285 if (_M_equals(_M_get_key(*__cur), __key)) {
286 do {
287 __cur = _M_elems.erase_after(__prev);
288 ++__erased;
289 } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
290 break;
291 }
292 }
293 }
294
295 _M_num_elements -= __erased;
296 _M_reduce();
297 return __erased;
298}
slist::erase_after
iterator erase_after(iterator __pos)
Definition: _slist.h:671

Referenced by hash_map< _Key, _Tp,,, >::erase(), hash_multimap< _Key, _Tp,,, >::erase(), hash_set< _Value,,, >::erase(), hash_multiset< _Value,,, >::erase(), unordered_map< _Key, _Tp,,, >::erase(), unordered_multimap< _Key, _Tp,,, >::erase(), unordered_set< _Value,,, >::erase(), and unordered_multiset< _Value,,, >::erase().

◆ erase() [3/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::erase ( const key_type &  __key)
inline

Definition at line 284 of file _hashtable.h.

284 {
285 pair<iterator, iterator> __p = equal_range(__key);
286 size_type __n = _STLP_STD::distance(__p.first, __p.second);
287 _Invalidate_iterators(__p.first, __p.second);
288 _M_non_dbg_impl.erase(__p.first._M_iterator, __p.second._M_iterator);
289 return __n;
290 }
hashtable::equal_range
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__key)
Definition: _hashtable.h:534

◆ erase() [4/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::erase ( const_iterator  __first,
const_iterator  __last 
)

Definition at line 334 of file _hashtable.c.

334 {
335 if (__first == __last)
336 return;
337 size_type __f_bucket = _M_bkt_num(*__first);
338 size_type __l_bucket = __last != end() ? _M_bkt_num(*__last) : (_M_buckets.size() - 1);
339
340 _ElemsIte __cur(_M_buckets[__f_bucket]);
341 _ElemsIte __prev;
342 if (__cur == __first._M_ite) {
343 __prev = _M_before_begin(__f_bucket)._M_ite;
344 }
345 else {
346 _ElemsIte __last(_M_buckets[++__f_bucket]);
347 __prev = __cur++;
348 for (; (__cur != __last) && (__cur != __first._M_ite); ++__prev, ++__cur);
349 }
350 size_type __erased = 0;
351 //We do not use the slist::erase_after method taking a range to count the
352 //number of erased elements:
353 while (__cur != __last._M_ite) {
354 __cur = _M_elems.erase_after(__prev);
355 ++__erased;
356 }
357 fill(_M_buckets.begin() + __f_bucket, _M_buckets.begin() + __l_bucket + 1, __cur._M_node);
358 _M_num_elements -= __erased;
359 _M_reduce();
360}
size
GLsizeiptr size
Definition: glext.h:5919

◆ erase() [5/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::erase ( const_iterator  __first,
const_iterator  __last 
)
inline

Definition at line 298 of file _hashtable.h.

298 {
299 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last,
300 const_iterator(begin()), const_iterator(end())))
301 _Invalidate_iterators(__first, __last);
302 _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator);
303 }
hashtable::erase
size_type erase(const key_type &__key)
Definition: _hashtable.c:263

◆ erase() [6/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::erase ( const_iterator  __it)

Definition at line 303 of file _hashtable.c.

303 {
304 const size_type __n = _M_bkt_num(*__it);
305 _ElemsIte __cur(_M_buckets[__n]);
306
307 size_type __erased = 0;
308 if (__cur == __it._M_ite) {
309 size_type __prev_b = __n;
310 _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
311 fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1,
312 _M_elems.erase_after(__prev)._M_node);
313 ++__erased;
314 }
315 else {
316 _ElemsIte __prev = __cur++;
317 _ElemsIte __last(_M_buckets[__n + 1]);
318 for (; __cur != __last; ++__prev, ++__cur) {
319 if (__cur == __it._M_ite) {
320 _M_elems.erase_after(__prev);
321 ++__erased;
322 break;
323 }
324 }
325 }
326
327 _M_num_elements -= __erased;
328 _M_reduce();
329}

◆ find() [1/4]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::find ( const _KT &  __key)
inline

Definition at line 511 of file _hashtable.h.

511{ return _M_find(__key); }
hashtable::_M_find
_STLP_TEMPLATE_FOR_CONT_EXT _ElemsIte _M_find(const _KT &__key) const
Definition: _hashtable.h:498

Referenced by hash_map< _Key, _Tp,,, >::find(), hash_multimap< _Key, _Tp,,, >::find(), hash_set< _Value,,, >::find(), hash_multiset< _Value,,, >::find(), unordered_map< _Key, _Tp,,, >::find(), unordered_multimap< _Key, _Tp,,, >::find(), unordered_set< _Value,,, >::find(), unordered_multiset< _Value,,, >::find(), hash_map< _Key, _Tp,,, >::operator[](), and unordered_map< _Key, _Tp,,, >::operator[]().

◆ find() [2/4]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::find ( const _KT &  __key)
inline

Definition at line 261 of file _hashtable.h.

262 { return iterator(&_M_iter_list, _M_non_dbg_impl.find(__key)); }

◆ find() [3/4]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::find ( const _KT &  __key) const
inline

Definition at line 513 of file _hashtable.h.

513{ return _M_find(__key); }

◆ find() [4/4]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::find ( const _KT &  __key) const
inline

Definition at line 264 of file _hashtable.h.

265 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.find(__key)); }

◆ get_allocator() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
allocator_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::get_allocator ( ) const
inline

Definition at line 300 of file _hashtable.h.

300{ return _M_elems.get_allocator(); }

Referenced by hash_map< _Key, _Tp,,, >::get_allocator(), hash_multimap< _Key, _Tp,,, >::get_allocator(), hash_set< _Value,,, >::get_allocator(), hash_multiset< _Value,,, >::get_allocator(), unordered_map< _Key, _Tp,,, >::get_allocator(), unordered_multimap< _Key, _Tp,,, >::get_allocator(), unordered_set< _Value,,, >::get_allocator(), and unordered_multiset< _Value,,, >::get_allocator().

◆ get_allocator() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
allocator_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::get_allocator ( ) const
inline

Definition at line 132 of file _hashtable.h.

132{ return _M_non_dbg_impl.get_allocator(); }

◆ hash_funct() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
hasher hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hash_funct ( ) const
inline

Definition at line 246 of file _hashtable.h.

246{ return _M_hash; }

Referenced by hash_map< _Key, _Tp,,, >::hash_funct(), hash_multimap< _Key, _Tp,,, >::hash_funct(), hash_set< _Value,,, >::hash_funct(), hash_multiset< _Value,,, >::hash_funct(), unordered_map< _Key, _Tp,,, >::hash_function(), unordered_multimap< _Key, _Tp,,, >::hash_function(), unordered_set< _Value,,, >::hash_function(), and unordered_multiset< _Value,,, >::hash_function().

◆ hash_funct() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
hasher hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hash_funct ( ) const
inline

Definition at line 120 of file _hashtable.h.

120{ return _M_non_dbg_impl.hash_funct(); }

◆ insert_equal() [1/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal ( const value_type &  __obj)
inline

Definition at line 412 of file _hashtable.h.

412 {
413 _M_enlarge(_M_num_elements + 1);
414 return insert_equal_noresize(__obj);
415 }
hashtable::insert_equal_noresize
iterator insert_equal_noresize(const value_type &__obj)
Definition: _hashtable.c:230

Referenced by hash_multimap< _Key, _Tp,,, >::hash_multimap(), hash_multiset< _Value,,, >::hash_multiset(), hash_multimap< _Key, _Tp,,, >::insert(), hash_multiset< _Value,,, >::insert(), unordered_multimap< _Key, _Tp,,, >::insert(), unordered_multiset< _Value,,, >::insert(), unordered_multimap< _Key, _Tp,,, >::unordered_multimap(), and unordered_multiset< _Value,,, >::unordered_multiset().

◆ insert_equal() [2/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal ( const value_type &  __obj)
inline

Definition at line 214 of file _hashtable.h.

215 { return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__obj)); }

◆ insert_equal() [3/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal ( const value_type *  __f,
const value_type *  __l 
)
inline

Definition at line 472 of file _hashtable.h.

472 {
473 size_type __n = __l - __f;
474 _M_enlarge(_M_num_elements + __n);
475 for ( ; __n > 0; --__n, ++__f)
476 insert_equal_noresize(*__f);
477 }

◆ insert_equal() [4/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal ( const value_type *  __f,
const value_type *  __l 
)
inline

Definition at line 244 of file _hashtable.h.

244 {
245 _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__f, __l))
246 _M_non_dbg_impl.insert_equal(__f, __l);
247 }

◆ insert_equal() [5/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal ( const_iterator  __f,
const_iterator  __l 
)
inline

Definition at line 486 of file _hashtable.h.

486 {
487 size_type __n = _STLP_STD::distance(__f, __l);
488 _M_enlarge(_M_num_elements + __n);
489 for ( ; __n > 0; --__n, ++__f)
490 insert_equal_noresize(*__f);
491 }

◆ insert_equal() [6/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal ( const_iterator  __f,
const_iterator  __l 
)
inline

Definition at line 254 of file _hashtable.h.

254 {
255 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l))
256 _M_non_dbg_impl.insert_equal(__f._M_iterator, __l._M_iterator);
257 }

◆ insert_equal_noresize() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
__iterator__ hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal_noresize ( const value_type &  __obj)

Definition at line 230 of file _hashtable.c.

230 {
231 const size_type __n = _M_bkt_num(__obj);
232 {
233 _ElemsIte __cur(_M_buckets[__n]);
234 _ElemsIte __last(_M_buckets[__n + 1]);
235
236 for (; __cur != __last; ++__cur) {
237 if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
238 //We check that equivalent keys have equals hash code as otherwise, on resize,
239 //equivalent value might not be in the same bucket
240 _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
241 ++_M_num_elements;
242 return _M_elems.insert_after(__cur, __obj);
243 }
244 }
245 }
246
247 return _M_insert_noresize(__n, __obj);
248}
_STLP_ASSERT
#define _STLP_ASSERT(expr)
Definition: _debug.h:165
hashtable::_M_insert_noresize
iterator _M_insert_noresize(size_type __n, const value_type &__obj)
Definition: _hashtable.c:183

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal(), hash_multimap< _Key, _Tp,,, >::insert_noresize(), and hash_multiset< _Value,,, >::insert_noresize().

◆ insert_equal_noresize() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
iterator hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal_noresize ( const value_type &  __obj)
inline

Definition at line 222 of file _hashtable.h.

223 { return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal_noresize(__obj)); }

◆ insert_unique() [1/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
pair< iterator, bool > hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique ( const value_type &  __obj)
inline

Definition at line 407 of file _hashtable.h.

407 {
408 _M_enlarge(_M_num_elements + 1);
409 return insert_unique_noresize(__obj);
410 }

Referenced by hash_map< _Key, _Tp,,, >::hash_map(), hash_set< _Value,,, >::hash_set(), hash_map< _Key, _Tp,,, >::insert(), hash_set< _Value,,, >::insert(), unordered_map< _Key, _Tp,,, >::insert(), unordered_set< _Value,,, >::insert(), unordered_map< _Key, _Tp,,, >::unordered_map(), and unordered_set< _Value,,, >::unordered_set().

◆ insert_unique() [2/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
pair< iterator, bool > hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique ( const value_type &  __obj)
inline

Definition at line 209 of file _hashtable.h.

209 {
210 pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique(__obj);
211 return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second);
212 }

◆ insert_unique() [3/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique ( const value_type *  __f,
const value_type *  __l 
)
inline

Definition at line 465 of file _hashtable.h.

465 {
466 size_type __n = __l - __f;
467 _M_enlarge(_M_num_elements + __n);
468 for ( ; __n > 0; --__n, ++__f)
469 insert_unique_noresize(*__f);
470 }

◆ insert_unique() [4/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique ( const value_type *  __f,
const value_type *  __l 
)
inline

Definition at line 239 of file _hashtable.h.

239 {
240 _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__f, __l))
241 _M_non_dbg_impl.insert_unique(__f, __l);
242 }

◆ insert_unique() [5/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique ( const_iterator  __f,
const_iterator  __l 
)
inline

Definition at line 479 of file _hashtable.h.

479 {
480 size_type __n = _STLP_STD::distance(__f, __l);
481 _M_enlarge(_M_num_elements + __n);
482 for ( ; __n > 0; --__n, ++__f)
483 insert_unique_noresize(*__f);
484 }

◆ insert_unique() [6/6]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique ( const_iterator  __f,
const_iterator  __l 
)
inline

Definition at line 249 of file _hashtable.h.

249 {
250 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l))
251 _M_non_dbg_impl.insert_unique(__f._M_iterator, __l._M_iterator);
252 }

◆ insert_unique_noresize() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
pair< __iterator__, bool > hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique_noresize ( const value_type &  __obj)

Definition at line 199 of file _hashtable.c.

199 {
200 const size_type __n = _M_bkt_num(__obj);
201 _ElemsIte __cur(_M_buckets[__n]);
202 _ElemsIte __last(_M_buckets[__n + 1]);
203
204 if (__cur != __last) {
205 for (; __cur != __last; ++__cur) {
206 if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
207 //We check that equivalent keys have equals hash code as otherwise, on resize,
208 //equivalent value might not be in the same bucket
209 _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
210 return pair<iterator, bool>(iterator(__cur), false);
211 }
212 }
213 /* Here we do not rely on the _M_insert_noresize method as we know
214 * that we cannot break element orders, elements are unique, and
215 * insertion after the first bucket element is faster than what is
216 * done in _M_insert_noresize.
217 */
218 __cur = _M_elems.insert_after(_ElemsIte(_M_buckets[__n]), __obj);
219 ++_M_num_elements;
220 return pair<iterator, bool>(iterator(__cur), true);
221 }
222
223 return pair<iterator, bool>(_M_insert_noresize(__n, __obj), true);
224}

Referenced by hash_map< _Key, _Tp,,, >::insert_noresize(), hash_set< _Value,,, >::insert_noresize(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique().

◆ insert_unique_noresize() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
pair< iterator, bool > hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique_noresize ( const value_type &  __obj)
inline

Definition at line 217 of file _hashtable.h.

217 {
218 pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique_noresize(__obj);
219 return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second);
220 }

◆ key_eq() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
key_equal hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::key_eq ( ) const
inline

Definition at line 247 of file _hashtable.h.

247{ return _M_equals; }

Referenced by hash_map< _Key, _Tp,,, >::key_eq(), hash_multimap< _Key, _Tp,,, >::key_eq(), hash_set< _Value,,, >::key_eq(), hash_multiset< _Value,,, >::key_eq(), unordered_map< _Key, _Tp,,, >::key_eq(), unordered_multimap< _Key, _Tp,,, >::key_eq(), unordered_set< _Value,,, >::key_eq(), and unordered_multiset< _Value,,, >::key_eq().

◆ key_eq() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
key_equal hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::key_eq ( ) const
inline

Definition at line 121 of file _hashtable.h.

121{ return _M_non_dbg_impl.key_eq().non_dbg_key_eq(); }

◆ load_factor() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
float hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::load_factor ( ) const
inline

Definition at line 400 of file _hashtable.h.

400{ return (float)size() / (float)bucket_count(); }
float
static float(__cdecl *square_half_float)(float x

Referenced by unordered_map< _Key, _Tp,,, >::load_factor(), unordered_multimap< _Key, _Tp,,, >::load_factor(), unordered_set< _Value,,, >::load_factor(), and unordered_multiset< _Value,,, >::load_factor().

◆ load_factor() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
float hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::load_factor ( ) const
inline

Definition at line 324 of file _hashtable.h.

324{ return _M_non_dbg_impl.load_factor(); }

◆ max_bucket_count() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::max_bucket_count ( ) const
inline

Definition at line 392 of file _hashtable.h.

392{ return _STLP_PRIV _Stl_prime_type::_S_max_nb_buckets(); }
_Stl_prime::_S_max_nb_buckets
static size_t _STLP_CALL _S_max_nb_buckets()

Referenced by hash_map< _Key, _Tp,,, >::max_bucket_count(), hash_multimap< _Key, _Tp,,, >::max_bucket_count(), hash_set< _Value,,, >::max_bucket_count(), hash_multiset< _Value,,, >::max_bucket_count(), unordered_map< _Key, _Tp,,, >::max_bucket_count(), unordered_multimap< _Key, _Tp,,, >::max_bucket_count(), unordered_set< _Value,,, >::max_bucket_count(), and unordered_multiset< _Value,,, >::max_bucket_count().

◆ max_bucket_count() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::max_bucket_count ( ) const
inline

Definition at line 316 of file _hashtable.h.

316{ return _M_non_dbg_impl.max_bucket_count(); }

◆ max_load_factor() [1/4]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
float hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::max_load_factor ( ) const
inline

Definition at line 401 of file _hashtable.h.

401{ return _M_max_load_factor; }

Referenced by unordered_map< _Key, _Tp,,, >::max_load_factor(), unordered_multimap< _Key, _Tp,,, >::max_load_factor(), unordered_set< _Value,,, >::max_load_factor(), and unordered_multiset< _Value,,, >::max_load_factor().

◆ max_load_factor() [2/4]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
float hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::max_load_factor ( ) const
inline

Definition at line 325 of file _hashtable.h.

325{ return _M_non_dbg_impl.max_load_factor(); }

◆ max_load_factor() [3/4]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::max_load_factor ( float  __z)
inline

Definition at line 402 of file _hashtable.h.

402 {
403 _M_max_load_factor = __z;
404 _M_resize();
405 }
hashtable::_M_resize
void _M_resize()
Definition: _hashtable.c:440

◆ max_load_factor() [4/4]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::max_load_factor ( float  __z)
inline

Definition at line 326 of file _hashtable.h.

326 {
327 _STLP_VERBOSE_ASSERT((__z > 0.0f), _StlMsg_INVALID_ARGUMENT)
328 _M_non_dbg_impl.max_load_factor(__z);
329 }

◆ max_size() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::max_size ( ) const
inline

Definition at line 364 of file _hashtable.h.

364{ return size_type(-1); }

Referenced by hash_map< _Key, _Tp,,, >::max_size(), hash_multimap< _Key, _Tp,,, >::max_size(), hash_set< _Value,,, >::max_size(), hash_multiset< _Value,,, >::max_size(), unordered_map< _Key, _Tp,,, >::max_size(), unordered_multimap< _Key, _Tp,,, >::max_size(), unordered_set< _Value,,, >::max_size(), and unordered_multiset< _Value,,, >::max_size().

◆ max_size() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::max_size ( ) const
inline

Definition at line 166 of file _hashtable.h.

166{ return _M_non_dbg_impl.max_size(); }

◆ operator=() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_Self & hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::operator= ( const _Self &  __ht)
inline

Definition at line 351 of file _hashtable.h.

351 {
352 if (&__ht != this) {
353 clear();
354 _M_hash = __ht._M_hash;
355 _M_equals = __ht._M_equals;
356 _M_copy_from(__ht);
357 }
358 return *this;
359 }

◆ operator=() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_Self & hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::operator= ( const _Self &  __ht)
inline

Definition at line 169 of file _hashtable.h.

169 {
170 if (this != &__ht) {
171 //Should not invalidate end iterator
172 _Invalidate_iterators(begin(), end());
173 _M_non_dbg_impl = __ht._M_non_dbg_impl;
174 }
175 return *this;
176 }

◆ rehash() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::rehash ( size_type  __num_buckets_hint)

Definition at line 365 of file _hashtable.c.

365 {
366 if (bucket_count() >= __num_buckets_hint) {
367 // We are trying to reduce number of buckets, we have to validate it:
368 size_type __limit_num_buckets = (size_type)((float)size() / max_load_factor());
369 if (__num_buckets_hint < __limit_num_buckets) {
370 // Targetted number of buckets __num_buckets_hint would break
371 // load_factor() <= max_load_factor() rule.
372 return;
373 }
374 }
375
376 _M_rehash(__num_buckets_hint);
377}

Referenced by unordered_map< _Key, _Tp,,, >::rehash(), unordered_multimap< _Key, _Tp,,, >::rehash(), unordered_set< _Value,,, >::rehash(), unordered_multiset< _Value,,, >::rehash(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::resize().

◆ rehash() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::rehash ( size_type  __num_buckets_hint)
inline

Definition at line 305 of file _hashtable.h.

305{ _M_non_dbg_impl.rehash(__num_buckets_hint); }

◆ resize() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::resize ( size_type  __num_buckets_hint)
inline

Definition at line 580 of file _hashtable.h.

581 { rehash(__num_buckets_hint); }
hashtable::rehash
void rehash(size_type __num_buckets_hint)
Definition: _hashtable.c:365

Referenced by hash_map< _Key, _Tp,,, >::resize(), hash_multimap< _Key, _Tp,,, >::resize(), hash_set< _Value,,, >::resize(), and hash_multiset< _Value,,, >::resize().

◆ resize() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::resize ( size_type  __num_elements_hint)
inline

Definition at line 306 of file _hashtable.h.

306{ _M_non_dbg_impl.resize(__num_elements_hint); }

◆ size() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::size ( ) const
inline

Definition at line 363 of file _hashtable.h.

363{ return _M_num_elements; }

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::empty(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::load_factor(), hash_map< _Key, _Tp,,, >::size(), hash_multimap< _Key, _Tp,,, >::size(), hash_set< _Value,,, >::size(), hash_multiset< _Value,,, >::size(), unordered_map< _Key, _Tp,,, >::size(), unordered_multimap< _Key, _Tp,,, >::size(), unordered_set< _Value,,, >::size(), and unordered_multiset< _Value,,, >::size().

◆ size() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::size ( ) const
inline

Definition at line 165 of file _hashtable.h.

165{ return _M_non_dbg_impl.size(); }

◆ swap() [1/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::swap ( _Self &  __ht)
inline

Definition at line 367 of file _hashtable.h.

367 {
368 _STLP_STD::swap(_M_hash, __ht._M_hash);
369 _STLP_STD::swap(_M_equals, __ht._M_equals);
370 _M_elems.swap(__ht._M_elems);
371 _M_buckets.swap(__ht._M_buckets);
372 _STLP_STD::swap(_M_num_elements, __ht._M_num_elements);
373 _STLP_STD::swap(_M_max_load_factor, __ht._M_max_load_factor);
374 }

Referenced by hash_map< _Key, _Tp,,, >::swap(), hash_multimap< _Key, _Tp,,, >::swap(), hash_set< _Value,,, >::swap(), unordered_map< _Key, _Tp,,, >::swap(), unordered_multimap< _Key, _Tp,,, >::swap(), unordered_set< _Value,,, >::swap(), hash_multiset< _Value,,, >::swap(), and unordered_multiset< _Value,,, >::swap().

◆ swap() [2/2]

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
void hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::swap ( _Self &  __ht)
inline

Definition at line 178 of file _hashtable.h.

178 {
179 _M_iter_list._Swap_owners(__ht._M_iter_list);
180 _M_non_dbg_impl.swap(__ht._M_non_dbg_impl);
181 }

Member Data Documentation

◆ _M_buckets

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_BucketVector hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_buckets
private

Definition at line 277 of file _hashtable.h.

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_copy_from(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_find(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_initialize_buckets(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::begin(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::bucket_count(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::count(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::elems_in_bucket(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::end(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::equal_range(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::swap().

◆ _M_elems

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_ElemsCont hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_elems
private

Definition at line 276 of file _hashtable.h.

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_copy_from(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_find(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::begin(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::end(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::get_allocator(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::swap().

◆ _M_equals

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
key_equal hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_equals
private

Definition at line 275 of file _hashtable.h.

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_find(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::count(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::equal_range(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::key_eq(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::operator=(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::swap().

◆ _M_hash

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
hasher hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_hash
private

Definition at line 274 of file _hashtable.h.

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_bkt_num_key(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hash_funct(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::operator=(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::swap().

◆ _M_iter_list

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_STLP_PRIV __owned_list hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_iter_list
private

Definition at line 101 of file _hashtable.h.

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_Invalidate_iterator(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_Invalidate_iterators(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::begin(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::end(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::equal_range(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::erase(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::find(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hashtable(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal_noresize(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique_noresize(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::swap().

◆ _M_max_load_factor

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
float hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_max_load_factor
private

Definition at line 279 of file _hashtable.h.

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_copy_from(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::max_load_factor(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::swap().

◆ _M_non_dbg_impl

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
_Base hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_non_dbg_impl
private

Definition at line 100 of file _hashtable.h.

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_insert(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::begin(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::bucket(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::bucket_count(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::clear(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::count(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::elems_in_bucket(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::empty(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::end(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::equal_range(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::erase(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::find(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::get_allocator(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::hash_funct(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal_noresize(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique_noresize(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::key_eq(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::load_factor(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::max_bucket_count(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::max_load_factor(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::max_size(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::operator=(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::rehash(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::resize(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::size(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::swap().

◆ _M_num_elements

template<class _Val , class _Key , class _HF , class _Traits , class _ExK , class _EqK , class _All >
size_type hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_num_elements
private

Definition at line 278 of file _hashtable.h.

Referenced by hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::_M_copy_from(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_equal(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::insert_unique(), hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::size(), and hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All >::swap().

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