libstdc++
|
00001 // Debugging multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2014 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file debug/multimap.h 00026 * This file is a GNU debug extension to the Standard C++ Library. 00027 */ 00028 00029 #ifndef _GLIBCXX_DEBUG_MULTIMAP_H 00030 #define _GLIBCXX_DEBUG_MULTIMAP_H 1 00031 00032 #include <debug/safe_sequence.h> 00033 #include <debug/safe_iterator.h> 00034 #include <utility> 00035 00036 namespace std _GLIBCXX_VISIBILITY(default) 00037 { 00038 namespace __debug 00039 { 00040 /// Class std::multimap with safety/checking/debug instrumentation. 00041 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 00042 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 00043 class multimap 00044 : public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>, 00045 public __gnu_debug::_Safe_sequence<multimap<_Key, _Tp, 00046 _Compare, _Allocator> > 00047 { 00048 typedef _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> _Base; 00049 00050 typedef typename _Base::const_iterator _Base_const_iterator; 00051 typedef typename _Base::iterator _Base_iterator; 00052 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 00053 00054 #if __cplusplus >= 201103L 00055 typedef __gnu_cxx::__alloc_traits<typename 00056 _Base::allocator_type> _Alloc_traits; 00057 #endif 00058 public: 00059 // types: 00060 typedef _Key key_type; 00061 typedef _Tp mapped_type; 00062 typedef std::pair<const _Key, _Tp> value_type; 00063 typedef _Compare key_compare; 00064 typedef _Allocator allocator_type; 00065 typedef typename _Base::reference reference; 00066 typedef typename _Base::const_reference const_reference; 00067 00068 typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap> 00069 iterator; 00070 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 00071 multimap> const_iterator; 00072 00073 typedef typename _Base::size_type size_type; 00074 typedef typename _Base::difference_type difference_type; 00075 typedef typename _Base::pointer pointer; 00076 typedef typename _Base::const_pointer const_pointer; 00077 typedef std::reverse_iterator<iterator> reverse_iterator; 00078 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00079 00080 // 23.3.1.1 construct/copy/destroy: 00081 00082 multimap() : _Base() { } 00083 00084 explicit multimap(const _Compare& __comp, 00085 const _Allocator& __a = _Allocator()) 00086 : _Base(__comp, __a) { } 00087 00088 template<typename _InputIterator> 00089 multimap(_InputIterator __first, _InputIterator __last, 00090 const _Compare& __comp = _Compare(), 00091 const _Allocator& __a = _Allocator()) 00092 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00093 __last)), 00094 __gnu_debug::__base(__last), 00095 __comp, __a) { } 00096 00097 multimap(const multimap& __x) 00098 : _Base(__x) { } 00099 00100 multimap(const _Base& __x) 00101 : _Base(__x) { } 00102 00103 #if __cplusplus >= 201103L 00104 multimap(multimap&& __x) 00105 noexcept(is_nothrow_copy_constructible<_Compare>::value) 00106 : _Base(std::move(__x)) 00107 { this->_M_swap(__x); } 00108 00109 multimap(initializer_list<value_type> __l, 00110 const _Compare& __c = _Compare(), 00111 const allocator_type& __a = allocator_type()) 00112 : _Base(__l, __c, __a) { } 00113 00114 explicit 00115 multimap(const allocator_type& __a) 00116 : _Base(__a) { } 00117 00118 multimap(const multimap& __m, const allocator_type& __a) 00119 : _Base(__m, __a) { } 00120 00121 multimap(multimap&& __m, const allocator_type& __a) 00122 : _Base(std::move(__m._M_base()), __a) { } 00123 00124 multimap(initializer_list<value_type> __l, const allocator_type& __a) 00125 : _Base(__l, __a) 00126 { } 00127 00128 template<typename _InputIterator> 00129 multimap(_InputIterator __first, _InputIterator __last, 00130 const allocator_type& __a) 00131 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00132 __last)), 00133 __gnu_debug::__base(__last), __a) 00134 { } 00135 #endif 00136 00137 ~multimap() _GLIBCXX_NOEXCEPT { } 00138 00139 multimap& 00140 operator=(const multimap& __x) 00141 { 00142 _M_base() = __x; 00143 this->_M_invalidate_all(); 00144 return *this; 00145 } 00146 00147 #if __cplusplus >= 201103L 00148 multimap& 00149 operator=(multimap&& __x) 00150 noexcept(_Alloc_traits::_S_nothrow_move()) 00151 { 00152 __glibcxx_check_self_move_assign(__x); 00153 bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign() 00154 || __x.get_allocator() == this->get_allocator(); 00155 _M_base() = std::move(__x._M_base()); 00156 if (__xfer_memory) 00157 this->_M_swap(__x); 00158 else 00159 this->_M_invalidate_all(); 00160 __x._M_invalidate_all(); 00161 return *this; 00162 } 00163 00164 multimap& 00165 operator=(initializer_list<value_type> __l) 00166 { 00167 _M_base() = __l; 00168 this->_M_invalidate_all(); 00169 return *this; 00170 } 00171 #endif 00172 00173 using _Base::get_allocator; 00174 00175 // iterators: 00176 iterator 00177 begin() _GLIBCXX_NOEXCEPT 00178 { return iterator(_Base::begin(), this); } 00179 00180 const_iterator 00181 begin() const _GLIBCXX_NOEXCEPT 00182 { return const_iterator(_Base::begin(), this); } 00183 00184 iterator 00185 end() _GLIBCXX_NOEXCEPT 00186 { return iterator(_Base::end(), this); } 00187 00188 const_iterator 00189 end() const _GLIBCXX_NOEXCEPT 00190 { return const_iterator(_Base::end(), this); } 00191 00192 reverse_iterator 00193 rbegin() _GLIBCXX_NOEXCEPT 00194 { return reverse_iterator(end()); } 00195 00196 const_reverse_iterator 00197 rbegin() const _GLIBCXX_NOEXCEPT 00198 { return const_reverse_iterator(end()); } 00199 00200 reverse_iterator 00201 rend() _GLIBCXX_NOEXCEPT 00202 { return reverse_iterator(begin()); } 00203 00204 const_reverse_iterator 00205 rend() const _GLIBCXX_NOEXCEPT 00206 { return const_reverse_iterator(begin()); } 00207 00208 #if __cplusplus >= 201103L 00209 const_iterator 00210 cbegin() const noexcept 00211 { return const_iterator(_Base::begin(), this); } 00212 00213 const_iterator 00214 cend() const noexcept 00215 { return const_iterator(_Base::end(), this); } 00216 00217 const_reverse_iterator 00218 crbegin() const noexcept 00219 { return const_reverse_iterator(end()); } 00220 00221 const_reverse_iterator 00222 crend() const noexcept 00223 { return const_reverse_iterator(begin()); } 00224 #endif 00225 00226 // capacity: 00227 using _Base::empty; 00228 using _Base::size; 00229 using _Base::max_size; 00230 00231 // modifiers: 00232 #if __cplusplus >= 201103L 00233 template<typename... _Args> 00234 iterator 00235 emplace(_Args&&... __args) 00236 { 00237 return iterator(_Base::emplace(std::forward<_Args>(__args)...), this); 00238 } 00239 00240 template<typename... _Args> 00241 iterator 00242 emplace_hint(const_iterator __pos, _Args&&... __args) 00243 { 00244 __glibcxx_check_insert(__pos); 00245 return iterator(_Base::emplace_hint(__pos.base(), 00246 std::forward<_Args>(__args)...), 00247 this); 00248 } 00249 #endif 00250 00251 iterator 00252 insert(const value_type& __x) 00253 { return iterator(_Base::insert(__x), this); } 00254 00255 #if __cplusplus >= 201103L 00256 template<typename _Pair, typename = typename 00257 std::enable_if<std::is_constructible<value_type, 00258 _Pair&&>::value>::type> 00259 iterator 00260 insert(_Pair&& __x) 00261 { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); } 00262 #endif 00263 00264 #if __cplusplus >= 201103L 00265 void 00266 insert(std::initializer_list<value_type> __list) 00267 { _Base::insert(__list); } 00268 #endif 00269 00270 iterator 00271 #if __cplusplus >= 201103L 00272 insert(const_iterator __position, const value_type& __x) 00273 #else 00274 insert(iterator __position, const value_type& __x) 00275 #endif 00276 { 00277 __glibcxx_check_insert(__position); 00278 return iterator(_Base::insert(__position.base(), __x), this); 00279 } 00280 00281 #if __cplusplus >= 201103L 00282 template<typename _Pair, typename = typename 00283 std::enable_if<std::is_constructible<value_type, 00284 _Pair&&>::value>::type> 00285 iterator 00286 insert(const_iterator __position, _Pair&& __x) 00287 { 00288 __glibcxx_check_insert(__position); 00289 return iterator(_Base::insert(__position.base(), 00290 std::forward<_Pair>(__x)), this); 00291 } 00292 #endif 00293 00294 template<typename _InputIterator> 00295 void 00296 insert(_InputIterator __first, _InputIterator __last) 00297 { 00298 __glibcxx_check_valid_range(__first, __last); 00299 _Base::insert(__gnu_debug::__base(__first), 00300 __gnu_debug::__base(__last)); 00301 } 00302 00303 #if __cplusplus >= 201103L 00304 iterator 00305 erase(const_iterator __position) 00306 { 00307 __glibcxx_check_erase(__position); 00308 this->_M_invalidate_if(_Equal(__position.base())); 00309 return iterator(_Base::erase(__position.base()), this); 00310 } 00311 00312 iterator 00313 erase(iterator __position) 00314 { return erase(const_iterator(__position)); } 00315 #else 00316 void 00317 erase(iterator __position) 00318 { 00319 __glibcxx_check_erase(__position); 00320 this->_M_invalidate_if(_Equal(__position.base())); 00321 _Base::erase(__position.base()); 00322 } 00323 #endif 00324 00325 size_type 00326 erase(const key_type& __x) 00327 { 00328 std::pair<_Base_iterator, _Base_iterator> __victims = 00329 _Base::equal_range(__x); 00330 size_type __count = 0; 00331 _Base_iterator __victim = __victims.first; 00332 while (__victim != __victims.second) 00333 { 00334 this->_M_invalidate_if(_Equal(__victim)); 00335 _Base::erase(__victim++); 00336 ++__count; 00337 } 00338 return __count; 00339 } 00340 00341 #if __cplusplus >= 201103L 00342 iterator 00343 erase(const_iterator __first, const_iterator __last) 00344 { 00345 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00346 // 151. can't currently clear() empty container 00347 __glibcxx_check_erase_range(__first, __last); 00348 for (_Base_const_iterator __victim = __first.base(); 00349 __victim != __last.base(); ++__victim) 00350 { 00351 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00352 _M_message(__gnu_debug::__msg_valid_range) 00353 ._M_iterator(__first, "first") 00354 ._M_iterator(__last, "last")); 00355 this->_M_invalidate_if(_Equal(__victim)); 00356 } 00357 return iterator(_Base::erase(__first.base(), __last.base()), this); 00358 } 00359 #else 00360 void 00361 erase(iterator __first, iterator __last) 00362 { 00363 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00364 // 151. can't currently clear() empty container 00365 __glibcxx_check_erase_range(__first, __last); 00366 for (_Base_iterator __victim = __first.base(); 00367 __victim != __last.base(); ++__victim) 00368 { 00369 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00370 _M_message(__gnu_debug::__msg_valid_range) 00371 ._M_iterator(__first, "first") 00372 ._M_iterator(__last, "last")); 00373 this->_M_invalidate_if(_Equal(__victim)); 00374 } 00375 _Base::erase(__first.base(), __last.base()); 00376 } 00377 #endif 00378 00379 void 00380 swap(multimap& __x) 00381 #if __cplusplus >= 201103L 00382 noexcept(_Alloc_traits::_S_nothrow_swap()) 00383 #endif 00384 { 00385 #if __cplusplus >= 201103L 00386 if (!_Alloc_traits::_S_propagate_on_swap()) 00387 __glibcxx_check_equal_allocs(__x); 00388 #endif 00389 _Base::swap(__x); 00390 this->_M_swap(__x); 00391 } 00392 00393 void 00394 clear() _GLIBCXX_NOEXCEPT 00395 { 00396 this->_M_invalidate_all(); 00397 _Base::clear(); 00398 } 00399 00400 // observers: 00401 using _Base::key_comp; 00402 using _Base::value_comp; 00403 00404 // 23.3.1.3 multimap operations: 00405 iterator 00406 find(const key_type& __x) 00407 { return iterator(_Base::find(__x), this); } 00408 00409 const_iterator 00410 find(const key_type& __x) const 00411 { return const_iterator(_Base::find(__x), this); } 00412 00413 using _Base::count; 00414 00415 iterator 00416 lower_bound(const key_type& __x) 00417 { return iterator(_Base::lower_bound(__x), this); } 00418 00419 const_iterator 00420 lower_bound(const key_type& __x) const 00421 { return const_iterator(_Base::lower_bound(__x), this); } 00422 00423 iterator 00424 upper_bound(const key_type& __x) 00425 { return iterator(_Base::upper_bound(__x), this); } 00426 00427 const_iterator 00428 upper_bound(const key_type& __x) const 00429 { return const_iterator(_Base::upper_bound(__x), this); } 00430 00431 std::pair<iterator,iterator> 00432 equal_range(const key_type& __x) 00433 { 00434 std::pair<_Base_iterator, _Base_iterator> __res = 00435 _Base::equal_range(__x); 00436 return std::make_pair(iterator(__res.first, this), 00437 iterator(__res.second, this)); 00438 } 00439 00440 std::pair<const_iterator,const_iterator> 00441 equal_range(const key_type& __x) const 00442 { 00443 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00444 _Base::equal_range(__x); 00445 return std::make_pair(const_iterator(__res.first, this), 00446 const_iterator(__res.second, this)); 00447 } 00448 00449 _Base& 00450 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 00451 00452 const _Base& 00453 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 00454 00455 private: 00456 void 00457 _M_invalidate_all() 00458 { 00459 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00460 this->_M_invalidate_if(_Not_equal(_Base::end())); 00461 } 00462 }; 00463 00464 template<typename _Key, typename _Tp, 00465 typename _Compare, typename _Allocator> 00466 inline bool 00467 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00468 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00469 { return __lhs._M_base() == __rhs._M_base(); } 00470 00471 template<typename _Key, typename _Tp, 00472 typename _Compare, typename _Allocator> 00473 inline bool 00474 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00475 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00476 { return __lhs._M_base() != __rhs._M_base(); } 00477 00478 template<typename _Key, typename _Tp, 00479 typename _Compare, typename _Allocator> 00480 inline bool 00481 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00482 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00483 { return __lhs._M_base() < __rhs._M_base(); } 00484 00485 template<typename _Key, typename _Tp, 00486 typename _Compare, typename _Allocator> 00487 inline bool 00488 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00489 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00490 { return __lhs._M_base() <= __rhs._M_base(); } 00491 00492 template<typename _Key, typename _Tp, 00493 typename _Compare, typename _Allocator> 00494 inline bool 00495 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00496 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00497 { return __lhs._M_base() >= __rhs._M_base(); } 00498 00499 template<typename _Key, typename _Tp, 00500 typename _Compare, typename _Allocator> 00501 inline bool 00502 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00503 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00504 { return __lhs._M_base() > __rhs._M_base(); } 00505 00506 template<typename _Key, typename _Tp, 00507 typename _Compare, typename _Allocator> 00508 inline void 00509 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00510 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00511 { __lhs.swap(__rhs); } 00512 00513 } // namespace __debug 00514 } // namespace std 00515 00516 #endif