STLdoc
STLdocumentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Public Types | Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
_Hash< _Traits > Class Template Reference
Inheritance diagram for _Hash< _Traits >:
stdext::hash_map< _Kty, _Ty, _Tr, _Alloc > stdext::hash_multimap< _Kty, _Ty, _Tr, _Alloc > stdext::hash_multiset< _Kty, _Tr, _Alloc > stdext::hash_set< _Kty, _Tr, _Alloc >

Public Types

enum  { _Bucket_size = key_compare::bucket_size, _Min_buckets = 8, _Multi = _Traits::_Multi }
 
typedef _Hash< _Traits > _Myt
 
typedef _Traits::key_type key_type
 
typedef _Traits::key_compare key_compare
 
typedef _Traits::value_compare value_compare
 
typedef list< typename _Traits::value_type, typename _Traits::allocator_type > _Mylist
 
typedef _Mylist::_Alty _Alty
 
typedef _Mylist::value_type value_type
 
typedef _Mylist::allocator_type allocator_type
 
typedef _Mylist::size_type size_type
 
typedef _Mylist::difference_type difference_type
 
typedef _Mylist::pointer pointer
 
typedef _Mylist::const_pointer const_pointer
 
typedef _Mylist::reference reference
 
typedef _Mylist::const_reference const_reference
 
typedef _If< is_same< key_type, value_type >::value, typename _Mylist::const_iterator, typename _Mylist::iterator >::type iterator
 
typedef _Mylist::const_iterator const_iterator
 
typedef _If< is_same< key_type, value_type >::value, typename _Mylist::_Unchecked_const_iterator, typename _Mylist::_Unchecked_iterator >::type _Unchecked_iterator
 
typedef _Mylist::_Unchecked_const_iterator _Unchecked_const_iterator
 
typedef vector< _Unchecked_iterator, typename _Alty::template rebind< _Unchecked_iterator >::other > _Myvec
 
typedef pair< iterator, bool_Pairib
 
typedef pair< iterator, iterator_Pairii
 
typedef pair< const_iterator, const_iterator_Paircc
 
typedef iterator local_iterator
 
typedef const_iterator const_local_iterator
 

Public Member Functions

 _Hash (const key_compare &_Parg, const allocator_type &_Al)
 
template<class _Any_alloc >
 _Hash (const _Myt &_Right, const _Any_alloc &_Al)
 
 _Hash (_Myt &&_Right)
 
template<class _Iter >
void _Move_nodes (_Iter _First, _Iter _Last, true_type)
 
template<class _Iter >
void _Move_nodes (_Iter _First, _Iter _Last, false_type)
 
template<class _Other >
void _Move_assign_list (_Other &_Right, true_type)
 
template<class _Other >
void _Move_assign_list (_Other &_Right, false_type)
 
 _Hash (_Myt &&_Right, const allocator_type &_Al)
 
_Mytoperator= (_Myt &&_Right)
 
template<class... _Valty>
_Pairib emplace (_Valty &&..._Val)
 
template<class... _Valty>
iterator emplace_hint (const_iterator, _Valty &&..._Val)
 
 ~_Hash () _NOEXCEPT
 
_Mytoperator= (const _Myt &_Right)
 
iterator begin () _NOEXCEPT
 
const_iterator begin () const _NOEXCEPT
 
iterator end () _NOEXCEPT
 
const_iterator end () const _NOEXCEPT
 
_Unchecked_iterator _Unchecked_begin ()
 
_Unchecked_const_iterator _Unchecked_begin () const
 
_Unchecked_iterator _Unchecked_end ()
 
_Unchecked_const_iterator _Unchecked_end () const
 
iterator _Make_iter (_Unchecked_const_iterator _Where) const
 
iterator _Make_iter (const_iterator _Where) const
 
const_iterator cbegin () const _NOEXCEPT
 
const_iterator cend () const _NOEXCEPT
 
size_type size () const _NOEXCEPT
 
size_type max_size () const _NOEXCEPT
 
bool empty () const _NOEXCEPT
 
allocator_type get_allocator () const _NOEXCEPT
 
key_compare key_comp () const
 
value_compare value_comp () const
 
size_type bucket_count () const _NOEXCEPT
 
size_type max_bucket_count () const _NOEXCEPT
 
size_type bucket (const key_type &_Keyval) const
 
size_type bucket_size (size_type _Bucket) const
 
local_iterator begin (size_type _Bucket)
 
const_local_iterator begin (size_type _Bucket) const
 
local_iterator end (size_type _Bucket)
 
const_local_iterator end (size_type _Bucket) const
 
const_local_iterator cbegin (size_type _Bucket) const
 
const_local_iterator cend (size_type _Bucket) const
 
float load_factor () const _NOEXCEPT
 
float max_load_factor () const _NOEXCEPT
 
void max_load_factor (float _Newmax)
 
void rehash (size_type _Buckets)
 
void reserve (size_type _Maxcount)
 
template<bool _Multi2 = _Multi, enable_if_t<!_Multi2, int > = 0>
_Pairib insert (const value_type &_Val)
 
template<bool _Multi2 = _Multi, enable_if_t< _Multi2, int > = 0>
iterator insert (const value_type &_Val)
 
template<bool _Multi2 = _Multi, enable_if_t<!_Multi2, int > = 0>
_Pairib insert (value_type &&_Val)
 
template<bool _Multi2 = _Multi, enable_if_t< _Multi2, int > = 0>
iterator insert (value_type &&_Val)
 
iterator insert (const_iterator, const value_type &_Val)
 
iterator insert (const_iterator, value_type &&_Val)
 
template<class _Iter >
void insert (_Iter _First, _Iter _Last)
 
void insert (initializer_list< value_type > _Ilist)
 
iterator erase (const_iterator _Plist)
 
iterator erase (const_iterator _First, const_iterator _Last)
 
size_type erase (const key_type &_Keyval)
 
void clear () _NOEXCEPT
 
iterator find (const key_type &_Keyval)
 
const_iterator find (const key_type &_Keyval) const
 
size_type count (const key_type &_Keyval) const
 
iterator lower_bound (const key_type &_Keyval)
 
const_iterator lower_bound (const key_type &_Keyval) const
 
iterator upper_bound (const key_type &_Keyval)
 
const_iterator upper_bound (const key_type &_Keyval) const
 
_Pairii equal_range (const key_type &_Keyval)
 
_Paircc equal_range (const key_type &_Keyval) const
 
void swap (_Myt &_Right)
 

Protected Member Functions

template<class _Valty >
_Unchecked_iterator _Buynode_if_nil (_Valty &&, _Unchecked_iterator _Plist)
 
template<class _Valty >
_Unchecked_iterator _Buynode_if_nil (_Valty &&_Val, _Nil)
 
void _Destroy_if_not_nil (_Unchecked_iterator _Plist)
 
void _Destroy_if_not_nil (_Nil)
 
template<class _Valty , class _Nodety >
_Pairib _Insert (_Valty &&_Val, _Nodety _Pnode)
 
_Unchecked_iterator_Vec_lo (size_type _Bucket)
 
_Unchecked_const_iterator_Vec_lo (size_type _Bucket) const
 
_Unchecked_iterator_Vec_hi (size_type _Bucket)
 
_Unchecked_const_iterator_Vec_hi (size_type _Bucket) const
 
_Unchecked_iterator _Begin (size_type _Bucket)
 
_Unchecked_const_iterator _Begin (size_type _Bucket) const
 
_Unchecked_iterator _End (size_type _Bucket)
 
_Unchecked_const_iterator _End (size_type _Bucket) const
 
void _Erase_bucket (iterator _Plist_arg, size_type _Bucket)
 
void _Insert_bucket (_Unchecked_iterator _Plist, _Unchecked_iterator _Where, size_type _Bucket)
 
void _Copy (const _Myt &_Right)
 
size_type _Hashval (const key_type &_Keyval) const
 
void _Init (size_type _Buckets=_Min_buckets)
 
void _Check_size ()
 
void _Reinsert ()
 
float & _Max_bucket_size () _NOEXCEPT
 
const float & _Max_bucket_size () const _NOEXCEPT
 

Protected Attributes

_Traits _Traitsobj
 
_Mylist _List
 
_Myvec _Vec
 
size_type _Mask
 
size_type _Maxidx
 

Member Typedef Documentation

template<class _Traits>
typedef _Mylist::_Alty _Hash< _Traits >::_Alty
template<class _Traits>
typedef list<typename _Traits::value_type, typename _Traits::allocator_type> _Hash< _Traits >::_Mylist
template<class _Traits>
typedef _Hash<_Traits> _Hash< _Traits >::_Myt
template<class _Traits>
typedef vector<_Unchecked_iterator, typename _Alty::template rebind<_Unchecked_iterator>::other> _Hash< _Traits >::_Myvec
template<class _Traits>
typedef pair<const_iterator, const_iterator> _Hash< _Traits >::_Paircc
template<class _Traits>
typedef pair<iterator, bool> _Hash< _Traits >::_Pairib
template<class _Traits>
typedef pair<iterator, iterator> _Hash< _Traits >::_Pairii
template<class _Traits>
typedef _Mylist::_Unchecked_const_iterator _Hash< _Traits >::_Unchecked_const_iterator
template<class _Traits>
typedef _If<is_same<key_type, value_type>::value, typename _Mylist::_Unchecked_const_iterator, typename _Mylist::_Unchecked_iterator>::type _Hash< _Traits >::_Unchecked_iterator
template<class _Traits>
typedef _Mylist::allocator_type _Hash< _Traits >::allocator_type
template<class _Traits>
typedef _Mylist::const_iterator _Hash< _Traits >::const_iterator
template<class _Traits>
typedef const_iterator _Hash< _Traits >::const_local_iterator
template<class _Traits>
typedef _Mylist::const_pointer _Hash< _Traits >::const_pointer
template<class _Traits>
typedef _Mylist::const_reference _Hash< _Traits >::const_reference
template<class _Traits>
typedef _Mylist::difference_type _Hash< _Traits >::difference_type
template<class _Traits>
typedef _If<is_same<key_type, value_type>::value, typename _Mylist::const_iterator, typename _Mylist::iterator>::type _Hash< _Traits >::iterator
template<class _Traits>
typedef _Traits::key_compare _Hash< _Traits >::key_compare
template<class _Traits>
typedef _Traits::key_type _Hash< _Traits >::key_type
template<class _Traits>
typedef iterator _Hash< _Traits >::local_iterator
template<class _Traits>
typedef _Mylist::pointer _Hash< _Traits >::pointer
template<class _Traits>
typedef _Mylist::reference _Hash< _Traits >::reference
template<class _Traits>
typedef _Mylist::size_type _Hash< _Traits >::size_type
template<class _Traits>
typedef _Traits::value_compare _Hash< _Traits >::value_compare
template<class _Traits>
typedef _Mylist::value_type _Hash< _Traits >::value_type

Member Enumeration Documentation

template<class _Traits>
anonymous enum
Enumerator
_Bucket_size 
_Min_buckets 
_Multi 
155  { // various constants
156  _Bucket_size = key_compare::bucket_size,
157  _Min_buckets = 8, // min_buckets = 2 ^^ N, 0 < N
158  _Multi = _Traits::_Multi};
Definition: xhash:156
Definition: xhash:158
Definition: xhash:157

Constructor & Destructor Documentation

template<class _Traits>
_Hash< _Traits >::_Hash ( const key_compare _Parg,
const allocator_type _Al 
)
inline
194  : _Traitsobj(_Parg),
195  _List(_Al),
196  _Vec(_Al)
197  { // construct empty hash table
199  _Init();
200  }
Definition: xhash:156
_Mylist _List
Definition: xhash:964
_Traits _Traitsobj
Definition: xhash:963
float & _Max_bucket_size() _NOEXCEPT
Definition: xhash:953
void _Init(size_type _Buckets=_Min_buckets)
Definition: xhash:915
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
template<class _Any_alloc >
_Hash< _Traits >::_Hash ( const _Myt _Right,
const _Any_alloc &  _Al 
)
inline
204  : _Traitsobj(_Right._Traitsobj),
205  _List(allocator_type(_Al)),
206  _Vec(_Al)
207  { // construct hash table by copying right
208  _Copy(_Right);
209  }
_Mylist::allocator_type allocator_type
Definition: xhash:164
void _Copy(const _Myt &_Right)
Definition: xhash:894
_Mylist _List
Definition: xhash:964
_Traits _Traitsobj
Definition: xhash:963
constexpr const _Ty &() _Right
Definition: algorithm:3723
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
_Hash< _Traits >::_Hash ( _Myt &&  _Right)
inline
212  : _Traitsobj(_Right._Traitsobj),
213  _List(_STD move(_Right._List)),
214  _Vec(_STD move(_Right._Vec)),
215  _Mask(_Right._Mask),
216  _Maxidx(_Right._Maxidx)
217  { // construct hash table by moving _Right
218  _Right.clear();
219  }
size_type _Mask
Definition: xhash:966
_Mylist _List
Definition: xhash:964
size_type _Maxidx
Definition: xhash:967
_Traits _Traitsobj
Definition: xhash:963
constexpr remove_reference< _Ty >::type && move(_Ty &&_Arg) _NOEXCEPT
Definition: type_traits:1349
constexpr const _Ty &() _Right
Definition: algorithm:3723
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
_Hash< _Traits >::_Hash ( _Myt &&  _Right,
const allocator_type _Al 
)
inline
264  : _Traitsobj(_Right._Traitsobj),
265  _List(_Al),
266  _Vec(_STD move(_Right._Vec), _Al),
267  _Mask(_Right._Mask),
268  _Maxidx(_Right._Maxidx)
269  { // construct hash table by moving _Right, allocator
271 
272  _Right.clear();
273  }
size_type _Mask
Definition: xhash:966
integral_constant< bool, false > false_type
Definition: xtr1common:42
_Mylist _List
Definition: xhash:964
void _Move_assign_list(_Other &_Right, true_type)
Definition: xhash:240
size_type _Maxidx
Definition: xhash:967
_Traits _Traitsobj
Definition: xhash:963
constexpr remove_reference< _Ty >::type && move(_Ty &&_Arg) _NOEXCEPT
Definition: type_traits:1349
constexpr const _Ty &() _Right
Definition: algorithm:3723
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
_Hash< _Traits >::~_Hash ( )
inline
307  { // destroy hash table
308 // _List.clear(); // speed orphaning of checked iterators
309  }

Member Function Documentation

template<class _Traits>
_Unchecked_iterator _Hash< _Traits >::_Begin ( size_type  _Bucket)
inlineprotected
835  { // return begin iterator for bucket _Bucket
836  return (_Vec_lo(_Bucket));
837  }
_Unchecked_iterator & _Vec_lo(size_type _Bucket)
Definition: xhash:814
template<class _Traits>
_Unchecked_const_iterator _Hash< _Traits >::_Begin ( size_type  _Bucket) const
inlineprotected
840  { // return begin iterator for bucket _Bucket
841  return (_Vec_lo(_Bucket));
842  }
_Unchecked_iterator & _Vec_lo(size_type _Bucket)
Definition: xhash:814
template<class _Traits>
template<class _Valty >
_Unchecked_iterator _Hash< _Traits >::_Buynode_if_nil ( _Valty &&  ,
_Unchecked_iterator  _Plist 
)
inlineprotected
738  { // node exists, just return it
739  return (_Plist);
740  }
template<class _Traits>
template<class _Valty >
_Unchecked_iterator _Hash< _Traits >::_Buynode_if_nil ( _Valty &&  _Val,
_Nil   
)
inlineprotected
744  { // node doesn't exist, make it
745  _List.push_front(_STD forward<_Valty>(_Val));
746  return (_Unchecked_begin());
747  }
void push_front(_Ty &&_Val)
Definition: list:1038
_Mylist _List
Definition: xhash:964
_Unchecked_iterator _Unchecked_begin()
Definition: xhash:345
_FwdIt const _Ty _Val
Definition: algorithm:1938
template<class _Traits>
void _Hash< _Traits >::_Check_size ( )
inlineprotected
924  { // grow table as needed
925  if (max_load_factor() < load_factor())
926 
927  { // rehash to bigger table
928  size_type _Newsize = bucket_count();
929 
930  if (_Newsize < 512)
931  _Newsize *= 8; // multiply by 8
932  else if (_Newsize < _Vec.max_size() / 2)
933  _Newsize *= 2; // multiply safely by 2
934  _Init(_Newsize);
935  _Reinsert();
936  }
937  }
size_type max_size() const _NOEXCEPT
Definition: vector:1713
size_type bucket_count() const _NOEXCEPT
Definition: xhash:419
void _Reinsert()
Definition: xhash:939
_Mylist::size_type size_type
Definition: xhash:165
float max_load_factor() const _NOEXCEPT
Definition: xhash:497
float load_factor() const _NOEXCEPT
Definition: xhash:492
void _Init(size_type _Buckets=_Min_buckets)
Definition: xhash:915
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
void _Hash< _Traits >::_Copy ( const _Myt _Right)
inlineprotected
895  { // copy entire hash table
896  _Mask = _Right._Mask;
897  _Maxidx = _Right._Maxidx;
898  _List.clear();
899 
900  _TRY_BEGIN
901  _Traitsobj = _Right._Traitsobj;
902  _Vec.assign(_Right._Vec.size(), _Unchecked_end());
903  insert(_Right.begin(), _Right.end());
904  _CATCH_ALL
905  clear(); // list or compare copy failed, bail out
906  _RERAISE;
907  _CATCH_END
908  }
void clear() _NOEXCEPT
Definition: list:1533
size_type _Mask
Definition: xhash:966
#define _TRY_BEGIN
Definition: xstddef:26
#define _CATCH_END
Definition: xstddef:29
_Unchecked_iterator _Unchecked_end()
Definition: xhash:355
void assign(_CRT_GUARDOVERFLOW const size_type _Newsize, const _Ty &_Val)
Definition: vector:1286
_Pairib insert(const value_type &_Val)
Definition: xhash:535
void clear() _NOEXCEPT
Definition: xhash:617
_Mylist _List
Definition: xhash:964
size_type _Maxidx
Definition: xhash:967
#define _CATCH_ALL
Definition: xstddef:28
_Traits _Traitsobj
Definition: xhash:963
#define _RERAISE
Definition: xstddef:32
constexpr const _Ty &() _Right
Definition: algorithm:3723
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
void _Hash< _Traits >::_Destroy_if_not_nil ( _Unchecked_iterator  _Plist)
inlineprotected
750  { // node exists, destroy it
751  _List.erase(_Make_iter(_Plist));
752  }
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
_Mylist _List
Definition: xhash:964
iterator erase(const_iterator _Where)
Definition: list:1499
template<class _Traits>
void _Hash< _Traits >::_Destroy_if_not_nil ( _Nil  )
inlineprotected
755  { // node doesn't exist, do nothing
756  }
template<class _Traits>
_Unchecked_iterator _Hash< _Traits >::_End ( size_type  _Bucket)
inlineprotected
845  { // return end iterator for bucket _Bucket
846  if (_Vec_lo(_Bucket) == _Unchecked_end())
847  return (_Unchecked_end());
848  else
849  { // point past last element
850  _Unchecked_iterator _Ans = _Vec_hi(_Bucket);
851  return (++_Ans);
852  }
853  }
_Unchecked_iterator & _Vec_hi(size_type _Bucket)
Definition: xhash:824
_Unchecked_iterator _Unchecked_end()
Definition: xhash:355
_Unchecked_iterator & _Vec_lo(size_type _Bucket)
Definition: xhash:814
_If< is_same< key_type, value_type >::value, typename _Mylist::_Unchecked_const_iterator, typename _Mylist::_Unchecked_iterator >::type _Unchecked_iterator
Definition: xhash:180
template<class _Traits>
_Unchecked_const_iterator _Hash< _Traits >::_End ( size_type  _Bucket) const
inlineprotected
855  { // return end iterator for bucket _Bucket
856  if (_Vec_lo(_Bucket) == _Unchecked_end())
857  return (_Unchecked_end());
858  else
859  { // point past last element
860  _Unchecked_const_iterator _Ans = _Vec_hi(_Bucket);
861  return (++_Ans);
862  }
863  }
_Unchecked_iterator & _Vec_hi(size_type _Bucket)
Definition: xhash:824
_Unchecked_iterator _Unchecked_end()
Definition: xhash:355
_Mylist::_Unchecked_const_iterator _Unchecked_const_iterator
Definition: xhash:182
_Unchecked_iterator & _Vec_lo(size_type _Bucket)
Definition: xhash:814
template<class _Traits>
void _Hash< _Traits >::_Erase_bucket ( iterator  _Plist_arg,
size_type  _Bucket 
)
inlineprotected
866  { // fix iterators before erasing _Plist before _Where
867  _Unchecked_iterator _Plist = _Plist_arg._Unchecked();
868  if (_Vec_hi(_Bucket) == _Plist)
869  if (_Vec_lo(_Bucket) == _Plist)
870  { // make bucket empty
871  _Vec_lo(_Bucket) = _Unchecked_end();
872  _Vec_hi(_Bucket) = _Unchecked_end();
873  }
874  else
875  _Vec_hi(_Bucket) = --_Plist; // move end back one element
876  else if (_Vec_lo(_Bucket) == _Plist)
877  _Vec_lo(_Bucket) = ++_Plist; // move beginning up one element
878  }
_Unchecked_iterator & _Vec_hi(size_type _Bucket)
Definition: xhash:824
_Unchecked_iterator _Unchecked_end()
Definition: xhash:355
_Unchecked_iterator & _Vec_lo(size_type _Bucket)
Definition: xhash:814
_If< is_same< key_type, value_type >::value, typename _Mylist::_Unchecked_const_iterator, typename _Mylist::_Unchecked_iterator >::type _Unchecked_iterator
Definition: xhash:180
template<class _Traits>
size_type _Hash< _Traits >::_Hashval ( const key_type _Keyval) const
inlineprotected
911  { // return hash value, masked to current table size
912  return (_Traitsobj(_Keyval) & _Mask);
913  }
size_type _Mask
Definition: xhash:966
_Traits _Traitsobj
Definition: xhash:963
template<class _Traits>
void _Hash< _Traits >::_Init ( size_type  _Buckets = _Min_buckets)
inlineprotected
916  { // initialize hash table with _Buckets buckets, leave list alone
917  _Vec.reserve(2 * _Buckets); // avoid curdling _Vec if exception occurs
918  _Vec.assign(2 * _Buckets, _Unchecked_end());
919  _Mask = _Buckets - 1;
920  _Maxidx = _Buckets;
921  }
void reserve(_CRT_GUARDOVERFLOW const size_type _Newcapacity)
Definition: vector:1527
size_type _Mask
Definition: xhash:966
_Unchecked_iterator _Unchecked_end()
Definition: xhash:355
void assign(_CRT_GUARDOVERFLOW const size_type _Newsize, const _Ty &_Val)
Definition: vector:1286
size_type _Maxidx
Definition: xhash:967
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
template<class _Valty , class _Nodety >
_Pairib _Hash< _Traits >::_Insert ( _Valty &&  _Val,
_Nodety  _Pnode 
)
inlineprotected
761  { // try to insert existing node with value _Val
762  size_type _Bucket;
763  _Unchecked_iterator _Where;
764 
765  _TRY_BEGIN
766  _Bucket = _Hashval(_Traits::_Kfn(_Val));
767  _Where = _End(_Bucket);
768  for (; _Where != _Begin(_Bucket); )
769  {
770 #pragma warning(push)
771 #pragma warning(disable: 4127) // conditional expression is constant
772  if (_Traitsobj(_Traits::_Kfn(_Val),
773  _Traits::_Kfn(*--_Where)))
774  ; // still too high in bucket list
775  else if (_Multi
776  || (!_Traits::_Standard
777  && _Traitsobj(_Traits::_Kfn(*_Where),
778  _Traits::_Kfn(_Val))))
779  { // found insertion point, back up to it
780  ++_Where;
781  break;
782  }
783  else
784  { // discard new list element and return existing
785  _Destroy_if_not_nil(_Pnode);
786  return (_Pairib(_Make_iter(_Where), false));
787  }
788 #pragma warning(pop)
789  }
790  _CATCH_ALL
791  _Destroy_if_not_nil(_Pnode);
792  _RERAISE;
793  _CATCH_END
794 
795  _Unchecked_iterator _Plist =
796  _Buynode_if_nil(_STD forward<_Valty>(_Val), _Pnode);
797  _Unchecked_iterator _Next = _Plist;
798 
799  if (_Where != ++_Next) // move element into place
800  _List._Unchecked_splice(_Where, _Plist, _Next);
801 
802  _Insert_bucket(_Plist, _Where, _Bucket);
803 
804  _TRY_BEGIN
805  _Check_size();
806  _CATCH_ALL
807  erase(_Make_iter(_Plist));
808  _RERAISE;
809  _CATCH_END
810 
811  return (_Pairib(_Make_iter(_Plist), true));
812  }
_Unchecked_iterator _Buynode_if_nil(_Valty &&, _Unchecked_iterator _Plist)
Definition: xhash:736
#define _TRY_BEGIN
Definition: xstddef:26
void _Check_size()
Definition: xhash:923
#define _CATCH_END
Definition: xstddef:29
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
void _Insert_bucket(_Unchecked_iterator _Plist, _Unchecked_iterator _Where, size_type _Bucket)
Definition: xhash:880
void _Destroy_if_not_nil(_Unchecked_iterator _Plist)
Definition: xhash:749
pair< iterator, bool > _Pairib
Definition: xhash:188
_Mylist _List
Definition: xhash:964
Definition: xhash:158
#define _CATCH_ALL
Definition: xstddef:28
_Unchecked_iterator _End(size_type _Bucket)
Definition: xhash:844
_Traits _Traitsobj
Definition: xhash:963
_Mylist::size_type size_type
Definition: xhash:165
_Unchecked_iterator _Begin(size_type _Bucket)
Definition: xhash:834
size_type _Hashval(const key_type &_Keyval) const
Definition: xhash:910
iterator erase(const_iterator _Plist)
Definition: xhash:585
void _Unchecked_splice(_Unchecked_const_iterator _Where, _Unchecked_const_iterator _First, _Unchecked_const_iterator _Last)
Definition: list:1906
#define _RERAISE
Definition: xstddef:32
_FwdIt const _Ty _Val
Definition: algorithm:1938
_If< is_same< key_type, value_type >::value, typename _Mylist::_Unchecked_const_iterator, typename _Mylist::_Unchecked_iterator >::type _Unchecked_iterator
Definition: xhash:180
template<class _Traits>
void _Hash< _Traits >::_Insert_bucket ( _Unchecked_iterator  _Plist,
_Unchecked_iterator  _Where,
size_type  _Bucket 
)
inlineprotected
882  { // fix iterators after inserting _Plist before _Where
883  if (_Vec_lo(_Bucket) == _Unchecked_end())
884  { // make bucket non-empty
885  _Vec_lo(_Bucket) = _Plist;
886  _Vec_hi(_Bucket) = _Plist;
887  }
888  else if (_Vec_lo(_Bucket) == _Where)
889  _Vec_lo(_Bucket) = _Plist; // move beginning back one element
890  else if (++_Vec_hi(_Bucket) != _Plist) // move end up one element
891  --_Vec_hi(_Bucket); // or not
892  }
_Unchecked_iterator & _Vec_hi(size_type _Bucket)
Definition: xhash:824
_Unchecked_iterator _Unchecked_end()
Definition: xhash:355
_Unchecked_iterator & _Vec_lo(size_type _Bucket)
Definition: xhash:814
template<class _Traits>
iterator _Hash< _Traits >::_Make_iter ( _Unchecked_const_iterator  _Where) const
inline
366  { // make iterator from _Unchecked_const_iterator
367  return (_List._Make_iter(_Where));
368  }
_Mylist _List
Definition: xhash:964
iterator _Make_iter(const_iterator _Where) const _NOEXCEPT
Definition: list:1187
template<class _Traits>
iterator _Hash< _Traits >::_Make_iter ( const_iterator  _Where) const
inline
371  { // make iterator from const_iterator
372  return (_List._Make_iter(_Where));
373  }
_Mylist _List
Definition: xhash:964
iterator _Make_iter(const_iterator _Where) const _NOEXCEPT
Definition: list:1187
template<class _Traits>
float& _Hash< _Traits >::_Max_bucket_size ( )
inlineprotected
954  { // return reference to current maximum bucket size
955  return (_Traitsobj._Get_max_bucket_size());
956  }
_Traits _Traitsobj
Definition: xhash:963
template<class _Traits>
const float& _Hash< _Traits >::_Max_bucket_size ( ) const
inlineprotected
959  { // return const reference to current maximum bucket size
960  return (_Traitsobj._Get_max_bucket_size());
961  }
_Traits _Traitsobj
Definition: xhash:963
template<class _Traits>
template<class _Other >
void _Hash< _Traits >::_Move_assign_list ( _Other &  _Right,
true_type   
)
inline
241  { // move elements, POCMA
242  _List = _STD move(_Right._List);
243  }
_Mylist _List
Definition: xhash:964
constexpr remove_reference< _Ty >::type && move(_Ty &&_Arg) _NOEXCEPT
Definition: type_traits:1349
constexpr const _Ty &() _Right
Definition: algorithm:3723
template<class _Traits>
template<class _Other >
void _Hash< _Traits >::_Move_assign_list ( _Other &  _Right,
false_type   
)
inline
247  { // move elements, non-POCMA
248  _List.clear();
249 
250  if (_List._Getal() == _Right._List._Getal())
251  {
253  }
254  else
255  {
256  _Move_nodes(_Right._List.begin(), _Right._List.end(), is_same<key_type, value_type>());
257 
258  _Init(bucket_count());
259  _Reinsert();
260  }
261  }
Definition: xtr1common:23
void clear() _NOEXCEPT
Definition: list:1533
void _Move_nodes(_Iter _First, _Iter _Last, true_type)
Definition: xhash:222
void _Assign_rv(_Myt &&_Right, true_type)
Definition: list:1022
_Mylist _List
Definition: xhash:964
size_type bucket_count() const _NOEXCEPT
Definition: xhash:419
void _Reinsert()
Definition: xhash:939
_Alty & _Getal() _NOEXCEPT
Definition: list:776
constexpr remove_reference< _Ty >::type && move(_Ty &&_Arg) _NOEXCEPT
Definition: type_traits:1349
Definition: xtr1common:87
constexpr const _Ty &() _Right
Definition: algorithm:3723
void _Init(size_type _Buckets=_Min_buckets)
Definition: xhash:915
template<class _Traits>
template<class _Iter >
void _Hash< _Traits >::_Move_nodes ( _Iter  _First,
_Iter  _Last,
true_type   
)
inline
223  { // move set elements
224  for ( ; _First != _Last; ++_First)
225  {
226  _List.push_back(_STD move(*_First));
227  }
228  }
void push_back(_Ty &&_Val)
Definition: list:1043
_Mylist _List
Definition: xhash:964
constexpr remove_reference< _Ty >::type && move(_Ty &&_Arg) _NOEXCEPT
Definition: type_traits:1349
_FwdIt _Last
Definition: algorithm:1936
template<class _Traits>
template<class _Iter >
void _Hash< _Traits >::_Move_nodes ( _Iter  _First,
_Iter  _Last,
false_type   
)
inline
232  { // move map elements
233  for ( ; _First != _Last; ++_First)
234  {
235  _List.emplace_back(_STD move(const_cast<key_type&>(_First->first)), _STD move(_First->second));
236  }
237  }
void emplace_back(_Valty &&..._Val)
Definition: list:1060
_Mylist _List
Definition: xhash:964
constexpr remove_reference< _Ty >::type && move(_Ty &&_Arg) _NOEXCEPT
Definition: type_traits:1349
_FwdIt _Last
Definition: algorithm:1936
template<class _Traits>
void _Hash< _Traits >::_Reinsert ( )
inlineprotected
940  { // insert elements in [begin(), end())
942  if (_Unchecked_begin() != _Last)
943  for (--_Last; ; )
944  { // reinsert elements in [begin(), _Last]
946  bool _Done = _First == _Last;
947  _Insert(*_First, _First);
948  if (_Done)
949  break;
950  }
951  }
_Unchecked_iterator _Unchecked_end()
Definition: xhash:355
_Pairib _Insert(_Valty &&_Val, _Nodety _Pnode)
Definition: xhash:760
_Unchecked_iterator _Unchecked_begin()
Definition: xhash:345
_FwdIt _Last
Definition: algorithm:1936
_If< is_same< key_type, value_type >::value, typename _Mylist::_Unchecked_const_iterator, typename _Mylist::_Unchecked_iterator >::type _Unchecked_iterator
Definition: xhash:180
template<class _Traits>
_Unchecked_iterator _Hash< _Traits >::_Unchecked_begin ( )
inline
346  { // return iterator for beginning of mutable sequence
347  return (_List._Unchecked_begin());
348  }
_Unchecked_iterator _Unchecked_begin()
Definition: list:1164
_Mylist _List
Definition: xhash:964
template<class _Traits>
_Unchecked_const_iterator _Hash< _Traits >::_Unchecked_begin ( ) const
inline
351  { // return iterator for beginning of nonmutable sequence
352  return (_List._Unchecked_begin());
353  }
_Unchecked_iterator _Unchecked_begin()
Definition: list:1164
_Mylist _List
Definition: xhash:964
template<class _Traits>
_Unchecked_iterator _Hash< _Traits >::_Unchecked_end ( )
inline
356  { // return iterator for end of mutable sequence
357  return (_List._Unchecked_end());
358  }
_Unchecked_iterator _Unchecked_end()
Definition: list:1176
_Mylist _List
Definition: xhash:964
template<class _Traits>
_Unchecked_const_iterator _Hash< _Traits >::_Unchecked_end ( ) const
inline
361  { // return iterator for end of nonmutable sequence
362  return (_List._Unchecked_end());
363  }
_Unchecked_iterator _Unchecked_end()
Definition: list:1176
_Mylist _List
Definition: xhash:964
template<class _Traits>
_Unchecked_iterator& _Hash< _Traits >::_Vec_hi ( size_type  _Bucket)
inlineprotected
825  { // return reference to end()-1 for _Bucket
826  return (_Vec[2 * _Bucket + 1]);
827  }
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
_Unchecked_const_iterator& _Hash< _Traits >::_Vec_hi ( size_type  _Bucket) const
inlineprotected
830  { // return reference to end()-1 for _Bucket
831  return ((_Unchecked_const_iterator&)_Vec[2 * _Bucket + 1]);
832  }
_Mylist::_Unchecked_const_iterator _Unchecked_const_iterator
Definition: xhash:182
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
_Unchecked_iterator& _Hash< _Traits >::_Vec_lo ( size_type  _Bucket)
inlineprotected
815  { // return reference to begin() for _Bucket
816  return (_Vec[2 * _Bucket]);
817  }
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
_Unchecked_const_iterator& _Hash< _Traits >::_Vec_lo ( size_type  _Bucket) const
inlineprotected
820  { // return reference to begin() for _Bucket
821  return ((_Unchecked_const_iterator&)_Vec[2 * _Bucket]);
822  }
_Mylist::_Unchecked_const_iterator _Unchecked_const_iterator
Definition: xhash:182
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
iterator _Hash< _Traits >::begin ( )
inline
326  { // return iterator for beginning of mutable sequence
327  return (_List.begin());
328  }
iterator begin() _NOEXCEPT
Definition: list:1142
_Mylist _List
Definition: xhash:964
template<class _Traits>
const_iterator _Hash< _Traits >::begin ( ) const
inline
331  { // return iterator for beginning of nonmutable sequence
332  return (_List.begin());
333  }
iterator begin() _NOEXCEPT
Definition: list:1142
_Mylist _List
Definition: xhash:964
template<class _Traits>
local_iterator _Hash< _Traits >::begin ( size_type  _Bucket)
inline
445  { // return iterator for bucket _Bucket
446  if (_Bucket < bucket_count())
447  return (_Make_iter(_Begin(_Bucket)));
448  else
449  return (end());
450  }
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
size_type bucket_count() const _NOEXCEPT
Definition: xhash:419
iterator end() _NOEXCEPT
Definition: xhash:335
_Unchecked_iterator _Begin(size_type _Bucket)
Definition: xhash:834
template<class _Traits>
const_local_iterator _Hash< _Traits >::begin ( size_type  _Bucket) const
inline
453  { // return iterator for bucket _Bucket
454  if (_Bucket < bucket_count())
455  return (_Make_iter(_Begin(_Bucket)));
456  else
457  return (end());
458  }
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
size_type bucket_count() const _NOEXCEPT
Definition: xhash:419
iterator end() _NOEXCEPT
Definition: xhash:335
_Unchecked_iterator _Begin(size_type _Bucket)
Definition: xhash:834
template<class _Traits>
size_type _Hash< _Traits >::bucket ( const key_type _Keyval) const
inline
430  { // return bucket corresponding to _Key
431  return (_Hashval(_Keyval));
432  }
size_type _Hashval(const key_type &_Keyval) const
Definition: xhash:910
template<class _Traits>
size_type _Hash< _Traits >::bucket_count ( ) const
inline
420  { // return number of buckets
421  return (_Maxidx);
422  }
size_type _Maxidx
Definition: xhash:967
template<class _Traits>
size_type _Hash< _Traits >::bucket_size ( size_type  _Bucket) const
inline
435  { // return size of bucket _Bucket
436  size_type _Ans = 0;
437  if (_Bucket < _Maxidx)
438  for (_Unchecked_const_iterator _Plist = _Begin(_Bucket);
439  _Plist != _End(_Bucket); ++_Plist)
440  ++_Ans;
441  return (_Ans);
442  }
_Mylist::_Unchecked_const_iterator _Unchecked_const_iterator
Definition: xhash:182
size_type _Maxidx
Definition: xhash:967
_Unchecked_iterator _End(size_type _Bucket)
Definition: xhash:844
_Mylist::size_type size_type
Definition: xhash:165
_Unchecked_iterator _Begin(size_type _Bucket)
Definition: xhash:834
template<class _Traits>
const_iterator _Hash< _Traits >::cbegin ( ) const
inline
376  { // return iterator for beginning of nonmutable sequence
377  return (begin());
378  }
iterator begin() _NOEXCEPT
Definition: xhash:325
template<class _Traits>
const_local_iterator _Hash< _Traits >::cbegin ( size_type  _Bucket) const
inline
477  { // return iterator for bucket _Bucket
478  if (_Bucket < bucket_count())
479  return (_Make_iter(_Begin(_Bucket)));
480  else
481  return (end());
482  }
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
size_type bucket_count() const _NOEXCEPT
Definition: xhash:419
iterator end() _NOEXCEPT
Definition: xhash:335
_Unchecked_iterator _Begin(size_type _Bucket)
Definition: xhash:834
template<class _Traits>
const_iterator _Hash< _Traits >::cend ( ) const
inline
381  { // return iterator for end of nonmutable sequence
382  return (end());
383  }
iterator end() _NOEXCEPT
Definition: xhash:335
template<class _Traits>
const_local_iterator _Hash< _Traits >::cend ( size_type  _Bucket) const
inline
485  { // return iterator for bucket following _Bucket
486  if (_Bucket < bucket_count())
487  return (_Make_iter(_End(_Bucket)));
488  else
489  return (end());
490  }
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
size_type bucket_count() const _NOEXCEPT
Definition: xhash:419
_Unchecked_iterator _End(size_type _Bucket)
Definition: xhash:844
iterator end() _NOEXCEPT
Definition: xhash:335
template<class _Traits>
void _Hash< _Traits >::clear ( )
inline
618  { // erase all
619  _List.clear();
620  _Init();
621  }
void clear() _NOEXCEPT
Definition: list:1533
_Mylist _List
Definition: xhash:964
void _Init(size_type _Buckets=_Min_buckets)
Definition: xhash:915
template<class _Traits>
size_type _Hash< _Traits >::count ( const key_type _Keyval) const
inline
634  { // count all elements that match _Keyval
635  _Paircc _Ans = equal_range(_Keyval);
636  return (_STD distance(_Ans.first, _Ans.second));
637  }
pair< const_iterator, const_iterator > _Paircc
Definition: xhash:190
_Iter_diff_t< _InIt > distance(_InIt _First, _InIt _Last)
Definition: xutility:1111
_Pairii equal_range(const key_type &_Keyval)
Definition: xhash:683
template<class _Traits>
template<class... _Valty>
_Pairib _Hash< _Traits >::emplace ( _Valty &&...  _Val)
inline
294  { // try to insert value_type(_Val...)
295  _List.emplace_front(_STD forward<_Valty>(_Val)...);
296  return (_Insert(_List.front(), _Unchecked_begin()));
297  }
void emplace_front(_Valty &&..._Val)
Definition: list:1054
_Pairib _Insert(_Valty &&_Val, _Nodety _Pnode)
Definition: xhash:760
_Mylist _List
Definition: xhash:964
reference front()
Definition: list:1286
_Unchecked_iterator _Unchecked_begin()
Definition: xhash:345
_FwdIt const _Ty _Val
Definition: algorithm:1938
template<class _Traits>
template<class... _Valty>
iterator _Hash< _Traits >::emplace_hint ( const_iterator  ,
_Valty &&...  _Val 
)
inline
301  { // try to insert value_type(_Val...), ignore hint
302  _List.emplace_front(_STD forward<_Valty>(_Val)...);
303  return (_Insert(_List.front(), _Unchecked_begin()).first);
304  }
void emplace_front(_Valty &&..._Val)
Definition: list:1054
_Pairib _Insert(_Valty &&_Val, _Nodety _Pnode)
Definition: xhash:760
_Mylist _List
Definition: xhash:964
reference front()
Definition: list:1286
_Unchecked_iterator _Unchecked_begin()
Definition: xhash:345
_FwdIt const _Ty _Val
Definition: algorithm:1938
template<class _Traits>
bool _Hash< _Traits >::empty ( ) const
inline
396  { // return true only if sequence is empty
397  return (_List.empty());
398  }
bool empty() const _NOEXCEPT
Definition: list:1275
_Mylist _List
Definition: xhash:964
template<class _Traits>
iterator _Hash< _Traits >::end ( )
inline
336  { // return iterator for end of mutable sequence
337  return (_List.end());
338  }
iterator end() _NOEXCEPT
Definition: list:1154
_Mylist _List
Definition: xhash:964
template<class _Traits>
const_iterator _Hash< _Traits >::end ( ) const
inline
341  { // return iterator for end of nonmutable sequence
342  return (_List.end());
343  }
iterator end() _NOEXCEPT
Definition: list:1154
_Mylist _List
Definition: xhash:964
template<class _Traits>
local_iterator _Hash< _Traits >::end ( size_type  _Bucket)
inline
461  { // return iterator for bucket following _Bucket
462  if (_Bucket < bucket_count())
463  return (_Make_iter(_End(_Bucket)));
464  else
465  return (end());
466  }
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
size_type bucket_count() const _NOEXCEPT
Definition: xhash:419
_Unchecked_iterator _End(size_type _Bucket)
Definition: xhash:844
iterator end() _NOEXCEPT
Definition: xhash:335
template<class _Traits>
const_local_iterator _Hash< _Traits >::end ( size_type  _Bucket) const
inline
469  { // return iterator for bucket following _Bucket
470  if (_Bucket < bucket_count())
471  return (_Make_iter(_End(_Bucket)));
472  else
473  return (end());
474  }
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
size_type bucket_count() const _NOEXCEPT
Definition: xhash:419
_Unchecked_iterator _End(size_type _Bucket)
Definition: xhash:844
iterator end() _NOEXCEPT
Definition: xhash:335
template<class _Traits>
_Pairii _Hash< _Traits >::equal_range ( const key_type _Keyval)
inline
684  { // find range equivalent to _Keyval in mutable hash table
685  size_type _Bucket = _Hashval(_Keyval);
686  for (_Unchecked_iterator _Where = _Begin(_Bucket);
687  _Where != _End(_Bucket); ++_Where)
688  if (!_Traitsobj(_Traits::_Kfn(*_Where), _Keyval))
689  { // found _First, look for end of range
690  _Unchecked_iterator _First = _Where;
691  for (; _Where != _End(_Bucket); ++_Where)
692  if (_Traitsobj(_Keyval, _Traits::_Kfn(*_Where)))
693  break;
694  if (_First == _Where)
695  break;
696  return (_Pairii(_Make_iter(_First),
697  _Make_iter(_Where)));
698  }
699  return (_Pairii(end(), end()));
700  }
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
_Unchecked_iterator _End(size_type _Bucket)
Definition: xhash:844
iterator end() _NOEXCEPT
Definition: xhash:335
_Traits _Traitsobj
Definition: xhash:963
pair< iterator, iterator > _Pairii
Definition: xhash:189
_Mylist::size_type size_type
Definition: xhash:165
_Unchecked_iterator _Begin(size_type _Bucket)
Definition: xhash:834
size_type _Hashval(const key_type &_Keyval) const
Definition: xhash:910
_If< is_same< key_type, value_type >::value, typename _Mylist::_Unchecked_const_iterator, typename _Mylist::_Unchecked_iterator >::type _Unchecked_iterator
Definition: xhash:180
template<class _Traits>
_Paircc _Hash< _Traits >::equal_range ( const key_type _Keyval) const
inline
703  { // find range equivalent to _Keyval in nonmutable hash table
704  size_type _Bucket = _Hashval(_Keyval);
705  for (_Unchecked_const_iterator _Where = _Begin(_Bucket);
706  _Where != _End(_Bucket); ++_Where)
707  if (!_Traitsobj(_Traits::_Kfn(*_Where), _Keyval))
708  { // found _First, look for end of range
709  _Unchecked_const_iterator _First = _Where;
710  for (; _Where != _End(_Bucket); ++_Where)
711  if (_Traitsobj(_Keyval, _Traits::_Kfn(*_Where)))
712  break;
713  if (_First == _Where)
714  break;
715  return (_Paircc(_Make_iter(_First),
716  _Make_iter(_Where)));
717  }
718  return (_Paircc(end(), end()));
719  }
pair< const_iterator, const_iterator > _Paircc
Definition: xhash:190
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
_Mylist::_Unchecked_const_iterator _Unchecked_const_iterator
Definition: xhash:182
_Unchecked_iterator _End(size_type _Bucket)
Definition: xhash:844
iterator end() _NOEXCEPT
Definition: xhash:335
_Traits _Traitsobj
Definition: xhash:963
_Mylist::size_type size_type
Definition: xhash:165
_Unchecked_iterator _Begin(size_type _Bucket)
Definition: xhash:834
size_type _Hashval(const key_type &_Keyval) const
Definition: xhash:910
template<class _Traits>
iterator _Hash< _Traits >::erase ( const_iterator  _Plist)
inline
586  { // erase element at _Plist
587  size_type _Bucket = _Hashval(_Traits::_Kfn(*_Plist));
588 
589  _Erase_bucket(_Make_iter(_Plist), _Bucket);
590  return (_List.erase(_Plist));
591  }
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
void _Erase_bucket(iterator _Plist_arg, size_type _Bucket)
Definition: xhash:865
_Mylist _List
Definition: xhash:964
iterator erase(const_iterator _Where)
Definition: list:1499
_Mylist::size_type size_type
Definition: xhash:165
size_type _Hashval(const key_type &_Keyval) const
Definition: xhash:910
template<class _Traits>
iterator _Hash< _Traits >::erase ( const_iterator  _First,
const_iterator  _Last 
)
inline
594  { // erase [_First, _Last)
595  _DEBUG_RANGE(_First, _Last);
596  if (_First == begin() && _Last == end())
597  { // erase all
598  clear();
599  return (begin());
600  }
601  else
602  { // partial erase, one at a time
603  while (_First != _Last)
604  erase(_First++);
605  return (_Make_iter(_First));
606  }
607  }
#define _DEBUG_RANGE(first, last)
Definition: xutility:902
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
void clear() _NOEXCEPT
Definition: xhash:617
iterator begin() _NOEXCEPT
Definition: xhash:325
iterator end() _NOEXCEPT
Definition: xhash:335
iterator erase(const_iterator _Plist)
Definition: xhash:585
_FwdIt _Last
Definition: algorithm:1936
template<class _Traits>
size_type _Hash< _Traits >::erase ( const key_type _Keyval)
inline
610  { // erase and count all that match _Keyval
611  _Pairii _Where = equal_range(_Keyval);
612  size_type _Num = _STD distance(_Where.first, _Where.second);
613  erase(_Where.first, _Where.second);
614  return (_Num);
615  }
_Iter_diff_t< _InIt > distance(_InIt _First, _InIt _Last)
Definition: xutility:1111
_Pairii equal_range(const key_type &_Keyval)
Definition: xhash:683
pair< iterator, iterator > _Pairii
Definition: xhash:189
_Mylist::size_type size_type
Definition: xhash:165
iterator erase(const_iterator _Plist)
Definition: xhash:585
template<class _Traits>
iterator _Hash< _Traits >::find ( const key_type _Keyval)
inline
624  { // find an element in mutable hash table that matches _Keyval
625  return (lower_bound(_Keyval));
626  }
iterator lower_bound(const key_type &_Keyval)
Definition: xhash:639
template<class _Traits>
const_iterator _Hash< _Traits >::find ( const key_type _Keyval) const
inline
629  { // find an element in nonmutable hash table that matches _Keyval
630  return (lower_bound(_Keyval));
631  }
iterator lower_bound(const key_type &_Keyval)
Definition: xhash:639
template<class _Traits>
allocator_type _Hash< _Traits >::get_allocator ( ) const
inline
401  { // return allocator object for values
403  return (_Ret);
404  }
_Mylist::allocator_type allocator_type
Definition: xhash:164
_Mylist _List
Definition: xhash:964
allocator_type get_allocator() const _NOEXCEPT
Definition: list:1280
template<class _Traits>
template<bool _Multi2 = _Multi, enable_if_t<!_Multi2, int > = 0>
_Pairib _Hash< _Traits >::insert ( const value_type _Val)
inline
536  { // try to insert node with value _Val
537  return (_Insert(_Val, _Nil()));
538  }
_Pairib _Insert(_Valty &&_Val, _Nodety _Pnode)
Definition: xhash:760
Definition: xtr1common:16
_FwdIt const _Ty _Val
Definition: algorithm:1938
template<class _Traits>
template<bool _Multi2 = _Multi, enable_if_t< _Multi2, int > = 0>
iterator _Hash< _Traits >::insert ( const value_type _Val)
inline
543  { // try to insert node with value _Val
544  return (_Insert(_Val, _Nil()).first);
545  }
_Pairib _Insert(_Valty &&_Val, _Nodety _Pnode)
Definition: xhash:760
Definition: xtr1common:16
_FwdIt const _Ty _Val
Definition: algorithm:1938
template<class _Traits>
template<bool _Multi2 = _Multi, enable_if_t<!_Multi2, int > = 0>
_Pairib _Hash< _Traits >::insert ( value_type &&  _Val)
inline
550  { // try to insert node with value _Val, favoring right side
551  return (_Insert(_STD move(_Val), _Nil()));
552  }
_Pairib _Insert(_Valty &&_Val, _Nodety _Pnode)
Definition: xhash:760
Definition: xtr1common:16
constexpr remove_reference< _Ty >::type && move(_Ty &&_Arg) _NOEXCEPT
Definition: type_traits:1349
_FwdIt const _Ty _Val
Definition: algorithm:1938
template<class _Traits>
template<bool _Multi2 = _Multi, enable_if_t< _Multi2, int > = 0>
iterator _Hash< _Traits >::insert ( value_type &&  _Val)
inline
557  { // try to insert node with value _Val, favoring right side
558  return (_Insert(_STD move(_Val), _Nil()).first);
559  }
_Pairib _Insert(_Valty &&_Val, _Nodety _Pnode)
Definition: xhash:760
Definition: xtr1common:16
constexpr remove_reference< _Ty >::type && move(_Ty &&_Arg) _NOEXCEPT
Definition: type_traits:1349
_FwdIt const _Ty _Val
Definition: algorithm:1938
template<class _Traits>
iterator _Hash< _Traits >::insert ( const_iterator  ,
const value_type _Val 
)
inline
563  { // try to insert node with value _Val, ignore hint
564  return (_Insert(_Val, _Nil()).first);
565  }
_Pairib _Insert(_Valty &&_Val, _Nodety _Pnode)
Definition: xhash:760
Definition: xtr1common:16
_FwdIt const _Ty _Val
Definition: algorithm:1938
template<class _Traits>
iterator _Hash< _Traits >::insert ( const_iterator  ,
value_type &&  _Val 
)
inline
568  { // try to insert node with value _Val, ignore hint
569  return (_Insert(_STD move(_Val), _Nil()).first);
570  }
_Pairib _Insert(_Valty &&_Val, _Nodety _Pnode)
Definition: xhash:760
Definition: xtr1common:16
constexpr remove_reference< _Ty >::type && move(_Ty &&_Arg) _NOEXCEPT
Definition: type_traits:1349
_FwdIt const _Ty _Val
Definition: algorithm:1938
template<class _Traits>
template<class _Iter >
void _Hash< _Traits >::insert ( _Iter  _First,
_Iter  _Last 
)
inline
574  { // insert [_First, _Last) at front, then put in place
575  _DEBUG_RANGE(_First, _Last);
576  for (; _First != _Last; ++_First)
577  emplace(*_First);
578  }
#define _DEBUG_RANGE(first, last)
Definition: xutility:902
_Pairib emplace(_Valty &&..._Val)
Definition: xhash:293
_FwdIt _Last
Definition: algorithm:1936
template<class _Traits>
void _Hash< _Traits >::insert ( initializer_list< value_type _Ilist)
inline
581  { // insert initializer_list
582  insert(_Ilist.begin(), _Ilist.end());
583  }
constexpr const _Elem * end() const _NOEXCEPT
Definition: initializer_list:44
_Pairib insert(const value_type &_Val)
Definition: xhash:535
constexpr const _Elem * begin() const _NOEXCEPT
Definition: initializer_list:39
template<class _Traits>
key_compare _Hash< _Traits >::key_comp ( ) const
inline
407  { // return object for comparing keys
408  return (_Traitsobj);
409  }
_Traits _Traitsobj
Definition: xhash:963
template<class _Traits>
float _Hash< _Traits >::load_factor ( ) const
inline
493  { // return elements per bucket
494  return ((float)size() / (float)bucket_count());
495  }
size_type size() const _NOEXCEPT
Definition: xhash:385
size_type bucket_count() const _NOEXCEPT
Definition: xhash:419
template<class _Traits>
iterator _Hash< _Traits >::lower_bound ( const key_type _Keyval)
inline
640  { // find leftmost not less than _Keyval in mutable hash table
641  size_type _Bucket = _Hashval(_Keyval);
642  for (_Unchecked_iterator _Where = _Begin(_Bucket);
643  _Where != _End(_Bucket); ++_Where)
644  if (!_Traitsobj(_Traits::_Kfn(*_Where), _Keyval))
645  return (_Traitsobj(_Keyval,
646  _Traits::_Kfn(*_Where)) ? end() : _Make_iter(_Where));
647  return (end());
648  }
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
_Unchecked_iterator _End(size_type _Bucket)
Definition: xhash:844
iterator end() _NOEXCEPT
Definition: xhash:335
_Traits _Traitsobj
Definition: xhash:963
_Mylist::size_type size_type
Definition: xhash:165
_Unchecked_iterator _Begin(size_type _Bucket)
Definition: xhash:834
size_type _Hashval(const key_type &_Keyval) const
Definition: xhash:910
_If< is_same< key_type, value_type >::value, typename _Mylist::_Unchecked_const_iterator, typename _Mylist::_Unchecked_iterator >::type _Unchecked_iterator
Definition: xhash:180
template<class _Traits>
const_iterator _Hash< _Traits >::lower_bound ( const key_type _Keyval) const
inline
651  { // find leftmost not less than _Keyval in nonmutable hash table
652  size_type _Bucket = _Hashval(_Keyval);
653  for (_Unchecked_const_iterator _Where = _Begin(_Bucket);
654  _Where != _End(_Bucket); ++_Where)
655  if (!_Traitsobj(_Traits::_Kfn(*_Where), _Keyval))
656  return (_Traitsobj(_Keyval,
657  _Traits::_Kfn(*_Where)) ? end() : _Make_iter(_Where));
658  return (end());
659  }
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
_Mylist::_Unchecked_const_iterator _Unchecked_const_iterator
Definition: xhash:182
_Unchecked_iterator _End(size_type _Bucket)
Definition: xhash:844
iterator end() _NOEXCEPT
Definition: xhash:335
_Traits _Traitsobj
Definition: xhash:963
_Mylist::size_type size_type
Definition: xhash:165
_Unchecked_iterator _Begin(size_type _Bucket)
Definition: xhash:834
size_type _Hashval(const key_type &_Keyval) const
Definition: xhash:910
template<class _Traits>
size_type _Hash< _Traits >::max_bucket_count ( ) const
inline
425  { // return maximum number of buckets
426  return (_Vec.max_size() / 2);
427  }
size_type max_size() const _NOEXCEPT
Definition: vector:1713
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
float _Hash< _Traits >::max_load_factor ( ) const
inline
498  { // return maximum elements per bucket
499  return (_Max_bucket_size());
500  }
float & _Max_bucket_size() _NOEXCEPT
Definition: xhash:953
template<class _Traits>
void _Hash< _Traits >::max_load_factor ( float  _Newmax)
inline
503  { // set new load factor
504  if (_Newmax != _Newmax // may detect a NaN
505  || _Newmax < 0)
506  _Xout_of_range("invalid hash load factor");
507 
508  _Max_bucket_size() = _Newmax;
509  }
_CRTIMP2_PURE void __CLRCALL_PURE_OR_CDECL _Xout_of_range(_In_z_ const char *)
float & _Max_bucket_size() _NOEXCEPT
Definition: xhash:953
template<class _Traits>
size_type _Hash< _Traits >::max_size ( ) const
inline
391  { // return maximum possible length of sequence
392  return (_List.max_size());
393  }
_Mylist _List
Definition: xhash:964
size_type max_size() const _NOEXCEPT
Definition: list:1270
template<class _Traits>
_Myt& _Hash< _Traits >::operator= ( _Myt &&  _Right)
inline
276  { // assign by moving _Right
277  if (this != _STD addressof(_Right))
278  {
279  _Traitsobj = _Right._Traitsobj;
280  _Vec = _STD move(_Right._Vec);
281  _Mask = _Right._Mask;
282  _Maxidx = _Right._Maxidx;
283 
284  _Move_assign_list(_Right, typename _Alty::propagate_on_container_move_assignment());
285 
286  _Right.clear();
287  }
288 
289  return (*this);
290  }
size_type _Mask
Definition: xhash:966
_STD_BEGIN constexpr _Ty * addressof(_Ty &_Val) _NOEXCEPT
Definition: xstddef:628
void _Move_assign_list(_Other &_Right, true_type)
Definition: xhash:240
size_type _Maxidx
Definition: xhash:967
_Traits _Traitsobj
Definition: xhash:963
constexpr remove_reference< _Ty >::type && move(_Ty &&_Arg) _NOEXCEPT
Definition: type_traits:1349
constexpr const _Ty &() _Right
Definition: algorithm:3723
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
_Myt& _Hash< _Traits >::operator= ( const _Myt _Right)
inline
312  { // replace contents from _Right
313  if (this != _STD addressof(_Right))
314  {
315  _Mylist _List2(_Right._List.get_allocator());
316  _List = _List2; // respect POCCA
317  _Myvec _Vec2(_Right._Vec.get_allocator());
318  _Vec = _Vec2; // respect POCCA
319  _Copy(_Right);
320  }
321 
322  return (*this);
323  }
_STD_BEGIN constexpr _Ty * addressof(_Ty &_Val) _NOEXCEPT
Definition: xstddef:628
void _Copy(const _Myt &_Right)
Definition: xhash:894
list< typename _Traits::value_type, typename _Traits::allocator_type > _Mylist
Definition: xhash:160
vector< _Unchecked_iterator, typename _Alty::template rebind< _Unchecked_iterator >::other > _Myvec
Definition: xhash:186
_Mylist _List
Definition: xhash:964
constexpr const _Ty &() _Right
Definition: algorithm:3723
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
void _Hash< _Traits >::rehash ( size_type  _Buckets)
inline
512  { // rebuild table with at least _Buckets buckets
514  size_type _Newsize = _Min_buckets;
515 
516  for (; _Newsize < _Buckets && _Newsize < _Maxsize; )
517  _Newsize *= 2; // double until big enough
518  if (_Newsize < _Buckets)
519  _Xout_of_range("invalid hash bucket count");
520  while (!(size() / max_load_factor() < _Newsize)
521  && _Newsize < _Maxsize)
522  _Newsize *= 2; // double until load factor okay
523 
524  _Init(_Newsize);
525  _Reinsert();
526  }
size_type size() const _NOEXCEPT
Definition: xhash:385
size_type max_size() const _NOEXCEPT
Definition: vector:1713
_In_ size_t _Maxsize
Definition: xlocinfo.h:144
void _Reinsert()
Definition: xhash:939
_CRTIMP2_PURE void __CLRCALL_PURE_OR_CDECL _Xout_of_range(_In_z_ const char *)
Definition: xhash:157
_Mylist::size_type size_type
Definition: xhash:165
float max_load_factor() const _NOEXCEPT
Definition: xhash:497
void _Init(size_type _Buckets=_Min_buckets)
Definition: xhash:915
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
void _Hash< _Traits >::reserve ( size_type  _Maxcount)
inline
529  { // rebuild table with room for _Maxcount elements
530  rehash((size_type)((float)(_Maxcount / max_load_factor() + 0.5F)));
531  }
_Mylist::size_type size_type
Definition: xhash:165
float max_load_factor() const _NOEXCEPT
Definition: xhash:497
void rehash(size_type _Buckets)
Definition: xhash:511
template<class _Traits>
size_type _Hash< _Traits >::size ( ) const
inline
386  { // return length of sequence
387  return (_List.size());
388  }
_Mylist _List
Definition: xhash:964
size_type size() const _NOEXCEPT
Definition: list:1265
template<class _Traits>
void _Hash< _Traits >::swap ( _Myt _Right)
inline
722  { // exchange contents with _Right
723  if (this != _STD addressof(_Right))
724  { // different, worth swapping
725  _Swap_adl(_Traitsobj, _Right._Traitsobj);
726 
727  this->_List.swap(_Right._List);
728  this->_Vec.swap(_Right._Vec);
729  _Swap_adl(this->_Mask, _Right._Mask);
730  _Swap_adl(this->_Maxidx, _Right._Maxidx);
731  }
732  }
size_type _Mask
Definition: xhash:966
_STD_BEGIN constexpr _Ty * addressof(_Ty &_Val) _NOEXCEPT
Definition: xstddef:628
void swap(vector &_Right) _NOEXCEPT_OP(_Alty
Definition: vector:1620
_Mylist _List
Definition: xhash:964
size_type _Maxidx
Definition: xhash:967
void _Swap_adl(_Ty &_Left, _Ty &_Right) _NOEXCEPT_OP(_Is_nothrow_swappable< _Ty >
Definition: utility:73
_Traits _Traitsobj
Definition: xhash:963
void swap(_Myt &_Right) _NOEXCEPT_OP(_Alty
Definition: list:1551
constexpr const _Ty &() _Right
Definition: algorithm:3723
_Myvec _Vec
Definition: xhash:965
template<class _Traits>
iterator _Hash< _Traits >::upper_bound ( const key_type _Keyval)
inline
662  { // find leftmost not greater than _Keyval in mutable hash table
663  size_type _Bucket = _Hashval(_Keyval);
664  for (_Unchecked_iterator _Where = _End(_Bucket);
665  _Where != _Begin(_Bucket); )
666  if (!_Traitsobj(_Keyval, _Traits::_Kfn(*--_Where)))
667  return (_Traitsobj(_Traits::_Kfn(*_Where),
668  _Keyval) ? end() : _Make_iter(++_Where));
669  return (end());
670  }
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
_Unchecked_iterator _End(size_type _Bucket)
Definition: xhash:844
iterator end() _NOEXCEPT
Definition: xhash:335
_Traits _Traitsobj
Definition: xhash:963
_Mylist::size_type size_type
Definition: xhash:165
_Unchecked_iterator _Begin(size_type _Bucket)
Definition: xhash:834
size_type _Hashval(const key_type &_Keyval) const
Definition: xhash:910
_If< is_same< key_type, value_type >::value, typename _Mylist::_Unchecked_const_iterator, typename _Mylist::_Unchecked_iterator >::type _Unchecked_iterator
Definition: xhash:180
template<class _Traits>
const_iterator _Hash< _Traits >::upper_bound ( const key_type _Keyval) const
inline
673  { // find leftmost not greater than _Keyval in nonmutable hash table
674  size_type _Bucket = _Hashval(_Keyval);
675  for (_Unchecked_const_iterator _Where = _End(_Bucket);
676  _Where != _Begin(_Bucket); )
677  if (!_Traitsobj(_Keyval, _Traits::_Kfn(*--_Where)))
678  return (_Traitsobj(_Traits::_Kfn(*_Where),
679  _Keyval) ? end() : _Make_iter(++_Where));
680  return (end());
681  }
iterator _Make_iter(_Unchecked_const_iterator _Where) const
Definition: xhash:365
_Mylist::_Unchecked_const_iterator _Unchecked_const_iterator
Definition: xhash:182
_Unchecked_iterator _End(size_type _Bucket)
Definition: xhash:844
iterator end() _NOEXCEPT
Definition: xhash:335
_Traits _Traitsobj
Definition: xhash:963
_Mylist::size_type size_type
Definition: xhash:165
_Unchecked_iterator _Begin(size_type _Bucket)
Definition: xhash:834
size_type _Hashval(const key_type &_Keyval) const
Definition: xhash:910
template<class _Traits>
value_compare _Hash< _Traits >::value_comp ( ) const
inline
412  { // return object for comparing values
413  return (value_compare(key_comp()));
414  }
key_compare key_comp() const
Definition: xhash:406
_Traits::value_compare value_compare
Definition: xhash:153

Member Data Documentation

template<class _Traits>
_Mylist _Hash< _Traits >::_List
protected
template<class _Traits>
size_type _Hash< _Traits >::_Mask
protected
template<class _Traits>
size_type _Hash< _Traits >::_Maxidx
protected
template<class _Traits>
_Traits _Hash< _Traits >::_Traitsobj
protected
template<class _Traits>
_Myvec _Hash< _Traits >::_Vec
protected

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