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