00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035 #ifndef _GLIBCXX_DEBUG_MULTISET_H
00036 #define _GLIBCXX_DEBUG_MULTISET_H 1
00037
00038 #include <debug/safe_sequence.h>
00039 #include <debug/safe_iterator.h>
00040 #include <utility>
00041
00042 namespace std
00043 {
00044 namespace __debug
00045 {
00046 template<typename _Key, typename _Compare = std::less<_Key>,
00047 typename _Allocator = std::allocator<_Key> >
00048 class multiset
00049 : public _GLIBCXX_STD::multiset<_Key, _Compare, _Allocator>,
00050 public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
00051 {
00052 typedef _GLIBCXX_STD::multiset<_Key, _Compare, _Allocator> _Base;
00053 typedef __gnu_debug::_Safe_sequence<multiset> _Safe_base;
00054
00055 public:
00056
00057 typedef _Key key_type;
00058 typedef _Key value_type;
00059 typedef _Compare key_compare;
00060 typedef _Compare value_compare;
00061 typedef _Allocator allocator_type;
00062 typedef typename _Base::reference reference;
00063 typedef typename _Base::const_reference const_reference;
00064
00065 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multiset>
00066 iterator;
00067 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
00068 multiset> const_iterator;
00069
00070 typedef typename _Base::size_type size_type;
00071 typedef typename _Base::difference_type difference_type;
00072 typedef typename _Base::pointer pointer;
00073 typedef typename _Base::const_pointer const_pointer;
00074 typedef std::reverse_iterator<iterator> reverse_iterator;
00075 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00076
00077
00078 explicit multiset(const _Compare& __comp = _Compare(),
00079 const _Allocator& __a = _Allocator())
00080 : _Base(__comp, __a) { }
00081
00082 template<typename _InputIterator>
00083 multiset(_InputIterator __first, _InputIterator __last,
00084 const _Compare& __comp = _Compare(),
00085 const _Allocator& __a = _Allocator())
00086 : _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
00087 __comp, __a) { }
00088
00089 multiset(const multiset<_Key,_Compare,_Allocator>& __x)
00090 : _Base(__x), _Safe_base() { }
00091
00092 multiset(const _Base& __x) : _Base(__x), _Safe_base() { }
00093
00094 ~multiset() { }
00095
00096 multiset<_Key,_Compare,_Allocator>&
00097 operator=(const multiset<_Key,_Compare,_Allocator>& __x)
00098 {
00099 *static_cast<_Base*>(this) = __x;
00100 this->_M_invalidate_all();
00101 return *this;
00102 }
00103
00104 using _Base::get_allocator;
00105
00106
00107 iterator
00108 begin()
00109 { return iterator(_Base::begin(), this); }
00110
00111 const_iterator
00112 begin() const
00113 { return const_iterator(_Base::begin(), this); }
00114
00115 iterator
00116 end()
00117 { return iterator(_Base::end(), this); }
00118
00119 const_iterator
00120 end() const
00121 { return const_iterator(_Base::end(), this); }
00122
00123 reverse_iterator
00124 rbegin()
00125 { return reverse_iterator(end()); }
00126
00127 const_reverse_iterator
00128 rbegin() const
00129 { return const_reverse_iterator(end()); }
00130
00131 reverse_iterator
00132 rend()
00133 { return reverse_iterator(begin()); }
00134
00135 const_reverse_iterator
00136 rend() const
00137 { return const_reverse_iterator(begin()); }
00138
00139
00140 using _Base::empty;
00141 using _Base::size;
00142 using _Base::max_size;
00143
00144
00145 iterator
00146 insert(const value_type& __x)
00147 { return iterator(_Base::insert(__x), this); }
00148
00149 iterator
00150 insert(iterator __position, const value_type& __x)
00151 {
00152 __glibcxx_check_insert(__position);
00153 return iterator(_Base::insert(__position.base(), __x), this);
00154 }
00155
00156 template<typename _InputIterator>
00157 void
00158 insert(_InputIterator __first, _InputIterator __last)
00159 {
00160 __glibcxx_check_valid_range(__first, __last);
00161 _Base::insert(__first, __last);
00162 }
00163
00164 void
00165 erase(iterator __position)
00166 {
00167 __glibcxx_check_erase(__position);
00168 __position._M_invalidate();
00169 _Base::erase(__position.base());
00170 }
00171
00172 size_type
00173 erase(const key_type& __x)
00174 {
00175 std::pair<iterator, iterator> __victims = this->equal_range(__x);
00176 size_type __count = 0;
00177 while (__victims.first != __victims.second)
00178 {
00179 iterator __victim = __victims.first++;
00180 __victim._M_invalidate();
00181 _Base::erase(__victim.base());
00182 ++__count;
00183 }
00184 return __count;
00185 }
00186
00187 void
00188 erase(iterator __first, iterator __last)
00189 {
00190
00191
00192 __glibcxx_check_erase_range(__first, __last);
00193 while (__first != __last)
00194 this->erase(__first++);
00195 }
00196
00197 void
00198 swap(multiset<_Key,_Compare,_Allocator>& __x)
00199 {
00200 _Base::swap(__x);
00201 this->_M_swap(__x);
00202 }
00203
00204 void
00205 clear()
00206 { this->erase(begin(), end()); }
00207
00208
00209 using _Base::key_comp;
00210 using _Base::value_comp;
00211
00212
00213 iterator
00214 find(const key_type& __x)
00215 { return iterator(_Base::find(__x), this); }
00216
00217
00218
00219 const_iterator
00220 find(const key_type& __x) const
00221 { return const_iterator(_Base::find(__x), this); }
00222
00223 using _Base::count;
00224
00225 iterator
00226 lower_bound(const key_type& __x)
00227 { return iterator(_Base::lower_bound(__x), this); }
00228
00229
00230
00231 const_iterator
00232 lower_bound(const key_type& __x) const
00233 { return const_iterator(_Base::lower_bound(__x), this); }
00234
00235 iterator
00236 upper_bound(const key_type& __x)
00237 { return iterator(_Base::upper_bound(__x), this); }
00238
00239
00240
00241 const_iterator
00242 upper_bound(const key_type& __x) const
00243 { return const_iterator(_Base::upper_bound(__x), this); }
00244
00245 std::pair<iterator,iterator>
00246 equal_range(const key_type& __x)
00247 {
00248 typedef typename _Base::iterator _Base_iterator;
00249 std::pair<_Base_iterator, _Base_iterator> __res =
00250 _Base::equal_range(__x);
00251 return std::make_pair(iterator(__res.first, this),
00252 iterator(__res.second, this));
00253 }
00254
00255
00256
00257 std::pair<const_iterator,const_iterator>
00258 equal_range(const key_type& __x) const
00259 {
00260 typedef typename _Base::const_iterator _Base_iterator;
00261 std::pair<_Base_iterator, _Base_iterator> __res =
00262 _Base::equal_range(__x);
00263 return std::make_pair(const_iterator(__res.first, this),
00264 const_iterator(__res.second, this));
00265 }
00266
00267 _Base&
00268 _M_base() { return *this; }
00269
00270 const _Base&
00271 _M_base() const { return *this; }
00272
00273 private:
00274 void
00275 _M_invalidate_all()
00276 {
00277 typedef typename _Base::const_iterator _Base_const_iterator;
00278 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00279 this->_M_invalidate_if(_Not_equal(_M_base().end()));
00280 }
00281 };
00282
00283 template<typename _Key, typename _Compare, typename _Allocator>
00284 inline bool
00285 operator==(const multiset<_Key,_Compare,_Allocator>& __lhs,
00286 const multiset<_Key,_Compare,_Allocator>& __rhs)
00287 { return __lhs._M_base() == __rhs._M_base(); }
00288
00289 template<typename _Key, typename _Compare, typename _Allocator>
00290 inline bool
00291 operator!=(const multiset<_Key,_Compare,_Allocator>& __lhs,
00292 const multiset<_Key,_Compare,_Allocator>& __rhs)
00293 { return __lhs._M_base() != __rhs._M_base(); }
00294
00295 template<typename _Key, typename _Compare, typename _Allocator>
00296 inline bool
00297 operator<(const multiset<_Key,_Compare,_Allocator>& __lhs,
00298 const multiset<_Key,_Compare,_Allocator>& __rhs)
00299 { return __lhs._M_base() < __rhs._M_base(); }
00300
00301 template<typename _Key, typename _Compare, typename _Allocator>
00302 inline bool
00303 operator<=(const multiset<_Key,_Compare,_Allocator>& __lhs,
00304 const multiset<_Key,_Compare,_Allocator>& __rhs)
00305 { return __lhs._M_base() <= __rhs._M_base(); }
00306
00307 template<typename _Key, typename _Compare, typename _Allocator>
00308 inline bool
00309 operator>=(const multiset<_Key,_Compare,_Allocator>& __lhs,
00310 const multiset<_Key,_Compare,_Allocator>& __rhs)
00311 { return __lhs._M_base() >= __rhs._M_base(); }
00312
00313 template<typename _Key, typename _Compare, typename _Allocator>
00314 inline bool
00315 operator>(const multiset<_Key,_Compare,_Allocator>& __lhs,
00316 const multiset<_Key,_Compare,_Allocator>& __rhs)
00317 { return __lhs._M_base() > __rhs._M_base(); }
00318
00319 template<typename _Key, typename _Compare, typename _Allocator>
00320 void
00321 swap(multiset<_Key,_Compare,_Allocator>& __x,
00322 multiset<_Key,_Compare,_Allocator>& __y)
00323 { return __x.swap(__y); }
00324 }
00325 }
00326
00327 #endif