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_SET_H
00031 #define _GLIBCXX_DEBUG_SET_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 set
00045 : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>,
00046 public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
00047 {
00048 typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
00049 typedef __gnu_debug::_Safe_sequence<set> _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, set>
00065 iterator;
00066 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
00067 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 set(const _Compare& __comp = _Compare(),
00078 const _Allocator& __a = _Allocator())
00079 : _Base(__comp, __a) { }
00080
00081 template<typename _InputIterator>
00082 set(_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 set(const set& __x)
00091 : _Base(__x), _Safe_base() { }
00092
00093 set(const _Base& __x)
00094 : _Base(__x), _Safe_base() { }
00095
00096 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00097 set(set&& __x)
00098 : _Base(std::move(__x)), _Safe_base()
00099 { this->_M_swap(__x); }
00100
00101 set(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 ~set() { }
00108
00109 set&
00110 operator=(const set& __x)
00111 {
00112 *static_cast<_Base*>(this) = __x;
00113 this->_M_invalidate_all();
00114 return *this;
00115 }
00116
00117 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00118 set&
00119 operator=(set&& __x)
00120 {
00121
00122
00123 clear();
00124 swap(__x);
00125 return *this;
00126 }
00127
00128 set&
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 std::pair<iterator, bool>
00197 insert(const value_type& __x)
00198 {
00199 std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
00200 return std::pair<iterator, bool>(iterator(__res.first, this),
00201 __res.second);
00202 }
00203
00204 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00205 std::pair<iterator, bool>
00206 insert(value_type&& __x)
00207 {
00208 typedef typename _Base::iterator _Base_iterator;
00209 std::pair<_Base_iterator, bool> __res
00210 = _Base::insert(std::move(__x));
00211 return std::pair<iterator, bool>(iterator(__res.first, this),
00212 __res.second);
00213 }
00214 #endif
00215
00216 iterator
00217 insert(const_iterator __position, const value_type& __x)
00218 {
00219 __glibcxx_check_insert(__position);
00220 return iterator(_Base::insert(__position.base(), __x), this);
00221 }
00222
00223 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00224 iterator
00225 insert(const_iterator __position, value_type&& __x)
00226 {
00227 __glibcxx_check_insert(__position);
00228 return iterator(_Base::insert(__position.base(), std::move(__x)),
00229 this);
00230 }
00231 #endif
00232
00233 template <typename _InputIterator>
00234 void
00235 insert(_InputIterator __first, _InputIterator __last)
00236 {
00237 __glibcxx_check_valid_range(__first, __last);
00238 _Base::insert(__gnu_debug::__base(__first),
00239 __gnu_debug::__base(__last));
00240 }
00241
00242 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00243 void
00244 insert(initializer_list<value_type> __l)
00245 { _Base::insert(__l); }
00246 #endif
00247
00248 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00249 iterator
00250 erase(const_iterator __position)
00251 {
00252 __glibcxx_check_erase(__position);
00253 this->_M_invalidate_if(_Equal(__position.base()));
00254 return iterator(_Base::erase(__position.base()), this);
00255 }
00256 #else
00257 void
00258 erase(iterator __position)
00259 {
00260 __glibcxx_check_erase(__position);
00261 this->_M_invalidate_if(_Equal(__position.base()));
00262 _Base::erase(__position.base());
00263 }
00264 #endif
00265
00266 size_type
00267 erase(const key_type& __x)
00268 {
00269 _Base_iterator __victim = _Base::find(__x);
00270 if (__victim == _Base::end())
00271 return 0;
00272 else
00273 {
00274 this->_M_invalidate_if(_Equal(__victim));
00275 _Base::erase(__victim);
00276 return 1;
00277 }
00278 }
00279
00280 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00281 iterator
00282 erase(const_iterator __first, const_iterator __last)
00283 {
00284
00285
00286 __glibcxx_check_erase_range(__first, __last);
00287 for (_Base_const_iterator __victim = __first.base();
00288 __victim != __last.base(); ++__victim)
00289 {
00290 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
00291 _M_message(__gnu_debug::__msg_valid_range)
00292 ._M_iterator(__first, "first")
00293 ._M_iterator(__last, "last"));
00294 this->_M_invalidate_if(_Equal(__victim));
00295 }
00296 return iterator(_Base::erase(__first.base(), __last.base()), this);
00297 }
00298 #else
00299 void
00300 erase(iterator __first, iterator __last)
00301 {
00302
00303
00304 __glibcxx_check_erase_range(__first, __last);
00305 for (_Base_iterator __victim = __first.base();
00306 __victim != __last.base(); ++__victim)
00307 {
00308 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
00309 _M_message(__gnu_debug::__msg_valid_range)
00310 ._M_iterator(__first, "first")
00311 ._M_iterator(__last, "last"));
00312 this->_M_invalidate_if(_Equal(__victim));
00313 }
00314 _Base::erase(__first.base(), __last.base());
00315 }
00316 #endif
00317
00318 void
00319 swap(set& __x)
00320 {
00321 _Base::swap(__x);
00322 this->_M_swap(__x);
00323 }
00324
00325 void
00326 clear()
00327 {
00328 this->_M_invalidate_all();
00329 _Base::clear();
00330 }
00331
00332
00333 using _Base::key_comp;
00334 using _Base::value_comp;
00335
00336
00337 iterator
00338 find(const key_type& __x)
00339 { return iterator(_Base::find(__x), this); }
00340
00341
00342
00343 const_iterator
00344 find(const key_type& __x) const
00345 { return const_iterator(_Base::find(__x), this); }
00346
00347 using _Base::count;
00348
00349 iterator
00350 lower_bound(const key_type& __x)
00351 { return iterator(_Base::lower_bound(__x), this); }
00352
00353
00354
00355 const_iterator
00356 lower_bound(const key_type& __x) const
00357 { return const_iterator(_Base::lower_bound(__x), this); }
00358
00359 iterator
00360 upper_bound(const key_type& __x)
00361 { return iterator(_Base::upper_bound(__x), this); }
00362
00363
00364
00365 const_iterator
00366 upper_bound(const key_type& __x) const
00367 { return const_iterator(_Base::upper_bound(__x), this); }
00368
00369 std::pair<iterator,iterator>
00370 equal_range(const key_type& __x)
00371 {
00372 std::pair<_Base_iterator, _Base_iterator> __res =
00373 _Base::equal_range(__x);
00374 return std::make_pair(iterator(__res.first, this),
00375 iterator(__res.second, this));
00376 }
00377
00378
00379
00380 std::pair<const_iterator,const_iterator>
00381 equal_range(const key_type& __x) const
00382 {
00383 std::pair<_Base_iterator, _Base_iterator> __res =
00384 _Base::equal_range(__x);
00385 return std::make_pair(const_iterator(__res.first, this),
00386 const_iterator(__res.second, this));
00387 }
00388
00389 _Base&
00390 _M_base() { return *this; }
00391
00392 const _Base&
00393 _M_base() const { return *this; }
00394
00395 private:
00396 void
00397 _M_invalidate_all()
00398 {
00399 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00400 this->_M_invalidate_if(_Not_equal(_M_base().end()));
00401 }
00402 };
00403
00404 template<typename _Key, typename _Compare, typename _Allocator>
00405 inline bool
00406 operator==(const set<_Key, _Compare, _Allocator>& __lhs,
00407 const set<_Key, _Compare, _Allocator>& __rhs)
00408 { return __lhs._M_base() == __rhs._M_base(); }
00409
00410 template<typename _Key, typename _Compare, typename _Allocator>
00411 inline bool
00412 operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
00413 const set<_Key, _Compare, _Allocator>& __rhs)
00414 { return __lhs._M_base() != __rhs._M_base(); }
00415
00416 template<typename _Key, typename _Compare, typename _Allocator>
00417 inline bool
00418 operator<(const set<_Key, _Compare, _Allocator>& __lhs,
00419 const set<_Key, _Compare, _Allocator>& __rhs)
00420 { return __lhs._M_base() < __rhs._M_base(); }
00421
00422 template<typename _Key, typename _Compare, typename _Allocator>
00423 inline bool
00424 operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
00425 const set<_Key, _Compare, _Allocator>& __rhs)
00426 { return __lhs._M_base() <= __rhs._M_base(); }
00427
00428 template<typename _Key, typename _Compare, typename _Allocator>
00429 inline bool
00430 operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
00431 const set<_Key, _Compare, _Allocator>& __rhs)
00432 { return __lhs._M_base() >= __rhs._M_base(); }
00433
00434 template<typename _Key, typename _Compare, typename _Allocator>
00435 inline bool
00436 operator>(const set<_Key, _Compare, _Allocator>& __lhs,
00437 const set<_Key, _Compare, _Allocator>& __rhs)
00438 { return __lhs._M_base() > __rhs._M_base(); }
00439
00440 template<typename _Key, typename _Compare, typename _Allocator>
00441 void
00442 swap(set<_Key, _Compare, _Allocator>& __x,
00443 set<_Key, _Compare, _Allocator>& __y)
00444 { return __x.swap(__y); }
00445
00446 }
00447 }
00448
00449 #endif