libstdc++-v3/include/bits/stl_multiset.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Hewlett-Packard Company makes no
  11  * representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  *
  15  * Copyright (c) 1996
  16  * Silicon Graphics Computer Systems, Inc.
  17  *
  18  * Permission to use, copy, modify, distribute and sell this software
  19  * and its documentation for any purpose is hereby granted without fee,
  20  * provided that the above copyright notice appear in all copies and
  21  * that both that copyright notice and this permission notice appear
  22  * in supporting documentation.  Silicon Graphics makes no
  23  * representations about the suitability of this software for any
  24  * purpose.  It is provided "as is" without express or implied warranty.
  25  */
  26
  27 /* NOTE: This is an internal header file, included by other STL headers.
  28  *   You should not attempt to use it directly.
  29  */
  30
  31 #ifndef __SGI_STL_INTERNAL_MULTISET_H
  32 #define __SGI_STL_INTERNAL_MULTISET_H
  33
  34 #include <bits/concept_check.h>
  35
  36 namespace std
  37 {
  38
  39 // Forward declaration of operators < and ==, needed for friend declaration.
  40
  41 template <class _Key, class _Compare = less<_Key>,
  42           class _Alloc = allocator<_Key> >
  43 class multiset;
  44
  45 template <class _Key, class _Compare, class _Alloc>
  46 inline bool operator==(const multiset<_Key,_Compare,_Alloc>& __x,
  47                        const multiset<_Key,_Compare,_Alloc>& __y);
  48
  49 template <class _Key, class _Compare, class _Alloc>
  50 inline bool operator<(const multiset<_Key,_Compare,_Alloc>& __x,
  51                       const multiset<_Key,_Compare,_Alloc>& __y);
  52
  53 template <class _Key, class _Compare, class _Alloc>
  54 class multiset
  55 {
  56   // concept requirements
  57   __glibcpp_class_requires(_Key, _SGIAssignableConcept);
  58   __glibcpp_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept);
  59
  60 public:
  61
  62   // typedefs:
  63
  64   typedef _Key     key_type;
  65   typedef _Key     value_type;
  66   typedef _Compare key_compare;
  67   typedef _Compare value_compare;
  68 private:
  69   typedef _Rb_tree<key_type, value_type,
  70                   _Identity<value_type>, key_compare, _Alloc> _Rep_type;
  71   _Rep_type _M_t;  // red-black tree representing multiset
  72 public:
  73   typedef typename _Rep_type::const_pointer pointer;
  74   typedef typename _Rep_type::const_pointer const_pointer;
  75   typedef typename _Rep_type::const_reference reference;
  76   typedef typename _Rep_type::const_reference const_reference;
  77   typedef typename _Rep_type::const_iterator iterator;
  78   typedef typename _Rep_type::const_iterator const_iterator;
  79   typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
  80   typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
  81   typedef typename _Rep_type::size_type size_type;
  82   typedef typename _Rep_type::difference_type difference_type;
  83   typedef typename _Rep_type::allocator_type allocator_type;
  84
  85   // allocation/deallocation
  86
  87   multiset() : _M_t(_Compare(), allocator_type()) {}
  88   explicit multiset(const _Compare& __comp,
  89                     const allocator_type& __a = allocator_type())
  90     : _M_t(__comp, __a) {}
  91
  92   template <class _InputIterator>
  93   multiset(_InputIterator __first, _InputIterator __last)
  94     : _M_t(_Compare(), allocator_type())
  95     { _M_t.insert_equal(__first, __last); }
  96
  97   template <class _InputIterator>
  98   multiset(_InputIterator __first, _InputIterator __last,
  99            const _Compare& __comp,
 100            const allocator_type& __a = allocator_type())
 101     : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
 102
 103   multiset(const multiset<_Key,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
 104
 105   multiset<_Key,_Compare,_Alloc>&
 106   operator=(const multiset<_Key,_Compare,_Alloc>& __x) {
 107     _M_t = __x._M_t;
 108     return *this;
 109   }
 110
 111   // accessors:
 112
 113   key_compare key_comp() const { return _M_t.key_comp(); }
 114   value_compare value_comp() const { return _M_t.key_comp(); }
 115   allocator_type get_allocator() const { return _M_t.get_allocator(); }
 116
 117   iterator begin() const { return _M_t.begin(); }
 118   iterator end() const { return _M_t.end(); }
 119   reverse_iterator rbegin() const { return _M_t.rbegin(); }
 120   reverse_iterator rend() const { return _M_t.rend(); }
 121   bool empty() const { return _M_t.empty(); }
 122   size_type size() const { return _M_t.size(); }
 123   size_type max_size() const { return _M_t.max_size(); }
 124   void swap(multiset<_Key,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }
 125
 126   // insert/erase
 127   iterator insert(const value_type& __x) {
 128     return _M_t.insert_equal(__x);
 129   }
 130   iterator insert(iterator __position, const value_type& __x) {
 131     typedef typename _Rep_type::iterator _Rep_iterator;
 132     return _M_t.insert_equal((_Rep_iterator&)__position, __x);
 133   }
 134
 135   template <class _InputIterator>
 136   void insert(_InputIterator __first, _InputIterator __last) {
 137     _M_t.insert_equal(__first, __last);
 138   }
 139   void erase(iterator __position) {
 140     typedef typename _Rep_type::iterator _Rep_iterator;
 141     _M_t.erase((_Rep_iterator&)__position);
 142   }
 143   size_type erase(const key_type& __x) {
 144     return _M_t.erase(__x);
 145   }
 146   void erase(iterator __first, iterator __last) {
 147     typedef typename _Rep_type::iterator _Rep_iterator;
 148     _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last);
 149   }
 150   void clear() { _M_t.clear(); }
 151
 152   // multiset operations:
 153
 154   size_type count(const key_type& __x) const { return _M_t.count(__x); }
 155
 156 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS
 157 //214.  set::find() missing const overload
 158   iterator find(const key_type& __x) { return _M_t.find(__x); }
 159   const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
 160   iterator lower_bound(const key_type& __x) {
 161     return _M_t.lower_bound(__x);
 162   }
 163   const_iterator lower_bound(const key_type& __x) const {
 164     return _M_t.lower_bound(__x);
 165   }
 166   iterator upper_bound(const key_type& __x) {
 167     return _M_t.upper_bound(__x);
 168   }
 169   const_iterator upper_bound(const key_type& __x) const {
 170     return _M_t.upper_bound(__x);
 171   }
 172   pair<iterator,iterator> equal_range(const key_type& __x) {
 173     return _M_t.equal_range(__x);
 174   }
 175   pair<const_iterator,const_iterator> equal_range(const key_type& __x) const {
 176     return _M_t.equal_range(__x);
 177   }
 178 #else
 179   iterator find(const key_type& __x) const { return _M_t.find(__x); }
 180   iterator lower_bound(const key_type& __x) const {
 181     return _M_t.lower_bound(__x);
 182   }
 183   iterator upper_bound(const key_type& __x) const {
 184     return _M_t.upper_bound(__x);
 185   }
 186   pair<iterator,iterator> equal_range(const key_type& __x) const {
 187     return _M_t.equal_range(__x);
 188   }
 189 #endif
 190
 191   template <class _K1, class _C1, class _A1>
 192   friend bool operator== (const multiset<_K1,_C1,_A1>&,
 193                           const multiset<_K1,_C1,_A1>&);
 194   template <class _K1, class _C1, class _A1>
 195   friend bool operator< (const multiset<_K1,_C1,_A1>&,
 196                          const multiset<_K1,_C1,_A1>&);
 197 };
 198
 199 template <class _Key, class _Compare, class _Alloc>
 200 inline bool operator==(const multiset<_Key,_Compare,_Alloc>& __x,
 201                        const multiset<_Key,_Compare,_Alloc>& __y) {
 202   return __x._M_t == __y._M_t;
 203 }
 204
 205 template <class _Key, class _Compare, class _Alloc>
 206 inline bool operator<(const multiset<_Key,_Compare,_Alloc>& __x,
 207                       const multiset<_Key,_Compare,_Alloc>& __y) {
 208   return __x._M_t < __y._M_t;
 209 }
 210
 211 template <class _Key, class _Compare, class _Alloc>
 212 inline bool operator!=(const multiset<_Key,_Compare,_Alloc>& __x,
 213                        const multiset<_Key,_Compare,_Alloc>& __y) {
 214   return !(__x == __y);
 215 }
 216
 217 template <class _Key, class _Compare, class _Alloc>
 218 inline bool operator>(const multiset<_Key,_Compare,_Alloc>& __x,
 219                       const multiset<_Key,_Compare,_Alloc>& __y) {
 220   return __y < __x;
 221 }
 222
 223 template <class _Key, class _Compare, class _Alloc>
 224 inline bool operator<=(const multiset<_Key,_Compare,_Alloc>& __x,
 225                        const multiset<_Key,_Compare,_Alloc>& __y) {
 226   return !(__y < __x);
 227 }
 228
 229 template <class _Key, class _Compare, class _Alloc>
 230 inline bool operator>=(const multiset<_Key,_Compare,_Alloc>& __x,
 231                        const multiset<_Key,_Compare,_Alloc>& __y) {
 232   return !(__x < __y);
 233 }
 234
 235 template <class _Key, class _Compare, class _Alloc>
 236 inline void swap(multiset<_Key,_Compare,_Alloc>& __x,
 237                  multiset<_Key,_Compare,_Alloc>& __y) {
 238   __x.swap(__y);
 239 }
 240
 241 } // namespace std
 242
 243 #endif /* __SGI_STL_INTERNAL_MULTISET_H */
 244
 245 // Local Variables:
 246 // mode:C++
 247 // End: