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_D::multiset<_Key, _Compare, _Allocator>,
00050 public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
00051 {
00052 typedef _GLIBCXX_STD_D::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& __x)
00090 : _Base(__x), _Safe_base() { }
00091
00092 multiset(const _Base& __x)
00093 : _Base(__x), _Safe_base() { }
00094
00095 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00096 multiset(multiset&& __x)
00097 : _Base(std::forward<multiset>(__x)), _Safe_base()
00098 { this->_M_swap(__x); }
00099 #endif
00100
00101 ~multiset() { }
00102
00103 multiset&
00104 operator=(const multiset& __x)
00105 {
00106 *static_cast<_Base*>(this) = __x;
00107 this->_M_invalidate_all();
00108 return *this;
00109 }
00110
00111 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00112 multiset&
00113 operator=(multiset&& __x)
00114 {
00115
00116 clear();
00117 swap(__x);
00118 return *this;
00119 }
00120 #endif
00121
00122 using _Base::get_allocator;
00123
00124
00125 iterator
00126 begin()
00127 { return iterator(_Base::begin(), this); }
00128
00129 const_iterator
00130 begin() const
00131 { return const_iterator(_Base::begin(), this); }
00132
00133 iterator
00134 end()
00135 { return iterator(_Base::end(), this); }
00136
00137 const_iterator
00138 end() const
00139 { return const_iterator(_Base::end(), this); }
00140
00141 reverse_iterator
00142 rbegin()
00143 { return reverse_iterator(end()); }
00144
00145 const_reverse_iterator
00146 rbegin() const
00147 { return const_reverse_iterator(end()); }
00148
00149 reverse_iterator
00150 rend()
00151 { return reverse_iterator(begin()); }
00152
00153 const_reverse_iterator
00154 rend() const
00155 { return const_reverse_iterator(begin()); }
00156
00157 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00158 const_iterator
00159 cbegin() const
00160 { return const_iterator(_Base::begin(), this); }
00161
00162 const_iterator
00163 cend() const
00164 { return const_iterator(_Base::end(), this); }
00165
00166 const_reverse_iterator
00167 crbegin() const
00168 { return const_reverse_iterator(end()); }
00169
00170 const_reverse_iterator
00171 crend() const
00172 { return const_reverse_iterator(begin()); }
00173 #endif
00174
00175
00176 using _Base::empty;
00177 using _Base::size;
00178 using _Base::max_size;
00179
00180
00181 iterator
00182 insert(const value_type& __x)
00183 { return iterator(_Base::insert(__x), this); }
00184
00185 iterator
00186 insert(iterator __position, const value_type& __x)
00187 {
00188 __glibcxx_check_insert(__position);
00189 return iterator(_Base::insert(__position.base(), __x), this);
00190 }
00191
00192 template<typename _InputIterator>
00193 void
00194 insert(_InputIterator __first, _InputIterator __last)
00195 {
00196 __glibcxx_check_valid_range(__first, __last);
00197 _Base::insert(__first, __last);
00198 }
00199
00200 void
00201 erase(iterator __position)
00202 {
00203 __glibcxx_check_erase(__position);
00204 __position._M_invalidate();
00205 _Base::erase(__position.base());
00206 }
00207
00208 size_type
00209 erase(const key_type& __x)
00210 {
00211 std::pair<iterator, iterator> __victims = this->equal_range(__x);
00212 size_type __count = 0;
00213 while (__victims.first != __victims.second)
00214 {
00215 iterator __victim = __victims.first++;
00216 __victim._M_invalidate();
00217 _Base::erase(__victim.base());
00218 ++__count;
00219 }
00220 return __count;
00221 }
00222
00223 void
00224 erase(iterator __first, iterator __last)
00225 {
00226
00227
00228 __glibcxx_check_erase_range(__first, __last);
00229 while (__first != __last)
00230 this->erase(__first++);
00231 }
00232
00233 void
00234 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00235 swap(multiset&& __x)
00236 #else
00237 swap(multiset& __x)
00238 #endif
00239 {
00240 _Base::swap(__x);
00241 this->_M_swap(__x);
00242 }
00243
00244 void
00245 clear()
00246 { this->erase(begin(), end()); }
00247
00248
00249 using _Base::key_comp;
00250 using _Base::value_comp;
00251
00252
00253 iterator
00254 find(const key_type& __x)
00255 { return iterator(_Base::find(__x), this); }
00256
00257
00258
00259 const_iterator
00260 find(const key_type& __x) const
00261 { return const_iterator(_Base::find(__x), this); }
00262
00263 using _Base::count;
00264
00265 iterator
00266 lower_bound(const key_type& __x)
00267 { return iterator(_Base::lower_bound(__x), this); }
00268
00269
00270
00271 const_iterator
00272 lower_bound(const key_type& __x) const
00273 { return const_iterator(_Base::lower_bound(__x), this); }
00274
00275 iterator
00276 upper_bound(const key_type& __x)
00277 { return iterator(_Base::upper_bound(__x), this); }
00278
00279
00280
00281 const_iterator
00282 upper_bound(const key_type& __x) const
00283 { return const_iterator(_Base::upper_bound(__x), this); }
00284
00285 std::pair<iterator,iterator>
00286 equal_range(const key_type& __x)
00287 {
00288 typedef typename _Base::iterator _Base_iterator;
00289 std::pair<_Base_iterator, _Base_iterator> __res =
00290 _Base::equal_range(__x);
00291 return std::make_pair(iterator(__res.first, this),
00292 iterator(__res.second, this));
00293 }
00294
00295
00296
00297 std::pair<const_iterator,const_iterator>
00298 equal_range(const key_type& __x) const
00299 {
00300 typedef typename _Base::const_iterator _Base_iterator;
00301 std::pair<_Base_iterator, _Base_iterator> __res =
00302 _Base::equal_range(__x);
00303 return std::make_pair(const_iterator(__res.first, this),
00304 const_iterator(__res.second, this));
00305 }
00306
00307 _Base&
00308 _M_base() { return *this; }
00309
00310 const _Base&
00311 _M_base() const { return *this; }
00312
00313 private:
00314 void
00315 _M_invalidate_all()
00316 {
00317 typedef typename _Base::const_iterator _Base_const_iterator;
00318 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00319 this->_M_invalidate_if(_Not_equal(_M_base().end()));
00320 }
00321 };
00322
00323 template<typename _Key, typename _Compare, typename _Allocator>
00324 inline bool
00325 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
00326 const multiset<_Key, _Compare, _Allocator>& __rhs)
00327 { return __lhs._M_base() == __rhs._M_base(); }
00328
00329 template<typename _Key, typename _Compare, typename _Allocator>
00330 inline bool
00331 operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00332 const multiset<_Key, _Compare, _Allocator>& __rhs)
00333 { return __lhs._M_base() != __rhs._M_base(); }
00334
00335 template<typename _Key, typename _Compare, typename _Allocator>
00336 inline bool
00337 operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
00338 const multiset<_Key, _Compare, _Allocator>& __rhs)
00339 { return __lhs._M_base() < __rhs._M_base(); }
00340
00341 template<typename _Key, typename _Compare, typename _Allocator>
00342 inline bool
00343 operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00344 const multiset<_Key, _Compare, _Allocator>& __rhs)
00345 { return __lhs._M_base() <= __rhs._M_base(); }
00346
00347 template<typename _Key, typename _Compare, typename _Allocator>
00348 inline bool
00349 operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00350 const multiset<_Key, _Compare, _Allocator>& __rhs)
00351 { return __lhs._M_base() >= __rhs._M_base(); }
00352
00353 template<typename _Key, typename _Compare, typename _Allocator>
00354 inline bool
00355 operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
00356 const multiset<_Key, _Compare, _Allocator>& __rhs)
00357 { return __lhs._M_base() > __rhs._M_base(); }
00358
00359 template<typename _Key, typename _Compare, typename _Allocator>
00360 void
00361 swap(multiset<_Key, _Compare, _Allocator>& __x,
00362 multiset<_Key, _Compare, _Allocator>& __y)
00363 { return __x.swap(__y); }
00364
00365 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00366 template<typename _Key, typename _Compare, typename _Allocator>
00367 void
00368 swap(multiset<_Key, _Compare, _Allocator>&& __x,
00369 multiset<_Key, _Compare, _Allocator>& __y)
00370 { return __x.swap(__y); }
00371
00372 template<typename _Key, typename _Compare, typename _Allocator>
00373 void
00374 swap(multiset<_Key, _Compare, _Allocator>& __x,
00375 multiset<_Key, _Compare, _Allocator>&& __y)
00376 { return __x.swap(__y); }
00377 #endif
00378
00379 }
00380 }
00381
00382 #endif