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