1 _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 #define set __WORKAROUND_RENAME(set)

    38 #define multiset __WORKAROUND_RENAME(multiset)

    39 

    40 _STLP_BEGIN_NAMESPACE

    41 

    42 template <class _Key, __DFL_TMPL_PARAM(_Compare,less<_Key>), 

    43                      _STLP_DEFAULT_ALLOCATOR_SELECT(_Key) >

    44 class set 

    45 {

    46 public:

    47 // typedefs:

    48   typedef _Key     key_type;

    49   typedef _Key     value_type;

    50   typedef _Compare key_compare;

    51   typedef _Compare value_compare;

    52 private:

    53   typedef _Rb_tree<key_type, value_type, 

    54     _Identity<value_type>, key_compare, _Alloc> _Rep_type;

    55 public:

    56   typedef typename _Rep_type::pointer pointer;

    57   typedef typename _Rep_type::const_pointer const_pointer;

    58   typedef typename _Rep_type::reference reference;

    59   typedef typename _Rep_type::const_reference const_reference;

    60   typedef typename _Rep_type::const_iterator const_iterator;

    61   typedef const_iterator iterator;

    62   typedef typename _Rep_type::const_reverse_iterator reverse_iterator;

    63   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;

    64   typedef typename _Rep_type::size_type size_type;

    65   typedef typename _Rep_type::difference_type difference_type;

    66   typedef typename _Rep_type::allocator_type allocator_type;

    67   typedef set<_Key,_Compare,_Alloc> _Self;

    68 

    69 private:

    70   _Rep_type _M_t;  // red-black tree representing set

    71 public:

    72 

    73   // allocation/deallocation

    74 

    75   set() : _M_t(_Compare(), allocator_type()) {

    76     _STLP_POP_IF_CHECK

    77   }

    78 

    79 # ifdef _STLP_USE_TRAP_LEAVE

    80   set(const set<_Key,_Compare,_Alloc>& __x)

    81   {

    82     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

    83     _M_t =__x._M_t; 

    84     _STLP_POP_CLEANUP_ITEM

    85   }

    86 # else

    87   set(const set<_Key,_Compare,_Alloc>& __o)

    88     : _M_t(__o._M_t) {

    89   }

    90 # endif

    91 

    92   explicit set(const _Compare& __comp,

    93 	       const allocator_type& __a = allocator_type())

    94     : _M_t(__comp, __a) {

    95     _STLP_POP_IF_CHECK

    96   }

    97 

    98 #ifdef _STLP_MEMBER_TEMPLATES

    99   template <class _InputIterator>

   100   set(_InputIterator __first, _InputIterator __last)

   101     : _M_t(_Compare(), allocator_type())

   102     { 

   103       _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   104       _M_t.insert_unique(__first, __last); 

   105       _STLP_POP_CLEANUP_ITEM

   106 }

   107 

   108 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS

   109   template <class _InputIterator>

   110   set(_InputIterator __first, _InputIterator __last, const _Compare& __comp)

   111     : _M_t(__comp, allocator_type()) { 

   112     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   113       _M_t.insert_unique(__first, __last);

   114     _STLP_POP_CLEANUP_ITEM

   115   }

   116 # endif

   117   template <class _InputIterator>

   118   set(_InputIterator __first, _InputIterator __last, const _Compare& __comp,

   119       const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)

   120     : _M_t(__comp, __a) { 

   121     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   122     _M_t.insert_unique(__first, __last); 

   123     _STLP_POP_CLEANUP_ITEM

   124   }

   125 #else

   126   set(const value_type* __first, const value_type* __last) 

   127     : _M_t(_Compare(), allocator_type()) 

   128     { 

   129       _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   130       _M_t.insert_unique(__first, __last); 

   131       _STLP_POP_CLEANUP_ITEM

   132     }

   133 

   134   set(const value_type* __first, 

   135       const value_type* __last, const _Compare& __comp,

   136       const allocator_type& __a = allocator_type())

   137     : _M_t(__comp, __a) { 

   138     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   139     _M_t.insert_unique(__first, __last); 

   140     _STLP_POP_CLEANUP_ITEM

   141   }

   142 

   143   set(const_iterator __first, const_iterator __last)

   144     : _M_t(_Compare(), allocator_type()) 

   145     { 

   146       _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   147       _M_t.insert_unique(__first, __last); 

   148       _STLP_POP_CLEANUP_ITEM

   149     }

   150 

   151   set(const_iterator __first, const_iterator __last, const _Compare& __comp,

   152       const allocator_type& __a = allocator_type())

   153     : _M_t(__comp, __a) { 

   154     _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   155     _M_t.insert_unique(__first, __last); 

   156     _STLP_POP_CLEANUP_ITEM

   157   }

   158 #endif /* _STLP_MEMBER_TEMPLATES */

   159 

   160 

   161   set<_Key,_Compare,_Alloc>& operator=(const set<_Key, _Compare, _Alloc>& __x)

   162   { 

   163     _M_t = __x._M_t; 

   164     return *this;

   165   }

   166 

   167 #ifdef _STLP_USE_TRAP_LEAVE

   168 public:

   169   static void* operator new (size_t __n, TLeave) { return _STLP_StackHelper<bool>::_NewLC(__n); }

   170   static void* operator new (size_t __n) { return _STLP_StackHelper<bool>::_NewLC(__n); }

   171 #endif

   172 

   173 

   174   // accessors:

   175 

   176   key_compare key_comp() const { return _M_t.key_comp(); }

   177   value_compare value_comp() const { return _M_t.key_comp(); }

   178   allocator_type get_allocator() const { return _M_t.get_allocator(); }

   179 

   180   iterator begin() const { return _M_t.begin(); }

   181   iterator end() const { return _M_t.end(); }

   182   reverse_iterator rbegin() const { return _M_t.rbegin(); } 

   183   reverse_iterator rend() const { return _M_t.rend(); }

   184   bool empty() const { return _M_t.empty(); }

   185   size_type size() const { return _M_t.size(); }

   186   size_type max_size() const { return _M_t.max_size(); }

   187   void swap(set<_Key,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }

   188 

   189   // insert/erase

   190   pair<iterator,bool> insert(const value_type& __x) { 

   191     typedef typename _Rep_type::iterator _Rep_iterator;

   192     pair<_Rep_iterator, bool> __p = _M_t.insert_unique(__x); 

   193     return pair<iterator, bool>(__REINTERPRET_CAST(const iterator&,__p.first), __p.second);

   194   }

   195   iterator insert(iterator __position, const value_type& __x) {

   196     typedef typename _Rep_type::iterator _Rep_iterator;

   197     return _M_t.insert_unique((_Rep_iterator&)__position, __x);

   198   }

   199 #ifdef _STLP_MEMBER_TEMPLATES

   200   template <class _InputIterator>

   201   void insert(_InputIterator __first, _InputIterator __last) {

   202     _M_t.insert_unique(__first, __last);

   203   }

   204 #else

   205   void insert(const_iterator __first, const_iterator __last) {

   206     _M_t.insert_unique(__first, __last);

   207   }

   208   void insert(const value_type* __first, const value_type* __last) {

   209     _M_t.insert_unique(__first, __last);

   210   }

   211 #endif /* _STLP_MEMBER_TEMPLATES */

   212   void erase(iterator __position) { 

   213     typedef typename _Rep_type::iterator _Rep_iterator;

   214     _M_t.erase((_Rep_iterator&)__position); 

   215   }

   216   size_type erase(const key_type& __x) { 

   217     return _M_t.erase(__x); 

   218   }

   219   void erase(iterator __first, iterator __last) { 

   220     typedef typename _Rep_type::iterator _Rep_iterator;

   221     _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last); 

   222   }

   223   void clear() { _M_t.clear(); }

   224 

   225   // set operations:

   226 # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS )

   227   template <class _KT>

   228   iterator find(const _KT& __x) const { return _M_t.find(__x); }

   229 # else

   230   iterator find(const key_type& __x) const { return _M_t.find(__x); }

   231 # endif

   232   size_type count(const key_type& __x) const { 

   233     return _M_t.find(__x) == _M_t.end() ? 0 : 1 ; 

   234   }

   235   iterator lower_bound(const key_type& __x) const {

   236     return _M_t.lower_bound(__x);

   237   }

   238   iterator upper_bound(const key_type& __x) const {

   239     return _M_t.upper_bound(__x); 

   240   }

   241   pair<iterator,iterator> equal_range(const key_type& __x) const {

   242     return _M_t.equal_range(__x);

   243   }

   244 };

   245 

   246 template <class _Key, __DFL_TMPL_PARAM(_Compare,less<_Key>), 

   247                      _STLP_DEFAULT_ALLOCATOR_SELECT(_Key) >

   248 class multiset 

   249 {

   250 public:

   251   // typedefs:

   252 

   253   typedef _Key     key_type;

   254   typedef _Key     value_type;

   255   typedef _Compare key_compare;

   256   typedef _Compare value_compare;

   257 private:

   258   typedef _Rb_tree<key_type, value_type, 

   259                   _Identity<value_type>, key_compare, _Alloc> _Rep_type;

   260 public:

   261   typedef typename _Rep_type::pointer pointer;

   262   typedef typename _Rep_type::const_pointer const_pointer;

   263   typedef typename _Rep_type::reference reference;

   264   typedef typename _Rep_type::const_reference const_reference;

   265   typedef typename _Rep_type::const_iterator const_iterator;

   266   typedef const_iterator iterator;

   267   typedef typename _Rep_type::const_reverse_iterator reverse_iterator;

   268   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;

   269   typedef typename _Rep_type::size_type size_type;

   270   typedef typename _Rep_type::difference_type difference_type;

   271   typedef typename _Rep_type::allocator_type allocator_type;

   272 

   273   typedef multiset<_Key,_Compare,_Alloc> _Self;

   274 

   275 private:

   276   _Rep_type _M_t;  // red-black tree representing multiset

   277 public:

   278   // allocation/deallocation

   279 

   280   multiset() : _M_t(_Compare(), allocator_type()) {

   281     _STLP_POP_IF_CHECK

   282   }

   283 

   284 # ifdef _STLP_USE_TRAP_LEAVE

   285   multiset(const multiset<_Key,_Compare,_Alloc>& __x)

   286   {

   287      _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   288     _M_t =__x._M_t; 

   289      _STLP_POP_CLEANUP_ITEM

   290   }

   291 # else

   292   multiset(const multiset<_Key,_Compare,_Alloc>& __o)

   293     : _M_t(__o._M_t) {

   294   }

   295 # endif

   296 

   297   explicit multiset(const _Compare& __comp,

   298                     const allocator_type& __a = allocator_type())

   299     : _M_t(__comp, __a) {

   300     _STLP_POP_IF_CHECK

   301   }

   302 

   303 #ifdef _STLP_MEMBER_TEMPLATES

   304 

   305   template <class _InputIterator>

   306   multiset(_InputIterator __first, _InputIterator __last)

   307     : _M_t(_Compare(), allocator_type())

   308     { 

   309        _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   310        _M_t.insert_equal(__first, __last); 

   311        _STLP_POP_CLEANUP_ITEM

   312     }

   313 

   314 # ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS

   315   template <class _InputIterator>

   316   multiset(_InputIterator __first, _InputIterator __last,

   317            const _Compare& __comp)

   318     : _M_t(__comp, allocator_type()) { 

   319      _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   320      _M_t.insert_equal(__first, __last); 

   321      _STLP_POP_CLEANUP_ITEM

   322   }

   323 # endif

   324   template <class _InputIterator>

   325   multiset(_InputIterator __first, _InputIterator __last,

   326            const _Compare& __comp,

   327            const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)

   328     : _M_t(__comp, __a) { 

   329      _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   330      _M_t.insert_equal(__first, __last); 

   331      _STLP_POP_CLEANUP_ITEM

   332   }

   333 

   334 #else

   335 

   336   multiset(const value_type* __first, const value_type* __last)

   337     : _M_t(_Compare(), allocator_type())

   338     {

   339       _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   340       _M_t.insert_equal(__first, __last); 

   341       _STLP_POP_CLEANUP_ITEM

   342     }

   343 

   344   multiset(const value_type* __first, const value_type* __last,

   345            const _Compare& __comp,

   346            const allocator_type& __a = allocator_type())

   347     : _M_t(__comp, __a) { 

   348      _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   349      _M_t.insert_equal(__first, __last); 

   350      _STLP_POP_CLEANUP_ITEM

   351   }

   352 

   353   multiset(const_iterator __first, const_iterator __last)

   354     : _M_t(_Compare(), allocator_type())

   355     { 

   356        _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   357        _M_t.insert_equal(__first, __last);

   358        _STLP_POP_CLEANUP_ITEM

   359     }

   360 

   361   multiset(const_iterator __first, const_iterator __last,

   362            const _Compare& __comp,

   363            const allocator_type& __a = allocator_type())

   364     : _M_t(__comp, __a) { 

   365      _STLP_PUSH_CLEANUP_ITEM(_Self, this)

   366      _M_t.insert_equal(__first, __last); 

   367      _STLP_POP_CLEANUP_ITEM

   368   }

   369    

   370 #endif /* _STLP_MEMBER_TEMPLATES */

   371 

   372   multiset<_Key,_Compare,_Alloc>&

   373   operator=(const multiset<_Key,_Compare,_Alloc>& __x) {

   374     _M_t = __x._M_t; 

   375     return *this;

   376   }

   377 

   378 #ifdef _STLP_USE_TRAP_LEAVE

   379 public:

   380   static void* operator new (size_t __n, TLeave) { return _STLP_StackHelper<bool>::_NewLC(__n); }

   381   static void* operator new (size_t __n) { return _STLP_StackHelper<bool>::_NewLC(__n); }

   382 #endif

   383 

   384   // accessors:

   385 

   386   key_compare key_comp() const { return _M_t.key_comp(); }

   387   value_compare value_comp() const { return _M_t.key_comp(); }

   388   allocator_type get_allocator() const { return _M_t.get_allocator(); }

   389 

   390   iterator begin() const { return _M_t.begin(); }

   391   iterator end() const { return _M_t.end(); }

   392   reverse_iterator rbegin() const { return _M_t.rbegin(); } 

   393   reverse_iterator rend() const { return _M_t.rend(); }

   394   bool empty() const { return _M_t.empty(); }

   395   size_type size() const { return _M_t.size(); }

   396   size_type max_size() const { return _M_t.max_size(); }

   397   void swap(multiset<_Key,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }

   398 

   399   // insert/erase

   400   iterator insert(const value_type& __x) { 

   401     return _M_t.insert_equal(__x);

   402   }

   403   iterator insert(iterator __position, const value_type& __x) {

   404     typedef typename _Rep_type::iterator _Rep_iterator;

   405     return _M_t.insert_equal((_Rep_iterator&)__position, __x);

   406   }

   407 

   408 #ifdef _STLP_MEMBER_TEMPLATES  

   409   template <class _InputIterator>

   410   void insert(_InputIterator __first, _InputIterator __last) {

   411     _M_t.insert_equal(__first, __last);

   412   }

   413 #else

   414   void insert(const value_type* __first, const value_type* __last) {

   415     _M_t.insert_equal(__first, __last);

   416   }

   417   void insert(const_iterator __first, const_iterator __last) {

   418     _M_t.insert_equal(__first, __last);

   419   }

   420 #endif /* _STLP_MEMBER_TEMPLATES */

   421   void erase(iterator __position) { 

   422     typedef typename _Rep_type::iterator _Rep_iterator;

   423     _M_t.erase((_Rep_iterator&)__position); 

   424   }

   425   size_type erase(const key_type& __x) { 

   426     return _M_t.erase(__x); 

   427   }

   428   void erase(iterator __first, iterator __last) { 

   429     typedef typename _Rep_type::iterator _Rep_iterator;

   430     _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last); 

   431   }

   432   void clear() { _M_t.clear(); }

   433 

   434   // multiset operations:

   435 

   436 # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS )

   437   template <class _KT>

   438   iterator find(const _KT& __x) const { return _M_t.find(__x); }

   439 # else

   440   iterator find(const key_type& __x) const { return _M_t.find(__x); }

   441 # endif

   442   size_type count(const key_type& __x) const { return _M_t.count(__x); }

   443   iterator lower_bound(const key_type& __x) const {

   444     return _M_t.lower_bound(__x);

   445   }

   446   iterator upper_bound(const key_type& __x) const {

   447     return _M_t.upper_bound(__x); 

   448   }

   449   pair<iterator,iterator> equal_range(const key_type& __x) const {

   450     return _M_t.equal_range(__x);

   451   }

   452 };

   453 

   454 # define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Alloc>

   455 # define _STLP_TEMPLATE_CONTAINER set<_Key,_Compare,_Alloc>

   456 # include <stl/_relops_cont.h>

   457 # undef  _STLP_TEMPLATE_CONTAINER

   458 # define _STLP_TEMPLATE_CONTAINER multiset<_Key,_Compare,_Alloc>

   459 # include <stl/_relops_cont.h>

   460 # undef  _STLP_TEMPLATE_CONTAINER

   461 # undef  _STLP_TEMPLATE_HEADER

   462 

   463 _STLP_END_NAMESPACE

   464 

   465 // do a cleanup

   466 # undef set

   467 # undef multiset

   468 // provide a way to access full funclionality 

   469 # define __set__  __FULL_NAME(set)

   470 # define __multiset__  __FULL_NAME(multiset)

   471 

   472 # ifdef _STLP_USE_WRAPPER_FOR_ALLOC_PARAM

   473 # include <stl/wrappers/_set.h>

   474 # endif

   475 

   476 #endif /* _STLP_INTERNAL_SET_H */

   477 

   478 // Local Variables:

   479 // mode:C++

   480 // End:

   481