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(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<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 map(__move_source<_Self> src)
149 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
151 _Self& operator=(const _Self& __x) {
157 key_compare key_comp() const { return _M_t.key_comp(); }
158 value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
159 allocator_type get_allocator() const { return _M_t.get_allocator(); }
161 iterator begin() { return _M_t.begin(); }
162 const_iterator begin() const { return _M_t.begin(); }
163 iterator end() { return _M_t.end(); }
164 const_iterator end() const { return _M_t.end(); }
165 reverse_iterator rbegin() { return _M_t.rbegin(); }
166 const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
167 reverse_iterator rend() { return _M_t.rend(); }
168 const_reverse_iterator rend() const { return _M_t.rend(); }
169 bool empty() const { return _M_t.empty(); }
170 size_type size() const { return _M_t.size(); }
171 size_type max_size() const { return _M_t.max_size(); }
172 _STLP_TEMPLATE_FOR_CONT_EXT
173 _Tp& operator[](const _KT& __k) {
174 iterator __i = lower_bound(__k);
175 // __i->first is greater than or equivalent to __k.
176 if (__i == end() || key_comp()(__k, (*__i).first))
177 __i = insert(__i, value_type(__k, _STLP_DEFAULT_CONSTRUCTED(_Tp)));
178 return (*__i).second;
180 void swap(_Self& __x) { _M_t.swap(__x._M_t); }
183 pair<iterator,bool> insert(const value_type& __x)
184 { return _M_t.insert_unique(__x); }
185 iterator insert(iterator __pos, const value_type& __x)
186 { return _M_t.insert_unique(__pos, __x); }
187 #ifdef _STLP_MEMBER_TEMPLATES
188 template <class _InputIterator>
189 void insert(_InputIterator __first, _InputIterator __last)
190 { _M_t.insert_unique(__first, __last); }
192 void insert(const value_type* __first, const value_type* __last)
193 { _M_t.insert_unique(__first, __last); }
194 void insert(const_iterator __first, const_iterator __last)
195 { _M_t.insert_unique(__first, __last); }
196 #endif /* _STLP_MEMBER_TEMPLATES */
198 void erase(iterator __pos) { _M_t.erase(__pos); }
199 size_type erase(const key_type& __x) { return _M_t.erase_unique(__x); }
200 void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); }
201 void clear() { _M_t.clear(); }
204 _STLP_TEMPLATE_FOR_CONT_EXT
205 iterator find(const _KT& __x) { return _M_t.find(__x); }
206 _STLP_TEMPLATE_FOR_CONT_EXT
207 const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
208 _STLP_TEMPLATE_FOR_CONT_EXT
209 size_type count(const _KT& __x) const { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
210 _STLP_TEMPLATE_FOR_CONT_EXT
211 iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
212 _STLP_TEMPLATE_FOR_CONT_EXT
213 const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
214 _STLP_TEMPLATE_FOR_CONT_EXT
215 iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
216 _STLP_TEMPLATE_FOR_CONT_EXT
217 const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
219 _STLP_TEMPLATE_FOR_CONT_EXT
220 pair<iterator,iterator> equal_range(const _KT& __x)
221 { return _M_t.equal_range_unique(__x); }
222 _STLP_TEMPLATE_FOR_CONT_EXT
223 pair<const_iterator,const_iterator> equal_range(const _KT& __x) const
224 { return _M_t.equal_range_unique(__x); }
227 //Specific iterator traits creation
228 _STLP_CREATE_ITERATOR_TRAITS(MultimapTraitsT, traits)
230 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key> ),
231 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(const _Key, _Tp) >
233 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
234 : public __stlport_class<multimap<_Key, _Tp, _Compare, _Alloc> >
237 typedef multimap<_Key, _Tp, _Compare, _Alloc> _Self;
242 typedef _Key key_type;
243 typedef _Tp data_type;
244 typedef _Tp mapped_type;
245 typedef pair<const _Key, _Tp> value_type;
246 typedef _Compare key_compare;
248 class value_compare : public binary_function<value_type, value_type, bool> {
249 friend class multimap<_Key,_Tp,_Compare,_Alloc>;
251 //comp is a Standard name (23.3.2), do no make it STLport naming convention compliant.
253 value_compare(_Compare __c) : comp(__c) {}
255 bool operator()(const value_type& __x, const value_type& __y) const
256 { return comp(__x.first, __y.first); }
260 //Specific iterator traits creation
261 typedef _STLP_PRIV _MultimapTraitsT<value_type> _MultimapTraits;
264 //Following typedef have to be public for __move_traits specialization.
265 typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
266 value_type, _STLP_SELECT1ST(value_type, _Key),
267 _MultimapTraits, _Alloc> _Rep_type;
269 typedef typename _Rep_type::pointer pointer;
270 typedef typename _Rep_type::const_pointer const_pointer;
271 typedef typename _Rep_type::reference reference;
272 typedef typename _Rep_type::const_reference const_reference;
273 typedef typename _Rep_type::iterator iterator;
274 typedef typename _Rep_type::const_iterator const_iterator;
275 typedef typename _Rep_type::reverse_iterator reverse_iterator;
276 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
277 typedef typename _Rep_type::size_type size_type;
278 typedef typename _Rep_type::difference_type difference_type;
279 typedef typename _Rep_type::allocator_type allocator_type;
282 _Rep_type _M_t; // red-black tree representing multimap
283 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
286 // allocation/deallocation
287 multimap() : _M_t(_Compare(), allocator_type()) { }
288 explicit multimap(const _Compare& __comp,
289 const allocator_type& __a = allocator_type())
290 : _M_t(__comp, __a) { }
292 #ifdef _STLP_MEMBER_TEMPLATES
293 template <class _InputIterator>
294 multimap(_InputIterator __first, _InputIterator __last)
295 : _M_t(_Compare(), allocator_type())
296 { _M_t.insert_equal(__first, __last); }
297 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
298 template <class _InputIterator>
299 multimap(_InputIterator __first, _InputIterator __last,
300 const _Compare& __comp)
301 : _M_t(__comp, allocator_type()) { _M_t.insert_equal(__first, __last); }
303 template <class _InputIterator>
304 multimap(_InputIterator __first, _InputIterator __last,
305 const _Compare& __comp,
306 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
307 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
309 multimap(const value_type* __first, const value_type* __last)
310 : _M_t(_Compare(), allocator_type())
311 { _M_t.insert_equal(__first, __last); }
312 multimap(const value_type* __first, const value_type* __last,
313 const _Compare& __comp,
314 const allocator_type& __a = allocator_type())
315 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
317 multimap(const_iterator __first, const_iterator __last)
318 : _M_t(_Compare(), allocator_type())
319 { _M_t.insert_equal(__first, __last); }
320 multimap(const_iterator __first, const_iterator __last,
321 const _Compare& __comp,
322 const allocator_type& __a = allocator_type())
323 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
324 #endif /* _STLP_MEMBER_TEMPLATES */
326 multimap(const _Self& __x) : _M_t(__x._M_t) {}
328 multimap(__move_source<_Self> src)
329 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
331 _Self& operator=(const _Self& __x) {
338 key_compare key_comp() const { return _M_t.key_comp(); }
339 value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
340 allocator_type get_allocator() const { return _M_t.get_allocator(); }
342 iterator begin() { return _M_t.begin(); }
343 const_iterator begin() const { return _M_t.begin(); }
344 iterator end() { return _M_t.end(); }
345 const_iterator end() const { return _M_t.end(); }
346 reverse_iterator rbegin() { return _M_t.rbegin(); }
347 const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
348 reverse_iterator rend() { return _M_t.rend(); }
349 const_reverse_iterator rend() const { return _M_t.rend(); }
350 bool empty() const { return _M_t.empty(); }
351 size_type size() const { return _M_t.size(); }
352 size_type max_size() const { return _M_t.max_size(); }
353 void swap(_Self& __x) { _M_t.swap(__x._M_t); }
356 iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); }
357 iterator insert(iterator __pos, const value_type& __x) { return _M_t.insert_equal(__pos, __x); }
358 #if defined (_STLP_MEMBER_TEMPLATES)
359 template <class _InputIterator>
360 void insert(_InputIterator __first, _InputIterator __last)
361 { _M_t.insert_equal(__first, __last); }
363 void insert(const value_type* __first, const value_type* __last)
364 { _M_t.insert_equal(__first, __last); }
365 void insert(const_iterator __first, const_iterator __last)
366 { _M_t.insert_equal(__first, __last); }
367 #endif /* _STLP_MEMBER_TEMPLATES */
368 void erase(iterator __pos) { _M_t.erase(__pos); }
369 size_type erase(const key_type& __x) { return _M_t.erase(__x); }
370 void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); }
371 void clear() { _M_t.clear(); }
373 // multimap operations:
375 _STLP_TEMPLATE_FOR_CONT_EXT
376 iterator find(const _KT& __x) { return _M_t.find(__x); }
377 _STLP_TEMPLATE_FOR_CONT_EXT
378 const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
379 _STLP_TEMPLATE_FOR_CONT_EXT
380 size_type count(const _KT& __x) const { return _M_t.count(__x); }
381 _STLP_TEMPLATE_FOR_CONT_EXT
382 iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
383 _STLP_TEMPLATE_FOR_CONT_EXT
384 const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
385 _STLP_TEMPLATE_FOR_CONT_EXT
386 iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
387 _STLP_TEMPLATE_FOR_CONT_EXT
388 const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
389 _STLP_TEMPLATE_FOR_CONT_EXT
390 pair<iterator,iterator> equal_range(const _KT& __x)
391 { return _M_t.equal_range(__x); }
392 _STLP_TEMPLATE_FOR_CONT_EXT
393 pair<const_iterator,const_iterator> equal_range(const _KT& __x) const
394 { return _M_t.equal_range(__x); }
397 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _Compare, class _Alloc>
398 #define _STLP_TEMPLATE_CONTAINER map<_Key,_Tp,_Compare,_Alloc>
399 #include <stl/_relops_cont.h>
400 #undef _STLP_TEMPLATE_CONTAINER
401 #define _STLP_TEMPLATE_CONTAINER multimap<_Key,_Tp,_Compare,_Alloc>
402 #include <stl/_relops_cont.h>
403 #undef _STLP_TEMPLATE_CONTAINER
404 #undef _STLP_TEMPLATE_HEADER
406 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
407 template <class _Key, class _Tp, class _Compare, class _Alloc>
408 struct __move_traits<map<_Key,_Tp,_Compare,_Alloc> > :
409 _STLP_PRIV __move_traits_aux<typename map<_Key,_Tp,_Compare,_Alloc>::_Rep_type>
412 template <class _Key, class _Tp, class _Compare, class _Alloc>
413 struct __move_traits<multimap<_Key,_Tp,_Compare,_Alloc> > :
414 _STLP_PRIV __move_traits_aux<typename multimap<_Key,_Tp,_Compare,_Alloc>::_Rep_type>
420 #endif /* _STLP_INTERNAL_MAP_H */