1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Copyright (c) 1996,1997 7 * Silicon Graphics Computer Systems, Inc. 8 * 9 * Copyright (c) 1997 10 * Moscow Center for SPARC Technology 11 * 12 * Copyright (c) 1999 13 * Boris Fomitchev 14 * 15 * This material is provided "as is", with absolutely no warranty expressed 16 * or implied. Any use is at your own risk. 17 * 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. 23 * 24 */ 25 26 /* NOTE: This is an internal header file, included by other STL headers. 27 * You should not attempt to use it directly. 28 */ 29 30 #ifndef _STLP_INTERNAL_MAP_H 31 #define _STLP_INTERNAL_MAP_H 32 33 #ifndef _STLP_INTERNAL_TREE_H 34 # include <stl/_tree.h> 35 #endif 36 37 _STLP_BEGIN_NAMESPACE 38 39 //Specific iterator traits creation 40 _STLP_CREATE_ITERATOR_TRAITS(MapTraitsT, traits) 41 42 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key> ), 43 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) > 44 class map 45 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 46 : public __stlport_class<map<_Key, _Tp, _Compare, _Alloc> > 47 #endif 48 { 49 typedef map<_Key, _Tp, _Compare, _Alloc> _Self; 50 public: 51 52 // typedefs: 53 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; 59 60 class value_compare 61 : public binary_function<value_type, value_type, bool> { 62 friend class map<_Key,_Tp,_Compare,_Alloc>; 63 protected : 64 //c is a Standard name (23.3.1), do no make it STLport naming convention compliant. 65 _Compare comp; 66 value_compare(_Compare __c) : comp(__c) {} 67 public: 68 bool operator()(const value_type& __x, const value_type& __y) const 69 { return comp(__x.first, __y.first); } 70 }; 71 72 protected: 73 typedef _STLP_PRIV _MapTraitsT<value_type> _MapTraits; 74 75 public: 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; 80 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; 92 93 private: 94 _Rep_type _M_t; // red-black tree representing map 95 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 96 97 public: 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()) 103 #else 104 explicit map(const _Compare& __comp) 105 : _M_t(__comp, allocator_type()) {} 106 explicit map(const _Compare& __comp, const allocator_type& __a) 107 #endif 108 : _M_t(__comp, __a) {} 109 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); } 115 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); } 120 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); } 125 # endif 126 127 #else 128 map(const value_type* __first, const value_type* __last) 129 : _M_t(_Compare(), allocator_type()) 130 { _M_t.insert_unique(__first, __last); } 131 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); } 136 137 map(const_iterator __first, const_iterator __last) 138 : _M_t(_Compare(), allocator_type()) 139 { _M_t.insert_unique(__first, __last); } 140 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 */ 145 146 map(const _Self& __x) : _M_t(__x._M_t) {} 147 148 #if !defined (_STLP_NO_MOVE_SEMANTIC) 149 map(__move_source<_Self> src) 150 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {} 151 #endif 152 153 _Self& operator=(const _Self& __x) { 154 _M_t = __x._M_t; 155 return *this; 156 } 157 158 // accessors: 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(); } 162 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; 181 } 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); } 185 #endif 186 187 // insert/erase 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); } 196 #else 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 */ 202 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(); } 207 208 // map operations: 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); } 223 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); } 230 }; 231 232 //Specific iterator traits creation 233 _STLP_CREATE_ITERATOR_TRAITS(MultimapTraitsT, traits) 234 235 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key> ), 236 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) > 237 class multimap 238 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 239 : public __stlport_class<multimap<_Key, _Tp, _Compare, _Alloc> > 240 #endif 241 { 242 typedef multimap<_Key, _Tp, _Compare, _Alloc> _Self; 243 public: 244 245 // typedefs: 246 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; 252 253 class value_compare : public binary_function<value_type, value_type, bool> { 254 friend class multimap<_Key,_Tp,_Compare,_Alloc>; 255 protected: 256 //comp is a Standard name (23.3.2), do no make it STLport naming convention compliant. 257 _Compare comp; 258 value_compare(_Compare __c) : comp(__c) {} 259 public: 260 bool operator()(const value_type& __x, const value_type& __y) const 261 { return comp(__x.first, __y.first); } 262 }; 263 264 protected: 265 //Specific iterator traits creation 266 typedef _STLP_PRIV _MultimapTraitsT<value_type> _MultimapTraits; 267 268 public: 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; 273 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; 285 286 private: 287 _Rep_type _M_t; // red-black tree representing multimap 288 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 289 290 public: 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) { } 296 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); } 307 # endif 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); } 313 #else 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); } 321 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 */ 330 331 multimap(const _Self& __x) : _M_t(__x._M_t) {} 332 333 #if !defined (_STLP_NO_MOVE_SEMANTIC) 334 multimap(__move_source<_Self> src) 335 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {} 336 #endif 337 338 _Self& operator=(const _Self& __x) { 339 _M_t = __x._M_t; 340 return *this; 341 } 342 343 // accessors: 344 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(); } 348 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); } 363 #endif 364 365 // insert/erase 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); } 372 #else 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(); } 382 383 // multimap operations: 384 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); } 405 }; 406 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 415 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> 420 {}; 421 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> 425 {}; 426 #endif 427 428 _STLP_END_NAMESPACE 429 430 #endif /* _STLP_INTERNAL_MAP_H */ 431 432 // Local Variables: 433 // mode:C++ 434 // End: 435 436
