include/c++/stlport/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 #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: