include/c++/stl/stl/pointers/_set.h

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