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 __STL_BEGIN_NAMESPACE 35 36 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 37 #pragma set woff 1174 38 #pragma set woff 1375 39 #endif 40 41 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES 42 template <class _Key, class _Compare = less<_Key>, 43 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Key) > 44 #else 45 template <class _Key, class _Compare, 46 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Key) > 47 #endif 48 class multiset { 49 public: 50 // typedefs: 51 52 typedef _Key key_type; 53 typedef _Key value_type; 54 typedef _Compare key_compare; 55 typedef _Compare value_compare; 56 private: 57 typedef _Rb_tree<key_type, value_type, 58 _Identity<value_type>, key_compare, _Alloc> _Rep_type; 59 _Rep_type _M_t; // red-black tree representing multiset 60 public: 61 typedef typename _Rep_type::const_pointer pointer; 62 typedef typename _Rep_type::const_pointer const_pointer; 63 typedef typename _Rep_type::const_reference reference; 64 typedef typename _Rep_type::const_reference const_reference; 65 typedef typename _Rep_type::const_iterator iterator; 66 typedef typename _Rep_type::const_iterator const_iterator; 67 typedef typename _Rep_type::const_reverse_iterator reverse_iterator; 68 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; 69 typedef typename _Rep_type::size_type size_type; 70 typedef typename _Rep_type::difference_type difference_type; 71 typedef typename _Rep_type::allocator_type allocator_type; 72 73 // allocation/deallocation 74 75 multiset() : _M_t(_Compare(), allocator_type()) {} 76 explicit multiset(const _Compare& __comp, 77 const allocator_type& __a = allocator_type()) 78 : _M_t(__comp, __a) {} 79 80 #ifdef __STL_MEMBER_TEMPLATES 81 82 template <class _InputIterator> 83 multiset(_InputIterator __first, _InputIterator __last) 84 : _M_t(_Compare(), allocator_type()) 85 { _M_t.insert_equal(__first, __last); } 86 87 template <class _InputIterator> 88 multiset(_InputIterator __first, _InputIterator __last, 89 const _Compare& __comp, 90 const allocator_type& __a = allocator_type()) 91 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 92 93 #else 94 95 multiset(const value_type* __first, const value_type* __last) 96 : _M_t(_Compare(), allocator_type()) 97 { _M_t.insert_equal(__first, __last); } 98 99 multiset(const value_type* __first, const value_type* __last, 100 const _Compare& __comp, 101 const allocator_type& __a = allocator_type()) 102 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 103 104 multiset(const_iterator __first, const_iterator __last) 105 : _M_t(_Compare(), allocator_type()) 106 { _M_t.insert_equal(__first, __last); } 107 108 multiset(const_iterator __first, const_iterator __last, 109 const _Compare& __comp, 110 const allocator_type& __a = allocator_type()) 111 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); } 112 113 #endif /* __STL_MEMBER_TEMPLATES */ 114 115 multiset(const multiset<_Key,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {} 116 multiset<_Key,_Compare,_Alloc>& 117 operator=(const multiset<_Key,_Compare,_Alloc>& __x) { 118 _M_t = __x._M_t; 119 return *this; 120 } 121 122 // accessors: 123 124 key_compare key_comp() const { return _M_t.key_comp(); } 125 value_compare value_comp() const { return _M_t.key_comp(); } 126 allocator_type get_allocator() const { return _M_t.get_allocator(); } 127 128 iterator begin() const { return _M_t.begin(); } 129 iterator end() const { return _M_t.end(); } 130 reverse_iterator rbegin() const { return _M_t.rbegin(); } 131 reverse_iterator rend() const { return _M_t.rend(); } 132 bool empty() const { return _M_t.empty(); } 133 size_type size() const { return _M_t.size(); } 134 size_type max_size() const { return _M_t.max_size(); } 135 void swap(multiset<_Key,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); } 136 137 // insert/erase 138 iterator insert(const value_type& __x) { 139 return _M_t.insert_equal(__x); 140 } 141 iterator insert(iterator __position, const value_type& __x) { 142 typedef typename _Rep_type::iterator _Rep_iterator; 143 return _M_t.insert_equal((_Rep_iterator&)__position, __x); 144 } 145 146 #ifdef __STL_MEMBER_TEMPLATES 147 template <class _InputIterator> 148 void insert(_InputIterator __first, _InputIterator __last) { 149 _M_t.insert_equal(__first, __last); 150 } 151 #else 152 void insert(const value_type* __first, const value_type* __last) { 153 _M_t.insert_equal(__first, __last); 154 } 155 void insert(const_iterator __first, const_iterator __last) { 156 _M_t.insert_equal(__first, __last); 157 } 158 #endif /* __STL_MEMBER_TEMPLATES */ 159 void erase(iterator __position) { 160 typedef typename _Rep_type::iterator _Rep_iterator; 161 _M_t.erase((_Rep_iterator&)__position); 162 } 163 size_type erase(const key_type& __x) { 164 return _M_t.erase(__x); 165 } 166 void erase(iterator __first, iterator __last) { 167 typedef typename _Rep_type::iterator _Rep_iterator; 168 _M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last); 169 } 170 void clear() { _M_t.clear(); } 171 172 // multiset operations: 173 174 iterator find(const key_type& __x) const { return _M_t.find(__x); } 175 size_type count(const key_type& __x) const { return _M_t.count(__x); } 176 iterator lower_bound(const key_type& __x) const { 177 return _M_t.lower_bound(__x); 178 } 179 iterator upper_bound(const key_type& __x) const { 180 return _M_t.upper_bound(__x); 181 } 182 pair<iterator,iterator> equal_range(const key_type& __x) const { 183 return _M_t.equal_range(__x); 184 } 185 friend bool operator== __STL_NULL_TMPL_ARGS (const multiset&, 186 const multiset&); 187 friend bool operator< __STL_NULL_TMPL_ARGS (const multiset&, 188 const multiset&); 189 }; 190 191 template <class _Key, class _Compare, class _Alloc> 192 inline bool operator==(const multiset<_Key,_Compare,_Alloc>& __x, 193 const multiset<_Key,_Compare,_Alloc>& __y) { 194 return __x._M_t == __y._M_t; 195 } 196 197 template <class _Key, class _Compare, class _Alloc> 198 inline bool operator<(const multiset<_Key,_Compare,_Alloc>& __x, 199 const multiset<_Key,_Compare,_Alloc>& __y) { 200 return __x._M_t < __y._M_t; 201 } 202 203 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER 204 205 template <class _Key, class _Compare, class _Alloc> 206 inline void swap(multiset<_Key,_Compare,_Alloc>& __x, 207 multiset<_Key,_Compare,_Alloc>& __y) { 208 __x.swap(__y); 209 } 210 211 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ 212 213 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 214 #pragma reset woff 1174 215 #pragma reset woff 1375 216 #endif 217 218 __STL_END_NAMESPACE 219 220 #endif /* __SGI_STL_INTERNAL_MULTISET_H */ 221 222 // Local Variables: 223 // mode:C++ 224 // End: 225