ReactOS Development > Doxygen
_unordered_map.h
Go to the documentation of this file.
00001 /* 00002 * Copyright (c) 2004 00003 * Francois Dumont 00004 * 00005 * This material is provided "as is", with absolutely no warranty expressed 00006 * or implied. Any use is at your own risk. 00007 * 00008 * Permission to use or copy this software for any purpose is hereby granted 00009 * without fee, provided the above notices are retained on all copies. 00010 * Permission to modify the code and to distribute modified code is granted, 00011 * provided the above notices are retained, and a notice that the code was 00012 * modified is included with the above copyright notice. 00013 * 00014 */ 00015 00016 /* NOTE: This is an internal header file, included by other STL headers. 00017 * You should not attempt to use it directly. 00018 */ 00019 00020 #ifndef _STLP_INTERNAL_UNORDERED_MAP_H 00021 #define _STLP_INTERNAL_UNORDERED_MAP_H 00022 00023 #ifndef _STLP_INTERNAL_HASHTABLE_H 00024 # include <stl/_hashtable.h> 00025 #endif 00026 00027 _STLP_BEGIN_NAMESPACE 00028 00029 //Specific iterator traits creation 00030 _STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMapTraitsT, traits) 00031 00032 _STLP_BEGIN_TR1_NAMESPACE 00033 00034 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>), 00035 _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Key>), 00036 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) > 00037 class unordered_map 00038 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 00039 : public __stlport_class<unordered_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> > 00040 #endif 00041 { 00042 private: 00043 typedef unordered_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self; 00044 public: 00045 typedef _Key key_type; 00046 typedef _Tp data_type; 00047 typedef _Tp mapped_type; 00048 typedef pair<_STLP_CONST key_type, data_type> value_type; 00049 private: 00050 //Specific iterator traits creation 00051 typedef _STLP_PRIV _UnorderedMapTraitsT<value_type> _UnorderedMapTraits; 00052 00053 public: 00054 typedef hashtable<value_type, key_type, _HashFcn, _UnorderedMapTraits, 00055 _STLP_SELECT1ST(value_type, _Key), _EqualKey, _Alloc > _Ht; 00056 00057 typedef typename _Ht::hasher hasher; 00058 typedef typename _Ht::key_equal key_equal; 00059 00060 typedef typename _Ht::size_type size_type; 00061 typedef typename _Ht::difference_type difference_type; 00062 typedef typename _Ht::pointer pointer; 00063 typedef typename _Ht::const_pointer const_pointer; 00064 typedef typename _Ht::reference reference; 00065 typedef typename _Ht::const_reference const_reference; 00066 00067 typedef typename _Ht::iterator iterator; 00068 typedef typename _Ht::const_iterator const_iterator; 00069 typedef typename _Ht::local_iterator local_iterator; 00070 typedef typename _Ht::const_local_iterator const_local_iterator; 00071 00072 typedef typename _Ht::allocator_type allocator_type; 00073 00074 hasher hash_function() const { return _M_ht.hash_funct(); } 00075 key_equal key_eq() const { return _M_ht.key_eq(); } 00076 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 00077 00078 private: 00079 _Ht _M_ht; 00080 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 00081 00082 public: 00083 explicit unordered_map(size_type __n = 0, const hasher& __hf = hasher(), 00084 const key_equal& __eql = key_equal(), 00085 const allocator_type& __a = allocator_type()) 00086 : _M_ht(__n, __hf, __eql, __a) {} 00087 00088 #if !defined (_STLP_NO_MOVE_SEMANTIC) 00089 unordered_map(__move_source<_Self> src) 00090 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {} 00091 #endif 00092 00093 #if defined (_STLP_MEMBER_TEMPLATES) 00094 template <class _InputIterator> 00095 unordered_map(_InputIterator __f, _InputIterator __l, 00096 size_type __n = 0, const hasher& __hf = hasher(), 00097 const key_equal& __eql = key_equal(), 00098 const allocator_type& __a = allocator_type()) 00099 : _M_ht(__n, __hf, __eql, __a) 00100 { _M_ht.insert_unique(__f, __l); } 00101 #else 00102 unordered_map(const value_type* __f, const value_type* __l, 00103 size_type __n = 0, const hasher& __hf = hasher(), 00104 const key_equal& __eql = key_equal(), 00105 const allocator_type& __a = allocator_type()) 00106 : _M_ht(__n, __hf, __eql, __a) 00107 { _M_ht.insert_unique(__f, __l); } 00108 00109 unordered_map(const_iterator __f, const_iterator __l, 00110 size_type __n = 0, const hasher& __hf = hasher(), 00111 const key_equal& __eql = key_equal(), 00112 const allocator_type& __a = allocator_type()) 00113 : _M_ht(__n, __hf, __eql, __a) 00114 { _M_ht.insert_unique(__f, __l); } 00115 #endif /*_STLP_MEMBER_TEMPLATES */ 00116 00117 _Self& operator = (const _Self& __other) 00118 { _M_ht = __other._M_ht; return *this; } 00119 00120 size_type size() const { return _M_ht.size(); } 00121 size_type max_size() const { return _M_ht.max_size(); } 00122 bool empty() const { return _M_ht.empty(); } 00123 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); } 00124 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 00125 void _M_swap_workaround(_Self& __x) { swap(__x); } 00126 #endif 00127 00128 iterator begin() { return _M_ht.begin(); } 00129 iterator end() { return _M_ht.end(); } 00130 const_iterator begin() const { return _M_ht.begin(); } 00131 const_iterator end() const { return _M_ht.end(); } 00132 00133 pair<iterator,bool> insert(const value_type& __obj) 00134 { return _M_ht.insert_unique(__obj); } 00135 iterator insert(const_iterator /*__hint*/, const value_type& __obj) 00136 { return _M_ht.insert_unique(__obj); } 00137 #if defined (_STLP_MEMBER_TEMPLATES) 00138 template <class _InputIterator> 00139 void insert(_InputIterator __f, _InputIterator __l) 00140 #else 00141 void insert(const value_type* __f, const value_type* __l) 00142 { _M_ht.insert_unique(__f,__l); } 00143 void insert(const_iterator __f, const_iterator __l) 00144 #endif /*_STLP_MEMBER_TEMPLATES */ 00145 { _M_ht.insert_unique(__f, __l); } 00146 00147 _STLP_TEMPLATE_FOR_CONT_EXT 00148 iterator find(const _KT& __key) { return _M_ht.find(__key); } 00149 _STLP_TEMPLATE_FOR_CONT_EXT 00150 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); } 00151 00152 _STLP_TEMPLATE_FOR_CONT_EXT 00153 _Tp& operator[](const _KT& __key) { 00154 iterator __it = _M_ht.find(__key); 00155 return (__it == _M_ht.end() ? 00156 _M_ht._M_insert(value_type(__key, _STLP_DEFAULT_CONSTRUCTED(_Tp))).second : 00157 (*__it).second ); 00158 } 00159 00160 _STLP_TEMPLATE_FOR_CONT_EXT 00161 size_type count(const _KT& __key) const { return _M_ht.count(__key); } 00162 00163 _STLP_TEMPLATE_FOR_CONT_EXT 00164 pair<iterator, iterator> equal_range(const _KT& __key) 00165 { return _M_ht.equal_range(__key); } 00166 _STLP_TEMPLATE_FOR_CONT_EXT 00167 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const 00168 { return _M_ht.equal_range(__key); } 00169 00170 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 00171 void erase(const_iterator __it) { _M_ht.erase(__it); } 00172 void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); } 00173 void clear() { _M_ht.clear(); } 00174 00175 size_type bucket_count() const { return _M_ht.bucket_count(); } 00176 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 00177 size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); } 00178 _STLP_TEMPLATE_FOR_CONT_EXT 00179 size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); } 00180 local_iterator begin(size_type __n) { return _M_ht.begin(__n); } 00181 local_iterator end(size_type __n) { return _M_ht.end(__n); } 00182 const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); } 00183 const_local_iterator end(size_type __n) const { return _M_ht.end(__n); } 00184 00185 float load_factor() const { return _M_ht.load_factor(); } 00186 float max_load_factor() const { return _M_ht.max_load_factor(); } 00187 void max_load_factor(float __val) { _M_ht.max_load_factor(__val); } 00188 void rehash(size_type __hint) { _M_ht.rehash(__hint); } 00189 00190 #if defined (__DMC__) // disable operator==(pair<x,unordered_map>, pair<x,unordered_map>) 00191 bool operator==(const _Self&) const; 00192 #endif 00193 }; 00194 00195 _STLP_END_NAMESPACE 00196 00197 //Specific iterator traits creation 00198 _STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMultimapTraitsT, traits) 00199 00200 _STLP_BEGIN_TR1_NAMESPACE 00201 00202 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>), 00203 _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Key>), 00204 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) > 00205 class unordered_multimap 00206 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 00207 : public __stlport_class<unordered_multimap<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> > 00208 #endif 00209 { 00210 private: 00211 typedef unordered_multimap<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self; 00212 public: 00213 typedef _Key key_type; 00214 typedef _Tp data_type; 00215 typedef _Tp mapped_type; 00216 typedef pair<_STLP_CONST key_type, data_type> value_type; 00217 private: 00218 //Specific iterator traits creation 00219 typedef _STLP_PRIV _UnorderedMultimapTraitsT<value_type> _UnorderedMultimapTraits; 00220 00221 public: 00222 typedef hashtable<value_type, key_type, _HashFcn, _UnorderedMultimapTraits, 00223 _STLP_SELECT1ST(value_type, _Key), _EqualKey, _Alloc > _Ht; 00224 00225 typedef typename _Ht::hasher hasher; 00226 typedef typename _Ht::key_equal key_equal; 00227 00228 typedef typename _Ht::size_type size_type; 00229 typedef typename _Ht::difference_type difference_type; 00230 typedef typename _Ht::pointer pointer; 00231 typedef typename _Ht::const_pointer const_pointer; 00232 typedef typename _Ht::reference reference; 00233 typedef typename _Ht::const_reference const_reference; 00234 00235 typedef typename _Ht::iterator iterator; 00236 typedef typename _Ht::const_iterator const_iterator; 00237 typedef typename _Ht::local_iterator local_iterator; 00238 typedef typename _Ht::const_local_iterator const_local_iterator; 00239 00240 typedef typename _Ht::allocator_type allocator_type; 00241 00242 hasher hash_function() const { return _M_ht.hash_funct(); } 00243 key_equal key_eq() const { return _M_ht.key_eq(); } 00244 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 00245 00246 private: 00247 _Ht _M_ht; 00248 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 00249 00250 public: 00251 explicit unordered_multimap(size_type __n = 0, const hasher& __hf = hasher(), 00252 const key_equal& __eql = key_equal(), 00253 const allocator_type& __a = allocator_type()) 00254 : _M_ht(__n, __hf, __eql, __a) {} 00255 00256 #if !defined (_STLP_NO_MOVE_SEMANTIC) 00257 unordered_multimap(__move_source<_Self> src) 00258 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {} 00259 #endif 00260 00261 #if defined (_STLP_MEMBER_TEMPLATES) 00262 template <class _InputIterator> 00263 unordered_multimap(_InputIterator __f, _InputIterator __l, 00264 size_type __n = 0, const hasher& __hf = hasher(), 00265 const key_equal& __eql = key_equal(), 00266 const allocator_type& __a = allocator_type()) 00267 : _M_ht(__n, __hf, __eql, __a) 00268 { _M_ht.insert_equal(__f, __l); } 00269 #else 00270 unordered_multimap(const value_type* __f, const value_type* __l, 00271 size_type __n = 0, const hasher& __hf = hasher(), 00272 const key_equal& __eql = key_equal(), 00273 const allocator_type& __a = allocator_type()) 00274 : _M_ht(__n, __hf, __eql, __a) 00275 { _M_ht.insert_equal(__f, __l); } 00276 00277 unordered_multimap(const_iterator __f, const_iterator __l, 00278 size_type __n = 0, const hasher& __hf = hasher(), 00279 const key_equal& __eql = key_equal(), 00280 const allocator_type& __a = allocator_type()) 00281 : _M_ht(__n, __hf, __eql, __a) 00282 { _M_ht.insert_equal(__f, __l); } 00283 #endif /*_STLP_MEMBER_TEMPLATES */ 00284 00285 _Self& operator = (const _Self& __other) 00286 { _M_ht = __other._M_ht; return *this; } 00287 00288 size_type size() const { return _M_ht.size(); } 00289 size_type max_size() const { return _M_ht.max_size(); } 00290 bool empty() const { return _M_ht.empty(); } 00291 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); } 00292 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 00293 void _M_swap_workaround(_Self& __x) { swap(__x); } 00294 #endif 00295 00296 iterator begin() { return _M_ht.begin(); } 00297 iterator end() { return _M_ht.end(); } 00298 const_iterator begin() const { return _M_ht.begin(); } 00299 const_iterator end() const { return _M_ht.end(); } 00300 00301 iterator insert(const value_type& __obj) 00302 { return _M_ht.insert_equal(__obj); } 00303 iterator insert(const_iterator /*__hint*/, const value_type& __obj) 00304 { return _M_ht.insert_equal(__obj); } 00305 #if defined (_STLP_MEMBER_TEMPLATES) 00306 template <class _InputIterator> 00307 void insert(_InputIterator __f, _InputIterator __l) 00308 #else 00309 void insert(const value_type* __f, const value_type* __l) 00310 { _M_ht.insert_equal(__f,__l); } 00311 void insert(const_iterator __f, const_iterator __l) 00312 #endif /*_STLP_MEMBER_TEMPLATES */ 00313 { _M_ht.insert_equal(__f, __l); } 00314 00315 _STLP_TEMPLATE_FOR_CONT_EXT 00316 iterator find(const _KT& __key) { return _M_ht.find(__key); } 00317 _STLP_TEMPLATE_FOR_CONT_EXT 00318 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); } 00319 00320 _STLP_TEMPLATE_FOR_CONT_EXT 00321 size_type count(const _KT& __key) const { return _M_ht.count(__key); } 00322 00323 _STLP_TEMPLATE_FOR_CONT_EXT 00324 pair<iterator, iterator> equal_range(const _KT& __key) 00325 { return _M_ht.equal_range(__key); } 00326 _STLP_TEMPLATE_FOR_CONT_EXT 00327 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const 00328 { return _M_ht.equal_range(__key); } 00329 00330 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 00331 void erase(const_iterator __it) { _M_ht.erase(__it); } 00332 void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); } 00333 void clear() { _M_ht.clear(); } 00334 00335 size_type bucket_count() const { return _M_ht.bucket_count(); } 00336 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 00337 size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); } 00338 _STLP_TEMPLATE_FOR_CONT_EXT 00339 size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); } 00340 local_iterator begin(size_type __n) { return _M_ht.begin(__n); } 00341 local_iterator end(size_type __n) { return _M_ht.end(__n); } 00342 const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); } 00343 const_local_iterator end(size_type __n) const { return _M_ht.end(__n); } 00344 00345 float load_factor() const { return _M_ht.load_factor(); } 00346 float max_load_factor() const { return _M_ht.max_load_factor(); } 00347 void max_load_factor(float __val) { _M_ht.max_load_factor(__val); } 00348 void rehash(size_type __hint) { _M_ht.rehash(__hint); } 00349 }; 00350 00351 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 00352 #define _STLP_TEMPLATE_CONTAINER unordered_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc> 00353 00354 #include <stl/_relops_hash_cont.h> 00355 00356 #undef _STLP_TEMPLATE_CONTAINER 00357 #define _STLP_TEMPLATE_CONTAINER unordered_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc> 00358 00359 #include <stl/_relops_hash_cont.h> 00360 00361 #undef _STLP_TEMPLATE_CONTAINER 00362 #undef _STLP_TEMPLATE_HEADER 00363 00364 _STLP_END_NAMESPACE 00365 00366 // Specialization of insert_iterator so that it will work for unordered_map 00367 // and unordered_multimap. 00368 00369 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 00370 # if !defined (_STLP_NO_MOVE_SEMANTIC) 00371 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 00372 struct __move_traits<_STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > : 00373 _STLP_PRIV __move_traits_help<typename _STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>::_Ht> 00374 {}; 00375 00376 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 00377 struct __move_traits<_STLP_TR1 unordered_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > : 00378 _STLP_PRIV __move_traits_help<typename _STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>::_Ht> 00379 {}; 00380 # endif 00381 00382 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 00383 class insert_iterator<_STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 00384 protected: 00385 typedef _STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 00386 _Container* container; 00387 public: 00388 typedef _Container container_type; 00389 typedef output_iterator_tag iterator_category; 00390 typedef void value_type; 00391 typedef void difference_type; 00392 typedef void pointer; 00393 typedef void reference; 00394 00395 insert_iterator(_Container& __x) : container(&__x) {} 00396 insert_iterator(_Container& __x, typename _Container::iterator) 00397 : container(&__x) {} 00398 insert_iterator<_Container>& 00399 operator=(const typename _Container::value_type& __val) { 00400 container->insert(__val); 00401 return *this; 00402 } 00403 insert_iterator<_Container>& operator*() { return *this; } 00404 insert_iterator<_Container>& operator++() { return *this; } 00405 insert_iterator<_Container>& operator++(int) { return *this; } 00406 }; 00407 00408 template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 00409 class insert_iterator<_STLP_TR1 unordered_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 00410 protected: 00411 typedef _STLP_TR1 unordered_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 00412 _Container* container; 00413 typename _Container::iterator iter; 00414 public: 00415 typedef _Container container_type; 00416 typedef output_iterator_tag iterator_category; 00417 typedef void value_type; 00418 typedef void difference_type; 00419 typedef void pointer; 00420 typedef void reference; 00421 00422 insert_iterator(_Container& __x) : container(&__x) {} 00423 insert_iterator(_Container& __x, typename _Container::iterator) 00424 : container(&__x) {} 00425 insert_iterator<_Container>& 00426 operator=(const typename _Container::value_type& __val) { 00427 container->insert(__val); 00428 return *this; 00429 } 00430 insert_iterator<_Container>& operator*() { return *this; } 00431 insert_iterator<_Container>& operator++() { return *this; } 00432 insert_iterator<_Container>& operator++(int) { return *this; } 00433 }; 00434 00435 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 00436 00437 _STLP_END_NAMESPACE 00438 00439 #endif /* _STLP_INTERNAL_UNORDERED_MAP_H */ 00440 00441 // Local Variables: 00442 // mode:C++ 00443 // End:
Generated on Sun May 27 2012 04:29:43 for ReactOS by
1.7.6.1
