libstdc++
|
00001 // Debugging multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2018 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_container.h> 00034 #include <debug/safe_iterator.h> 00035 #include <utility> 00036 00037 namespace std _GLIBCXX_VISIBILITY(default) 00038 { 00039 namespace __debug 00040 { 00041 /// Class std::multimap with safety/checking/debug instrumentation. 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 __gnu_debug::_Safe_container< 00046 multimap<_Key, _Tp, _Compare, _Allocator>, _Allocator, 00047 __gnu_debug::_Safe_node_sequence>, 00048 public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> 00049 { 00050 typedef _GLIBCXX_STD_C::multimap< 00051 _Key, _Tp, _Compare, _Allocator> _Base; 00052 typedef __gnu_debug::_Safe_container< 00053 multimap, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe; 00054 00055 typedef typename _Base::const_iterator _Base_const_iterator; 00056 typedef typename _Base::iterator _Base_iterator; 00057 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 00058 00059 public: 00060 // types: 00061 typedef _Key key_type; 00062 typedef _Tp mapped_type; 00063 typedef std::pair<const _Key, _Tp> value_type; 00064 typedef _Compare key_compare; 00065 typedef _Allocator allocator_type; 00066 typedef typename _Base::reference reference; 00067 typedef typename _Base::const_reference const_reference; 00068 00069 typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap> 00070 iterator; 00071 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 00072 multimap> const_iterator; 00073 00074 typedef typename _Base::size_type size_type; 00075 typedef typename _Base::difference_type difference_type; 00076 typedef typename _Base::pointer pointer; 00077 typedef typename _Base::const_pointer const_pointer; 00078 typedef std::reverse_iterator<iterator> reverse_iterator; 00079 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00080 00081 // 23.3.1.1 construct/copy/destroy: 00082 00083 #if __cplusplus < 201103L 00084 multimap() : _Base() { } 00085 00086 multimap(const multimap& __x) 00087 : _Base(__x) { } 00088 00089 ~multimap() { } 00090 #else 00091 multimap() = default; 00092 multimap(const multimap&) = default; 00093 multimap(multimap&&) = default; 00094 00095 multimap(initializer_list<value_type> __l, 00096 const _Compare& __c = _Compare(), 00097 const allocator_type& __a = allocator_type()) 00098 : _Base(__l, __c, __a) { } 00099 00100 explicit 00101 multimap(const allocator_type& __a) 00102 : _Base(__a) { } 00103 00104 multimap(const multimap& __m, const allocator_type& __a) 00105 : _Base(__m, __a) { } 00106 00107 multimap(multimap&& __m, const allocator_type& __a) 00108 noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) ) 00109 : _Safe(std::move(__m._M_safe()), __a), 00110 _Base(std::move(__m._M_base()), __a) { } 00111 00112 multimap(initializer_list<value_type> __l, const allocator_type& __a) 00113 : _Base(__l, __a) { } 00114 00115 template<typename _InputIterator> 00116 multimap(_InputIterator __first, _InputIterator __last, 00117 const allocator_type& __a) 00118 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00119 __last)), 00120 __gnu_debug::__base(__last), __a) { } 00121 00122 ~multimap() = default; 00123 #endif 00124 00125 explicit multimap(const _Compare& __comp, 00126 const _Allocator& __a = _Allocator()) 00127 : _Base(__comp, __a) { } 00128 00129 template<typename _InputIterator> 00130 multimap(_InputIterator __first, _InputIterator __last, 00131 const _Compare& __comp = _Compare(), 00132 const _Allocator& __a = _Allocator()) 00133 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00134 __last)), 00135 __gnu_debug::__base(__last), 00136 __comp, __a) { } 00137 00138 multimap(const _Base& __x) 00139 : _Base(__x) { } 00140 00141 #if __cplusplus < 201103L 00142 multimap& 00143 operator=(const multimap& __x) 00144 { 00145 this->_M_safe() = __x; 00146 _M_base() = __x; 00147 return *this; 00148 } 00149 #else 00150 multimap& 00151 operator=(const multimap&) = default; 00152 00153 multimap& 00154 operator=(multimap&&) = default; 00155 00156 multimap& 00157 operator=(initializer_list<value_type> __l) 00158 { 00159 _M_base() = __l; 00160 this->_M_invalidate_all(); 00161 return *this; 00162 } 00163 #endif 00164 00165 using _Base::get_allocator; 00166 00167 // iterators: 00168 iterator 00169 begin() _GLIBCXX_NOEXCEPT 00170 { return iterator(_Base::begin(), this); } 00171 00172 const_iterator 00173 begin() const _GLIBCXX_NOEXCEPT 00174 { return const_iterator(_Base::begin(), this); } 00175 00176 iterator 00177 end() _GLIBCXX_NOEXCEPT 00178 { return iterator(_Base::end(), this); } 00179 00180 const_iterator 00181 end() const _GLIBCXX_NOEXCEPT 00182 { return const_iterator(_Base::end(), this); } 00183 00184 reverse_iterator 00185 rbegin() _GLIBCXX_NOEXCEPT 00186 { return reverse_iterator(end()); } 00187 00188 const_reverse_iterator 00189 rbegin() const _GLIBCXX_NOEXCEPT 00190 { return const_reverse_iterator(end()); } 00191 00192 reverse_iterator 00193 rend() _GLIBCXX_NOEXCEPT 00194 { return reverse_iterator(begin()); } 00195 00196 const_reverse_iterator 00197 rend() const _GLIBCXX_NOEXCEPT 00198 { return const_reverse_iterator(begin()); } 00199 00200 #if __cplusplus >= 201103L 00201 const_iterator 00202 cbegin() const noexcept 00203 { return const_iterator(_Base::begin(), this); } 00204 00205 const_iterator 00206 cend() const noexcept 00207 { return const_iterator(_Base::end(), this); } 00208 00209 const_reverse_iterator 00210 crbegin() const noexcept 00211 { return const_reverse_iterator(end()); } 00212 00213 const_reverse_iterator 00214 crend() const noexcept 00215 { return const_reverse_iterator(begin()); } 00216 #endif 00217 00218 // capacity: 00219 using _Base::empty; 00220 using _Base::size; 00221 using _Base::max_size; 00222 00223 // modifiers: 00224 #if __cplusplus >= 201103L 00225 template<typename... _Args> 00226 iterator 00227 emplace(_Args&&... __args) 00228 { 00229 return iterator(_Base::emplace(std::forward<_Args>(__args)...), this); 00230 } 00231 00232 template<typename... _Args> 00233 iterator 00234 emplace_hint(const_iterator __pos, _Args&&... __args) 00235 { 00236 __glibcxx_check_insert(__pos); 00237 return iterator(_Base::emplace_hint(__pos.base(), 00238 std::forward<_Args>(__args)...), 00239 this); 00240 } 00241 #endif 00242 00243 iterator 00244 insert(const value_type& __x) 00245 { return iterator(_Base::insert(__x), this); } 00246 00247 #if __cplusplus >= 201103L 00248 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00249 // 2354. Unnecessary copying when inserting into maps with braced-init 00250 iterator 00251 insert(value_type&& __x) 00252 { return { _Base::insert(std::move(__x)), this }; } 00253 00254 template<typename _Pair, typename = typename 00255 std::enable_if<std::is_constructible<value_type, 00256 _Pair&&>::value>::type> 00257 iterator 00258 insert(_Pair&& __x) 00259 { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); } 00260 #endif 00261 00262 #if __cplusplus >= 201103L 00263 void 00264 insert(std::initializer_list<value_type> __list) 00265 { _Base::insert(__list); } 00266 #endif 00267 00268 iterator 00269 #if __cplusplus >= 201103L 00270 insert(const_iterator __position, const value_type& __x) 00271 #else 00272 insert(iterator __position, const value_type& __x) 00273 #endif 00274 { 00275 __glibcxx_check_insert(__position); 00276 return iterator(_Base::insert(__position.base(), __x), this); 00277 } 00278 00279 #if __cplusplus >= 201103L 00280 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00281 // 2354. Unnecessary copying when inserting into maps with braced-init 00282 iterator 00283 insert(const_iterator __position, value_type&& __x) 00284 { 00285 __glibcxx_check_insert(__position); 00286 return { _Base::insert(__position.base(), std::move(__x)), this }; 00287 } 00288 00289 template<typename _Pair, typename = typename 00290 std::enable_if<std::is_constructible<value_type, 00291 _Pair&&>::value>::type> 00292 iterator 00293 insert(const_iterator __position, _Pair&& __x) 00294 { 00295 __glibcxx_check_insert(__position); 00296 return iterator(_Base::insert(__position.base(), 00297 std::forward<_Pair>(__x)), this); 00298 } 00299 #endif 00300 00301 template<typename _InputIterator> 00302 void 00303 insert(_InputIterator __first, _InputIterator __last) 00304 { 00305 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 00306 __glibcxx_check_valid_range2(__first, __last, __dist); 00307 00308 if (__dist.second >= __gnu_debug::__dp_sign) 00309 _Base::insert(__gnu_debug::__unsafe(__first), 00310 __gnu_debug::__unsafe(__last)); 00311 else 00312 _Base::insert(__first, __last); 00313 } 00314 00315 #if __cplusplus > 201402L 00316 using node_type = typename _Base::node_type; 00317 00318 node_type 00319 extract(const_iterator __position) 00320 { 00321 __glibcxx_check_erase(__position); 00322 this->_M_invalidate_if(_Equal(__position.base())); 00323 return _Base::extract(__position.base()); 00324 } 00325 00326 node_type 00327 extract(const key_type& __key) 00328 { 00329 const auto __position = find(__key); 00330 if (__position != end()) 00331 return extract(__position); 00332 return {}; 00333 } 00334 00335 iterator 00336 insert(node_type&& __nh) 00337 { return iterator(_Base::insert(std::move(__nh)), this); } 00338 00339 iterator 00340 insert(const_iterator __hint, node_type&& __nh) 00341 { 00342 __glibcxx_check_insert(__hint); 00343 return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); 00344 } 00345 00346 using _Base::merge; 00347 #endif // C++17 00348 00349 #if __cplusplus >= 201103L 00350 iterator 00351 erase(const_iterator __position) 00352 { 00353 __glibcxx_check_erase(__position); 00354 this->_M_invalidate_if(_Equal(__position.base())); 00355 return iterator(_Base::erase(__position.base()), this); 00356 } 00357 00358 iterator 00359 erase(iterator __position) 00360 { return erase(const_iterator(__position)); } 00361 #else 00362 void 00363 erase(iterator __position) 00364 { 00365 __glibcxx_check_erase(__position); 00366 this->_M_invalidate_if(_Equal(__position.base())); 00367 _Base::erase(__position.base()); 00368 } 00369 #endif 00370 00371 size_type 00372 erase(const key_type& __x) 00373 { 00374 std::pair<_Base_iterator, _Base_iterator> __victims = 00375 _Base::equal_range(__x); 00376 size_type __count = 0; 00377 _Base_iterator __victim = __victims.first; 00378 while (__victim != __victims.second) 00379 { 00380 this->_M_invalidate_if(_Equal(__victim)); 00381 _Base::erase(__victim++); 00382 ++__count; 00383 } 00384 return __count; 00385 } 00386 00387 #if __cplusplus >= 201103L 00388 iterator 00389 erase(const_iterator __first, const_iterator __last) 00390 { 00391 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00392 // 151. can't currently clear() empty container 00393 __glibcxx_check_erase_range(__first, __last); 00394 for (_Base_const_iterator __victim = __first.base(); 00395 __victim != __last.base(); ++__victim) 00396 { 00397 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00398 _M_message(__gnu_debug::__msg_valid_range) 00399 ._M_iterator(__first, "first") 00400 ._M_iterator(__last, "last")); 00401 this->_M_invalidate_if(_Equal(__victim)); 00402 } 00403 return iterator(_Base::erase(__first.base(), __last.base()), this); 00404 } 00405 #else 00406 void 00407 erase(iterator __first, iterator __last) 00408 { 00409 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00410 // 151. can't currently clear() empty container 00411 __glibcxx_check_erase_range(__first, __last); 00412 for (_Base_iterator __victim = __first.base(); 00413 __victim != __last.base(); ++__victim) 00414 { 00415 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00416 _M_message(__gnu_debug::__msg_valid_range) 00417 ._M_iterator(__first, "first") 00418 ._M_iterator(__last, "last")); 00419 this->_M_invalidate_if(_Equal(__victim)); 00420 } 00421 _Base::erase(__first.base(), __last.base()); 00422 } 00423 #endif 00424 00425 void 00426 swap(multimap& __x) 00427 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 00428 { 00429 _Safe::_M_swap(__x); 00430 _Base::swap(__x); 00431 } 00432 00433 void 00434 clear() _GLIBCXX_NOEXCEPT 00435 { 00436 this->_M_invalidate_all(); 00437 _Base::clear(); 00438 } 00439 00440 // observers: 00441 using _Base::key_comp; 00442 using _Base::value_comp; 00443 00444 // 23.3.1.3 multimap operations: 00445 iterator 00446 find(const key_type& __x) 00447 { return iterator(_Base::find(__x), this); } 00448 00449 #if __cplusplus > 201103L 00450 template<typename _Kt, 00451 typename _Req = 00452 typename __has_is_transparent<_Compare, _Kt>::type> 00453 iterator 00454 find(const _Kt& __x) 00455 { return { _Base::find(__x), this }; } 00456 #endif 00457 00458 const_iterator 00459 find(const key_type& __x) const 00460 { return const_iterator(_Base::find(__x), this); } 00461 00462 #if __cplusplus > 201103L 00463 template<typename _Kt, 00464 typename _Req = 00465 typename __has_is_transparent<_Compare, _Kt>::type> 00466 const_iterator 00467 find(const _Kt& __x) const 00468 { return { _Base::find(__x), this }; } 00469 #endif 00470 00471 using _Base::count; 00472 00473 iterator 00474 lower_bound(const key_type& __x) 00475 { return iterator(_Base::lower_bound(__x), this); } 00476 00477 #if __cplusplus > 201103L 00478 template<typename _Kt, 00479 typename _Req = 00480 typename __has_is_transparent<_Compare, _Kt>::type> 00481 iterator 00482 lower_bound(const _Kt& __x) 00483 { return { _Base::lower_bound(__x), this }; } 00484 #endif 00485 00486 const_iterator 00487 lower_bound(const key_type& __x) const 00488 { return const_iterator(_Base::lower_bound(__x), this); } 00489 00490 #if __cplusplus > 201103L 00491 template<typename _Kt, 00492 typename _Req = 00493 typename __has_is_transparent<_Compare, _Kt>::type> 00494 const_iterator 00495 lower_bound(const _Kt& __x) const 00496 { return { _Base::lower_bound(__x), this }; } 00497 #endif 00498 00499 iterator 00500 upper_bound(const key_type& __x) 00501 { return iterator(_Base::upper_bound(__x), this); } 00502 00503 #if __cplusplus > 201103L 00504 template<typename _Kt, 00505 typename _Req = 00506 typename __has_is_transparent<_Compare, _Kt>::type> 00507 iterator 00508 upper_bound(const _Kt& __x) 00509 { return { _Base::upper_bound(__x), this }; } 00510 #endif 00511 00512 const_iterator 00513 upper_bound(const key_type& __x) const 00514 { return const_iterator(_Base::upper_bound(__x), this); } 00515 00516 #if __cplusplus > 201103L 00517 template<typename _Kt, 00518 typename _Req = 00519 typename __has_is_transparent<_Compare, _Kt>::type> 00520 const_iterator 00521 upper_bound(const _Kt& __x) const 00522 { return { _Base::upper_bound(__x), this }; } 00523 #endif 00524 00525 std::pair<iterator,iterator> 00526 equal_range(const key_type& __x) 00527 { 00528 std::pair<_Base_iterator, _Base_iterator> __res = 00529 _Base::equal_range(__x); 00530 return std::make_pair(iterator(__res.first, this), 00531 iterator(__res.second, this)); 00532 } 00533 00534 #if __cplusplus > 201103L 00535 template<typename _Kt, 00536 typename _Req = 00537 typename __has_is_transparent<_Compare, _Kt>::type> 00538 std::pair<iterator, iterator> 00539 equal_range(const _Kt& __x) 00540 { 00541 auto __res = _Base::equal_range(__x); 00542 return { { __res.first, this }, { __res.second, this } }; 00543 } 00544 #endif 00545 00546 std::pair<const_iterator,const_iterator> 00547 equal_range(const key_type& __x) const 00548 { 00549 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00550 _Base::equal_range(__x); 00551 return std::make_pair(const_iterator(__res.first, this), 00552 const_iterator(__res.second, this)); 00553 } 00554 00555 #if __cplusplus > 201103L 00556 template<typename _Kt, 00557 typename _Req = 00558 typename __has_is_transparent<_Compare, _Kt>::type> 00559 std::pair<const_iterator, const_iterator> 00560 equal_range(const _Kt& __x) const 00561 { 00562 auto __res = _Base::equal_range(__x); 00563 return { { __res.first, this }, { __res.second, this } }; 00564 } 00565 #endif 00566 00567 _Base& 00568 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 00569 00570 const _Base& 00571 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 00572 }; 00573 00574 #if __cpp_deduction_guides >= 201606 00575 00576 template<typename _InputIterator, 00577 typename _Compare = less<__iter_key_t<_InputIterator>>, 00578 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 00579 typename = _RequireInputIter<_InputIterator>, 00580 typename = _RequireAllocator<_Allocator>> 00581 multimap(_InputIterator, _InputIterator, 00582 _Compare = _Compare(), _Allocator = _Allocator()) 00583 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, 00584 _Compare, _Allocator>; 00585 00586 template<typename _Key, typename _Tp, typename _Compare = less<_Key>, 00587 typename _Allocator = allocator<pair<const _Key, _Tp>>, 00588 typename = _RequireAllocator<_Allocator>> 00589 multimap(initializer_list<pair<_Key, _Tp>>, 00590 _Compare = _Compare(), _Allocator = _Allocator()) 00591 -> multimap<_Key, _Tp, _Compare, _Allocator>; 00592 00593 template<typename _InputIterator, typename _Allocator, 00594 typename = _RequireInputIter<_InputIterator>, 00595 typename = _RequireAllocator<_Allocator>> 00596 multimap(_InputIterator, _InputIterator, _Allocator) 00597 -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, 00598 less<__iter_key_t<_InputIterator>>, _Allocator>; 00599 00600 template<typename _Key, typename _Tp, typename _Allocator, 00601 typename = _RequireAllocator<_Allocator>> 00602 multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 00603 -> multimap<_Key, _Tp, less<_Key>, _Allocator>; 00604 00605 #endif 00606 00607 template<typename _Key, typename _Tp, 00608 typename _Compare, typename _Allocator> 00609 inline bool 00610 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00611 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00612 { return __lhs._M_base() == __rhs._M_base(); } 00613 00614 template<typename _Key, typename _Tp, 00615 typename _Compare, typename _Allocator> 00616 inline bool 00617 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00618 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00619 { return __lhs._M_base() != __rhs._M_base(); } 00620 00621 template<typename _Key, typename _Tp, 00622 typename _Compare, typename _Allocator> 00623 inline bool 00624 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00625 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00626 { return __lhs._M_base() < __rhs._M_base(); } 00627 00628 template<typename _Key, typename _Tp, 00629 typename _Compare, typename _Allocator> 00630 inline bool 00631 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00632 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00633 { return __lhs._M_base() <= __rhs._M_base(); } 00634 00635 template<typename _Key, typename _Tp, 00636 typename _Compare, typename _Allocator> 00637 inline bool 00638 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00639 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00640 { return __lhs._M_base() >= __rhs._M_base(); } 00641 00642 template<typename _Key, typename _Tp, 00643 typename _Compare, typename _Allocator> 00644 inline bool 00645 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00646 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00647 { return __lhs._M_base() > __rhs._M_base(); } 00648 00649 template<typename _Key, typename _Tp, 00650 typename _Compare, typename _Allocator> 00651 inline void 00652 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00653 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00654 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs))) 00655 { __lhs.swap(__rhs); } 00656 00657 } // namespace __debug 00658 } // namespace std 00659 00660 #endif