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 1 : { // construct with specified comparator
39 1 : }
40 :
41 : typedef key_compare value_compare;
42 :
43 : static const _Kty& _Kfn(const value_type& _Val)
44 1 : { // extract key from element value
45 1 : return (_Val);
46 1 : }
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;
60 : typedef _Tree<_Tset_traits<_Kty, _Pr, _Alloc, false> > _Mybase;
61 : typedef _Kty key_type;
62 : typedef _Pr key_compare;
63 : typedef typename _Mybase::value_compare value_compare;
64 : typedef typename _Mybase::allocator_type allocator_type;
65 : typedef typename _Mybase::size_type size_type;
66 : typedef typename _Mybase::difference_type difference_type;
67 : typedef typename _Mybase::pointer pointer;
68 : typedef typename _Mybase::const_pointer const_pointer;
69 : typedef typename _Mybase::reference reference;
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 1 : { // construct empty set from defaults
81 1 : }
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 */
|
