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