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 #ifndef _GLIBCXX_DEBUG_MULTISET_H
00031 #define _GLIBCXX_DEBUG_MULTISET_H 1
00032
00033 #include <debug/safe_sequence.h>
00034 #include <debug/safe_iterator.h>
00035 #include <utility>
00036
00037 namespace std _GLIBCXX_VISIBILITY(default)
00038 {
00039 namespace __debug
00040 {
00041
00042 template<typename _Key, typename _Compare = std::less<_Key>,
00043 typename _Allocator = std::allocator<_Key> >
00044 class multiset
00045 : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>,
00046 public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
00047 {
00048 typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
00049 typedef __gnu_debug::_Safe_sequence<multiset> _Safe_base;
00050
00051 typedef typename _Base::const_iterator _Base_const_iterator;
00052 typedef typename _Base::iterator _Base_iterator;
00053 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00054 public:
00055
00056 typedef _Key key_type;
00057 typedef _Key value_type;
00058 typedef _Compare key_compare;
00059 typedef _Compare value_compare;
00060 typedef _Allocator allocator_type;
00061 typedef typename _Base::reference reference;
00062 typedef typename _Base::const_reference const_reference;
00063
00064 typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
00065 iterator;
00066 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00067 multiset> const_iterator;
00068
00069 typedef typename _Base::size_type size_type;
00070 typedef typename _Base::difference_type difference_type;
00071 typedef typename _Base::pointer pointer;
00072 typedef typename _Base::const_pointer const_pointer;
00073 typedef std::reverse_iterator<iterator> reverse_iterator;
00074 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00075
00076
00077 explicit multiset(const _Compare& __comp = _Compare(),
00078 const _Allocator& __a = _Allocator())
00079 : _Base(__comp, __a) { }
00080
00081 template<typename _InputIterator>
00082 multiset(_InputIterator __first, _InputIterator __last,
00083 const _Compare& __comp = _Compare(),
00084 const _Allocator& __a = _Allocator())
00085 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00086 __last)),
00087 __gnu_debug::__base(__last),
00088 __comp, __a) { }
00089
00090 multiset(const multiset& __x)
00091 : _Base(__x), _Safe_base() { }
00092
00093 multiset(const _Base& __x)
00094 : _Base(__x), _Safe_base() { }
00095
00096 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00097 multiset(multiset&& __x)
00098 : _Base(std::move(__x)), _Safe_base()
00099 { this->_M_swap(__x); }
00100
00101 multiset(initializer_list<value_type> __l,
00102 const _Compare& __comp = _Compare(),
00103 const allocator_type& __a = allocator_type())
00104 : _Base(__l, __comp, __a), _Safe_base() { }
00105 #endif
00106
00107 ~multiset() { }
00108
00109 multiset&
00110 operator=(const multiset& __x)
00111 {
00112 *static_cast<_Base*>(this) = __x;
00113 this->_M_invalidate_all();
00114 return *this;
00115 }
00116
00117 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00118 multiset&
00119 operator=(multiset&& __x)
00120 {
00121
00122
00123 clear();
00124 swap(__x);
00125 return *this;
00126 }
00127
00128 multiset&
00129 operator=(initializer_list<value_type> __l)
00130 {
00131 this->clear();
00132 this->insert(__l);
00133 return *this;
00134 }
00135 #endif
00136
00137 using _Base::get_allocator;
00138
00139
00140 iterator
00141 begin()
00142 { return iterator(_Base::begin(), this); }
00143
00144 const_iterator
00145 begin() const
00146 { return const_iterator(_Base::begin(), this); }
00147
00148 iterator
00149 end()
00150 { return iterator(_Base::end(), this); }
00151
00152 const_iterator
00153 end() const
00154 { return const_iterator(_Base::end(), this); }
00155
00156 reverse_iterator
00157 rbegin()
00158 { return reverse_iterator(end()); }
00159
00160 const_reverse_iterator
00161 rbegin() const
00162 { return const_reverse_iterator(end()); }
00163
00164 reverse_iterator
00165 rend()
00166 { return reverse_iterator(begin()); }
00167
00168 const_reverse_iterator
00169 rend() const
00170 { return const_reverse_iterator(begin()); }
00171
00172 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00173 const_iterator
00174 cbegin() const
00175 { return const_iterator(_Base::begin(), this); }
00176
00177 const_iterator
00178 cend() const
00179 { return const_iterator(_Base::end(), this); }
00180
00181 const_reverse_iterator
00182 crbegin() const
00183 { return const_reverse_iterator(end()); }
00184
00185 const_reverse_iterator
00186 crend() const
00187 { return const_reverse_iterator(begin()); }
00188 #endif
00189
00190
00191 using _Base::empty;
00192 using _Base::size;
00193 using _Base::max_size;
00194
00195
00196 iterator
00197 insert(const value_type& __x)
00198 { return iterator(_Base::insert(__x), this); }
00199
00200 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00201 iterator
00202 insert(value_type&& __x)
00203 { return iterator(_Base::insert(std::move(__x)), this); }
00204 #endif
00205
00206 iterator
00207 insert(const_iterator __position, const value_type& __x)
00208 {
00209 __glibcxx_check_insert(__position);
00210 return iterator(_Base::insert(__position.base(), __x), this);
00211 }
00212
00213 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00214 iterator
00215 insert(const_iterator __position, value_type&& __x)
00216 {
00217 __glibcxx_check_insert(__position);
00218 return iterator(_Base::insert(__position.base(), std::move(__x)),
00219 this);
00220 }
00221 #endif
00222
00223 template<typename _InputIterator>
00224 void
00225 insert(_InputIterator __first, _InputIterator __last)
00226 {
00227 __glibcxx_check_valid_range(__first, __last);
00228 _Base::insert(__gnu_debug::__base(__first),
00229 __gnu_debug::__base(__last));
00230 }
00231
00232 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00233 void
00234 insert(initializer_list<value_type> __l)
00235 { _Base::insert(__l); }
00236 #endif
00237
00238 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00239 iterator
00240 erase(const_iterator __position)
00241 {
00242 __glibcxx_check_erase(__position);
00243 this->_M_invalidate_if(_Equal(__position.base()));
00244 return iterator(_Base::erase(__position.base()), this);
00245 }
00246 #else
00247 void
00248 erase(iterator __position)
00249 {
00250 __glibcxx_check_erase(__position);
00251 this->_M_invalidate_if(_Equal(__position.base()));
00252 _Base::erase(__position.base());
00253 }
00254 #endif
00255
00256 size_type
00257 erase(const key_type& __x)
00258 {
00259 std::pair<_Base_iterator, _Base_iterator> __victims =
00260 _Base::equal_range(__x);
00261 size_type __count = 0;
00262 _Base_iterator __victim = __victims.first;
00263 while (__victim != __victims.second)
00264 {
00265 this->_M_invalidate_if(_Equal(__victim));
00266 _Base::erase(__victim++);
00267 ++__count;
00268 }
00269 return __count;
00270 }
00271
00272 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00273 iterator
00274 erase(const_iterator __first, const_iterator __last)
00275 {
00276
00277
00278 __glibcxx_check_erase_range(__first, __last);
00279 for (_Base_const_iterator __victim = __first.base();
00280 __victim != __last.base(); ++__victim)
00281 {
00282 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
00283 _M_message(__gnu_debug::__msg_valid_range)
00284 ._M_iterator(__first, "first")
00285 ._M_iterator(__last, "last"));
00286 this->_M_invalidate_if(_Equal(__victim));
00287 }
00288 return iterator(_Base::erase(__first.base(), __last.base()), this);
00289 }
00290 #else
00291 void
00292 erase(iterator __first, iterator __last)
00293 {
00294
00295
00296 __glibcxx_check_erase_range(__first, __last);
00297 for (_Base_iterator __victim = __first.base();
00298 __victim != __last.base(); ++__victim)
00299 {
00300 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
00301 _M_message(__gnu_debug::__msg_valid_range)
00302 ._M_iterator(__first, "first")
00303 ._M_iterator(__last, "last"));
00304 this->_M_invalidate_if(_Equal(__victim));
00305 }
00306 _Base::erase(__first.base(), __last.base());
00307 }
00308 #endif
00309
00310 void
00311 swap(multiset& __x)
00312 {
00313 _Base::swap(__x);
00314 this->_M_swap(__x);
00315 }
00316
00317 void
00318 clear()
00319 {
00320 this->_M_invalidate_all();
00321 _Base::clear();
00322 }
00323
00324
00325 using _Base::key_comp;
00326 using _Base::value_comp;
00327
00328
00329 iterator
00330 find(const key_type& __x)
00331 { return iterator(_Base::find(__x), this); }
00332
00333
00334
00335 const_iterator
00336 find(const key_type& __x) const
00337 { return const_iterator(_Base::find(__x), this); }
00338
00339 using _Base::count;
00340
00341 iterator
00342 lower_bound(const key_type& __x)
00343 { return iterator(_Base::lower_bound(__x), this); }
00344
00345
00346
00347 const_iterator
00348 lower_bound(const key_type& __x) const
00349 { return const_iterator(_Base::lower_bound(__x), this); }
00350
00351 iterator
00352 upper_bound(const key_type& __x)
00353 { return iterator(_Base::upper_bound(__x), this); }
00354
00355
00356
00357 const_iterator
00358 upper_bound(const key_type& __x) const
00359 { return const_iterator(_Base::upper_bound(__x), this); }
00360
00361 std::pair<iterator,iterator>
00362 equal_range(const key_type& __x)
00363 {
00364 std::pair<_Base_iterator, _Base_iterator> __res =
00365 _Base::equal_range(__x);
00366 return std::make_pair(iterator(__res.first, this),
00367 iterator(__res.second, this));
00368 }
00369
00370
00371
00372 std::pair<const_iterator,const_iterator>
00373 equal_range(const key_type& __x) const
00374 {
00375 std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00376 _Base::equal_range(__x);
00377 return std::make_pair(const_iterator(__res.first, this),
00378 const_iterator(__res.second, this));
00379 }
00380
00381 _Base&
00382 _M_base() { return *this; }
00383
00384 const _Base&
00385 _M_base() const { return *this; }
00386
00387 private:
00388 void
00389 _M_invalidate_all()
00390 {
00391 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00392 this->_M_invalidate_if(_Not_equal(_Base::end()));
00393 }
00394 };
00395
00396 template<typename _Key, typename _Compare, typename _Allocator>
00397 inline bool
00398 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
00399 const multiset<_Key, _Compare, _Allocator>& __rhs)
00400 { return __lhs._M_base() == __rhs._M_base(); }
00401
00402 template<typename _Key, typename _Compare, typename _Allocator>
00403 inline bool
00404 operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00405 const multiset<_Key, _Compare, _Allocator>& __rhs)
00406 { return __lhs._M_base() != __rhs._M_base(); }
00407
00408 template<typename _Key, typename _Compare, typename _Allocator>
00409 inline bool
00410 operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
00411 const multiset<_Key, _Compare, _Allocator>& __rhs)
00412 { return __lhs._M_base() < __rhs._M_base(); }
00413
00414 template<typename _Key, typename _Compare, typename _Allocator>
00415 inline bool
00416 operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00417 const multiset<_Key, _Compare, _Allocator>& __rhs)
00418 { return __lhs._M_base() <= __rhs._M_base(); }
00419
00420 template<typename _Key, typename _Compare, typename _Allocator>
00421 inline bool
00422 operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00423 const multiset<_Key, _Compare, _Allocator>& __rhs)
00424 { return __lhs._M_base() >= __rhs._M_base(); }
00425
00426 template<typename _Key, typename _Compare, typename _Allocator>
00427 inline bool
00428 operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
00429 const multiset<_Key, _Compare, _Allocator>& __rhs)
00430 { return __lhs._M_base() > __rhs._M_base(); }
00431
00432 template<typename _Key, typename _Compare, typename _Allocator>
00433 void
00434 swap(multiset<_Key, _Compare, _Allocator>& __x,
00435 multiset<_Key, _Compare, _Allocator>& __y)
00436 { return __x.swap(__y); }
00437
00438 }
00439 }
00440
00441 #endif