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