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