ReactOS Development > Doxygen
_map.h
Go to the documentation of this file.
00001 /* 00002 * 00003 * Copyright (c) 1994 00004 * Hewlett-Packard Company 00005 * 00006 * Copyright (c) 1996,1997 00007 * Silicon Graphics Computer Systems, Inc. 00008 * 00009 * Copyright (c) 1997 00010 * Moscow Center for SPARC Technology 00011 * 00012 * Copyright (c) 1999 00013 * Boris Fomitchev 00014 * 00015 * This material is provided "as is", with absolutely no warranty expressed 00016 * or implied. Any use is at your own risk. 00017 * 00018 * Permission to use or copy this software for any purpose is hereby granted 00019 * without fee, provided the above notices are retained on all copies. 00020 * Permission to modify the code and to distribute modified code is granted, 00021 * provided the above notices are retained, and a notice that the code was 00022 * modified is included with the above copyright notice. 00023 * 00024 */ 00025 00026 /* NOTE: This is an internal header file, included by other STL headers. 00027 * You should not attempt to use it directly. 00028 */ 00029 00030 #ifndef _STLP_INTERNAL_MAP_H 00031 #define _STLP_INTERNAL_MAP_H 00032 00033 #ifndef _STLP_INTERNAL_TREE_H 00034 # include <stl/_tree.h> 00035 #endif 00036 00037 _STLP_BEGIN_NAMESPACE 00038 00039 //Specific iterator traits creation 00040 _STLP_CREATE_ITERATOR_TRAITS(MapTraitsT, traits) 00041 00042 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key> ), 00043 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) > 00044 class map 00045 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 00046 : public __stlport_class<map<_Key, _Tp, _Compare, _Alloc> > 00047 #endif 00048 { 00049 typedef map<_Key, _Tp, _Compare, _Alloc> _Self; 00050 public: 00051 00052 // typedefs: 00053 00054 typedef _Key key_type; 00055 typedef _Tp data_type; 00056 typedef _Tp mapped_type; 00057 typedef pair<_STLP_CONST _Key, _Tp> value_type; 00058 typedef _Compare key_compare; 00059 00060 class value_compare 00061 : public binary_function<value_type, value_type, bool> { 00062 friend class map<_Key,_Tp,_Compare,_Alloc>; 00063 protected : 00064 //c is a Standard name (23.3.1), do no make it STLport naming convention compliant. 00065 _Compare comp; 00066 value_compare(_Compare __c) : comp(__c) {} 00067 public: 00068 bool operator()(const value_type& __x, const value_type& __y) const 00069 { return comp(__x.first, __y.first); } 00070 }; 00071 00072 protected: 00073 typedef _STLP_PRIV _MapTraitsT<value_type> _MapTraits; 00074 00075 public: 00076 //Following typedef have to be public for __move_traits specialization. 00077 typedef _STLP_PRIV _Rb_tree<key_type, key_compare, 00078 value_type, _STLP_SELECT1ST(value_type, _Key), 00079 _MapTraits, _Alloc> _Rep_type; 00080 00081 typedef typename _Rep_type::pointer pointer; 00082 typedef typename _Rep_type::const_pointer const_pointer; 00083 typedef typename _Rep_type::reference reference; 00084 typedef typename _Rep_type::const_reference const_reference; 00085 typedef typename _Rep_type::iterator iterator; 00086 typedef typename _Rep_type::const_iterator const_iterator; 00087 typedef typename _Rep_type::reverse_iterator reverse_iterator; 00088 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 00089 typedef typename _Rep_type::size_type size_type; 00090 typedef typename _Rep_type::difference_type difference_type; 00091 typedef typename _Rep_type::allocator_type allocator_type; 00092 00093 private: 00094 _Rep_type _M_t; // red-black tree representing map 00095 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 00096 00097 public: 00098 // allocation/deallocation 00099 map() : _M_t(_Compare(), allocator_type()) {} 00100 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) 00101 explicit map(const _Compare& __comp, 00102 const allocator_type& __a = allocator_type()) 00103 #else 00104 explicit map(const _Compare& __comp) 00105 : _M_t(__comp, allocator_type()) {} 00106 explicit map(const _Compare& __comp, const allocator_type& __a) 00107 #endif 00108 : _M_t(__comp, __a) {} 00109 00110 #if defined (_STLP_MEMBER_TEMPLATES) 00111 template <class _InputIterator> 00112 map(_InputIterator __first, _InputIterator __last) 00113 : _M_t(_Compare(), allocator_type()) 00114 { _M_t.insert_unique(__first, __last); } 00115 00116 template <class _InputIterator> 00117 map(_InputIterator __first, _InputIterator __last, const _Compare& __comp, 00118 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 00119 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 00120 00121 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS) 00122 template <class _InputIterator> 00123 map(_InputIterator __first, _InputIterator __last, const _Compare& __comp) 00124 : _M_t(__comp, allocator_type()) { _M_t.insert_unique(__first, __last); } 00125 # endif 00126 00127 #else 00128 map(const value_type* __first, const value_type* __last) 00129 : _M_t(_Compare(), allocator_type()) 00130 { _M_t.insert_unique(__first, __last); } 00131 00132 map(const value_type* __first, 00133 const value_type* __last, const _Compare& __comp, 00134 const allocator_type& __a = allocator_type()) 00135 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 00136 00137 map(const_iterator __first, const_iterator __last) 00138 : _M_t(_Compare(), allocator_type()) 00139 { _M_t.insert_unique(__first, __last); } 00140 00141 map(const_iterator __first, const_iterator __last, const _Compare& __comp, 00142 const allocator_type& __a = allocator_type()) 00143 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); } 00144 #endif /* _STLP_MEMBER_TEMPLATES */ 00145 00146 map(const _Self& __x) : _M_t(__x._M_t) {} 00147 00148 #if !defined (_STLP_NO_MOVE_SEMANTIC) 00149 map(__move_source<_Self> src) 00150 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {} 00151 #endif 00152 00153 _Self& operator=(const _Self& __x) { 00154 _M_t = __x._M_t; 00155 return *this; 00156 } 00157 00158 // accessors: 00159 key_compare key_comp() const { return _M_t.key_comp(); } 00160 value_compare value_comp() const { return value_compare(_M_t.key_comp()); } 00161 allocator_type get_allocator() const { return _M_t.get_allocator(); } 00162 00163 iterator begin() { return _M_t.begin(); } 00164 const_iterator begin() const { return _M_t.begin(); } 00165 iterator end() { return _M_t.end(); } 00166 const_iterator end() const { return _M_t.end(); } 00167 reverse_iterator rbegin() { return _M_t.rbegin(); } 00168 const_reverse_iterator rbegin() const { return _M_t.rbegin(); } 00169 reverse_iterator rend() { return _M_t.rend(); } 00170 const_reverse_iterator rend() const { return _M_t.rend(); } 00171 bool empty() const { return _M_t.empty(); } 00172 size_type size() const { return _M_t.size(); } 00173 size_type max_size() const { return _M_t.max_size(); } 00174 _STLP_TEMPLATE_FOR_CONT_EXT 00175 _Tp& operator[](const _KT& __k) { 00176 iterator __i = lower_bound(__k); 00177 // __i->first is greater than or equivalent to __k. 00178 if (__i == end() || key_comp()(__k, (*__i).first)) 00179 __i = insert(__i, value_type(__k, _STLP_DEFAULT_CONSTRUCTED(_Tp))); 00180 return (*__i).second; 00181 } 00182 void swap(_Self& __x) { _M_t.swap(__x._M_t); } 00183 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 00184 void _M_swap_workaround(_Self& __x) { swap(__x); } 00185 #endif 00186 00187 // insert/erase 00188 pair<iterator,bool> insert(const value_type& __x) 00189 { return _M_t.insert_unique(__x); } 00190 iterator insert(iterator __pos, const value_type& __x) 00191 { return _M_t.insert_unique(__pos, __x); } 00192 #ifdef _STLP_MEMBER_TEMPLATES 00193 template <class _InputIterator> 00194 void insert(_InputIterator __first, _InputIterator __last) 00195 { _M_t.insert_unique(__first, __last); } 00196 #else 00197 void insert(const value_type* __first, const value_type* __last) 00198 { _M_t.insert_unique(__first, __last); } 00199 void insert(const_iterator __first, const_iterator __last) 00200 { _M_t.insert_unique(__first, __last); } 00201 #endif /* _STLP_MEMBER_TEMPLATES */ 00202 00203 void erase(iterator __pos) { _M_t.erase(__pos); } 00204 size_type erase(const key_type& __x) { return _M_t.erase_unique(__x); } 00205 void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); } 00206 void clear() { _M_t.clear(); } 00207 00208 // map operations: 00209 _STLP_TEMPLATE_FOR_CONT_EXT 00210 iterator find(const _KT& __x) { return _M_t.find(__x); } 00211 _STLP_TEMPLATE_FOR_CONT_EXT 00212 const_iterator find(const _KT& __x) const { return _M_t.find(__x); } 00213 _STLP_TEMPLATE_FOR_CONT_EXT 00214 size_type count(const _KT& __x) const { return _M_t.find(__x) == _M_t.end() ? 0 : 1; } 00215 _STLP_TEMPLATE_FOR_CONT_EXT 00216 iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); } 00217 _STLP_TEMPLATE_FOR_CONT_EXT 00218 const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); } 00219 _STLP_TEMPLATE_FOR_CONT_EXT 00220 iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); } 00221 _STLP_TEMPLATE_FOR_CONT_EXT 00222 const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); } 00223 00224 _STLP_TEMPLATE_FOR_CONT_EXT 00225 pair<iterator,iterator> equal_range(const _KT& __x) 00226 { return _M_t.equal_range_unique(__x); } 00227 _STLP_TEMPLATE_FOR_CONT_EXT 00228 pair<const_iterator,const_iterator> equal_range(const _KT& __x) const 00229 { return _M_t.equal_range_unique(__x); } 00230 }; 00231 00232 //Specific iterator traits creation 00233 _STLP_CREATE_ITERATOR_TRAITS(MultimapTraitsT, traits) 00234 00235 template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key> ), 00236 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) > 00237 class multimap 00238 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 00239 : public __stlport_class<multimap<_Key, _Tp, _Compare, _Alloc> > 00240 #endif 00241 { 00242 typedef multimap<_Key, _Tp, _Compare, _Alloc> _Self; 00243 public: 00244 00245 // typedefs: 00246 00247 typedef _Key key_type; 00248 typedef _Tp data_type; 00249 typedef _Tp mapped_type; 00250 typedef pair<_STLP_CONST _Key, _Tp> value_type; 00251 typedef _Compare key_compare; 00252 00253 class value_compare : public binary_function<value_type, value_type, bool> { 00254 friend class multimap<_Key,_Tp,_Compare,_Alloc>; 00255 protected: 00256 //comp is a Standard name (23.3.2), do no make it STLport naming convention compliant. 00257 _Compare comp; 00258 value_compare(_Compare __c) : comp(__c) {} 00259 public: 00260 bool operator()(const value_type& __x, const value_type& __y) const 00261 { return comp(__x.first, __y.first); } 00262 }; 00263 00264 protected: 00265 //Specific iterator traits creation 00266 typedef _STLP_PRIV _MultimapTraitsT<value_type> _MultimapTraits; 00267 00268 public: 00269 //Following typedef have to be public for __move_traits specialization. 00270 typedef _STLP_PRIV _Rb_tree<key_type, key_compare, 00271 value_type, _STLP_SELECT1ST(value_type, _Key), 00272 _MultimapTraits, _Alloc> _Rep_type; 00273 00274 typedef typename _Rep_type::pointer pointer; 00275 typedef typename _Rep_type::const_pointer const_pointer; 00276 typedef typename _Rep_type::reference reference; 00277 typedef typename _Rep_type::const_reference const_reference; 00278 typedef typename _Rep_type::iterator iterator; 00279 typedef typename _Rep_type::const_iterator const_iterator; 00280 typedef typename _Rep_type::reverse_iterator reverse_iterator; 00281 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 00282 typedef typename _Rep_type::size_type size_type; 00283 typedef typename _Rep_type::difference_type difference_type; 00284 typedef typename _Rep_type::allocator_type allocator_type; 00285 00286 private: 00287 _Rep_type _M_t; // red-black tree representing multimap 00288 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 00289 00290 public: 00291 // allocation/deallocation 00292 multimap() : _M_t(_Compare(), allocator_type()) { } 00293 explicit multimap(const _Compare& __comp, 00294 const allocator_type& __a = allocator_type()) 00295 : _M_t(__comp, __a) { } 00296 00297 #ifdef _STLP_MEMBER_TEMPLATES 00298 template <class _InputIterator> 00299 multimap(_InputIterator __first, _InputIterator __last) 00300 : _M_t(_Compare(), allocator_type()) 00301 { _M_t.insert_equal(__first, __last); } 00302 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS 00303 template <class _InputIterator> 00304 multimap(_InputIterator __first, _InputIterator __last, 00305 const _Compare& __comp) 00306 : _M_t(__comp, allocator_type()) { _M_t.insert_equal(__first, __last); } 00307 # endif 00308 template <class _InputIterator> 00309 multimap(_InputIterator __first, _InputIterator __last, 00310 const _Compare& __comp, 00311 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 00312 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 00313 #else 00314 multimap(const value_type* __first, const value_type* __last) 00315 : _M_t(_Compare(), allocator_type()) 00316 { _M_t.insert_equal(__first, __last); } 00317 multimap(const value_type* __first, const value_type* __last, 00318 const _Compare& __comp, 00319 const allocator_type& __a = allocator_type()) 00320 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 00321 00322 multimap(const_iterator __first, const_iterator __last) 00323 : _M_t(_Compare(), allocator_type()) 00324 { _M_t.insert_equal(__first, __last); } 00325 multimap(const_iterator __first, const_iterator __last, 00326 const _Compare& __comp, 00327 const allocator_type& __a = allocator_type()) 00328 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 00329 #endif /* _STLP_MEMBER_TEMPLATES */ 00330 00331 multimap(const _Self& __x) : _M_t(__x._M_t) {} 00332 00333 #if !defined (_STLP_NO_MOVE_SEMANTIC) 00334 multimap(__move_source<_Self> src) 00335 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {} 00336 #endif 00337 00338 _Self& operator=(const _Self& __x) { 00339 _M_t = __x._M_t; 00340 return *this; 00341 } 00342 00343 // accessors: 00344 00345 key_compare key_comp() const { return _M_t.key_comp(); } 00346 value_compare value_comp() const { return value_compare(_M_t.key_comp()); } 00347 allocator_type get_allocator() const { return _M_t.get_allocator(); } 00348 00349 iterator begin() { return _M_t.begin(); } 00350 const_iterator begin() const { return _M_t.begin(); } 00351 iterator end() { return _M_t.end(); } 00352 const_iterator end() const { return _M_t.end(); } 00353 reverse_iterator rbegin() { return _M_t.rbegin(); } 00354 const_reverse_iterator rbegin() const { return _M_t.rbegin(); } 00355 reverse_iterator rend() { return _M_t.rend(); } 00356 const_reverse_iterator rend() const { return _M_t.rend(); } 00357 bool empty() const { return _M_t.empty(); } 00358 size_type size() const { return _M_t.size(); } 00359 size_type max_size() const { return _M_t.max_size(); } 00360 void swap(_Self& __x) { _M_t.swap(__x._M_t); } 00361 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 00362 void _M_swap_workaround(_Self& __x) { swap(__x); } 00363 #endif 00364 00365 // insert/erase 00366 iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); } 00367 iterator insert(iterator __pos, const value_type& __x) { return _M_t.insert_equal(__pos, __x); } 00368 #if defined (_STLP_MEMBER_TEMPLATES) 00369 template <class _InputIterator> 00370 void insert(_InputIterator __first, _InputIterator __last) 00371 { _M_t.insert_equal(__first, __last); } 00372 #else 00373 void insert(const value_type* __first, const value_type* __last) 00374 { _M_t.insert_equal(__first, __last); } 00375 void insert(const_iterator __first, const_iterator __last) 00376 { _M_t.insert_equal(__first, __last); } 00377 #endif /* _STLP_MEMBER_TEMPLATES */ 00378 void erase(iterator __pos) { _M_t.erase(__pos); } 00379 size_type erase(const key_type& __x) { return _M_t.erase(__x); } 00380 void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); } 00381 void clear() { _M_t.clear(); } 00382 00383 // multimap operations: 00384 00385 _STLP_TEMPLATE_FOR_CONT_EXT 00386 iterator find(const _KT& __x) { return _M_t.find(__x); } 00387 _STLP_TEMPLATE_FOR_CONT_EXT 00388 const_iterator find(const _KT& __x) const { return _M_t.find(__x); } 00389 _STLP_TEMPLATE_FOR_CONT_EXT 00390 size_type count(const _KT& __x) const { return _M_t.count(__x); } 00391 _STLP_TEMPLATE_FOR_CONT_EXT 00392 iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); } 00393 _STLP_TEMPLATE_FOR_CONT_EXT 00394 const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); } 00395 _STLP_TEMPLATE_FOR_CONT_EXT 00396 iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); } 00397 _STLP_TEMPLATE_FOR_CONT_EXT 00398 const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); } 00399 _STLP_TEMPLATE_FOR_CONT_EXT 00400 pair<iterator,iterator> equal_range(const _KT& __x) 00401 { return _M_t.equal_range(__x); } 00402 _STLP_TEMPLATE_FOR_CONT_EXT 00403 pair<const_iterator,const_iterator> equal_range(const _KT& __x) const 00404 { return _M_t.equal_range(__x); } 00405 }; 00406 00407 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _Compare, class _Alloc> 00408 #define _STLP_TEMPLATE_CONTAINER map<_Key,_Tp,_Compare,_Alloc> 00409 #include <stl/_relops_cont.h> 00410 #undef _STLP_TEMPLATE_CONTAINER 00411 #define _STLP_TEMPLATE_CONTAINER multimap<_Key,_Tp,_Compare,_Alloc> 00412 #include <stl/_relops_cont.h> 00413 #undef _STLP_TEMPLATE_CONTAINER 00414 #undef _STLP_TEMPLATE_HEADER 00415 00416 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC) 00417 template <class _Key, class _Tp, class _Compare, class _Alloc> 00418 struct __move_traits<map<_Key,_Tp,_Compare,_Alloc> > : 00419 _STLP_PRIV __move_traits_aux<typename map<_Key,_Tp,_Compare,_Alloc>::_Rep_type> 00420 {}; 00421 00422 template <class _Key, class _Tp, class _Compare, class _Alloc> 00423 struct __move_traits<multimap<_Key,_Tp,_Compare,_Alloc> > : 00424 _STLP_PRIV __move_traits_aux<typename multimap<_Key,_Tp,_Compare,_Alloc>::_Rep_type> 00425 {}; 00426 #endif 00427 00428 _STLP_END_NAMESPACE 00429 00430 #endif /* _STLP_INTERNAL_MAP_H */ 00431 00432 // Local Variables: 00433 // mode:C++ 00434 // End: 00435
Generated on Thu May 24 2012 04:29:58 for ReactOS by
1.7.6.1
