1 : // map standard header
2 : #pragma once
3 : #ifndef _MAP_
4 : #define _MAP_
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 _Tmap_traits
15 : template<class _Kty, // key type
16 : class _Ty, // mapped type
17 : class _Pr, // comparator predicate type
18 : class _Alloc, // actual allocator type (should be value allocator)
19 : bool _Mfl> // true if multiple equivalent keys are permitted
20 : class _Tmap_traits
21 : : public _CONTAINER_BASE_AUX_ALLOC<_Alloc>
22 : { // traits required to make _Tree behave like a map
23 : public:
24 : typedef _Kty key_type;
25 : typedef pair<const _Kty, _Ty> value_type;
26 : typedef _Pr key_compare;
27 : typedef typename _Alloc::template rebind<value_type>::other
28 : allocator_type;
29 :
30 : typedef typename allocator_type::pointer _ITptr;
31 : typedef typename allocator_type::reference _IReft;
32 :
33 : enum
34 : { // make multi parameter visible as an enum constant
35 : _Multi = _Mfl};
36 :
37 : _Tmap_traits(_Pr _Parg, _Alloc _Al)
38 : : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), comp(_Parg)
39 1 : { // construct with specified comparator
40 1 : }
41 :
42 : class value_compare
43 : : public binary_function<value_type, value_type, bool>
44 : { // functor for comparing two element values
45 : friend class _Tmap_traits<_Kty, _Ty, _Pr, _Alloc, _Mfl>;
46 :
47 : public:
48 : bool operator()(const value_type& _Left,
49 : const value_type& _Right) const
50 : { // test if _Left precedes _Right by comparing just keys
51 : return (comp(_Left.first, _Right.first));
52 : }
53 :
54 : value_compare(key_compare _Pred)
55 : : comp(_Pred)
56 : { // construct with specified predicate
57 : }
58 :
59 : protected:
60 : key_compare comp; // the comparator predicate for keys
61 : };
62 :
63 : static const _Kty& _Kfn(const value_type& _Val)
64 1 : { // extract key from element value
65 1 : return (_Val.first);
66 1 : }
67 :
68 : _Pr comp; // the comparator predicate for keys
69 : };
70 :
71 : // TEMPLATE CLASS map
72 : template<class _Kty,
73 : class _Ty,
74 : class _Pr = less<_Kty>,
75 : class _Alloc = allocator<pair<const _Kty, _Ty> > >
76 : class map
77 : : public _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, false> >
78 : { // ordered red-black tree of {key, mapped} values, unique keys
79 : public:
80 : typedef map<_Kty, _Ty, _Pr, _Alloc> _Myt;
81 : typedef _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, false> > _Mybase;
82 : typedef _Kty key_type;
83 : typedef _Ty mapped_type;
84 : typedef _Ty referent_type; // retained
85 : typedef _Pr key_compare;
86 : typedef typename _Mybase::value_compare value_compare;
87 : typedef typename _Mybase::allocator_type allocator_type;
88 : typedef typename _Mybase::size_type size_type;
89 : typedef typename _Mybase::difference_type difference_type;
90 : typedef typename _Mybase::pointer pointer;
91 : typedef typename _Mybase::const_pointer const_pointer;
92 : typedef typename _Mybase::reference reference;
93 : typedef typename _Mybase::const_reference const_reference;
94 : typedef typename _Mybase::iterator iterator;
95 : typedef typename _Mybase::const_iterator const_iterator;
96 : typedef typename _Mybase::reverse_iterator reverse_iterator;
97 : typedef typename _Mybase::const_reverse_iterator
98 : const_reverse_iterator;
99 : typedef typename _Mybase::value_type value_type;
100 :
101 : map()
102 : : _Mybase(key_compare(), allocator_type())
103 1 : { // construct empty map from defaults
104 1 : }
105 :
106 : explicit map(const key_compare& _Pred)
107 : : _Mybase(_Pred, allocator_type())
108 : { // construct empty map from comparator
109 : }
110 :
111 : map(const key_compare& _Pred, const allocator_type& _Al)
112 : : _Mybase(_Pred, _Al)
113 : { // construct empty map from comparator and allocator
114 : }
115 :
116 : template<class _Iter>
117 : map(_Iter _First, _Iter _Last)
118 : : _Mybase(key_compare(), allocator_type())
119 : { // construct map from [_First, _Last), defaults
120 : _DEBUG_RANGE(_First, _Last);
121 : for (; _First != _Last; ++_First)
122 : this->insert(*_First);
123 : }
124 :
125 : template<class _Iter>
126 : map(_Iter _First, _Iter _Last,
127 : const key_compare& _Pred)
128 : : _Mybase(_Pred, allocator_type())
129 : { // construct map from [_First, _Last), comparator
130 : _DEBUG_RANGE(_First, _Last);
131 : for (; _First != _Last; ++_First)
132 : this->insert(*_First);
133 : }
134 :
135 : template<class _Iter>
136 : map(_Iter _First, _Iter _Last,
137 : const key_compare& _Pred, const allocator_type& _Al)
138 : : _Mybase(_Pred, _Al)
139 : { // construct map from [_First, _Last), comparator, and allocator
140 : _DEBUG_RANGE(_First, _Last);
141 : for (; _First != _Last; ++_First)
142 : this->insert(*_First);
143 : }
144 :
145 : #if _HAS_STRICT_CONFORMANCE
146 : void erase(const_iterator _Where)
147 : { // erase element at _Where
148 : _Mybase::erase(_Where);
149 : }
150 :
151 : size_type erase(const key_type& _Keyval)
152 : { // erase and count all that match _Keyval
153 : return (_Mybase::erase(_Keyval));
154 : }
155 :
156 : void erase(const_iterator _First, const_iterator _Last)
157 : { // erase [_First, _Last)
158 : _Mybase::erase(_First, _Last);
159 : }
160 :
161 : void clear()
162 : {
163 : _Mybase::clear();
164 : }
165 : #endif /* _HAS_STRICT_CONFORMANCE */
166 :
167 : mapped_type& operator[](const key_type& _Keyval)
168 1 : { // find element matching _Keyval or insert with default mapped
169 1 : iterator _Where = this->lower_bound(_Keyval);
170 : if (_Where == this->end()
171 1 : || this->comp(_Keyval, this->_Key(_Where._Mynode())))
172 : _Where = this->insert(_Where,
173 1 : value_type(_Keyval, mapped_type()));
174 1 : return ((*_Where).second);
175 1 : }
176 : };
177 :
178 : // map implements a performant swap
179 : template<class _Kty, class _Ty, class _Pr, class _Alloc>
180 : class _Move_operation_category<map<_Kty, _Ty, _Pr, _Alloc> >
181 : {
182 : public:
183 : typedef _Swap_move_tag _Move_cat;
184 : };
185 :
186 : template<class _Kty,
187 : class _Ty,
188 : class _Pr,
189 : class _Alloc> inline
190 : void swap(map<_Kty, _Ty, _Pr, _Alloc>& _Left,
191 : map<_Kty, _Ty, _Pr, _Alloc>& _Right)
192 : { // swap _Left and _Right maps
193 : _Left.swap(_Right);
194 : }
195 :
196 : // TEMPLATE CLASS multimap
197 : template<class _Kty,
198 : class _Ty,
199 : class _Pr = less<_Kty>,
200 : class _Alloc = allocator<pair<const _Kty, _Ty> > >
201 : class multimap
202 : : public _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, true> >
203 : { // ordered red-black tree of {key, mapped} values, non-unique keys
204 : public:
205 : typedef multimap<_Kty, _Ty, _Pr, _Alloc> _Myt;
206 : typedef _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, true> > _Mybase;
207 : typedef _Kty key_type;
208 : typedef _Ty mapped_type;
209 : typedef _Ty referent_type; // retained
210 : typedef _Pr key_compare;
211 : typedef typename _Mybase::value_compare value_compare;
212 : typedef typename _Mybase::allocator_type allocator_type;
213 : typedef typename _Mybase::size_type size_type;
214 : typedef typename _Mybase::difference_type difference_type;
215 : typedef typename _Mybase::pointer pointer;
216 : typedef typename _Mybase::const_pointer const_pointer;
217 : typedef typename _Mybase::reference reference;
218 : typedef typename _Mybase::const_reference const_reference;
219 : typedef typename _Mybase::iterator iterator;
220 : typedef typename _Mybase::const_iterator const_iterator;
221 : typedef typename _Mybase::reverse_iterator reverse_iterator;
222 : typedef typename _Mybase::const_reverse_iterator
223 : const_reverse_iterator;
224 : typedef typename _Mybase::value_type value_type;
225 :
226 : multimap()
227 : : _Mybase(key_compare(), allocator_type())
228 : { // construct empty map from defaults
229 : }
230 :
231 : explicit multimap(const key_compare& _Pred)
232 : : _Mybase(_Pred, allocator_type())
233 : { // construct empty map from comparator
234 : }
235 : multimap(const key_compare& _Pred, const allocator_type& _Al)
236 : : _Mybase(_Pred, _Al)
237 : { // construct empty map from comparator and allocator
238 : }
239 :
240 : template<class _Iter>
241 : multimap(_Iter _First, _Iter _Last)
242 : : _Mybase(key_compare(), allocator_type())
243 : { // construct map from [_First, _Last), defaults
244 : _DEBUG_RANGE(_First, _Last);
245 : for (; _First != _Last; ++_First)
246 : insert(*_First);
247 : }
248 :
249 : template<class _Iter>
250 : multimap(_Iter _First, _Iter _Last,
251 : const key_compare& _Pred)
252 : : _Mybase(_Pred, allocator_type())
253 : { // construct map from [_First, _Last), comparator
254 : _DEBUG_RANGE(_First, _Last);
255 : for (; _First != _Last; ++_First)
256 : insert(*_First);
257 : }
258 :
259 : template<class _Iter>
260 : multimap(_Iter _First, _Iter _Last,
261 : const key_compare& _Pred, const allocator_type& _Al)
262 : : _Mybase(_Pred, _Al)
263 : { // construct map from [_First, _Last), comparator, and allocator
264 : _DEBUG_RANGE(_First, _Last);
265 : for (; _First != _Last; ++_First)
266 : insert(*_First);
267 : }
268 :
269 : iterator insert(const value_type& _Val)
270 : { // insert a {key, mapped} value
271 : return (_Mybase::insert(_Val).first);
272 : }
273 :
274 : iterator insert(const_iterator _Where, const value_type& _Val)
275 : { // insert a {key, mapped} value, with hint
276 : return (_Mybase::insert(_Where, _Val));
277 : }
278 :
279 : #if _HAS_STRICT_CONFORMANCE
280 : void erase(const_iterator _Where)
281 : { // erase element at _Where
282 : _Mybase::erase(_Where);
283 : }
284 :
285 : size_type erase(const key_type& _Keyval)
286 : { // erase and count all that match _Keyval
287 : return (_Mybase::erase(_Keyval));
288 : }
289 :
290 : void erase(const_iterator _First, const_iterator _Last)
291 : { // erase [_First, _Last)
292 : _Mybase::erase(_First, _Last);
293 : }
294 : #endif /* _HAS_STRICT_CONFORMANCE */
295 :
296 : template<class _Iter>
297 : void insert(_Iter _First, _Iter _Last)
298 : { // insert [_First, _Last), arbitrary iterators
299 :
300 : #if _HAS_ITERATOR_DEBUGGING
301 : _DEBUG_RANGE(_First, _Last);
302 : #endif /* _HAS_ITERATOR_DEBUGGING */
303 :
304 : for (; _First != _Last; ++_First)
305 : insert(*_First);
306 : }
307 : };
308 :
309 : // multimap implements a performant swap
310 : template<class _Kty, class _Ty, class _Pr, class _Alloc>
311 : class _Move_operation_category<multimap<_Kty, _Ty, _Pr, _Alloc> >
312 : {
313 : public:
314 : typedef _Swap_move_tag _Move_cat;
315 : };
316 :
317 : template<class _Kty,
318 : class _Ty,
319 : class _Pr,
320 : class _Alloc> inline
321 : void swap(multimap<_Kty, _Ty, _Pr, _Alloc>& _Left,
322 : multimap<_Kty, _Ty, _Pr, _Alloc>& _Right)
323 : { // swap _Left and _Right multimaps
324 : _Left.swap(_Right);
325 : }
326 :
327 : #if _HAS_TRADITIONAL_STL
328 : #define __map__ map
329 : #define __multimap__ multimap
330 : #endif /* _HAS_TRADITIONAL_STL */
331 :
332 : _STD_END
333 : #ifdef _MSC_VER
334 : #pragma warning(pop)
335 : #pragma pack(pop)
336 : #endif /* _MSC_VER */
337 :
338 : #endif /* RC_INVOKED */
339 : #endif /* _MAP_ */
340 :
341 : /*
342 : * Copyright (c) 1992-2007 by P.J. Plauger. ALL RIGHTS RESERVED.
343 : * Consult your license regarding permissions and restrictions.
344 : V5.03:0009 */
|
