1 /* 2 * Copyright (c) 2005 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 /* NOTE: This is an internal header file, included by other STL headers. 16 * You should not attempt to use it directly. 17 */ 18 19 #ifndef _STLP_PTR_SPECIALIZED_SET_H 20 #define _STLP_PTR_SPECIALIZED_SET_H 21 22 #ifndef _STLP_POINTERS_SPEC_TOOLS_H 23 # include <stl/pointers/_tools.h> 24 #endif 25 26 _STLP_BEGIN_NAMESPACE 27 28 #if defined (__BORLANDC__) || defined (__DMC__) 29 # define typename 30 #endif 31 32 //Specific iterator traits creation 33 _STLP_CREATE_ITERATOR_TRAITS(SetTraitsT, Const_traits) 34 35 #if defined (_STLP_USE_TEMPLATE_EXPORT) && !defined (_STLP_USE_MSVC6_MEM_T_BUG_WORKAROUND) 36 _STLP_EXPORT template struct _STLP_CLASS_DECLSPEC less<void*>; 37 38 _STLP_MOVE_TO_PRIV_NAMESPACE 39 40 typedef _Rb_tree_node<void*> _Node; 41 _STLP_EXPORT_TEMPLATE_CLASS _STLP_alloc_proxy<_Rb_tree_node_base, _Node, allocator<_Node> >; 42 _STLP_EXPORT_TEMPLATE_CLASS _Rb_tree_base<void*, allocator<void*> >; 43 # if defined (_STLP_DEBUG) 44 _STLP_EXPORT_TEMPLATE_CLASS _DbgCompare<void*, less<void*> >; 45 # define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree) 46 _STLP_EXPORT_TEMPLATE_CLASS _Rb_tree<void*, _DbgCompare<void*, less<void*> >, void*, _Identity<void*>, 47 _SetTraitsT<void*>, allocator<void*> >; 48 # undef _Rb_tree 49 # endif 50 _STLP_EXPORT_TEMPLATE_CLASS _Rb_tree<void*, less<void*>, void*, _Identity<void*>, 51 _SetTraitsT<void*>, allocator<void*> >; 52 _STLP_MOVE_TO_STD_NAMESPACE 53 #endif 54 55 template <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>), 56 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Key>) > 57 class set 58 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 59 : public __stlport_class<set<_Key, _Compare, _Alloc> > 60 #endif 61 { 62 #if !defined (__BORLANDC__) 63 typedef _STLP_PRIV _AssocStorageTypes<_Key, _Compare> _AssocStorageTypes; 64 typedef typename _AssocStorageTypes::_KeyStorageType _KeyStorageType; 65 typedef typename _AssocStorageTypes::_CompareStorageType _CompareStorageType; 66 #else 67 typedef _STLP_PRIV _AssocStorageTypes<_Key, _Compare>::_KeyStorageType _KeyStorageType; 68 typedef _STLP_PRIV _AssocStorageTypes<_Key, _Compare>::_CompareStorageType _CompareStorageType; 69 #endif 70 typedef typename _Alloc_traits<_KeyStorageType, _Alloc>::allocator_type _StorageTypeAlloc; 71 typedef _STLP_PRIV _CastTraits<_KeyStorageType, _Key> cast_traits; 72 73 typedef set<_Key, _Compare, _Alloc> _Self; 74 public: 75 typedef _Key key_type; 76 typedef _Key value_type; 77 typedef _Compare key_compare; 78 typedef _Compare value_compare; 79 80 protected: 81 //Specific iterator traits creation 82 typedef _STLP_PRIV _SetTraitsT<value_type> _SetTraits; 83 typedef _STLP_PRIV _Rb_tree<key_type, key_compare, 84 value_type, _STLP_PRIV _Identity<value_type>, 85 _SetTraits, _Alloc> _Priv_Rep_type; 86 87 typedef _STLP_PRIV _SetTraitsT<_KeyStorageType> _SetStorageTraits; 88 89 public: 90 //dums: need the following public for the __move_traits framework 91 typedef _STLP_PRIV _Rb_tree<_KeyStorageType, _CompareStorageType, 92 _KeyStorageType, _STLP_PRIV _Identity<_KeyStorageType>, 93 _SetStorageTraits, _StorageTypeAlloc> _Rep_type; 94 95 private: 96 typedef typename _Rep_type::iterator base_iterator; 97 typedef typename _Rep_type::const_iterator const_base_iterator; 98 99 public: 100 typedef typename _Priv_Rep_type::pointer pointer; 101 typedef typename _Priv_Rep_type::const_pointer const_pointer; 102 typedef typename _Priv_Rep_type::reference reference; 103 typedef typename _Priv_Rep_type::const_reference const_reference; 104 typedef typename _Priv_Rep_type::iterator iterator; 105 typedef typename _Priv_Rep_type::const_iterator const_iterator; 106 typedef typename _Priv_Rep_type::reverse_iterator reverse_iterator; 107 typedef typename _Priv_Rep_type::const_reverse_iterator const_reverse_iterator; 108 typedef typename _Priv_Rep_type::size_type size_type; 109 typedef typename _Priv_Rep_type::difference_type difference_type; 110 typedef typename _Priv_Rep_type::allocator_type allocator_type; 111 112 private: 113 _Rep_type _M_t; // red-black tree representing set 114 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 115 116 #if defined (_STLP_DEBUG) 117 static iterator _S_to_value_ite(const_base_iterator __ite) 118 { return iterator(__ite._Owner(), __ite._M_iterator._M_node); } 119 static base_iterator _S_to_storage_ite(const_iterator __ite) 120 { return base_iterator(__ite._Owner(), __ite._M_iterator._M_node); } 121 #else 122 static iterator _S_to_value_ite(const_base_iterator __ite) 123 { return iterator(__ite._M_node); } 124 static base_iterator _S_to_storage_ite(const_iterator __ite) 125 { return base_iterator(__ite._M_node); } 126 #endif 127 128 public: 129 set() : _M_t(_CompareStorageType(), _StorageTypeAlloc()) {} 130 explicit set(const _Compare& __comp, 131 const allocator_type& __a = allocator_type()) 132 : _M_t(__comp, _STLP_CONVERT_ALLOCATOR(__a, _KeyStorageType)) {} 133 134 #if defined (_STLP_MEMBER_TEMPLATES) 135 template <class _InputIterator> 136 set(_InputIterator __first, _InputIterator __last) 137 : _M_t(_Compare(), _StorageTypeAlloc()) { 138 # if defined (_STLP_USE_ITERATOR_WRAPPER) 139 _M_t.insert_unique(_STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__first), 140 _STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__last)); 141 # else 142 _M_t.insert_unique(__first, __last); 143 # endif 144 } 145 146 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS) 147 template <class _InputIterator> 148 set(_InputIterator __first, _InputIterator __last, const _Compare& __comp) 149 : _M_t(__comp, _StorageTypeAlloc()) { 150 # if defined (_STLP_USE_ITERATOR_WRAPPER) 151 _M_t.insert_unique(_STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__first), 152 _STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__last)); 153 # else 154 _M_t.insert_unique(__first, __last); 155 # endif 156 } 157 # endif 158 template <class _InputIterator> 159 set(_InputIterator __first, _InputIterator __last, const _Compare& __comp, 160 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 161 : _M_t(__comp, _STLP_CONVERT_ALLOCATOR(__a, _KeyStorageType)) { 162 # if defined (_STLP_USE_ITERATOR_WRAPPER) 163 _M_t.insert_unique(_STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__first), 164 _STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__last)); 165 # else 166 _M_t.insert_unique(__first, __last); 167 # endif 168 } 169 #else 170 set(const value_type* __first, const value_type* __last) 171 : _M_t(_Compare(), _StorageTypeAlloc()) { 172 _M_t.insert_unique(cast_traits::to_storage_type_cptr(__first), 173 cast_traits::to_storage_type_cptr(__last)); 174 } 175 176 set(const value_type* __first, const value_type* __last, 177 const _Compare& __comp, const allocator_type& __a = allocator_type()) 178 : _M_t(__comp, _STLP_CONVERT_ALLOCATOR(__a, _KeyStorageType)) { 179 _M_t.insert_unique(cast_traits::to_storage_type_cptr(__first), 180 cast_traits::to_storage_type_cptr(__last)); 181 } 182 183 set(const_iterator __first, const_iterator __last) 184 : _M_t(_Compare(), _StorageTypeAlloc()) 185 { _M_t.insert_unique(_S_to_storage_ite(__first), _S_to_storage_ite(__last)); } 186 187 set(const_iterator __first, const_iterator __last, 188 const _Compare& __comp, const allocator_type& __a = allocator_type()) 189 : _M_t(__comp, _STLP_CONVERT_ALLOCATOR(__a, _KeyStorageType)) 190 { _M_t.insert_unique(_S_to_storage_ite(__first), _S_to_storage_ite(__last)); } 191 #endif /* _STLP_MEMBER_TEMPLATES */ 192 193 set(const _Self& __x) : _M_t(__x._M_t) {} 194 195 #if !defined (_STLP_NO_MOVE_SEMANTIC) 196 set(__move_source<_Self> src) 197 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {} 198 #endif 199 200 _Self& operator=(const _Self& __x) { 201 _M_t = __x._M_t; 202 return *this; 203 } 204 205 // accessors: 206 key_compare key_comp() const { return _M_t.key_comp(); } 207 value_compare value_comp() const { return _M_t.key_comp(); } 208 allocator_type get_allocator() const 209 { return _STLP_CONVERT_ALLOCATOR(_M_t.get_allocator(), value_type); } 210 211 iterator begin() { return _S_to_value_ite(_M_t.begin()); } 212 iterator end() { return _S_to_value_ite(_M_t.end()); } 213 const_iterator begin() const { return _S_to_value_ite(_M_t.begin()); } 214 const_iterator end() const { return _S_to_value_ite(_M_t.end()); } 215 reverse_iterator rbegin() { return reverse_iterator(end()); } 216 reverse_iterator rend() { return reverse_iterator(begin()); } 217 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 218 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 219 bool empty() const { return _M_t.empty(); } 220 size_type size() const { return _M_t.size(); } 221 size_type max_size() const { return _M_t.max_size(); } 222 void swap(_Self& __x) { _M_t.swap(__x._M_t); } 223 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 224 void _M_swap_workaround(_Self& __x) { swap(__x); } 225 #endif 226 227 // insert/erase 228 pair<iterator,bool> insert(const value_type& __x) { 229 pair<base_iterator, bool> ret = _M_t.insert_unique(cast_traits::to_storage_type_cref(__x)); 230 return pair<iterator, bool>(_S_to_value_ite(ret.first), ret.second); 231 } 232 iterator insert(iterator __pos, const value_type& __x) 233 { return _S_to_value_ite(_M_t.insert_unique(_S_to_storage_ite(__pos), cast_traits::to_storage_type_cref(__x))); } 234 235 #if defined (_STLP_MEMBER_TEMPLATES) 236 template <class _InputIterator> 237 void insert(_InputIterator __first, _InputIterator __last) { 238 # if defined (_STLP_USE_ITERATOR_WRAPPER) 239 _M_t.insert_unique(_STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__first), 240 _STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__last)); 241 # else 242 _M_t.insert_unique(__first, __last); 243 # endif 244 } 245 #else 246 void insert(const_iterator __first, const_iterator __last) 247 { _M_t.insert_unique(_S_to_storage_ite(__first), _S_to_storage_ite(__last)); } 248 void insert(const value_type* __first, const value_type* __last) { 249 _M_t.insert_unique(cast_traits::to_storage_type_cptr(__first), 250 cast_traits::to_storage_type_cptr(__last)); 251 } 252 #endif 253 void erase(iterator __pos) 254 { _M_t.erase(_S_to_storage_ite(__pos)); } 255 size_type erase(const key_type& __x) 256 { return _M_t.erase_unique(cast_traits::to_storage_type_cref(__x)); } 257 void erase(iterator __first, iterator __last) 258 { _M_t.erase(_S_to_storage_ite(__first), _S_to_storage_ite(__last)); } 259 void clear() { _M_t.clear(); } 260 261 // set operations: 262 _STLP_TEMPLATE_FOR_CONT_EXT 263 const_iterator find(const _KT& __x) const 264 { return _S_to_value_ite(_M_t.find(cast_traits::to_storage_type_crefT(__x))); } 265 _STLP_TEMPLATE_FOR_CONT_EXT 266 iterator find(const _KT& __x) 267 { return _S_to_value_ite(_M_t.find(cast_traits::to_storage_type_crefT(__x))); } 268 _STLP_TEMPLATE_FOR_CONT_EXT 269 size_type count(const _KT& __x) const 270 { return _M_t.find(cast_traits::to_storage_type_crefT(__x)) == _M_t.end() ? 0 : 1; } 271 _STLP_TEMPLATE_FOR_CONT_EXT 272 iterator lower_bound(const _KT& __x) 273 { return _S_to_value_ite(_M_t.lower_bound(cast_traits::to_storage_type_crefT(__x))); } 274 _STLP_TEMPLATE_FOR_CONT_EXT 275 const_iterator lower_bound(const _KT& __x) const 276 { return _S_to_value_ite(_M_t.lower_bound(cast_traits::to_storage_type_crefT(__x))); } 277 _STLP_TEMPLATE_FOR_CONT_EXT 278 iterator upper_bound(const _KT& __x) 279 { return _S_to_value_ite(_M_t.upper_bound(cast_traits::to_storage_type_crefT(__x))); } 280 _STLP_TEMPLATE_FOR_CONT_EXT 281 const_iterator upper_bound(const _KT& __x) const 282 { return _S_to_value_ite(_M_t.upper_bound(cast_traits::to_storage_type_crefT(__x))); } 283 _STLP_TEMPLATE_FOR_CONT_EXT 284 pair<iterator, iterator> equal_range(const _KT& __x) { 285 pair<base_iterator, base_iterator> __ret; 286 __ret = _M_t.equal_range(cast_traits::to_storage_type_crefT(__x)); 287 return pair<iterator, iterator>(_S_to_value_ite(__ret.first), 288 _S_to_value_ite(__ret.second)); 289 } 290 _STLP_TEMPLATE_FOR_CONT_EXT 291 pair<const_iterator, const_iterator> equal_range(const _KT& __x) const { 292 pair<const_base_iterator, const_base_iterator> __ret; 293 __ret = _M_t.equal_range_unique(cast_traits::to_storage_type_crefT(__x)); 294 return pair<const_iterator, const_iterator>(_S_to_value_ite(__ret.first), 295 _S_to_value_ite(__ret.second)); 296 } 297 }; 298 299 //Specific iterator traits creation 300 _STLP_CREATE_ITERATOR_TRAITS(MultisetTraitsT, Const_traits) 301 302 template <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>), 303 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Key>) > 304 class multiset 305 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 306 : public __stlport_class<multiset<_Key, _Compare, _Alloc> > 307 #endif 308 { 309 #if !defined (__BORLANDC__) 310 typedef _STLP_PRIV _AssocStorageTypes<_Key, _Compare> _AssocStorageTypes; 311 typedef typename _AssocStorageTypes::_KeyStorageType _KeyStorageType; 312 typedef typename _AssocStorageTypes::_CompareStorageType _CompareStorageType; 313 #else 314 typedef _STLP_PRIV _AssocStorageTypes<_Key, _Compare>::_KeyStorageType _KeyStorageType; 315 typedef _STLP_PRIV _AssocStorageTypes<_Key, _Compare>::_CompareStorageType _CompareStorageType; 316 #endif 317 typedef typename _Alloc_traits<_KeyStorageType, _Alloc>::allocator_type _StorageTypeAlloc; 318 typedef _STLP_PRIV _CastTraits<_KeyStorageType, _Key> cast_traits; 319 320 typedef multiset<_Key, _Compare, _Alloc> _Self; 321 public: 322 // typedefs: 323 typedef _Key key_type; 324 typedef _Key value_type; 325 typedef _Compare key_compare; 326 typedef _Compare value_compare; 327 328 protected: 329 //Specific iterator traits creation 330 typedef _STLP_PRIV _MultisetTraitsT<value_type> _MultisetTraits; 331 typedef _STLP_PRIV _Rb_tree<key_type, key_compare, 332 value_type, _STLP_PRIV _Identity<value_type>, 333 _MultisetTraits, _Alloc> _Priv_Rep_type; 334 335 typedef _STLP_PRIV _MultisetTraitsT<_KeyStorageType> _MultisetStorageTraits; 336 public: 337 //dums: need the following public for the __move_traits framework 338 typedef _STLP_PRIV _Rb_tree<_KeyStorageType, _CompareStorageType, 339 _KeyStorageType, _STLP_PRIV _Identity<_KeyStorageType>, 340 _MultisetStorageTraits, _StorageTypeAlloc> _Rep_type; 341 342 private: 343 typedef typename _Rep_type::iterator base_iterator; 344 typedef typename _Rep_type::const_iterator const_base_iterator; 345 346 public: 347 typedef typename _Priv_Rep_type::pointer pointer; 348 typedef typename _Priv_Rep_type::const_pointer const_pointer; 349 typedef typename _Priv_Rep_type::reference reference; 350 typedef typename _Priv_Rep_type::const_reference const_reference; 351 typedef typename _Priv_Rep_type::iterator iterator; 352 typedef typename _Priv_Rep_type::const_iterator const_iterator; 353 typedef typename _Priv_Rep_type::reverse_iterator reverse_iterator; 354 typedef typename _Priv_Rep_type::const_reverse_iterator const_reverse_iterator; 355 typedef typename _Priv_Rep_type::size_type size_type; 356 typedef typename _Priv_Rep_type::difference_type difference_type; 357 typedef typename _Priv_Rep_type::allocator_type allocator_type; 358 359 private: 360 _Rep_type _M_t; // red-black tree representing multiset 361 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 362 363 #if defined (_STLP_DEBUG) 364 static iterator _S_to_value_ite(const_base_iterator __ite) 365 { return iterator(__ite._Owner(), __ite._M_iterator._M_node); } 366 static base_iterator _S_to_storage_ite(const_iterator __ite) 367 { return base_iterator(__ite._Owner(), __ite._M_iterator._M_node); } 368 #else 369 static iterator _S_to_value_ite(const_base_iterator __ite) 370 { return iterator(__ite._M_node); } 371 static base_iterator _S_to_storage_ite(const_iterator __ite) 372 { return base_iterator(__ite._M_node); } 373 #endif 374 375 public: 376 multiset() : _M_t(_Compare(), _StorageTypeAlloc()) {} 377 explicit multiset(const _Compare& __comp, 378 const allocator_type& __a = allocator_type()) 379 : _M_t(__comp, _STLP_CONVERT_ALLOCATOR(__a, _KeyStorageType)) {} 380 381 #if defined (_STLP_MEMBER_TEMPLATES) 382 template <class _InputIterator> 383 multiset(_InputIterator __first, _InputIterator __last) 384 : _M_t(_Compare(), _StorageTypeAlloc()) { 385 # if defined (_STLP_USE_ITERATOR_WRAPPER) 386 _M_t.insert_equal(_STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__first), 387 _STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__last)); 388 # else 389 _M_t.insert_equal(__first, __last); 390 # endif 391 } 392 393 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS) 394 template <class _InputIterator> 395 multiset(_InputIterator __first, _InputIterator __last, 396 const _Compare& __comp) 397 : _M_t(__comp, _StorageTypeAlloc()) { 398 # if defined (_STLP_USE_ITERATOR_WRAPPER) 399 _M_t.insert_equal(_STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__first), 400 _STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__last)); 401 # else 402 _M_t.insert_equal(__first, __last); 403 # endif 404 } 405 # endif 406 template <class _InputIterator> 407 multiset(_InputIterator __first, _InputIterator __last, 408 const _Compare& __comp, 409 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 410 : _M_t(__comp, _STLP_CONVERT_ALLOCATOR(__a, _KeyStorageType)) { 411 # if defined (_STLP_USE_ITERATOR_WRAPPER) 412 _M_t.insert_equal(_STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__first), 413 _STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__last)); 414 # else 415 _M_t.insert_equal(__first, __last); 416 # endif 417 } 418 419 #else 420 multiset(const value_type* __first, const value_type* __last) 421 : _M_t(_Compare(), _StorageTypeAlloc()) { 422 _M_t.insert_equal(cast_traits::to_storage_type_cptr(__first), 423 cast_traits::to_storage_type_cptr(__last)); 424 } 425 426 multiset(const value_type* __first, const value_type* __last, 427 const _Compare& __comp, 428 const allocator_type& __a = allocator_type()) 429 : _M_t(__comp, _STLP_CONVERT_ALLOCATOR(__a, _KeyStorageType)) { 430 _M_t.insert_equal(cast_traits::to_storage_type_cptr(__first), 431 cast_traits::to_storage_type_cptr(__last)); 432 } 433 434 multiset(const_iterator __first, const_iterator __last) 435 : _M_t(_Compare(), _StorageTypeAlloc()) 436 { _M_t.insert_equal(_S_to_storage_ite(__first), _S_to_storage_ite(__last)); } 437 438 multiset(const_iterator __first, const_iterator __last, 439 const _Compare& __comp, 440 const allocator_type& __a = allocator_type()) 441 : _M_t(__comp, _STLP_CONVERT_ALLOCATOR(__a, _KeyStorageType)) 442 { _M_t.insert_equal(_S_to_storage_ite(__first), _S_to_storage_ite(__last)); } 443 #endif /* _STLP_MEMBER_TEMPLATES */ 444 445 multiset(const _Self& __x) 446 : _M_t(__x._M_t) {} 447 448 _Self& operator=(const _Self& __x) { 449 _M_t = __x._M_t; 450 return *this; 451 } 452 453 #if !defined (_STLP_NO_MOVE_SEMANTIC) 454 multiset(__move_source<_Self> src) 455 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {} 456 #endif 457 458 // accessors: 459 key_compare key_comp() const { return _M_t.key_comp(); } 460 value_compare value_comp() const { return _M_t.key_comp(); } 461 allocator_type get_allocator() const 462 { return _STLP_CONVERT_ALLOCATOR(_M_t.get_allocator(), value_type); } 463 464 iterator begin() { return _S_to_value_ite(_M_t.begin()); } 465 iterator end() { return _S_to_value_ite(_M_t.end()); } 466 const_iterator begin() const { return _S_to_value_ite(_M_t.begin()); } 467 const_iterator end() const { return _S_to_value_ite(_M_t.end()); } 468 reverse_iterator rbegin() { return reverse_iterator(end()); } 469 reverse_iterator rend() { return reverse_iterator(begin()); } 470 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 471 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 472 bool empty() const { return _M_t.empty(); } 473 size_type size() const { return _M_t.size(); } 474 size_type max_size() const { return _M_t.max_size(); } 475 void swap(_Self& __x) { _M_t.swap(__x._M_t); } 476 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 477 void _M_swap_workaround(_Self& __x) { swap(__x); } 478 #endif 479 480 // insert/erase 481 iterator insert(const value_type& __x) 482 { return _S_to_value_ite(_M_t.insert_equal(cast_traits::to_storage_type_cref(__x))); } 483 iterator insert(iterator __pos, const value_type& __x) { 484 return _S_to_value_ite(_M_t.insert_equal(_S_to_storage_ite(__pos), 485 cast_traits::to_storage_type_cref(__x))); 486 } 487 488 #if defined (_STLP_MEMBER_TEMPLATES) 489 template <class _InputIterator> 490 void insert(_InputIterator __first, _InputIterator __last) { 491 # if defined (_STLP_USE_ITERATOR_WRAPPER) 492 _M_t.insert_equal(_STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__first), 493 _STLP_TYPENAME _STLP_PRIV _IteWrapper<_KeyStorageType, _Key, _InputIterator>::_Ite(__last)); 494 # else 495 _M_t.insert_equal(__first, __last); 496 # endif 497 } 498 #else 499 void insert(const value_type* __first, const value_type* __last) { 500 _M_t.insert_equal(cast_traits::to_storage_type_cptr(__first), 501 cast_traits::to_storage_type_cptr(__last)); 502 } 503 void insert(const_iterator __first, const_iterator __last) 504 { _M_t.insert_equal(_S_to_storage_ite(__first), _S_to_storage_ite(__last)); } 505 #endif /* _STLP_MEMBER_TEMPLATES */ 506 507 void erase(iterator __pos) 508 { _M_t.erase(_S_to_storage_ite(__pos)); } 509 size_type erase(const key_type& __x) 510 { return _M_t.erase(cast_traits::to_storage_type_cref(__x)); } 511 void erase(iterator __first, iterator __last) 512 { _M_t.erase(_S_to_storage_ite(__first), _S_to_storage_ite(__last)); } 513 void clear() { _M_t.clear(); } 514 515 // multiset operations: 516 517 _STLP_TEMPLATE_FOR_CONT_EXT 518 iterator find(const _KT& __x) 519 { return _S_to_value_ite(_M_t.find(cast_traits::to_storage_type_crefT(__x))); } 520 _STLP_TEMPLATE_FOR_CONT_EXT 521 const_iterator find(const _KT& __x) const 522 { return _S_to_value_ite(_M_t.find(cast_traits::to_storage_type_crefT(__x))); } 523 _STLP_TEMPLATE_FOR_CONT_EXT 524 size_type count(const _KT& __x) const 525 { return _M_t.count(cast_traits::to_storage_type_crefT(__x)); } 526 _STLP_TEMPLATE_FOR_CONT_EXT 527 iterator lower_bound(const _KT& __x) 528 { return _S_to_value_ite(_M_t.lower_bound(cast_traits::to_storage_type_crefT(__x))); } 529 _STLP_TEMPLATE_FOR_CONT_EXT 530 const_iterator lower_bound(const _KT& __x) const 531 { return _S_to_value_ite(_M_t.lower_bound(cast_traits::to_storage_type_crefT(__x))); } 532 _STLP_TEMPLATE_FOR_CONT_EXT 533 iterator upper_bound(const _KT& __x) 534 { return _S_to_value_ite(_M_t.upper_bound(cast_traits::to_storage_type_crefT(__x))); } 535 _STLP_TEMPLATE_FOR_CONT_EXT 536 const_iterator upper_bound(const _KT& __x) const 537 { return _S_to_value_ite(_M_t.upper_bound(cast_traits::to_storage_type_crefT(__x))); } 538 _STLP_TEMPLATE_FOR_CONT_EXT 539 pair<iterator, iterator> equal_range(const _KT& __x) { 540 pair<base_iterator, base_iterator> __ret; 541 __ret = _M_t.equal_range(cast_traits::to_storage_type_crefT(__x)); 542 return pair<iterator, iterator>(_S_to_value_ite(__ret.first), 543 _S_to_value_ite(__ret.second)); 544 } 545 _STLP_TEMPLATE_FOR_CONT_EXT 546 pair<const_iterator, const_iterator> equal_range(const _KT& __x) const { 547 pair<const_base_iterator, const_base_iterator> __ret; 548 __ret = _M_t.equal_range(cast_traits::to_storage_type_crefT(__x)); 549 return pair<const_iterator, const_iterator>(_S_to_value_ite(__ret.first), 550 _S_to_value_ite(__ret.second)); 551 } 552 }; 553 554 #if defined (__BORLANDC__) || defined (__DMC__) 555 # undef typename 556 #endif 557 558 _STLP_END_NAMESPACE 559 560 #endif /* _STLP_PTR_SPECIALIZED_SET_H */ 561 562 // Local Variables: 563 // mode:C++ 564 // End: 565