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