4 * Hewlett-Packard Company
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
10 * Moscow Center for SPARC Technology
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
30 #ifndef _STLP_INTERNAL_MAP_H
31 #define _STLP_INTERNAL_MAP_H
33 #ifndef _STLP_INTERNAL_TREE_H
34 # include <stl/_tree.h>
39 //Specific iterator traits creation
40 _STLP_CREATE_ITERATOR_TRAITS(MapTraitsT
, traits
)
42 template <class _Key
, class _Tp
, _STLP_DFL_TMPL_PARAM(_Compare
, less
<_Key
> ),
43 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key
, _Tp
) >
45 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
46 : public __stlport_class
<map
<_Key
, _Tp
, _Compare
, _Alloc
> >
49 typedef map
<_Key
, _Tp
, _Compare
, _Alloc
> _Self
;
54 typedef _Key key_type
;
55 typedef _Tp data_type
;
56 typedef _Tp mapped_type
;
57 typedef pair
<_STLP_CONST _Key
, _Tp
> value_type
;
58 typedef _Compare key_compare
;
61 : public binary_function
<value_type
, value_type
, bool> {
62 friend class map
<_Key
,_Tp
,_Compare
,_Alloc
>;
64 //c is a Standard name (23.3.1), do no make it STLport naming convention compliant.
66 value_compare(_Compare __c
) : comp(__c
) {}
68 bool operator()(const value_type
& __x
, const value_type
& __y
) const
69 { return comp(__x
.first
, __y
.first
); }
73 typedef _STLP_PRIV _MapTraitsT
<value_type
> _MapTraits
;
76 //Following typedef have to be public for __move_traits specialization.
77 typedef _STLP_PRIV _Rb_tree
<key_type
, key_compare
,
78 value_type
, _STLP_SELECT1ST(value_type
, _Key
),
79 _MapTraits
, _Alloc
> _Rep_type
;
81 typedef typename
_Rep_type::pointer pointer
;
82 typedef typename
_Rep_type::const_pointer const_pointer
;
83 typedef typename
_Rep_type::reference reference
;
84 typedef typename
_Rep_type::const_reference const_reference
;
85 typedef typename
_Rep_type::iterator iterator
;
86 typedef typename
_Rep_type::const_iterator const_iterator
;
87 typedef typename
_Rep_type::reverse_iterator reverse_iterator
;
88 typedef typename
_Rep_type::const_reverse_iterator const_reverse_iterator
;
89 typedef typename
_Rep_type::size_type size_type
;
90 typedef typename
_Rep_type::difference_type difference_type
;
91 typedef typename
_Rep_type::allocator_type allocator_type
;
94 _Rep_type _M_t
; // red-black tree representing map
95 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type
)
98 // allocation/deallocation
99 map() : _M_t(_Compare(), allocator_type()) {}
100 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
101 explicit map(const _Compare
& __comp
,
102 const allocator_type
& __a
= allocator_type())
104 explicit map(const _Compare
& __comp
)
105 : _M_t(__comp
, allocator_type()) {}
106 explicit map(const _Compare
& __comp
, const allocator_type
& __a
)
108 : _M_t(__comp
, __a
) {}
110 #if defined (_STLP_MEMBER_TEMPLATES)
111 template <class _InputIterator
>
112 map(_InputIterator __first
, _InputIterator __last
)
113 : _M_t(_Compare(), allocator_type())
114 { _M_t
.insert_unique(__first
, __last
); }
116 template <class _InputIterator
>
117 map(_InputIterator __first
, _InputIterator __last
, const _Compare
& __comp
,
118 const allocator_type
& __a _STLP_ALLOCATOR_TYPE_DFL
)
119 : _M_t(__comp
, __a
) { _M_t
.insert_unique(__first
, __last
); }
121 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
122 template <class _InputIterator
>
123 map(_InputIterator __first
, _InputIterator __last
, const _Compare
& __comp
)
124 : _M_t(__comp
, allocator_type()) { _M_t
.insert_unique(__first
, __last
); }
128 map(const value_type
* __first
, const value_type
* __last
)
129 : _M_t(_Compare(), allocator_type())
130 { _M_t
.insert_unique(__first
, __last
); }
132 map(const value_type
* __first
,
133 const value_type
* __last
, const _Compare
& __comp
,
134 const allocator_type
& __a
= allocator_type())
135 : _M_t(__comp
, __a
) { _M_t
.insert_unique(__first
, __last
); }
137 map(const_iterator __first
, const_iterator __last
)
138 : _M_t(_Compare(), allocator_type())
139 { _M_t
.insert_unique(__first
, __last
); }
141 map(const_iterator __first
, const_iterator __last
, const _Compare
& __comp
,
142 const allocator_type
& __a
= allocator_type())
143 : _M_t(__comp
, __a
) { _M_t
.insert_unique(__first
, __last
); }
144 #endif /* _STLP_MEMBER_TEMPLATES */
146 map(const _Self
& __x
) : _M_t(__x
._M_t
) {}
148 #if !defined (_STLP_NO_MOVE_SEMANTIC)
149 map(__move_source
<_Self
> src
)
150 : _M_t(__move_source
<_Rep_type
>(src
.get()._M_t
)) {}
153 _Self
& operator=(const _Self
& __x
) {
159 key_compare
key_comp() const { return _M_t
.key_comp(); }
160 value_compare
value_comp() const { return value_compare(_M_t
.key_comp()); }
161 allocator_type
get_allocator() const { return _M_t
.get_allocator(); }
163 iterator
begin() { return _M_t
.begin(); }
164 const_iterator
begin() const { return _M_t
.begin(); }
165 iterator
end() { return _M_t
.end(); }
166 const_iterator
end() const { return _M_t
.end(); }
167 reverse_iterator
rbegin() { return _M_t
.rbegin(); }
168 const_reverse_iterator
rbegin() const { return _M_t
.rbegin(); }
169 reverse_iterator
rend() { return _M_t
.rend(); }
170 const_reverse_iterator
rend() const { return _M_t
.rend(); }
171 bool empty() const { return _M_t
.empty(); }
172 size_type
size() const { return _M_t
.size(); }
173 size_type
max_size() const { return _M_t
.max_size(); }
174 _STLP_TEMPLATE_FOR_CONT_EXT
175 _Tp
& operator[](const _KT
& __k
) {
176 iterator __i
= lower_bound(__k
);
177 // __i->first is greater than or equivalent to __k.
178 if (__i
== end() || key_comp()(__k
, (*__i
).first
))
179 __i
= insert(__i
, value_type(__k
, _STLP_DEFAULT_CONSTRUCTED(_Tp
)));
180 return (*__i
).second
;
182 void swap(_Self
& __x
) { _M_t
.swap(__x
._M_t
); }
183 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
184 void _M_swap_workaround(_Self
& __x
) { swap(__x
); }
188 pair
<iterator
,bool> insert(const value_type
& __x
)
189 { return _M_t
.insert_unique(__x
); }
190 iterator
insert(iterator __pos
, const value_type
& __x
)
191 { return _M_t
.insert_unique(__pos
, __x
); }
192 #ifdef _STLP_MEMBER_TEMPLATES
193 template <class _InputIterator
>
194 void insert(_InputIterator __first
, _InputIterator __last
)
195 { _M_t
.insert_unique(__first
, __last
); }
197 void insert(const value_type
* __first
, const value_type
* __last
)
198 { _M_t
.insert_unique(__first
, __last
); }
199 void insert(const_iterator __first
, const_iterator __last
)
200 { _M_t
.insert_unique(__first
, __last
); }
201 #endif /* _STLP_MEMBER_TEMPLATES */
203 void erase(iterator __pos
) { _M_t
.erase(__pos
); }
204 size_type
erase(const key_type
& __x
) { return _M_t
.erase_unique(__x
); }
205 void erase(iterator __first
, iterator __last
) { _M_t
.erase(__first
, __last
); }
206 void clear() { _M_t
.clear(); }
209 _STLP_TEMPLATE_FOR_CONT_EXT
210 iterator
find(const _KT
& __x
) { return _M_t
.find(__x
); }
211 _STLP_TEMPLATE_FOR_CONT_EXT
212 const_iterator
find(const _KT
& __x
) const { return _M_t
.find(__x
); }
213 _STLP_TEMPLATE_FOR_CONT_EXT
214 size_type
count(const _KT
& __x
) const { return _M_t
.find(__x
) == _M_t
.end() ? 0 : 1; }
215 _STLP_TEMPLATE_FOR_CONT_EXT
216 iterator
lower_bound(const _KT
& __x
) { return _M_t
.lower_bound(__x
); }
217 _STLP_TEMPLATE_FOR_CONT_EXT
218 const_iterator
lower_bound(const _KT
& __x
) const { return _M_t
.lower_bound(__x
); }
219 _STLP_TEMPLATE_FOR_CONT_EXT
220 iterator
upper_bound(const _KT
& __x
) { return _M_t
.upper_bound(__x
); }
221 _STLP_TEMPLATE_FOR_CONT_EXT
222 const_iterator
upper_bound(const _KT
& __x
) const { return _M_t
.upper_bound(__x
); }
224 _STLP_TEMPLATE_FOR_CONT_EXT
225 pair
<iterator
,iterator
> equal_range(const _KT
& __x
)
226 { return _M_t
.equal_range_unique(__x
); }
227 _STLP_TEMPLATE_FOR_CONT_EXT
228 pair
<const_iterator
,const_iterator
> equal_range(const _KT
& __x
) const
229 { return _M_t
.equal_range_unique(__x
); }
232 //Specific iterator traits creation
233 _STLP_CREATE_ITERATOR_TRAITS(MultimapTraitsT
, traits
)
235 template <class _Key
, class _Tp
, _STLP_DFL_TMPL_PARAM(_Compare
, less
<_Key
> ),
236 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key
, _Tp
) >
238 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
239 : public __stlport_class
<multimap
<_Key
, _Tp
, _Compare
, _Alloc
> >
242 typedef multimap
<_Key
, _Tp
, _Compare
, _Alloc
> _Self
;
247 typedef _Key key_type
;
248 typedef _Tp data_type
;
249 typedef _Tp mapped_type
;
250 typedef pair
<_STLP_CONST _Key
, _Tp
> value_type
;
251 typedef _Compare key_compare
;
253 class value_compare
: public binary_function
<value_type
, value_type
, bool> {
254 friend class multimap
<_Key
,_Tp
,_Compare
,_Alloc
>;
256 //comp is a Standard name (23.3.2), do no make it STLport naming convention compliant.
258 value_compare(_Compare __c
) : comp(__c
) {}
260 bool operator()(const value_type
& __x
, const value_type
& __y
) const
261 { return comp(__x
.first
, __y
.first
); }
265 //Specific iterator traits creation
266 typedef _STLP_PRIV _MultimapTraitsT
<value_type
> _MultimapTraits
;
269 //Following typedef have to be public for __move_traits specialization.
270 typedef _STLP_PRIV _Rb_tree
<key_type
, key_compare
,
271 value_type
, _STLP_SELECT1ST(value_type
, _Key
),
272 _MultimapTraits
, _Alloc
> _Rep_type
;
274 typedef typename
_Rep_type::pointer pointer
;
275 typedef typename
_Rep_type::const_pointer const_pointer
;
276 typedef typename
_Rep_type::reference reference
;
277 typedef typename
_Rep_type::const_reference const_reference
;
278 typedef typename
_Rep_type::iterator iterator
;
279 typedef typename
_Rep_type::const_iterator const_iterator
;
280 typedef typename
_Rep_type::reverse_iterator reverse_iterator
;
281 typedef typename
_Rep_type::const_reverse_iterator const_reverse_iterator
;
282 typedef typename
_Rep_type::size_type size_type
;
283 typedef typename
_Rep_type::difference_type difference_type
;
284 typedef typename
_Rep_type::allocator_type allocator_type
;
287 _Rep_type _M_t
; // red-black tree representing multimap
288 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type
)
291 // allocation/deallocation
292 multimap() : _M_t(_Compare(), allocator_type()) { }
293 explicit multimap(const _Compare
& __comp
,
294 const allocator_type
& __a
= allocator_type())
295 : _M_t(__comp
, __a
) { }
297 #ifdef _STLP_MEMBER_TEMPLATES
298 template <class _InputIterator
>
299 multimap(_InputIterator __first
, _InputIterator __last
)
300 : _M_t(_Compare(), allocator_type())
301 { _M_t
.insert_equal(__first
, __last
); }
302 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
303 template <class _InputIterator
>
304 multimap(_InputIterator __first
, _InputIterator __last
,
305 const _Compare
& __comp
)
306 : _M_t(__comp
, allocator_type()) { _M_t
.insert_equal(__first
, __last
); }
308 template <class _InputIterator
>
309 multimap(_InputIterator __first
, _InputIterator __last
,
310 const _Compare
& __comp
,
311 const allocator_type
& __a _STLP_ALLOCATOR_TYPE_DFL
)
312 : _M_t(__comp
, __a
) { _M_t
.insert_equal(__first
, __last
); }
314 multimap(const value_type
* __first
, const value_type
* __last
)
315 : _M_t(_Compare(), allocator_type())
316 { _M_t
.insert_equal(__first
, __last
); }
317 multimap(const value_type
* __first
, const value_type
* __last
,
318 const _Compare
& __comp
,
319 const allocator_type
& __a
= allocator_type())
320 : _M_t(__comp
, __a
) { _M_t
.insert_equal(__first
, __last
); }
322 multimap(const_iterator __first
, const_iterator __last
)
323 : _M_t(_Compare(), allocator_type())
324 { _M_t
.insert_equal(__first
, __last
); }
325 multimap(const_iterator __first
, const_iterator __last
,
326 const _Compare
& __comp
,
327 const allocator_type
& __a
= allocator_type())
328 : _M_t(__comp
, __a
) { _M_t
.insert_equal(__first
, __last
); }
329 #endif /* _STLP_MEMBER_TEMPLATES */
331 multimap(const _Self
& __x
) : _M_t(__x
._M_t
) {}
333 #if !defined (_STLP_NO_MOVE_SEMANTIC)
334 multimap(__move_source
<_Self
> src
)
335 : _M_t(__move_source
<_Rep_type
>(src
.get()._M_t
)) {}
338 _Self
& operator=(const _Self
& __x
) {
345 key_compare
key_comp() const { return _M_t
.key_comp(); }
346 value_compare
value_comp() const { return value_compare(_M_t
.key_comp()); }
347 allocator_type
get_allocator() const { return _M_t
.get_allocator(); }
349 iterator
begin() { return _M_t
.begin(); }
350 const_iterator
begin() const { return _M_t
.begin(); }
351 iterator
end() { return _M_t
.end(); }
352 const_iterator
end() const { return _M_t
.end(); }
353 reverse_iterator
rbegin() { return _M_t
.rbegin(); }
354 const_reverse_iterator
rbegin() const { return _M_t
.rbegin(); }
355 reverse_iterator
rend() { return _M_t
.rend(); }
356 const_reverse_iterator
rend() const { return _M_t
.rend(); }
357 bool empty() const { return _M_t
.empty(); }
358 size_type
size() const { return _M_t
.size(); }
359 size_type
max_size() const { return _M_t
.max_size(); }
360 void swap(_Self
& __x
) { _M_t
.swap(__x
._M_t
); }
361 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
362 void _M_swap_workaround(_Self
& __x
) { swap(__x
); }
366 iterator
insert(const value_type
& __x
) { return _M_t
.insert_equal(__x
); }
367 iterator
insert(iterator __pos
, const value_type
& __x
) { return _M_t
.insert_equal(__pos
, __x
); }
368 #if defined (_STLP_MEMBER_TEMPLATES)
369 template <class _InputIterator
>
370 void insert(_InputIterator __first
, _InputIterator __last
)
371 { _M_t
.insert_equal(__first
, __last
); }
373 void insert(const value_type
* __first
, const value_type
* __last
)
374 { _M_t
.insert_equal(__first
, __last
); }
375 void insert(const_iterator __first
, const_iterator __last
)
376 { _M_t
.insert_equal(__first
, __last
); }
377 #endif /* _STLP_MEMBER_TEMPLATES */
378 void erase(iterator __pos
) { _M_t
.erase(__pos
); }
379 size_type
erase(const key_type
& __x
) { return _M_t
.erase(__x
); }
380 void erase(iterator __first
, iterator __last
) { _M_t
.erase(__first
, __last
); }
381 void clear() { _M_t
.clear(); }
383 // multimap operations:
385 _STLP_TEMPLATE_FOR_CONT_EXT
386 iterator
find(const _KT
& __x
) { return _M_t
.find(__x
); }
387 _STLP_TEMPLATE_FOR_CONT_EXT
388 const_iterator
find(const _KT
& __x
) const { return _M_t
.find(__x
); }
389 _STLP_TEMPLATE_FOR_CONT_EXT
390 size_type
count(const _KT
& __x
) const { return _M_t
.count(__x
); }
391 _STLP_TEMPLATE_FOR_CONT_EXT
392 iterator
lower_bound(const _KT
& __x
) { return _M_t
.lower_bound(__x
); }
393 _STLP_TEMPLATE_FOR_CONT_EXT
394 const_iterator
lower_bound(const _KT
& __x
) const { return _M_t
.lower_bound(__x
); }
395 _STLP_TEMPLATE_FOR_CONT_EXT
396 iterator
upper_bound(const _KT
& __x
) { return _M_t
.upper_bound(__x
); }
397 _STLP_TEMPLATE_FOR_CONT_EXT
398 const_iterator
upper_bound(const _KT
& __x
) const { return _M_t
.upper_bound(__x
); }
399 _STLP_TEMPLATE_FOR_CONT_EXT
400 pair
<iterator
,iterator
> equal_range(const _KT
& __x
)
401 { return _M_t
.equal_range(__x
); }
402 _STLP_TEMPLATE_FOR_CONT_EXT
403 pair
<const_iterator
,const_iterator
> equal_range(const _KT
& __x
) const
404 { return _M_t
.equal_range(__x
); }
407 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _Compare, class _Alloc>
408 #define _STLP_TEMPLATE_CONTAINER map<_Key,_Tp,_Compare,_Alloc>
409 #include <stl/_relops_cont.h>
410 #undef _STLP_TEMPLATE_CONTAINER
411 #define _STLP_TEMPLATE_CONTAINER multimap<_Key,_Tp,_Compare,_Alloc>
412 #include <stl/_relops_cont.h>
413 #undef _STLP_TEMPLATE_CONTAINER
414 #undef _STLP_TEMPLATE_HEADER
416 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
417 template <class _Key
, class _Tp
, class _Compare
, class _Alloc
>
418 struct __move_traits
<map
<_Key
,_Tp
,_Compare
,_Alloc
> > :
419 _STLP_PRIV __move_traits_aux
<typename map
<_Key
,_Tp
,_Compare
,_Alloc
>::_Rep_type
>
422 template <class _Key
, class _Tp
, class _Compare
, class _Alloc
>
423 struct __move_traits
<multimap
<_Key
,_Tp
,_Compare
,_Alloc
> > :
424 _STLP_PRIV __move_traits_aux
<typename multimap
<_Key
,_Tp
,_Compare
,_Alloc
>::_Rep_type
>
430 #endif /* _STLP_INTERNAL_MAP_H */