1 /* 2 * Copyright (c) 2004 3 * Francois Dumont 4 * 5 * This material is provided "as is", with absolutely no warranty expressed 6 * or implied. Any use is at your own risk. 7 * 8 * Permission to use or copy this software for any purpose is hereby granted 9 * without fee, provided the above notices are retained on all copies. 10 * Permission to modify the code and to distribute modified code is granted, 11 * provided the above notices are retained, and a notice that the code was 12 * modified is included with the above copyright notice. 13 * 14 */ 15 16 /* NOTE: This is an internal header file, included by other STL headers. 17 * You should not attempt to use it directly. 18 */ 19 20 #ifndef _STLP_INTERNAL_UNORDERED_MAP_H 21 #define _STLP_INTERNAL_UNORDERED_MAP_H 22 23 #ifndef _STLP_INTERNAL_HASHTABLE_H 24 # include <stl/_hashtable.h> 25 #endif 26 27 _STLP_BEGIN_NAMESPACE 28 29 //Specific iterator traits creation 30 _STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMapTraitsT, traits) 31 32 _STLP_BEGIN_TR1_NAMESPACE 33 34 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>), 35 _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Key>), 36 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) > 37 class unordered_map 38 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 39 : public __stlport_class<unordered_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> > 40 #endif 41 { 42 private: 43 typedef unordered_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self; 44 public: 45 typedef _Key key_type; 46 typedef _Tp data_type; 47 typedef _Tp mapped_type; 48 typedef pair<_STLP_CONST key_type, data_type> value_type; 49 private: 50 //Specific iterator traits creation 51 typedef _STLP_PRIV _UnorderedMapTraitsT<value_type> _UnorderedMapTraits; 52 53 public: 54 typedef hashtable<value_type, key_type, _HashFcn, _UnorderedMapTraits, 55 _STLP_SELECT1ST(value_type, _Key), _EqualKey, _Alloc > _Ht; 56 57 typedef typename _Ht::hasher hasher; 58 typedef typename _Ht::key_equal key_equal; 59 60 typedef typename _Ht::size_type size_type; 61 typedef typename _Ht::difference_type difference_type; 62 typedef typename _Ht::pointer pointer; 63 typedef typename _Ht::const_pointer const_pointer; 64 typedef typename _Ht::reference reference; 65 typedef typename _Ht::const_reference const_reference; 66 67 typedef typename _Ht::iterator iterator; 68 typedef typename _Ht::const_iterator const_iterator; 69 typedef typename _Ht::local_iterator local_iterator; 70 typedef typename _Ht::const_local_iterator const_local_iterator; 71 72 typedef typename _Ht::allocator_type allocator_type; 73 74 hasher hash_function() const { return _M_ht.hash_funct(); } 75 key_equal key_eq() const { return _M_ht.key_eq(); } 76 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 77 78 private: 79 _Ht _M_ht; 80 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 81 82 public: 83 explicit unordered_map(size_type __n = 0, const hasher& __hf = hasher(), 84 const key_equal& __eql = key_equal(), 85 const allocator_type& __a = allocator_type()) 86 : _M_ht(__n, __hf, __eql, __a) {} 87 88 #if !defined (_STLP_NO_MOVE_SEMANTIC) 89 unordered_map(__move_source<_Self> src) 90 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {} 91 #endif 92 93 #if defined (_STLP_MEMBER_TEMPLATES) 94 template <class _InputIterator> 95 unordered_map(_InputIterator __f, _InputIterator __l, 96 size_type __n = 0, const hasher& __hf = hasher(), 97 const key_equal& __eql = key_equal(), 98 const allocator_type& __a = allocator_type()) 99 : _M_ht(__n, __hf, __eql, __a) 100 { _M_ht.insert_unique(__f, __l); } 101 #else 102 unordered_map(const value_type* __f, const value_type* __l, 103 size_type __n = 0, const hasher& __hf = hasher(), 104 const key_equal& __eql = key_equal(), 105 const allocator_type& __a = allocator_type()) 106 : _M_ht(__n, __hf, __eql, __a) 107 { _M_ht.insert_unique(__f, __l); } 108 109 unordered_map(const_iterator __f, const_iterator __l, 110 size_type __n = 0, const hasher& __hf = hasher(), 111 const key_equal& __eql = key_equal(), 112 const allocator_type& __a = allocator_type()) 113 : _M_ht(__n, __hf, __eql, __a) 114 { _M_ht.insert_unique(__f, __l); } 115 #endif /*_STLP_MEMBER_TEMPLATES */ 116 117 _Self& operator = (const _Self& __other) 118 { _M_ht = __other._M_ht; return *this; } 119 120 size_type size() const { return _M_ht.size(); } 121 size_type max_size() const { return _M_ht.max_size(); } 122 bool empty() const { return _M_ht.empty(); } 123 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); } 124 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 125 void _M_swap_workaround(_Self& __x) { swap(__x); } 126 #endif 127 128 iterator begin() { return _M_ht.begin(); } 129 iterator end() { return _M_ht.end(); } 130 const_iterator begin() const { return _M_ht.begin(); } 131 const_iterator end() const { return _M_ht.end(); } 132 133 pair<iterator,bool> insert(const value_type& __obj) 134 { return _M_ht.insert_unique(__obj); } 135 iterator insert(const_iterator /*__hint*/, const value_type& __obj) 136 { return _M_ht.insert_unique(__obj); } 137 #if defined (_STLP_MEMBER_TEMPLATES) 138 template <class _InputIterator> 139 void insert(_InputIterator __f, _InputIterator __l) 140 #else 141 void insert(const value_type* __f, const value_type* __l) 142 { _M_ht.insert_unique(__f,__l); } 143 void insert(const_iterator __f, const_iterator __l) 144 #endif /*_STLP_MEMBER_TEMPLATES */ 145 { _M_ht.insert_unique(__f, __l); } 146 147 _STLP_TEMPLATE_FOR_CONT_EXT 148 iterator find(const _KT& __key) { return _M_ht.find(__key); } 149 _STLP_TEMPLATE_FOR_CONT_EXT 150 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); } 151 152 _STLP_TEMPLATE_FOR_CONT_EXT 153 _Tp& operator[](const _KT& __key) { 154 iterator __it = _M_ht.find(__key); 155 return (__it == _M_ht.end() ? 156 _M_ht._M_insert(value_type(__key, _STLP_DEFAULT_CONSTRUCTED(_Tp))).second : 157 (*__it).second ); 158 } 159 160 _STLP_TEMPLATE_FOR_CONT_EXT 161 size_type count(const _KT& __key) const { return _M_ht.count(__key); } 162 163 _STLP_TEMPLATE_FOR_CONT_EXT 164 pair<iterator, iterator> equal_range(const _KT& __key) 165 { return _M_ht.equal_range(__key); } 166 _STLP_TEMPLATE_FOR_CONT_EXT 167 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const 168 { return _M_ht.equal_range(__key); } 169 170 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 171 void erase(const_iterator __it) { _M_ht.erase(__it); } 172 void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); } 173 void clear() { _M_ht.clear(); } 174 175 size_type bucket_count() const { return _M_ht.bucket_count(); } 176 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 177 size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); } 178 _STLP_TEMPLATE_FOR_CONT_EXT 179 size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); } 180 local_iterator begin(size_type __n) { return _M_ht.begin(__n); } 181 local_iterator end(size_type __n) { return _M_ht.end(__n); } 182 const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); } 183 const_local_iterator end(size_type __n) const { return _M_ht.end(__n); } 184 185 float load_factor() const { return _M_ht.load_factor(); } 186 float max_load_factor() const { return _M_ht.max_load_factor(); } 187 void max_load_factor(float __val) { _M_ht.max_load_factor(__val); } 188 void rehash(size_type __hint) { _M_ht.rehash(__hint); } 189 190 #if defined (__DMC__) // disable operator==(pair<x,unordered_map>, pair<x,unordered_map>) 191 bool operator==(const _Self&) const; 192 #endif 193 }; 194 195 _STLP_END_NAMESPACE 196 197 //Specific iterator traits creation 198 _STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMultimapTraitsT, traits) 199 200 _STLP_BEGIN_TR1_NAMESPACE 201 202 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>), 203 _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Key>), 204 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) > 205 class unordered_multimap 206 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 207 : public __stlport_class<unordered_multimap<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> > 208 #endif 209 { 210 private: 211 typedef unordered_multimap<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self; 212 public: 213 typedef _Key key_type; 214 typedef _Tp data_type; 215 typedef _Tp mapped_type; 216 typedef pair<_STLP_CONST key_type, data_type> value_type; 217 private: 218 //Specific iterator traits creation 219 typedef _STLP_PRIV _UnorderedMultimapTraitsT<value_type> _UnorderedMultimapTraits; 220 221 public: 222 typedef hashtable<value_type, key_type, _HashFcn, _UnorderedMultimapTraits, 223 _STLP_SELECT1ST(value_type, _Key), _EqualKey, _Alloc > _Ht; 224 225 typedef typename _Ht::hasher hasher; 226 typedef typename _Ht::key_equal key_equal; 227 228 typedef typename _Ht::size_type size_type; 229 typedef typename _Ht::difference_type difference_type; 230 typedef typename _Ht::pointer pointer; 231 typedef typename _Ht::const_pointer const_pointer; 232 typedef typename _Ht::reference reference; 233 typedef typename _Ht::const_reference const_reference; 234 235 typedef typename _Ht::iterator iterator; 236 typedef typename _Ht::const_iterator const_iterator; 237 typedef typename _Ht::local_iterator local_iterator; 238 typedef typename _Ht::const_local_iterator const_local_iterator; 239 240 typedef typename _Ht::allocator_type allocator_type; 241 242 hasher hash_function() const { return _M_ht.hash_funct(); } 243 key_equal key_eq() const { return _M_ht.key_eq(); } 244 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 245 246 private: 247 _Ht _M_ht; 248 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 249 250 public: 251 explicit unordered_multimap(size_type __n = 0, const hasher& __hf = hasher(), 252 const key_equal& __eql = key_equal(), 253 const allocator_type& __a = allocator_type()) 254 : _M_ht(__n, __hf, __eql, __a) {} 255 256 #if !defined (_STLP_NO_MOVE_SEMANTIC) 257 unordered_multimap(__move_source<_Self> src) 258 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {} 259 #endif 260 261 #if defined (_STLP_MEMBER_TEMPLATES) 262 template <class _InputIterator> 263 unordered_multimap(_InputIterator __f, _InputIterator __l, 264 size_type __n = 0, const hasher& __hf = hasher(), 265 const key_equal& __eql = key_equal(), 266 const allocator_type& __a = allocator_type()) 267 : _M_ht(__n, __hf, __eql, __a) 268 { _M_ht.insert_equal(__f, __l); } 269 #else 270 unordered_multimap(const value_type* __f, const value_type* __l, 271 size_type __n = 0, const hasher& __hf = hasher(), 272 const key_equal& __eql = key_equal(), 273 const allocator_type& __a = allocator_type()) 274 : _M_ht(__n, __hf, __eql, __a) 275 { _M_ht.insert_equal(__f, __l); } 276 277 unordered_multimap(const_iterator __f, const_iterator __l, 278 size_type __n = 0, const hasher& __hf = hasher(), 279 const key_equal& __eql = key_equal(), 280 const allocator_type& __a = allocator_type()) 281 : _M_ht(__n, __hf, __eql, __a) 282 { _M_ht.insert_equal(__f, __l); } 283 #endif /*_STLP_MEMBER_TEMPLATES */ 284 285 _Self& operator = (const _Self& __other) 286 { _M_ht = __other._M_ht; return *this; } 287 288 size_type size() const { return _M_ht.size(); } 289 size_type max_size() const { return _M_ht.max_size(); } 290 bool empty() const { return _M_ht.empty(); } 291 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); } 292 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 293 void _M_swap_workaround(_Self& __x) { swap(__x); } 294 #endif 295 296 iterator begin() { return _M_ht.begin(); } 297 iterator end() { return _M_ht.end(); } 298 const_iterator begin() const { return _M_ht.begin(); } 299 const_iterator end() const { return _M_ht.end(); } 300 301 iterator insert(const value_type& __obj) 302 { return _M_ht.insert_equal(__obj); } 303 iterator insert(const_iterator /*__hint*/, const value_type& __obj) 304 { return _M_ht.insert_equal(__obj); } 305 #if defined (_STLP_MEMBER_TEMPLATES) 306 template <class _InputIterator> 307 void insert(_InputIterator __f, _InputIterator __l) 308 #else 309 void insert(const value_type* __f, const value_type* __l) 310 { _M_ht.insert_equal(__f,__l); } 311 void insert(const_iterator __f, const_iterator __l) 312 #endif /*_STLP_MEMBER_TEMPLATES */ 313 { _M_ht.insert_equal(__f, __l); } 314 315 _STLP_TEMPLATE_FOR_CONT_EXT 316 iterator find(const _KT& __key) { return _M_ht.find(__key); } 317 _STLP_TEMPLATE_FOR_CONT_EXT 318 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); } 319 320 _STLP_TEMPLATE_FOR_CONT_EXT 321 size_type count(const _KT& __key) const { return _M_ht.count(__key); } 322 323 _STLP_TEMPLATE_FOR_CONT_EXT 324 pair<iterator, iterator> equal_range(const _KT& __key) 325 { return _M_ht.equal_range(__key); } 326 _STLP_TEMPLATE_FOR_CONT_EXT 327 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const 328 { return _M_ht.equal_range(__key); } 329 330 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 331 void erase(const_iterator __it) { _M_ht.erase(__it); } 332 void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); } 333 void clear() { _M_ht.clear(); } 334 335 size_type bucket_count() const { return _M_ht.bucket_count(); } 336 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 337 size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); } 338 _STLP_TEMPLATE_FOR_CONT_EXT 339 size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); } 340 local_iterator begin(size_type __n) { return _M_ht.begin(__n); } 341 local_iterator end(size_type __n) { return _M_ht.end(__n); } 342 const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); } 343 const_local_iterator end(size_type __n) const { return _M_ht.end(__n); } 344 345 float load_factor() const { return _M_ht.load_factor(); } 346 float max_load_factor() const { return _M_ht.max_load_factor(); } 347 void max_load_factor(float __val) { _M_ht.max_load_factor(__val); } 348 void rehash(size_type __hint) { _M_ht.rehash(__hint); } 349 }; 350 351 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 352 #define _STLP_TEMPLATE_CONTAINER unordered_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc> 353 354 #include <stl/_relops_hash_cont.h> 355 356 #undef _STLP_TEMPLATE_CONTAINER 357 #define _STLP_TEMPLATE_CONTAINER unordered_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc> 358 359 #include <stl/_relops_hash_cont.h> 360 361 #undef _STLP_TEMPLATE_CONTAINER 362 #undef _STLP_TEMPLATE_HEADER 363 364 _STLP_END_NAMESPACE 365 366 // Specialization of insert_iterator so that it will work for unordered_map 367 // and unordered_multimap. 368 369 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 370 # if !defined (_STLP_NO_MOVE_SEMANTIC) 371 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 372 struct __move_traits<_STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > : 373 _STLP_PRIV __move_traits_help<typename _STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>::_Ht> 374 {}; 375 376 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 377 struct __move_traits<_STLP_TR1 unordered_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > : 378 _STLP_PRIV __move_traits_help<typename _STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>::_Ht> 379 {}; 380 # endif 381 382 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 383 class insert_iterator<_STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 384 protected: 385 typedef _STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 386 _Container* container; 387 public: 388 typedef _Container container_type; 389 typedef output_iterator_tag iterator_category; 390 typedef void value_type; 391 typedef void difference_type; 392 typedef void pointer; 393 typedef void reference; 394 395 insert_iterator(_Container& __x) : container(&__x) {} 396 insert_iterator(_Container& __x, typename _Container::iterator) 397 : container(&__x) {} 398 insert_iterator<_Container>& 399 operator=(const typename _Container::value_type& __val) { 400 container->insert(__val); 401 return *this; 402 } 403 insert_iterator<_Container>& operator*() { return *this; } 404 insert_iterator<_Container>& operator++() { return *this; } 405 insert_iterator<_Container>& operator++(int) { return *this; } 406 }; 407 408 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 409 class insert_iterator<_STLP_TR1 unordered_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 410 protected: 411 typedef _STLP_TR1 unordered_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 412 _Container* container; 413 typename _Container::iterator iter; 414 public: 415 typedef _Container container_type; 416 typedef output_iterator_tag iterator_category; 417 typedef void value_type; 418 typedef void difference_type; 419 typedef void pointer; 420 typedef void reference; 421 422 insert_iterator(_Container& __x) : container(&__x) {} 423 insert_iterator(_Container& __x, typename _Container::iterator) 424 : container(&__x) {} 425 insert_iterator<_Container>& 426 operator=(const typename _Container::value_type& __val) { 427 container->insert(__val); 428 return *this; 429 } 430 insert_iterator<_Container>& operator*() { return *this; } 431 insert_iterator<_Container>& operator++() { return *this; } 432 insert_iterator<_Container>& operator++(int) { return *this; } 433 }; 434 435 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 436 437 _STLP_END_NAMESPACE 438 439 #endif /* _STLP_INTERNAL_UNORDERED_MAP_H */ 440 441 // Local Variables: 442 // mode:C++ 443 // End: 444
