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

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Copyright (c) 1996,1997
   7  * Silicon Graphics Computer Systems, Inc.
   8  *
   9  * Copyright (c) 1997
  10  * Moscow Center for SPARC Technology
  11  *
  12  * Copyright (c) 1999
  13  * Boris Fomitchev
  14  *
  15  * This material is provided "as is", with absolutely no warranty expressed
  16  * or implied. Any use is at your own risk.
  17  *
  18  * Permission to use or copy this software for any purpose is hereby granted
  19  * without fee, provided the above notices are retained on all copies.
  20  * Permission to modify the code and to distribute modified code is granted,
  21  * provided the above notices are retained, and a notice that the code was
  22  * modified is included with the above copyright notice.
  23  *
  24  */
  25
  26 /* NOTE: This is an internal header file, included by other STL headers.
  27  *   You should not attempt to use it directly.
  28  */
  29
  30 #ifndef _STLP_INTERNAL_SET_H
  31 #define _STLP_INTERNAL_SET_H
  32
  33 #ifndef _STLP_INTERNAL_TREE_H
  34 #  include <stl/_tree.h>
  35 #endif
  36
  37 #if !defined (_STLP_USE_PTR_SPECIALIZATIONS)
  38
  39 _STLP_BEGIN_NAMESPACE
  40
  41 //Specific iterator traits creation
  42 _STLP_CREATE_ITERATOR_TRAITS(SetTraitsT, Const_traits)
  43
  44 template <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>),
  45                      _STLP_DEFAULT_ALLOCATOR_SELECT(_Key) >
  46 class set
  47 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
  48           : public __stlport_class<set<_Key, _Compare, _Alloc> >
  49 #endif
  50 {
  51   typedef set<_Key, _Compare, _Alloc> _Self;
  52 public:
  53 // typedefs:
  54   typedef _Key     key_type;
  55   typedef _Key     value_type;
  56   typedef _Compare key_compare;
  57   typedef _Compare value_compare;
  58
  59 private:
  60   //Specific iterator traits creation
  61   typedef _STLP_PRIV _SetTraitsT<value_type> _SetTraits;
  62
  63 public:
  64   //Following typedef have to be public for __move_traits specialization.
  65   typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
  66                               value_type, _STLP_PRIV _Identity<value_type>,
  67                               _SetTraits, _Alloc> _Rep_type;
  68
  69   typedef typename _Rep_type::pointer pointer;
  70   typedef typename _Rep_type::const_pointer const_pointer;
  71   typedef typename _Rep_type::reference reference;
  72   typedef typename _Rep_type::const_reference const_reference;
  73   typedef typename _Rep_type::iterator iterator;
  74   typedef typename _Rep_type::const_iterator const_iterator;
  75   typedef typename _Rep_type::reverse_iterator reverse_iterator;
  76   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
  77   typedef typename _Rep_type::size_type size_type;
  78   typedef typename _Rep_type::difference_type difference_type;
  79   typedef typename _Rep_type::allocator_type allocator_type;
  80
  81 private:
  82   _Rep_type _M_t;  // red-black tree representing set
  83   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
  84
  85 public:
  86
  87   // allocation/deallocation
  88 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
  89   explicit set(const _Compare& __comp = _Compare(),
  90                const allocator_type& __a = allocator_type())
  91 #else
  92   set()
  93     : _M_t(_Compare(), allocator_type()) {}
  94   explicit set(const _Compare& __comp)
  95     : _M_t(__comp, allocator_type()) {}
  96   set(const _Compare& __comp, const allocator_type& __a)
  97 #endif
  98     : _M_t(__comp, __a) {}
  99
 100 #if defined (_STLP_MEMBER_TEMPLATES)
 101   template <class _InputIterator>
 102   set(_InputIterator __first, _InputIterator __last)
 103     : _M_t(_Compare(), allocator_type())
 104     { _M_t.insert_unique(__first, __last); }
 105
 106 #  if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
 107   template <class _InputIterator>
 108   set(_InputIterator __first, _InputIterator __last, const _Compare& __comp)
 109     : _M_t(__comp, allocator_type()) { _M_t.insert_unique(__first, __last); }
 110 #  endif
 111   template <class _InputIterator>
 112   set(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
 113       const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
 114     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
 115 #else
 116   set(const value_type* __first, const value_type* __last)
 117     : _M_t(_Compare(), allocator_type())
 118     { _M_t.insert_unique(__first, __last); }
 119
 120   set(const value_type* __first,
 121       const value_type* __last, const _Compare& __comp,
 122       const allocator_type& __a = allocator_type())
 123     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
 124
 125   set(const_iterator __first, const_iterator __last)
 126     : _M_t(_Compare(), allocator_type())
 127     { _M_t.insert_unique(__first, __last); }
 128
 129   set(const_iterator __first, const_iterator __last, const _Compare& __comp,
 130       const allocator_type& __a = allocator_type())
 131     : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
 132 #endif /* _STLP_MEMBER_TEMPLATES */
 133
 134   set(const _Self& __x) : _M_t(__x._M_t) {}
 135
 136   set(__move_source<_Self> src)
 137     : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
 138
 139   _Self& operator=(const _Self& __x) {
 140     _M_t = __x._M_t;
 141     return *this;
 142   }
 143
 144   // accessors:
 145   key_compare key_comp() const { return _M_t.key_comp(); }
 146   value_compare value_comp() const { return _M_t.key_comp(); }
 147   allocator_type get_allocator() const { return _M_t.get_allocator(); }
 148
 149   iterator begin() { return _M_t.begin(); }
 150   iterator end() { return _M_t.end(); }
 151   const_iterator begin() const { return _M_t.begin(); }
 152   const_iterator end() const { return _M_t.end(); }
 153   reverse_iterator rbegin() { return _M_t.rbegin(); }
 154   reverse_iterator rend() { return _M_t.rend(); }
 155   const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
 156   const_reverse_iterator rend() const { return _M_t.rend(); }
 157   bool empty() const { return _M_t.empty(); }
 158   size_type size() const { return _M_t.size(); }
 159   size_type max_size() const { return _M_t.max_size(); }
 160   void swap(_Self& __x) { _M_t.swap(__x._M_t); }
 161
 162   // insert/erase
 163   pair<iterator,bool> insert(const value_type& __x)
 164   { return _M_t.insert_unique(__x); }
 165   iterator insert(iterator __pos, const value_type& __x)
 166   { return _M_t.insert_unique( __pos , __x); }
 167 #if defined (_STLP_MEMBER_TEMPLATES)
 168   template <class _InputIterator>
 169   void insert(_InputIterator __first, _InputIterator __last)
 170   { _M_t.insert_unique(__first, __last); }
 171 #else
 172   void insert(const_iterator __first, const_iterator __last)
 173   { _M_t.insert_unique(__first, __last); }
 174   void insert(const value_type* __first, const value_type* __last)
 175   { _M_t.insert_unique(__first, __last); }
 176 #endif /* _STLP_MEMBER_TEMPLATES */
 177   void erase(iterator __pos) { _M_t.erase( __pos ); }
 178   size_type erase(const key_type& __x) { return _M_t.erase_unique(__x); }
 179   void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last ); }
 180   void clear() { _M_t.clear(); }
 181
 182   // set operations:
 183   _STLP_TEMPLATE_FOR_CONT_EXT
 184   const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
 185   _STLP_TEMPLATE_FOR_CONT_EXT
 186   iterator find(const _KT& __x) { return _M_t.find(__x); }
 187   _STLP_TEMPLATE_FOR_CONT_EXT
 188   size_type count(const _KT& __x) const
 189   { return _M_t.find(__x) == _M_t.end() ? 0 : 1 ; }
 190   _STLP_TEMPLATE_FOR_CONT_EXT
 191   iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
 192   _STLP_TEMPLATE_FOR_CONT_EXT
 193   const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
 194   _STLP_TEMPLATE_FOR_CONT_EXT
 195   iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
 196   _STLP_TEMPLATE_FOR_CONT_EXT
 197   const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
 198   _STLP_TEMPLATE_FOR_CONT_EXT
 199   pair<iterator, iterator> equal_range(const _KT& __x)
 200   { return _M_t.equal_range_unique(__x); }
 201   _STLP_TEMPLATE_FOR_CONT_EXT
 202   pair<const_iterator, const_iterator> equal_range(const _KT& __x) const
 203   { return _M_t.equal_range_unique(__x); }
 204 };
 205
 206 //Specific iterator traits creation
 207 _STLP_CREATE_ITERATOR_TRAITS(MultisetTraitsT, Const_traits)
 208
 209 template <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>),
 210           _STLP_DEFAULT_ALLOCATOR_SELECT(_Key) >
 211 class multiset
 212 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
 213                : public __stlport_class<multiset<_Key, _Compare, _Alloc> >
 214 #endif
 215 {
 216   typedef multiset<_Key, _Compare, _Alloc> _Self;
 217 public:
 218   // typedefs:
 219
 220   typedef _Key     key_type;
 221   typedef _Key     value_type;
 222   typedef _Compare key_compare;
 223   typedef _Compare value_compare;
 224
 225 private:
 226   //Specific iterator traits creation
 227   typedef _STLP_PRIV _MultisetTraitsT<value_type> _MultisetTraits;
 228
 229 public:
 230   //Following typedef have to be public for __move_traits specialization.
 231   typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
 232                               value_type, _STLP_PRIV _Identity<value_type>,
 233                               _MultisetTraits, _Alloc> _Rep_type;
 234
 235   typedef typename _Rep_type::pointer pointer;
 236   typedef typename _Rep_type::const_pointer const_pointer;
 237   typedef typename _Rep_type::reference reference;
 238   typedef typename _Rep_type::const_reference const_reference;
 239   typedef typename _Rep_type::iterator iterator;
 240   typedef typename _Rep_type::const_iterator const_iterator;
 241   typedef typename _Rep_type::reverse_iterator reverse_iterator;
 242   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
 243   typedef typename _Rep_type::size_type size_type;
 244   typedef typename _Rep_type::difference_type difference_type;
 245   typedef typename _Rep_type::allocator_type allocator_type;
 246
 247 private:
 248   _Rep_type _M_t;  // red-black tree representing multiset
 249   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
 250
 251 public:
 252 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
 253   explicit multiset(const _Compare& __comp = _Compare(),
 254                     const allocator_type& __a = allocator_type())
 255 #else
 256   multiset()
 257     : _M_t(_Compare(), allocator_type()) {}
 258   explicit multiset(const _Compare& __comp)
 259     : _M_t(__comp, allocator_type()) {}
 260   multiset(const _Compare& __comp, const allocator_type& __a)
 261 #endif
 262     : _M_t(__comp, __a) {}
 263
 264 #if defined (_STLP_MEMBER_TEMPLATES)
 265   template <class _InputIterator>
 266   multiset(_InputIterator __first, _InputIterator __last)
 267     : _M_t(_Compare(), allocator_type())
 268     { _M_t.insert_equal(__first, __last); }
 269
 270   template <class _InputIterator>
 271   multiset(_InputIterator __first, _InputIterator __last,
 272            const _Compare& __comp,
 273            const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
 274     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
 275 #  if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
 276   template <class _InputIterator>
 277   multiset(_InputIterator __first, _InputIterator __last,
 278            const _Compare& __comp)
 279     : _M_t(__comp, allocator_type()) { _M_t.insert_equal(__first, __last); }
 280 #  endif
 281 #else
 282   multiset(const value_type* __first, const value_type* __last)
 283     : _M_t(_Compare(), allocator_type())
 284     { _M_t.insert_equal(__first, __last); }
 285
 286   multiset(const value_type* __first, const value_type* __last,
 287            const _Compare& __comp,
 288            const allocator_type& __a = allocator_type())
 289     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
 290
 291   multiset(const_iterator __first, const_iterator __last)
 292     : _M_t(_Compare(), allocator_type())
 293     { _M_t.insert_equal(__first, __last); }
 294
 295   multiset(const_iterator __first, const_iterator __last,
 296            const _Compare& __comp,
 297            const allocator_type& __a = allocator_type())
 298     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
 299 #endif /* _STLP_MEMBER_TEMPLATES */
 300
 301   multiset(const _Self& __x) : _M_t(__x._M_t) {}
 302   _Self& operator=(const _Self& __x) {
 303     _M_t = __x._M_t;
 304     return *this;
 305   }
 306
 307   multiset(__move_source<_Self> src)
 308     : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
 309
 310   // accessors:
 311   key_compare key_comp() const { return _M_t.key_comp(); }
 312   value_compare value_comp() const { return _M_t.key_comp(); }
 313   allocator_type get_allocator() const { return _M_t.get_allocator(); }
 314
 315   iterator begin() { return _M_t.begin(); }
 316   iterator end() { return _M_t.end(); }
 317   const_iterator begin() const { return _M_t.begin(); }
 318   const_iterator end() const { return _M_t.end(); }
 319   reverse_iterator rbegin() { return _M_t.rbegin(); }
 320   reverse_iterator rend() { return _M_t.rend(); }
 321   const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
 322   const_reverse_iterator rend() const { return _M_t.rend(); }
 323   bool empty() const { return _M_t.empty(); }
 324   size_type size() const { return _M_t.size(); }
 325   size_type max_size() const { return _M_t.max_size(); }
 326   void swap(_Self& __x) { _M_t.swap(__x._M_t); }
 327
 328   // insert/erase
 329   iterator insert(const value_type& __x)
 330   { return _M_t.insert_equal(__x); }
 331   iterator insert(iterator __pos, const value_type& __x)
 332   { return _M_t.insert_equal(__pos, __x); }
 333
 334 #if defined (_STLP_MEMBER_TEMPLATES)
 335   template <class _InputIterator>
 336   void insert(_InputIterator __first, _InputIterator __last)
 337   { _M_t.insert_equal(__first, __last); }
 338 #else
 339   void insert(const value_type* __first, const value_type* __last)
 340   { _M_t.insert_equal(__first, __last); }
 341   void insert(const_iterator __first, const_iterator __last)
 342   { _M_t.insert_equal(__first, __last); }
 343 #endif /* _STLP_MEMBER_TEMPLATES */
 344   void erase(iterator __pos) { _M_t.erase( __pos ); }
 345   size_type erase(const key_type& __x) { return _M_t.erase(__x); }
 346   void erase(iterator __first, iterator __last) { _M_t.erase( __first, __last ); }
 347   void clear() { _M_t.clear(); }
 348
 349   // multiset operations:
 350   _STLP_TEMPLATE_FOR_CONT_EXT
 351   iterator find(const _KT& __x) { return _M_t.find(__x); }
 352   _STLP_TEMPLATE_FOR_CONT_EXT
 353   const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
 354   _STLP_TEMPLATE_FOR_CONT_EXT
 355   size_type count(const _KT& __x) const { return _M_t.count(__x); }
 356   _STLP_TEMPLATE_FOR_CONT_EXT
 357   iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
 358   _STLP_TEMPLATE_FOR_CONT_EXT
 359   const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
 360   _STLP_TEMPLATE_FOR_CONT_EXT
 361   iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
 362   _STLP_TEMPLATE_FOR_CONT_EXT
 363   const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
 364   _STLP_TEMPLATE_FOR_CONT_EXT
 365   pair<iterator, iterator> equal_range(const _KT& __x) { return _M_t.equal_range(__x); }
 366   _STLP_TEMPLATE_FOR_CONT_EXT
 367   pair<const_iterator, const_iterator> equal_range(const _KT& __x) const { return _M_t.equal_range(__x); }
 368 };
 369
 370 #else
 371 #  include <stl/pointers/_set.h>
 372 _STLP_BEGIN_NAMESPACE
 373 #endif /* _STLP_USE_PTR_SPECIALIZATIONS */
 374
 375 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Alloc>
 376 #define _STLP_TEMPLATE_CONTAINER set<_Key,_Compare,_Alloc>
 377 #include <stl/_relops_cont.h>
 378 #undef  _STLP_TEMPLATE_CONTAINER
 379 #define _STLP_TEMPLATE_CONTAINER multiset<_Key,_Compare,_Alloc>
 380 #include <stl/_relops_cont.h>
 381 #undef  _STLP_TEMPLATE_CONTAINER
 382 #undef  _STLP_TEMPLATE_HEADER
 383
 384 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
 385 template <class _Key, class _Compare, class _Alloc>
 386 struct __move_traits<set<_Key,_Compare,_Alloc> > :
 387   _STLP_PRIV __move_traits_aux<typename set<_Key,_Compare,_Alloc>::_Rep_type>
 388 {};
 389
 390 template <class _Key, class _Compare, class _Alloc>
 391 struct __move_traits<multiset<_Key,_Compare,_Alloc> > :
 392   _STLP_PRIV __move_traits_aux<typename multiset<_Key,_Compare,_Alloc>::_Rep_type>
 393 {};
 394 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
 395
 396 _STLP_END_NAMESPACE
 397
 398 #endif /* _STLP_INTERNAL_SET_H */
 399
 400 // Local Variables:
 401 // mode:C++
 402 // End: