Inheritance diagram for _Hash< _Traits >:

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 _STD reverse_iterator< iterator >	reverse_iterator

typedef _STD reverse_iterator< const_iterator >	const_reverse_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)

	_Hash (const value_type _First, const value_type _Last, const key_compare &_Parg, const allocator_type &_Al)

	_Hash (const _Myt &_Right, const allocator_type &_Al)

	_Hash (_Myt &&_Right, const allocator_type &_Al)

_Myt &	operator= (_Myt &&_Right)

void	_Assign_rv (_Myt &&_Right)

_Pairib	insert (value_type &&_Val)

iterator	insert (const_iterator, value_type &&_Val)

template<class _Valty >
enable_if< is_convertible< _Valty, value_type >::value, _Pairib >::type	insert (_Valty &&_Val)

template<class _Valty >
enable_if< is_convertible< _Valty, value_type >::value, iterator >::type	insert (const_iterator, _Valty &&_Val)

template<class... _Valty>
_Pairib	emplace (_Valty &&..._Val)

template<class... _Valty>
iterator	emplace_hint (const_iterator, _Valty &&..._Val)

	~_Hash () _NOEXCEPT

_Myt &	operator= (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

reverse_iterator	rbegin () _NOEXCEPT

const_reverse_iterator	rbegin () const _NOEXCEPT

reverse_iterator	rend () _NOEXCEPT

const_reverse_iterator	rend () const _NOEXCEPT

const_iterator	cbegin () const _NOEXCEPT

const_iterator	cend () const _NOEXCEPT

const_reverse_iterator	crbegin () const _NOEXCEPT

const_reverse_iterator	crend () 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 _NOEXCEPT

const_local_iterator	cend (size_type _Bucket) const _NOEXCEPT

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)

_Pairib	insert (const value_type &_Val)

iterator	insert (const_iterator, const value_type &_Val)

template<class _Iter >
void	insert (_Iter _First, _Iter _Last)

void	insert (_XSTD 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 ()

Protected Attributes
_Mylist	_List

_Myvec	_Vec

size_type	_Mask

size_type	_Maxidx

float	_Max_bucket_size

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 _STD reverse_iterator<const_iterator> _Hash< _Traits >::const_reverse_iterator

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 _STD reverse_iterator<iterator> _Hash< _Traits >::reverse_iterator

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

         {   // various constants
         _Bucket_size = key_compare::bucket_size,
         _Min_buckets = 8,   // min_buckets = 2 ^^ N, 0 < N
         _Multi = _Traits::_Multi};

Constructor & Destructor Documentation

template<class _Traits>

_Hash< _Traits >::_Hash	(	const key_compare &	_Parg,
		const allocator_type &	_Al
	)

inline

         : _Traits(_Parg),
 
             _List(_Al),
             _Vec(_Al),
 
             _Max_bucket_size(_Bucket_size)
         {   // construct empty hash table
         _Init();
         }

template<class _Traits>

_Hash< _Traits >::_Hash	(	const value_type *	_First,
		const value_type *	_Last,
		const key_compare &	_Parg,
		const allocator_type &	_Al
	)

inline

         : _Traits(_Parg),
 
             _List(_Al),
             _Vec(_Al),
 
             _Max_bucket_size(_Bucket_size)
         {   // construct hash table from [_First, _Last) array
         _Init();
         insert(_First, _Last);
         }

template<class _Traits>

_Hash< _Traits >::_Hash	(	const _Myt &	_Right,
		const allocator_type &	_Al
	)

inline

         : _Traits(),
 
             _List(_Al),
             _Vec(_Al),
 
             _Max_bucket_size(_Bucket_size)
         {   // construct hash table by copying right
         _Copy(_Right);
         }

template<class _Traits>

_Hash< _Traits >::_Hash	(	_Myt &&	_Right,
		const allocator_type &	_Al
	)

inline

         : _Traits(),
 
             _List(_Al),
             _Vec(_Al),
 
             _Max_bucket_size(_Bucket_size)
         {   // construct hash table by moving _Right, allocator
         _Assign_rv(_STD forward<_Myt>(_Right));
         }

template<class _Traits>

_Hash< _Traits >::~_Hash ( )

inline

         {   // destroy hash table
 //      _List.clear();  // speed orphaning of checked iterators
         }

Member Function Documentation

template<class _Traits>

void _Hash< _Traits >::_Assign_rv ( _Myt && _Right )

inline

         {   // assign by moving _Right
         _Right.swap(*this);
         _Right.clear();
         }

template<class _Traits>

_Unchecked_iterator _Hash< _Traits >::_Begin ( size_type _Bucket )

inlineprotected

         {   // return begin iterator for bucket _Bucket
         return (_Vec_lo(_Bucket));
         }

template<class _Traits>

_Unchecked_const_iterator _Hash< _Traits >::_Begin ( size_type _Bucket ) const

inlineprotected

         {   // return begin iterator for bucket _Bucket
         return (_Vec_lo(_Bucket));
         }

template<class _Traits>

template<class _Valty >

_Unchecked_iterator _Hash< _Traits >::_Buynode_if_nil	(	_Valty &&	,
		_Unchecked_iterator	_Plist
	)

inlineprotected

         {   // node exists, just return it
         return (_Plist);
         }

template<class _Traits>

template<class _Valty >

_Unchecked_iterator _Hash< _Traits >::_Buynode_if_nil	(	_Valty &&	_Val,
		_Nil
	)

inlineprotected

         {   // node doesn't exist, make it
         _List.push_front(_STD forward<_Valty>(_Val));
         return (_Unchecked_begin());
         }

template<class _Traits>

void _Hash< _Traits >::_Check_size ( )

inlineprotected

         {   // grow table as needed
         if (max_load_factor() < load_factor())
 
             {   // rehash to bigger table
             size_type _Newsize = bucket_count();
 
             if (_Newsize <  512)
                 _Newsize *= 8;  // multiply by 8
             else if (_Newsize < _Vec.max_size() / 2)
                 _Newsize *= 2;  // multiply safely by 2
             _Init(_Newsize);
             _Reinsert();
             }
         }

template<class _Traits>

void _Hash< _Traits >::_Copy ( const _Myt & _Right )

inlineprotected

         {   // copy entire hash table
         _Mask = _Right._Mask;
         _Maxidx = _Right._Maxidx;
         _Max_bucket_size = _Right._Max_bucket_size;
         _List.clear();
 
         _TRY_BEGIN
         (_Traits&)*this = (_Traits&)_Right;
         _Vec.assign(_Right._Vec.size(), _Unchecked_end());
         insert(_Right.begin(), _Right.end());
         _CATCH_ALL
         clear();    // list or compare copy failed, bail out
         _RERAISE;
         _CATCH_END
         }

template<class _Traits>

void _Hash< _Traits >::_Destroy_if_not_nil ( _Unchecked_iterator _Plist )

inlineprotected

         {   // node exists, destroy it
         _List.erase(_Make_iter(_Plist));
         }

template<class _Traits>

void _Hash< _Traits >::_Destroy_if_not_nil ( _Nil )

inlineprotected

855 { // node doesn't exist, do nothing

856 }

template<class _Traits>

_Unchecked_iterator _Hash< _Traits >::_End ( size_type _Bucket )

inlineprotected

         {   // return end iterator for bucket _Bucket
         if (_Vec_lo(_Bucket) == _Unchecked_end())
             return (_Unchecked_end());
         else
             {   // point past last element
             _Unchecked_iterator _Ans = _Vec_hi(_Bucket);
             return (++_Ans);
             }
         }

template<class _Traits>

_Unchecked_const_iterator _Hash< _Traits >::_End ( size_type _Bucket ) const

inlineprotected

         {   // return end iterator for bucket _Bucket
         if (_Vec_lo(_Bucket) == _Unchecked_end())
             return (_Unchecked_end());
         else
             {   // point past last element
             _Unchecked_const_iterator _Ans = _Vec_hi(_Bucket);
             return (++_Ans);
             }
         }

template<class _Traits>

void _Hash< _Traits >::_Erase_bucket	(	iterator	_Plist_arg,
		size_type	_Bucket
	)

inlineprotected

         {   // fix iterators before erasing _Plist before _Where
         _Unchecked_iterator _Plist = _Plist_arg._Unchecked();
         if (_Vec_hi(_Bucket) == _Plist)
             if (_Vec_lo(_Bucket) == _Plist)
                 {   // make bucket empty
                 _Vec_lo(_Bucket) = _Unchecked_end();
                 _Vec_hi(_Bucket) = _Unchecked_end();
                 }
             else
                 _Vec_hi(_Bucket) = --_Plist;    // move end back one element
         else if (_Vec_lo(_Bucket) == _Plist)
             _Vec_lo(_Bucket) = ++_Plist;    // move beginning up one element
         }

template<class _Traits>

size_type _Hash< _Traits >::_Hashval ( const key_type & _Keyval ) const

inlineprotected

         {   // return hash value, masked and wrapped to current table size
         size_type _Num = ((_Traits&)*this)(_Keyval) & _Mask;
         if (_Maxidx <= _Num)
             _Num -= (_Mask >> 1) + 1;
         return (_Num);
         }

template<class _Traits>

void _Hash< _Traits >::_Init ( size_type _Buckets = _Min_buckets )

inlineprotected

         {   // initialize hash table with _Buckets buckets, leave list alone
         _Vec.assign(2 * _Buckets, _Unchecked_end());
         _Mask = _Buckets - 1;
         _Maxidx = _Buckets;
         }

template<class _Traits>

template<class _Valty , class _Nodety >

_Pairib _Hash< _Traits >::_Insert	(	_Valty &&	_Val,
		_Nodety	_Pnode
	)

inlineprotected

         {   // try to insert existing node with value _Val
         size_type _Bucket;
         _Unchecked_iterator _Where;
 
         _TRY_BEGIN
         _Bucket = _Hashval(this->_Kfn(_Val));
         _Where = _End(_Bucket);
         for (; _Where != _Begin(_Bucket); )
             if (((_Traits&)*this)(this->_Kfn(_Val), this->_Kfn(*--_Where)))
                 ;   // still too high in bucket list
             else if (_Multi
                 || ((_Traits&)*this)(this->_Kfn(*_Where), this->_Kfn(_Val)))
                 {   // found insertion point, back up to it
                 ++_Where;
                 break;
                 }
             else
                 {   // discard new list element and return existing
                 _Destroy_if_not_nil(_Pnode);
                 return (_Pairib(_Make_iter(_Where), false));
                 }
         _CATCH_ALL
         _Destroy_if_not_nil(_Pnode);
         _RERAISE;
         _CATCH_END
 
         _Unchecked_iterator _Plist =
             _Buynode_if_nil(_STD forward<_Valty>(_Val), _Pnode);
         _Unchecked_iterator _Next = _Plist;
 
         if (_Where != ++_Next)  // move element into place
             _List._Unchecked_splice(_Where, _Plist, _Next);
 
         _Insert_bucket(_Plist, _Where, _Bucket);
         _Check_size();
         return (_Pairib(_Make_iter(_Plist), true));
         }

template<class _Traits>

void _Hash< _Traits >::_Insert_bucket	(	_Unchecked_iterator	_Plist,
		_Unchecked_iterator	_Where,
		size_type	_Bucket
	)

inlineprotected

         {   // fix iterators after inserting _Plist before _Where
         if (_Vec_lo(_Bucket) == _Unchecked_end())
             {   // make bucket non-empty
             _Vec_lo(_Bucket) = _Plist;
             _Vec_hi(_Bucket) = _Plist;
             }
         else if (_Vec_lo(_Bucket) == _Where)
             _Vec_lo(_Bucket) = _Plist;  // move beginning back one element
         else if (++_Vec_hi(_Bucket) != _Plist)  // move end up one element
             --_Vec_hi(_Bucket); // or not
         }

template<class _Traits>

iterator _Hash< _Traits >::_Make_iter ( _Unchecked_const_iterator _Where ) const

inline

         {   // make iterator from _Unchecked_const_iterator
         return (_List._Make_iter(_Where));
         }

template<class _Traits>

iterator _Hash< _Traits >::_Make_iter ( const_iterator _Where ) const

inline

         {   // make iterator from const_iterator
         return (_List._Make_iter(_Where));
         }

template<class _Traits>

void _Hash< _Traits >::_Reinsert ( )

inlineprotected

         {   // insert elements in [begin(), end())
         _Unchecked_iterator _Last = _Unchecked_end();
         if (_Unchecked_begin() != _Last)
             for (--_Last; ; )
                 {   // reinsert elements in [begin(), _Last]
                 _Unchecked_iterator _First = _Unchecked_begin();
                 bool _Done = _First == _Last;
                 _Insert(*_First, _First);
                 if (_Done)
                     break;
                 }
         }

template<class _Traits>

_Unchecked_iterator _Hash< _Traits >::_Unchecked_begin ( )

inline

         {   // return iterator for beginning of mutable sequence
         return (_List._Unchecked_begin());
         }

template<class _Traits>

_Unchecked_const_iterator _Hash< _Traits >::_Unchecked_begin ( ) const

inline

         {   // return iterator for beginning of nonmutable sequence
         return (_List._Unchecked_begin());
         }

template<class _Traits>

_Unchecked_iterator _Hash< _Traits >::_Unchecked_end ( )

inline

         {   // return iterator for end of mutable sequence
         return (_List._Unchecked_end());
         }

template<class _Traits>

_Unchecked_const_iterator _Hash< _Traits >::_Unchecked_end ( ) const

inline

         {   // return iterator for end of nonmutable sequence
         return (_List._Unchecked_end());
         }

template<class _Traits>

_Unchecked_iterator& _Hash< _Traits >::_Vec_hi ( size_type _Bucket )

inlineprotected

         {   // return reference to end()-1 for _Bucket
         return (_Vec[2 * _Bucket + 1]);
         }

template<class _Traits>

_Unchecked_const_iterator& _Hash< _Traits >::_Vec_hi ( size_type _Bucket ) const

inlineprotected

         {   // return reference to end()-1 for _Bucket
         return ((_Unchecked_const_iterator&)_Vec[2 * _Bucket + 1]);
         }

template<class _Traits>

_Unchecked_iterator& _Hash< _Traits >::_Vec_lo ( size_type _Bucket )

inlineprotected

         {   // return reference to begin() for _Bucket
         return (_Vec[2 * _Bucket]);
         }

template<class _Traits>

_Unchecked_const_iterator& _Hash< _Traits >::_Vec_lo ( size_type _Bucket ) const

inlineprotected

         {   // return reference to begin() for _Bucket
         return ((_Unchecked_const_iterator&)_Vec[2 * _Bucket]);
         }

template<class _Traits>

iterator _Hash< _Traits >::begin ( )

inline

         {   // return iterator for beginning of mutable sequence
         return (_List.begin());
         }

template<class _Traits>

const_iterator _Hash< _Traits >::begin ( ) const

inline

         {   // return iterator for beginning of nonmutable sequence
         return (_List.begin());
         }

template<class _Traits>

local_iterator _Hash< _Traits >::begin ( size_type _Bucket )

inline

         {   // return iterator for bucket _Bucket
         if (_Bucket < bucket_count())
             return (_Make_iter(_Begin(_Bucket)));
         else
             return (end());
         }

template<class _Traits>

const_local_iterator _Hash< _Traits >::begin ( size_type _Bucket ) const

inline

         {   // return iterator for bucket _Bucket
         if (_Bucket < bucket_count())
             return (_Make_iter(_Begin(_Bucket)));
         else
             return (end());
         }

template<class _Traits>

size_type _Hash< _Traits >::bucket ( const key_type & _Keyval ) const

inline

         {   // return bucket corresponding to _Key
         return (_Hashval(_Keyval));
         }

template<class _Traits>

size_type _Hash< _Traits >::bucket_count ( ) const

inline

         {   // return number of buckets
         return (_Maxidx);
         }

template<class _Traits>

size_type _Hash< _Traits >::bucket_size ( size_type _Bucket ) const

inline

         {   // return size of bucket _Bucket
         size_type _Ans = 0;
         if (_Bucket < _Maxidx)
             for (_Unchecked_const_iterator _Plist = _Begin(_Bucket);
                 _Plist != _End(_Bucket); ++_Plist)
                 ++_Ans;
         return (_Ans);
         }

template<class _Traits>

const_iterator _Hash< _Traits >::cbegin ( ) const

inline

         {   // return iterator for beginning of nonmutable sequence
         return (((const _Myt *)this)->begin());
         }

template<class _Traits>

const_local_iterator _Hash< _Traits >::cbegin ( size_type _Bucket ) const

inline

         {   // return iterator for bucket _Bucket
         if (_Bucket < bucket_count())
             return (_Make_iter(_Begin(_Bucket)));
         else
             return (end());
         }

template<class _Traits>

const_iterator _Hash< _Traits >::cend ( ) const

inline

         {   // return iterator for end of nonmutable sequence
         return (((const _Myt *)this)->end());
         }

template<class _Traits>

const_local_iterator _Hash< _Traits >::cend ( size_type _Bucket ) const

inline

         {   // return iterator for bucket following _Bucket
         if (_Bucket < bucket_count())
             return (_Make_iter(_End(_Bucket)));
         else
             return (end());
         }

template<class _Traits>

void _Hash< _Traits >::clear ( )

inline

         {   // erase all
         _List.clear();
         _Init();
         }

template<class _Traits>

size_type _Hash< _Traits >::count ( const key_type & _Keyval ) const

inline

         {   // count all elements that match _Keyval
         _Paircc _Ans = equal_range(_Keyval);
         size_type _Num = 0;
         _Distance(_Ans.first, _Ans.second, _Num);
         return (_Num);
         }

template<class _Traits>

const_reverse_iterator _Hash< _Traits >::crbegin ( ) const

inline

         {   // return iterator for beginning of reversed nonmutable sequence
         return (((const _Myt *)this)->rbegin());
         }

template<class _Traits>

const_reverse_iterator _Hash< _Traits >::crend ( ) const

inline

         {   // return iterator for end of reversed nonmutable sequence
         return (((const _Myt *)this)->rend());
         }

template<class _Traits>

template<class... _Valty>

_Pairib _Hash< _Traits >::emplace ( _Valty &&... _Val )

inline

         {   // try to insert value_type(_Val...)
         _List.emplace_front(_STD forward<_Valty>(_Val)...);
         return (_Insert(_List.front(), _Unchecked_begin()));
         }

template<class _Traits>

template<class... _Valty>

iterator _Hash< _Traits >::emplace_hint	(	const_iterator	,
		_Valty &&...	_Val
	)

inline

         {   // try to insert value_type(_Val...), ignore hint
         _List.emplace_front(_STD forward<_Valty>(_Val)...);
         return (_Insert(_List.front(), _Unchecked_begin()).first);
         }

template<class _Traits>

bool _Hash< _Traits >::empty ( ) const

inline

         {   // return true only if sequence is empty
         return (_List.empty());
         }

template<class _Traits>

iterator _Hash< _Traits >::end ( )

inline

         {   // return iterator for end of mutable sequence
         return (_List.end());
         }

template<class _Traits>

const_iterator _Hash< _Traits >::end ( ) const

inline

         {   // return iterator for end of nonmutable sequence
         return (_List.end());
         }

template<class _Traits>

local_iterator _Hash< _Traits >::end ( size_type _Bucket )

inline

         {   // return iterator for bucket following _Bucket
         if (_Bucket < bucket_count())
             return (_Make_iter(_End(_Bucket)));
         else
             return (end());
         }

template<class _Traits>

const_local_iterator _Hash< _Traits >::end ( size_type _Bucket ) const

inline

         {   // return iterator for bucket following _Bucket
         if (_Bucket < bucket_count())
             return (_Make_iter(_End(_Bucket)));
         else
             return (end());
         }

template<class _Traits>

_Pairii _Hash< _Traits >::equal_range ( const key_type & _Keyval )

inline

         {   // find range equivalent to _Keyval in mutable hash table
         size_type _Bucket = _Hashval(_Keyval);
         for (_Unchecked_iterator _Where = _Begin(_Bucket);
             _Where != _End(_Bucket); ++_Where)
             if (!((_Traits&)*this)(this->_Kfn(*_Where), _Keyval))
                 {   // found _First, look for end of range
                 _Unchecked_iterator _First = _Where;
                 for (; _Where != _End(_Bucket); ++_Where)
                     if (((_Traits&)*this)(_Keyval, this->_Kfn(*_Where)))
                         break;
                 if (_First == _Where)
                     break;
                 return (_Pairii(_Make_iter(_First),
                     _Make_iter(_Where)));
                 }
         return (_Pairii(end(), end()));
         }

template<class _Traits>

_Paircc _Hash< _Traits >::equal_range ( const key_type & _Keyval ) const

inline

         {   // find range equivalent to _Keyval in nonmutable hash table
         size_type _Bucket = _Hashval(_Keyval);
         for (_Unchecked_const_iterator _Where = _Begin(_Bucket);
             _Where != _End(_Bucket); ++_Where)
             if (!((_Traits&)*this)(this->_Kfn(*_Where), _Keyval))
                 {   // found _First, look for end of range
                 _Unchecked_const_iterator _First = _Where;
                 for (; _Where != _End(_Bucket); ++_Where)
                     if (((_Traits&)*this)(_Keyval, this->_Kfn(*_Where)))
                         break;
                 if (_First == _Where)
                     break;
                 return (_Paircc(_Make_iter(_First),
                     _Make_iter(_Where)));
                 }
         return (_Paircc(end(), end()));
         }

template<class _Traits>

iterator _Hash< _Traits >::erase ( const_iterator _Plist )

inline

         {   // erase element at _Plist
         size_type _Bucket = _Hashval(this->_Kfn(*_Plist));
 
         _Erase_bucket(_Make_iter(_Plist), _Bucket);
         return (_List.erase(_Plist));
         }

template<class _Traits>

iterator _Hash< _Traits >::erase	(	const_iterator	_First,
		const_iterator	_Last
	)

inline

         {   // erase [_First, _Last)
         _DEBUG_RANGE(_First, _Last);
         if (_First == begin() && _Last == end())
             {   // erase all
             clear();
             return (begin());
             }
         else
             {   // partial erase, one at a time
             while (_First != _Last)
                 erase(_First++);
             return (_Make_iter(_First));
             }
         }

template<class _Traits>

size_type _Hash< _Traits >::erase ( const key_type & _Keyval )

inline

         {   // erase and count all that match _Keyval
         _Pairii _Where = equal_range(_Keyval);
         size_type _Num = 0;
         _Distance(_Where.first, _Where.second, _Num);
         erase(_Where.first, _Where.second);
         return (_Num);
         }

template<class _Traits>

iterator _Hash< _Traits >::find ( const key_type & _Keyval )

inline

         {   // find an element in mutable hash table that matches _Keyval
         return (lower_bound(_Keyval));
         }

template<class _Traits>

const_iterator _Hash< _Traits >::find ( const key_type & _Keyval ) const

inline

         {   // find an element in nonmutable hash table that matches _Keyval
         return (lower_bound(_Keyval));
         }

template<class _Traits>

allocator_type _Hash< _Traits >::get_allocator ( ) const

inline

         {   // return allocator object for values
         return (_List.get_allocator());
         }

template<class _Traits>

_Pairib _Hash< _Traits >::insert ( value_type && _Val )

inline

         {   // try to insert node with value _Val, favoring right side
         return (_Insert(_STD forward<value_type>(_Val), _Nil_obj));
         }

template<class _Traits>

iterator _Hash< _Traits >::insert	(	const_iterator	,
		value_type &&	_Val
	)

inline

         {   // try to insert node with value _Val ignoring hint
         return (_Insert(_STD forward<value_type>(_Val), _Nil_obj).first);
         }

template<class _Traits>

template<class _Valty >

enable_if<is_convertible<_Valty, value_type>::value, _Pairib>::type _Hash< _Traits >::insert ( _Valty && _Val )

inline

         {   // try to insert node with value _Val
         _List.emplace_front(_STD forward<_Valty>(_Val));
         return (_Insert(_List.front(), _Unchecked_begin()));
         }

template<class _Traits>

template<class _Valty >

enable_if<is_convertible<_Valty, value_type>::value, iterator>::type _Hash< _Traits >::insert	(	const_iterator	,
		_Valty &&	_Val
	)

inline

         {   // try to insert node with value _Val, ignore hint
         _List.emplace_front(_STD forward<_Valty>(_Val));
         return (_Insert(_List.front(), _Unchecked_begin()).first);
         }

template<class _Traits>

_Pairib _Hash< _Traits >::insert ( const value_type & _Val )

inline

         {   // try to insert node with value _Val
         return (_Insert(_Val, _Nil_obj));
         }

template<class _Traits>

iterator _Hash< _Traits >::insert	(	const_iterator	,
		const value_type &	_Val
	)

inline

         {   // try to insert node with value _Val, ignore hint
         return (_Insert(_Val, _Nil_obj).first);
         }

template<class _Traits>

template<class _Iter >

void _Hash< _Traits >::insert	(	_Iter	_First,
		_Iter	_Last
	)

inline

         {   // insert [_First, _Last) at front, then put in place
         _DEBUG_RANGE(_First, _Last);
         for (; _First != _Last; ++_First)
 
             emplace(*_First);
         }

template<class _Traits>

void _Hash< _Traits >::insert ( _XSTD initializer_list< value_type > _Ilist )

inline

         {   // insert initializer_list
         insert(_Ilist.begin(), _Ilist.end());
         }

template<class _Traits>

key_compare _Hash< _Traits >::key_comp ( ) const

inline

         {   // return object for comparing keys
         return (*this);
         }

template<class _Traits>

float _Hash< _Traits >::load_factor ( ) const

inline

         {   // return elements per bucket
         return ((float)size() / (float)bucket_count());
         }

template<class _Traits>

iterator _Hash< _Traits >::lower_bound ( const key_type & _Keyval )

inline

         {   // find leftmost not less than _Keyval in mutable hash table
         size_type _Bucket = _Hashval(_Keyval);
         for (_Unchecked_iterator _Where = _Begin(_Bucket);
             _Where != _End(_Bucket); ++_Where)
             if (!((_Traits&)*this)(this->_Kfn(*_Where), _Keyval))
                 return (((_Traits&)*this)(_Keyval,
                     this->_Kfn(*_Where)) ? end() : _Make_iter(_Where));
         return (end());
         }

template<class _Traits>

const_iterator _Hash< _Traits >::lower_bound ( const key_type & _Keyval ) const

inline

         {   // find leftmost not less than _Keyval in nonmutable hash table
         size_type _Bucket = _Hashval(_Keyval);
         for (_Unchecked_const_iterator _Where = _Begin(_Bucket);
             _Where != _End(_Bucket); ++_Where)
             if (!((_Traits&)*this)(this->_Kfn(*_Where), _Keyval))
                 return (((_Traits&)*this)(_Keyval,
                     this->_Kfn(*_Where)) ? end() : _Make_iter(_Where));
         return (end());
         }

template<class _Traits>

size_type _Hash< _Traits >::max_bucket_count ( ) const

inline

         {   // return maximum number of buckets
         return (_Vec.size() / 2);
         }

template<class _Traits>

float _Hash< _Traits >::max_load_factor ( ) const

inline

         {   // return maximum elements per bucket
         return (_Max_bucket_size);
         }

template<class _Traits>

void _Hash< _Traits >::max_load_factor ( float _Newmax )

inline

         {   // set new load factor
         if (_Newmax != _Newmax  // may detect a NaN
             || _Newmax < 0)
             _Xout_of_range("invalid hash load factor");
 
         _Max_bucket_size = _Newmax;
         }

template<class _Traits>

size_type _Hash< _Traits >::max_size ( ) const

inline

         {   // return maximum possible length of sequence
         return (_List.max_size());
         }

template<class _Traits>

_Myt& _Hash< _Traits >::operator= ( _Myt && _Right )

inline

         {   // assign by moving _Right
         if (this != &_Right)
             _Assign_rv(_STD forward<_Myt>(_Right));
         return (*this);
         }

template<class _Traits>

_Myt& _Hash< _Traits >::operator= ( const _Myt & _Right )

inline

         {   // replace contents from _Right
         if (this != &_Right)
             _Copy(_Right);
         return (*this);
         }

template<class _Traits>

reverse_iterator _Hash< _Traits >::rbegin ( )

inline

         {   // return iterator for beginning of reversed mutable sequence
         return (_List.rbegin());
         }

template<class _Traits>

const_reverse_iterator _Hash< _Traits >::rbegin ( ) const

inline

         {   // return iterator for beginning of reversed nonmutable sequence
         return (_List.rbegin());
         }

template<class _Traits>

void _Hash< _Traits >::rehash ( size_type _Buckets )

inline

         {   // rebuild table with at least _Buckets buckets
         size_type _Maxsize = _Vec.max_size() / 4;
         size_type _Newsize = _Min_buckets;
 
         for (; _Newsize < _Buckets && _Newsize < _Maxsize; )
             _Newsize *= 2;  // double until big enough
         if (_Newsize < _Buckets)
             _Xout_of_range("invalid hash bucket count");
         for (float _Size = (float)size();
             max_load_factor() < _Size / _Newsize && _Newsize < _Maxsize; )
             _Newsize *= 2;  // double until load factor okay
 
         _Init(_Newsize);
         _Reinsert();
         }

template<class _Traits>

reverse_iterator _Hash< _Traits >::rend ( )

inline

         {   // return iterator for end of reversed mutable sequence
         return (_List.rend());
         }

template<class _Traits>

const_reverse_iterator _Hash< _Traits >::rend ( ) const

inline

         {   // return iterator for end of reversed nonmutable sequence
         return (_List.rend());
         }

template<class _Traits>

void _Hash< _Traits >::reserve ( size_type _Maxcount )

inline

         {   // rebuild table with room for _Maxcount elements
         rehash((size_type)((float)(_Maxcount / max_load_factor() + 0.5F)));
         }

template<class _Traits>

size_type _Hash< _Traits >::size ( ) const

inline

         {   // return length of sequence
         return (_List.size());
         }

template<class _Traits>

void _Hash< _Traits >::swap ( _Myt & _Right )

inline

         {   // exchange contents with _Right
         if (this != &_Right)
             {   // different, worth swapping
             _Swap_adl((_Traits&)*this, (_Traits&)_Right);
             this->_List.swap(_Right._List);
             this->_Vec.swap(_Right._Vec);
             _STD swap(this->_Mask, _Right._Mask);
             _STD swap(this->_Maxidx, _Right._Maxidx);
             _STD swap(this->_Max_bucket_size, _Right._Max_bucket_size);
             }
         }

template<class _Traits>

iterator _Hash< _Traits >::upper_bound ( const key_type & _Keyval )

inline

         {   // find leftmost not greater than _Keyval in mutable hash table
         size_type _Bucket = _Hashval(_Keyval);
         for (_Unchecked_iterator _Where = _End(_Bucket);
             _Where != _Begin(_Bucket); )
             if (!((_Traits&)*this)(_Keyval, this->_Kfn(*--_Where)))
                 return (((_Traits&)*this)(this->_Kfn(*_Where),
                     _Keyval) ? end() : _Make_iter(++_Where));
         return (end());
         }

template<class _Traits>

const_iterator _Hash< _Traits >::upper_bound ( const key_type & _Keyval ) const

inline

         {   // find leftmost not greater than _Keyval in nonmutable hash table
         size_type _Bucket = _Hashval(_Keyval);
         for (_Unchecked_const_iterator _Where = _End(_Bucket);
             _Where != _Begin(_Bucket); )
             if (!((_Traits&)*this)(_Keyval, this->_Kfn(*--_Where)))
                 return (((_Traits&)*this)(this->_Kfn(*_Where),
                     _Keyval) ? end() : _Make_iter(++_Where));
         return (end());
         }

template<class _Traits>

value_compare _Hash< _Traits >::value_comp ( ) const

inline

         {   // return object for comparing values
         return (value_compare(key_comp()));
         }

Member Data Documentation

template<class _Traits>

_Mylist _Hash< _Traits >::_List

protected

template<class _Traits>

size_type _Hash< _Traits >::_Mask

protected

template<class _Traits>

float _Hash< _Traits >::_Max_bucket_size

protected

template<class _Traits>

size_type _Hash< _Traits >::_Maxidx

protected

template<class _Traits>

_Myvec _Hash< _Traits >::_Vec

protected

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

VS2013/inc/xhash

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation