1		// set standard header
2		#pragma once
3		#ifndef _SET_
4		#define _SET_
5		#ifndef RC_INVOKED
6		#include <xtree>
7
8		#ifdef _MSC_VER
9		#pragma pack(push,_CRT_PACKING)
10		#pragma warning(push,3)
11		#endif  /* _MSC_VER */
12		_STD_BEGIN
13
14		// TEMPLATE CLASS _Tset_traits
15		template<class _Kty,    // key/value type
16		class _Pr,    // comparator predicate type
17		class _Alloc,    // actual allocator type (should be value allocator)
18		bool _Mfl>    // true if multiple equivalent keys are permitted
19		class _Tset_traits
20		: public _CONTAINER_BASE_AUX_ALLOC<_Alloc>
21		{    // traits required to make _Tree behave like a set
22		public:
23		typedef _Kty key_type;
24		typedef _Kty value_type;
25		typedef _Pr key_compare;
26		typedef typename _Alloc::template rebind<value_type>::other
27		allocator_type;
28
29		typedef typename allocator_type::const_pointer _ITptr;
30		typedef typename allocator_type::const_reference _IReft;
31
32		enum
33		{    // make multi parameter visible as an enumeration constant
34		_Multi = _Mfl};
35
36		_Tset_traits(_Pr _Parg, _Alloc _Al)
37		: _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), comp(_Parg)
38		{    // construct with specified comparator
39		}
40
41		typedef key_compare value_compare;
42
43		static const _Kty& _Kfn(const value_type& _Val)
44		{    // extract key from element value
45		return (_Val);
46		}
47
48		_Pr comp;    // the comparator predicate for keys
49		};
50
51		// TEMPLATE CLASS set
52		template<class _Kty,
53		class _Pr = less<_Kty>,
54		class _Alloc = allocator<_Kty> >
55		class set
56		: public _Tree<_Tset_traits<_Kty, _Pr, _Alloc, false> >
57		{    // ordered red-black tree of key values, unique keys
58		public:
59		typedef set<_Kty, _Pr, _Alloc> _Myt;

Lines 60 ... 69 are skipped.

70		typedef typename _Mybase::const_reference const_reference;
71		typedef typename _Mybase::iterator iterator;
72		typedef typename _Mybase::const_iterator const_iterator;
73		typedef typename _Mybase::reverse_iterator reverse_iterator;
74		typedef typename _Mybase::const_reverse_iterator
75		const_reverse_iterator;
76		typedef typename _Mybase::value_type value_type;
77
78		set()
79		: _Mybase(key_compare(), allocator_type())
80		{    // construct empty set from defaults
81		}
82
83		explicit set(const key_compare& _Pred)
84		: _Mybase(_Pred, allocator_type())
85		{    // construct empty set from comparator
86		}
87
88		set(const key_compare& _Pred, const allocator_type& _Al)
89		: _Mybase(_Pred, _Al)
90		{    // construct empty set from comparator and allocator
91		}
92
93		template<class _Iter>
94		set(_Iter _First, _Iter _Last)
95		: _Mybase(key_compare(), allocator_type())
96		{    // construct set from [_First, _Last), defaults
97		_DEBUG_RANGE(_First, _Last);
98		for (; _First != _Last; ++_First)
99		this->insert(*_First);
100		}
101
102		template<class _Iter>
103		set(_Iter _First, _Iter _Last,
104		const key_compare& _Pred)
105		: _Mybase(_Pred, allocator_type())
106		{    // construct set from [_First, _Last), comparator
107		_DEBUG_RANGE(_First, _Last);
108		for (; _First != _Last; ++_First)
109		this->insert(*_First);
110		}
111
112		template<class _Iter>
113		set(_Iter _First, _Iter _Last,
114		const key_compare& _Pred, const allocator_type& _Al)
115		: _Mybase(_Pred, _Al)
116		{    // construct set from [_First, _Last), defaults, and allocator
117		_DEBUG_RANGE(_First, _Last);
118		for (; _First != _Last; ++_First)
119		this->insert(*_First);
120		}
121
122		#if _HAS_STRICT_CONFORMANCE
123		void erase(const_iterator _Where)
124		{    // erase element at _Where
125		_Mybase::erase(_Where);
126		}
127
128		size_type erase(const key_type& _Keyval)
129		{    // erase and count all that match _Keyval
130		return (_Mybase::erase(_Keyval));
131		}
132
133		void erase(const_iterator _First, const_iterator _Last)
134		{    // erase [_First, _Last)
135		_Mybase::erase(_First, _Last);
136		}
137		#endif /* _HAS_STRICT_CONFORMANCE */
138
139
140
141		};
142
143		// set implements a performant swap
144		template<class _Kty, class _Pr, class _Alloc>
145		class _Move_operation_category<set<_Kty, _Pr, _Alloc> >
146		{
147		public:
148		typedef _Swap_move_tag _Move_cat;
149		};
150
151		template<class _Kty,
152		class _Pr,
153		class _Alloc> inline
154		void swap(set<_Kty, _Pr, _Alloc>& _Left,
155		set<_Kty, _Pr, _Alloc>& _Right)
156		{    // swap _Left and _Right sets
157		_Left.swap(_Right);
158		}
159
160		// TEMPLATE CLASS multiset
161		template<class _Kty,
162		class _Pr = less<_Kty>,
163		class _Alloc = allocator<_Kty> >
164		class multiset
165		: public _Tree<_Tset_traits<_Kty, _Pr, _Alloc, true> >
166		{    // ordered red-black tree of key values, non-unique keys
167		public:
168		typedef multiset<_Kty, _Pr, _Alloc> _Myt;
169		typedef _Tree<_Tset_traits<_Kty, _Pr, _Alloc, true> > _Mybase;
170		typedef _Kty key_type;
171		typedef _Pr key_compare;
172		typedef typename _Mybase::value_compare value_compare;
173		typedef typename _Mybase::allocator_type allocator_type;
174		typedef typename _Mybase::size_type size_type;
175		typedef typename _Mybase::difference_type difference_type;
176		typedef typename _Mybase::pointer pointer;
177		typedef typename _Mybase::const_pointer const_pointer;
178		typedef typename _Mybase::reference reference;
179		typedef typename _Mybase::const_reference const_reference;
180		typedef typename _Mybase::iterator iterator;
181		typedef typename _Mybase::const_iterator const_iterator;
182		typedef typename _Mybase::reverse_iterator reverse_iterator;
183		typedef typename _Mybase::const_reverse_iterator
184		const_reverse_iterator;
185		typedef typename _Mybase::value_type value_type;
186
187		multiset()
188		: _Mybase(key_compare(), allocator_type())
189		{    // construct empty set from defaults
190		}
191
192		explicit multiset(const key_compare& _Pred)
193		: _Mybase(_Pred, allocator_type())
194		{    // construct empty set from comparator
195		}
196
197		multiset(const key_compare& _Pred, const allocator_type& _Al)
198		: _Mybase(_Pred, _Al)
199		{    // construct empty set from comparator and allocator
200		}
201
202		template<class _Iter>
203		multiset(_Iter _First, _Iter _Last)
204		: _Mybase(key_compare(), allocator_type())
205		{    // construct set from [_First, _Last)
206		_DEBUG_RANGE(_First, _Last);
207		for (; _First != _Last; ++_First)
208		this->insert(*_First);
209		}
210
211		template<class _Iter>
212		multiset(_Iter _First, _Iter _Last,
213		const key_compare& _Pred)
214		: _Mybase(_Pred, allocator_type())
215		{    // construct set from [_First, _Last), comparator
216		_DEBUG_RANGE(_First, _Last);
217		for (; _First != _Last; ++_First)
218		this->insert(*_First);
219		}
220
221		template<class _Iter>
222		multiset(_Iter _First, _Iter _Last,
223		const key_compare& _Pred, const allocator_type& _Al)
224		: _Mybase(_Pred, _Al)
225		{    // construct set from [_First, _Last), comparator, and allocator
226		_DEBUG_RANGE(_First, _Last);
227		for (; _First != _Last; ++_First)
228		this->insert(*_First);
229		}
230
231		#if _HAS_STRICT_CONFORMANCE
232		void erase(const_iterator _Where)
233		{    // erase element at _Where
234		_Mybase::erase(_Where);
235		}
236
237		size_type erase(const key_type& _Keyval)
238		{    // erase and count all that match _Keyval
239		return (_Mybase::erase(_Keyval));
240		}
241
242		void erase(const_iterator _First, const_iterator _Last)
243		{    // erase [_First, _Last)
244		_Mybase::erase(_First, _Last);
245		}
246		#endif /* _HAS_STRICT_CONFORMANCE */
247
248		iterator insert(const value_type& _Val)
249		{    // insert a key value
250		return (_Mybase::insert(_Val).first);
251		}
252
253		iterator insert(const_iterator _Where, const value_type& _Val)
254		{    // insert a key value, with hint
255		return (_Mybase::insert(_Where, _Val));
256		}
257
258		template<class _Iter>
259		void insert(_Iter _First, _Iter _Last)
260		{    // insert [_First, _Last)
261
262		#if _HAS_ITERATOR_DEBUGGING
263		_DEBUG_RANGE(_First, _Last);
264		#endif /* _HAS_ITERATOR_DEBUGGING */
265
266		for (; _First != _Last; ++_First)
267		this->insert(*_First);
268		}
269		};
270
271		// multiset implements a performant swap
272		template<class _Kty, class _Pr, class _Alloc>
273		class _Move_operation_category<multiset<_Kty, _Pr, _Alloc> >
274		{
275		public:
276		typedef _Swap_move_tag _Move_cat;
277		};
278
279		template<class _Kty,
280		class _Pr,
281		class _Alloc> inline
282		void swap(multiset<_Kty, _Pr, _Alloc>& _Left,
283		multiset<_Kty, _Pr, _Alloc>& _Right)
284		{    // swap _Left and _Right multisets
285		_Left.swap(_Right);
286		}
287
288		#if _HAS_TRADITIONAL_STL
289		#define __set__    set
290		#define __multiset__    multiset
291		#endif /* _HAS_TRADITIONAL_STL */
292
293		_STD_END
294		#ifdef _MSC_VER
295		#pragma warning(pop)
296		#pragma pack(pop)
297		#endif  /* _MSC_VER */
298
299		#endif /* RC_INVOKED */
300		#endif /* _SET_ */
301
302		/*
303		* Copyright (c) 1992-2007 by P.J. Plauger.  ALL RIGHTS RESERVED.
304		* Consult your license regarding permissions and restrictions.
305		V5.03:0009 */
306