1		// xhash internal header
2		#pragma once
3		#ifndef _XHASH_
4		#define _XHASH_
5		#ifndef RC_INVOKED
6
7		#include <cstring>
8		#include <cwchar>
9		#include <functional>
10		#include <list>
11		#include <vector>
12
13		#ifdef  _MSC_VER
14		#pragma pack(push,_CRT_PACKING)
15		#pragma warning(push,3)
16		#pragma warning(disable: 4127)
17		#endif  /* _MSC_VER */
18
19
20		#ifndef _HAS_INCREMENTAL_HASH
21		#define _HAS_INCREMENTAL_HASH    0    /* 1 for slow growth, 0 for rapid */
22		#endif /* _HAS_INCREMENTAL_HASH */
23
24		#if _HAS_TRADITIONAL_STL
25		#ifdef _HAS_STLPORT_EMULATION
26		#undef _HAS_STLPORT_EMULATION
27		#endif
28		#define _HAS_STLPORT_EMULATION    1
29		#endif /* _HAS_TRADITIONAL_STL */
30
31
32		// TEMPLATE FUNCTION hash_value
33		#define _HASH_SEED    (size_t)0xdeadbeef
34
35		/*
36		We start off by defining a specialisation of hash_value for stdext.
37		This will work for stdext::hash_map<std::string, ...
38		If the user is using std::hash_map, we pull the specialisation into std
39		as well.
40
41		This comes at the top of our file before everything else to ensure we
42		only pull in this one specialisation.
43		*/
44
45		_STDEXT_BEGIN
46
47		#if _HAS_ITERATOR_DEBUGGING
48		using std::_Debug_message;
49		using std::_Debug_range;
50		#endif
51
52		template <class _InIt>
53		inline size_t _Hash_value(_InIt _Begin, _InIt _End)
54		{    // hash range of elements
55		size_t _Val = 2166136261U;
56		while(_Begin != _End)
57		_Val = 16777619U * _Val ^ (size_t)*_Begin++;
58		return (_Val);
59		}
60
61		template<class _Elem,
62		class _Traits,
63		class _Alloc> inline
64		size_t hash_value(const _STD basic_string<_Elem, _Traits, _Alloc>& _Str)
65		{    // hash string to size_t value
66		const _Elem *_Ptr = _Str.c_str();
67
68		return (_Hash_value(_Ptr, _Ptr + _Str.size()));
69		}
70
71
72		template<class _Kty> inline
73		size_t hash_value(const _Kty& _Keyval)
74		{    // hash _Keyval to size_t value one-to-one
75		return ((size_t)_Keyval ^ _HASH_SEED);
76		}
77
78		inline size_t hash_value(_In_z_ const char *_Str)
79		{    // hash NTBS to size_t value
80		return (_Hash_value(_Str, _Str + ::strlen(_Str)));
81		}
82
83		inline size_t hash_value(_In_z_ const wchar_t *_Str)
84		{    // hash NTWCS to size_t value
85		return (_Hash_value(_Str, _Str + ::wcslen(_Str)));
86		}
87
88
89		#if _HAS_TRADITIONAL_STL
90		// TEMPLATE CLASS hash for STLport
91		template<class _Kty>
92		class hash
93		{    // traits class for hash function
94		public:
95		size_t operator()(const _Kty& _Keyval) const
96		{    // hash _Keyval to size_t value by pseudorandomizing transform
97		ldiv_t _Qrem = ldiv((size_t)hash_value(_Keyval), 127773);
98		_Qrem.rem = 16807 * _Qrem.rem - 2836 * _Qrem.quot;
99		if (_Qrem.rem < 0)
100		_Qrem.rem += 2147483647;
101		return ((size_t)_Qrem.rem);
102		}
103		};
104		#endif /* _HAS_TRADITIONAL_STL */
105
106		template<class _Kty,
107		class _Pr = _STD less<_Kty> >
108		class hash_compare
109		{    // traits class for hash containers
110		public:
111		enum
112		{    // parameters for hash table
113		bucket_size = 4,    // 0 < bucket_size
114		min_buckets = 8};    // min_buckets = 2 ^^ N, 0 < N
115
116		hash_compare()
117		: comp()
118		{    // construct with default comparator
119		}
120
121		hash_compare(_Pr _Pred)
122		: comp(_Pred)
123		{    // construct with _Pred comparator
124		}
125
126		size_t operator()(const _Kty& _Keyval) const
127		{    // hash _Keyval to size_t value by pseudorandomizing transform
128		long _Quot = (long)(hash_value(_Keyval) & LONG_MAX);
129		ldiv_t _Qrem = ldiv(_Quot, 127773);
130
131		_Qrem.rem = 16807 * _Qrem.rem - 2836 * _Qrem.quot;
132		if (_Qrem.rem < 0)
133		_Qrem.rem += LONG_MAX;
134		return ((size_t)_Qrem.rem);
135		}
136
137		bool operator()(const _Kty& _Keyval1, const _Kty& _Keyval2) const
138		{    // test if _Keyval1 ordered before _Keyval2
139		return (comp(_Keyval1, _Keyval2));
140		}
141
142		protected:
143		_Pr comp;    // the comparator object
144		};
145
146		// TEMPLATE CLASS _Hash_compare
147		template<class _Kty,
148		class _Hasher,
149		class _Keyeq>
150		class _Hash_compare
151		{    // traits class for hash containers
152		public:
153		typedef _Hasher hasher;
154		enum
155		{    // parameters for hash table
156		bucket_size = 4,    // 0 < bucket_size
157		min_buckets = 8};    // min_buckets = 2 ^^ N, 0 < N
158
159		_Hash_compare()
160		{    // construct with default hasher and equality comparator
161		}
162
163		_Hash_compare(hasher _Hasharg)
164		: _Hashobj(_Hasharg)
165		{    // construct with hasher and default equality comparator
166		}
167
168		_Hash_compare(hasher _Hasharg, _Keyeq _Keyeqarg)
169		: _Hashobj(_Hasharg), _Keyeqobj(_Keyeqarg)
170		{    // construct with hasher and equality comparator
171		}
172
173		size_t operator()(const _Kty& _Keyval) const
174		{    // hash _Keyval to size_t value
175		return ((size_t)_Hashobj(_Keyval));
176		}
177
178		bool operator()(const _Kty& _Keyval1, const _Kty& _Keyval2) const
179		{    // test if _Keyval1 NOT equal to _Keyval2
180		return (!_Keyeqobj(_Keyval1, _Keyval2));
181		}
182
183		hasher _Hashobj;    // the hash object
184		_Keyeq _Keyeqobj;    // the equality comparator object
185		};
186
187		// TEMPLATE CLASS _Hash
188		template<class _Traits>
189		class _Hash
190		: public _Traits    // traits serves as base class
191		{    // hash table -- list with vector of iterators for quick access
192		public:
193		typedef _Hash<_Traits> _Myt;
194		typedef typename _Traits::key_type key_type;
195		typedef typename _Traits::key_compare key_compare;
196		typedef typename _Traits::value_compare value_compare;
197		enum
198		{    // hoist constants from key_compare
199		_Bucket_size = key_compare::bucket_size,
200		min_buckets = key_compare::min_buckets,
201		_Multi = _Traits::_Multi};
202		typedef _STD list<typename _Traits::value_type,
203		typename _Traits::allocator_type> _Mylist;
204
205		typedef typename _Mylist::allocator_type allocator_type;
206		typedef typename _Mylist::size_type size_type;
207		typedef typename _Mylist::difference_type difference_type;
208		typedef typename _Mylist::pointer pointer;
209		typedef typename _Mylist::const_pointer const_pointer;
210		typedef typename _Mylist::reference reference;
211		typedef typename _Mylist::const_reference const_reference;
212
213		#if _HAS_IMMUTABLE_SETS
214		typedef typename _Mylist::iterator _Myiterator;
215		typedef typename _Traits::_ITptr _ITptr;
216		typedef typename _Traits::_IReft _IReft;
217
218		// CLASS iterator
219		class iterator
220		: public _Myiterator
221		{    // possibly non-mutable iterator
222		public:
223		typedef _ITptr pointer;
224		typedef _IReft reference;
225
226		iterator()
227		{    // construct default iterator
228		}
229
230		iterator(const _Myiterator& _Iter)
231		: _Myiterator(_Iter)
232		{    // construct from _Myiterator
233		}
234
235		_IReft operator*() const
236		{    // change to const_reference
237		return ((_IReft)**(_Myiterator *)this);
238		}
239
240		_ITptr operator->() const
241		{    // change to const_pointer
242		return ((_ITptr)&**(_Myiterator *)this);
243		}
244		};
245
246		#else /* _HAS_IMMUTABLE_SETS */
247		typedef typename _Mylist::iterator _Myiterator;
248		typedef typename _Mylist::iterator iterator;
249		#endif /* _HAS_IMMUTABLE_SETS */
250
251		typedef typename _Mylist::const_iterator const_iterator;
252
253		#if _SECURE_SCL && !_HAS_ITERATOR_DEBUGGING
254
255		// _List_position is used to keep a pointer to a certain position in the list.
256		// List iterators can easily be converted to _List_position, and you can get
257		// the correctly parented iterator from a _List_position calling _Get_iter() or
258		// the helper function _Get_iter_from_vec() below.
259		struct _List_position
260		{
261		public:
262		_List_position()
263		: _Mypos()
264		{
265		}
266
267		_List_position(iterator _Iter)
268		: _Mypos(_Iter._Mynode(), (_Mylist*)_Iter._Getmycont())
269		{
270		}
271
272		_List_position(const_iterator _Iter)
273		: _Mypos(_Iter._Mynode(), (_Mylist*)_Iter._Getmycont())
274		{
275		}
276
277		// default copy constructor and assignment operator
278
279		iterator _Get_iter(const _Mylist &_List) const
280		{
281		// reparent the iterator
282		return (_Myiterator(_Mypos._Mynode(), &_List));
283		}
284
285		bool operator==(const _List_position &_Right) const
286		{
287		return (_Mypos._Mynode() == _Right._Mypos._Mynode());
288		}
289
290		bool operator!=(const _List_position &_Right) const
291		{
292		return (!(*this == _Right));
293		}
294
295		bool operator==(const const_iterator &_Right) const
296		{
297		return (_Mypos._Mynode() == _Right._Mynode());
298		}
299
300		bool operator!=(const const_iterator &_Right) const
301		{
302		return (!(*this == _Right));
303		}

Lines 304 ... 516 are skipped.

517		{    // set new load factor
518		if (_Newmax != _Newmax    // may detect a NaN
519		|| _Newmax < 0)
520		_THROW(_STD out_of_range, "invalid hash load factor");
521
522		_Max_bucket_size = _Newmax;
523		}
524
525		void rehash(size_type _Buckets)
526		{    // rebuild table with at least _Buckets buckets
527		size_type _Maxsize = _Vec.max_size() / 2;
528		size_type _Newsize = min_buckets;
529
530		for (; _Newsize < _Buckets && _Newsize < _Maxsize; )
531		_Newsize *= 2;    // double until big enough
532		if (_Newsize < _Buckets)
533		_THROW(_STD out_of_range, "invalid hash bucket count");
534		for (float _Size = (float)size();
535		max_load_factor() < _Size / _Newsize && _Newsize < _Maxsize; )
536		_Newsize *= 2;    // double until load factor okay
537
538		_Init(_Newsize);
539		_Reinsert();
540		}
541		// ADDED WITH TR1 -- END
542
543		_Pairib insert(const value_type& _Val)
544		{    // try to insert node with value _Val
545		return (_Insert(_Val, end()));
546		}
547
548		iterator insert(const_iterator, const value_type& _Val)
549		{    // try to insert node with value _Val, ignore hint
550		return (insert(_Val).first);
551		}
552
553		template<class _Iter>
554		void insert(_Iter _First, _Iter _Last)
555		{    // insert [_First, _Last) one at a time
556		_List.insert(begin(), _First, _Last);
557		_Reinsert();
558		}
559
560
561		iterator erase(const_iterator _Where)
562		{    // erase element at _Where
563		size_type _Bucket = _Hashval(this->_Kfn(*_Where));
564		for (; _Vec[_Bucket] == _Where; --_Bucket)
565		{    // update end iterators if erasing first
566		#if _SECURE_SCL && !_HAS_ITERATOR_DEBUGGING
567		iterator _Vec_iter = _Get_iter_from_vec(_Vec[_Bucket]);
568		++_Vec_iter;
569		_Vec[_Bucket] = _Vec_iter;
570		#else
571		++_Vec[_Bucket];
572		#endif
573		if (_Bucket == 0)
574		break;
575		}
576		return (_List.erase(_Where));
577		}
578
579		iterator erase(const_iterator _First, const_iterator _Last)
580		{    // erase [_First, _Last)
581		_DEBUG_RANGE(_First, _Last);
582		if (_First == begin() && _Last == end())
583		{    // erase all
584		clear();
585		return (begin());
586		}
587		else
588		{    // partial erase, one at a time
589		while (_First != _Last)
590		erase(_First++);
591		return (_List._Make_iter(_First));
592		}
593		}
594
595		size_type erase(const key_type& _Keyval)
596		{    // erase and count all that match _Keyval
597		_Pairii _Where = equal_range(_Keyval);
598		size_type _Num = 0;
599		_Distance(_Where.first, _Where.second, _Num);
600		erase(_Where.first, _Where.second);
601		return (_Num);
602		}
603
604		void erase(const key_type *_First,
605		const key_type *_Last)
606		{    // erase all that match array of keys [_First, _Last)
607		_DEBUG_RANGE(_First, _Last);
608		for (; _First != _Last; ++_First)
609		erase(*_First);
610		}
611
612		void clear()
613		{    // erase all
614		_List.clear();
615		_Init();
616		}
617
618		iterator find(const key_type& _Keyval)
619		{    // find an element in mutable hash table that matches _Keyval
620		return (lower_bound(_Keyval));
621		}
622
623		const_iterator find(const key_type& _Keyval) const
624		{    // find an element in nonmutable hash table that matches _Keyval
625		return (lower_bound(_Keyval));
626		}
627
628		size_type count(const key_type& _Keyval) const
629		{    // count all elements that match _Keyval
630		_Paircc _Ans = equal_range(_Keyval);
631		size_type _Num = 0;
632		_Distance(_Ans.first, _Ans.second, _Num);
633		return (_Num);
634		}
635
636		iterator lower_bound(const key_type& _Keyval)
637		{    // find leftmost not less than _Keyval in mutable hash table
638		size_type _Bucket = _Hashval(_Keyval);
639		iterator _Where;
640		for (_Where = _Get_iter_from_vec(_Vec[_Bucket]); _Vec[_Bucket + 1] != _Where; ++_Where)
641		if (!this->comp(this->_Kfn(*_Where), _Keyval))
642		return (this->comp(_Keyval,
643		this->_Kfn(*_Where)) ? end() : _Where);
644		return (end());
645		}
646
647		const_iterator lower_bound(const key_type& _Keyval) const
648		{    // find leftmost not less than _Keyval in nonmutable hash table
649		size_type _Bucket = _Hashval(_Keyval);
650		const_iterator _Where;
651		for (_Where = _Get_iter_from_vec(_Vec[_Bucket]); _Vec[_Bucket + 1] != _Where; ++_Where)
652		if (!this->comp(this->_Kfn(*_Where), _Keyval))
653		return (this->comp(_Keyval,
654		this->_Kfn(*_Where)) ? end() : _Where);
655		return (end());
656		}
657
658		iterator upper_bound(const key_type& _Keyval)
659		{    // find leftmost not greater than _Keyval in mutable hash table
660		size_type _Bucket = _Hashval(_Keyval);
661		iterator _Where;
662		for (_Where = _Get_iter_from_vec(_Vec[_Bucket + 1]); _Vec[_Bucket] != _Where; )
663		if (!this->comp(_Keyval, this->_Kfn(*--_Where)))
664		return (this->comp(this->_Kfn(*_Where),
665		_Keyval) ? end() : (iterator)++_Where);
666		return (end());
667		}
668
669		const_iterator upper_bound(const key_type& _Keyval) const
670		{    // find leftmost not greater than _Keyval in nonmutable hash table
671		size_type _Bucket = _Hashval(_Keyval);
672		const_iterator _Where;
673		for (_Where = _Get_iter_from_vec(_Vec[_Bucket + 1]); _Vec[_Bucket] != _Where; )
674		if (!this->comp(_Keyval, this->_Kfn(*--_Where)))
675		return (this->comp(this->_Kfn(*_Where),
676		_Keyval) ? end() : (const_iterator)++_Where);
677		return (end());
678		}
679
680		_Pairii equal_range(const key_type& _Keyval)
681		{    // find range equivalent to _Keyval in mutable hash table
682		size_type _Bucket = _Hashval(_Keyval);
683		iterator _First, _Where;
684		for (_Where = _Get_iter_from_vec(_Vec[_Bucket]); _Vec[_Bucket + 1] != _Where; ++_Where)
685		if (!this->comp(this->_Kfn(*_Where), _Keyval))
686		{    // found _First, look for end of range
687		for (_First = _Where; _Vec[_Bucket + 1] != _Where; ++_Where)
688		if (this->comp(_Keyval, this->_Kfn(*_Where)))
689		break;
690		if (_First == _Where)
691		break;
692		return (_Pairii(_First, _Where));
693		}
694		return (_Pairii(end(), end()));
695		}
696
697		_Paircc equal_range(const key_type& _Keyval) const
698		{    // find range equivalent to _Keyval in nonmutable hash table
699		size_type _Bucket = _Hashval(_Keyval);
700		iterator _First, _Where;
701		for (_Where = _Get_iter_from_vec(_Vec[_Bucket]); _Vec[_Bucket + 1] != _Where; ++_Where)
702		if (!this->comp(this->_Kfn(*_Where), _Keyval))
703		{    // found _First, look for end of range
704		for (_First = _Where; _Vec[_Bucket + 1] != _Where; ++_Where)
705		if (this->comp(_Keyval, this->_Kfn(*_Where)))
706		break;
707		if (_First == _Where)
708		break;
709		return (_Paircc(_First, _Where));
710		}
711		return (_Paircc(end(), end()));
712		}
713
714		void swap(_Myt& _Right)
715		{    // exchange contents with _Right
716		if (this != &_Right)
717		{    // different, worth swapping
718		_STD _Swap_adl(this->comp, _Right.comp);
719		this->_List.swap(_Right._List);
720		this->_Vec.swap(_Right._Vec);
721		_STD swap(this->_Mask, _Right._Mask);
722		_STD swap(this->_Maxidx, _Right._Maxidx);
723		_STD swap(this->_Max_bucket_size, _Right._Max_bucket_size);
724		}
725		}
726
727		#if _HAS_TRADITIONAL_STL
728		size_type elems_in_bucket(size_type _Bucket) const
729		{    // return number of elements in bucket
730		return (bucket_size(_Bucket));
731		}
732		#endif /* _HAS_TRADITIONAL_STL */
733
734		protected:
735		void _Copy(const _Myt& _Right)
736		{    // copy entire hash table
737		_Vec.resize(_Right._Vec.size(), end());
738		_Mask = _Right._Mask;
739		_Maxidx = _Right._Maxidx;
740		_Max_bucket_size = _Right._Max_bucket_size;
741		_List.clear();
742
743		_TRY_BEGIN
744		_List.insert(end(), _Right._List.begin(), _Right._List.end());
745		this->comp = _Right.comp;
746		_CATCH_ALL
747		_List.clear();    // list or compare copy failed, bail out
748		fill(_Vec.begin(), _Vec.end(), end());
749		_RERAISE;
750		_CATCH_END
751
752		iterator _Whereto = begin();
753		const_iterator _Wherefrom = _Right.begin();
754		for (size_type _Bucket = 0; _Bucket < _Vec.size(); )
755		if (_Right._Vec[_Bucket] == _Wherefrom)
756		_Vec[_Bucket] = _Whereto, ++_Bucket;
757		else
758		++_Whereto, ++_Wherefrom;
759		}
760
761		void _Grow()
762		{    // grow hash table by one bucket
763		iterator _Plist;
764
765		if (_Vec.size() - 1 <= _Maxidx)
766		{    // table full, double its size
767		_Mask = ((_Vec.size() - 1) << 1) - 1;
768		_Vec.resize(_Mask + 2, end());
769		}
770		else if (_Mask < _Maxidx)
771		_Mask = (_Mask << 1) + 1;
772
773		size_type _Bucket = _Maxidx - (_Mask >> 1) - 1;
774		for (_Plist = _Get_iter_from_vec(_Vec[_Bucket]);
775		_Plist != _Get_iter_from_vec(_Vec[_Bucket + 1]); )
776		{    // split old bucket
777		size_type _Newbucket =
778		this->comp(this->_Kfn(*_Plist)) & _Mask;
779		if (_Newbucket == _Bucket)
780		++_Plist;    // leave element in old bucket
781
782		#if _HAS_ITERATOR_DEBUGGING
783		else if (_Newbucket != _Maxidx)
784		_DEBUG_ERROR("bad hash function");
785		#endif /* _HAS_ITERATOR_DEBUGGING */
786
787		else
788		{    // move element to new bucket
789		size_type _Idx;
790		iterator _Pnext = _Plist;
791		if (++_Pnext != end())
792		{    // not at end, move it
793		for (_Idx = _Bucket; _Plist == _Get_iter_from_vec(_Vec[_Idx]); --_Idx)
794		{    // update end iterators if moving first
795		_Vec[_Idx] = _Pnext;
796		if (_Idx == 0)
797		break;
798		}
799		_List._Splice(end(), _List, _Plist, _Pnext, 0);
800		_Plist = --end();
801		_Vec[_Maxidx + 1] = end();
802		}
803
804		for (_Idx = _Maxidx; _Bucket < _Idx; --_Idx)
805		{    // update end iterators if new bucket filled
806		if (_Get_iter_from_vec(_Vec[_Idx]) != end())
807		break;
808		_Vec[_Idx] = _Plist;
809		}
810
811		if (_Pnext == end())
812		break;
813		else
814		_Plist = _Pnext;
815		}
816		}
817		++_Maxidx;    // open new bucket for hash lookup
818		}
819
820		size_type _Hashval(const key_type& _Keyval) const
821		{    // return hash value, masked and wrapped to current table size
822		size_type _Num = this->comp(_Keyval) & _Mask;
823		if (_Maxidx <= _Num)
824		_Num -= (_Mask >> 1) + 1;
825		return (_Num);
826		}
827
828		void _Init(size_type _Buckets = min_buckets)
829		{    // initialize hash table with _Buckets buckets, leave list alone
830		_Vec.assign(_Buckets + 1, end());
831		_Mask = _Buckets - 1;
832		_Maxidx = _Buckets;
833		}
834
835		_Pairib _Insert(const value_type& _Val, iterator _Where)
836		{    // try to insert (possibly existing) node with value _Val
837		size_type _Bucket = _Hashval(this->_Kfn(_Val));
838		iterator _Plist = _Get_iter_from_vec(_Vec[_Bucket + 1]);
839
840		for (; _Plist != _Get_iter_from_vec(_Vec[_Bucket]); )
841		if (this->comp(this->_Kfn(_Val), this->_Kfn(*--_Plist)))
842		;    // still too high in bucket list
843		else if (_Multi
844		|| this->comp(this->_Kfn(*_Plist), this->_Kfn(_Val)))
845		{    // found insertion point, back up to it
846		++_Plist;
847		break;
848		}
849		else
850		{    // discard new list element and return existing
851		if (_Where != end())
852		_List.erase(_Where);
853		return (_Pairib(_Plist, false));
854		}
855
856		if (_Where != end())
857		_List.splice(_Plist, _List, _Where);    // move element into place
858		else
859		_Where = _List.insert(_Plist, _Val);    // insert new element
860		for (; _Plist == _Get_iter_from_vec(_Vec[_Bucket]); --_Bucket)
861		{    // update end iterators if new first bucket element
862		_Vec[_Bucket] = _Where;
863		if (_Bucket == 0)
864		break;
865		}
866
867		if (max_load_factor() < load_factor())
868		#if _HAS_INCREMENTAL_HASH
869		_Grow();    // too dense, need to grow hash table
870
871		#else /* _HAS_INCREMENTAL_HASH */
872		{    // rehash to bigger table
873		size_type _Maxsize = _Vec.max_size() / 2;
874		size_type _Newsize = bucket_count();
875
876		for (int _Idx = 0; _Idx < 3 && _Newsize < _Maxsize; ++_Idx)
877		_Newsize *= 2;    // multiply safely by 8
878		_Init(_Newsize);
879		_Reinsert();
880		}
881		#endif /* _HAS_INCREMENTAL_HASH */
882
883		return (_Pairib(_Where, true));    // return iterator for new element
884		}
885
886		void _Reinsert()
887		{    // insert elements at beginning of list into table
888		iterator _First;
889		for (; (_First = _List.begin()) != _Get_iter_from_vec(_Vec[0]); )
890		_Insert(*_First, _First);
891		}
892
893		_Mylist _List;    // the list of elements, must initialize before _Vec
894		_Myvec _Vec;    // the vector of list iterators
895		size_type _Mask;    // the key mask
896		size_type _Maxidx;    // current maximum key value
897		float _Max_bucket_size;    // current maximum bucket size
898		};
899
900		// _Hash TEMPLATE OPERATORS
901		template<class _Ty> inline
902		bool operator==(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
903		{    // test for hash table equality
904		return (_Left.size() == _Right.size()
905		&& equal(_Left.begin(), _Left.end(), _Right.begin()));
906		}
907
908		template<class _Ty> inline
909		bool operator!=(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
910		{    // test for hash table inequality
911		return (!(_Left == _Right));
912		}
913
914		template<class _Ty> inline
915		bool operator<(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
916		{    // test if _Left < _Right for hash tables
917		return (lexicographical_compare(_Left.begin(), _Left.end(),
918		_Right.begin(), _Right.end()));
919		}
920
921		template<class _Ty> inline
922		bool operator>(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
923		{    // test if _Left > _Right for hash tables
924		return (_Right < _Left);
925		}
926
927		template<class _Ty> inline
928		bool operator<=(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
929		{    // test if _Left <= _Right for hash tables
930		return (!(_Right < _Left));
931		}
932
933		template<class _Ty> inline
934		bool operator>=(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
935		{    // test if _Left >= _Right for hash tables
936		return (!(_Left < _Right));
937		}
938		_STDEXT_END
939
940		_STD_BEGIN
941
942		// _Hash implements a performant swap
943		template <class _Traits>
944		class _Move_operation_category<_STDEXT _Hash<_Traits> >
945		{
946		public:
947		typedef _Swap_move_tag _Move_cat;
948		};
949
950		_STD_END
951
952		#ifdef _MSC_VER
953		#pragma warning(default: 4127)
954		#pragma warning(pop)
955		#pragma pack(pop)
956		#endif  /* _MSC_VER */
957
958		#endif /* RC_INVOKED */
959		#endif /* _XHASH_ */
960
961		/*
962		* Copyright (c) 1992-2008 by P.J. Plauger.  ALL RIGHTS RESERVED.
963		* Consult your license regarding permissions and restrictions.
964		V5.05:0009 */
965
966
967