libstdc++
|
00001 // Debugging multiset 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/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 public: 00059 // types: 00060 typedef _Key key_type; 00061 typedef _Key value_type; 00062 typedef _Compare key_compare; 00063 typedef _Compare value_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, multiset> 00069 iterator; 00070 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 00071 multiset> 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.3.1 construct/copy/destroy: 00081 00082 #if __cplusplus < 201103L 00083 multiset() : _Base() { } 00084 00085 multiset(const multiset& __x) 00086 : _Base(__x) { } 00087 00088 ~multiset() { } 00089 #else 00090 multiset() = default; 00091 multiset(const multiset&) = default; 00092 multiset(multiset&&) = default; 00093 00094 multiset(initializer_list<value_type> __l, 00095 const _Compare& __comp = _Compare(), 00096 const allocator_type& __a = allocator_type()) 00097 : _Base(__l, __comp, __a) { } 00098 00099 explicit 00100 multiset(const allocator_type& __a) 00101 : _Base(__a) { } 00102 00103 multiset(const multiset& __m, const allocator_type& __a) 00104 : _Base(__m, __a) { } 00105 00106 multiset(multiset&& __m, const allocator_type& __a) 00107 noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) ) 00108 : _Safe(std::move(__m._M_safe()), __a), 00109 _Base(std::move(__m._M_base()), __a) { } 00110 00111 multiset(initializer_list<value_type> __l, const allocator_type& __a) 00112 : _Base(__l, __a) 00113 { } 00114 00115 template<typename _InputIterator> 00116 multiset(_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 ~multiset() = default; 00123 #endif 00124 00125 explicit multiset(const _Compare& __comp, 00126 const _Allocator& __a = _Allocator()) 00127 : _Base(__comp, __a) { } 00128 00129 template<typename _InputIterator> 00130 multiset(_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 multiset(const _Base& __x) 00139 : _Base(__x) { } 00140 00141 #if __cplusplus < 201103L 00142 multiset& 00143 operator=(const multiset& __x) 00144 { 00145 this->_M_safe() = __x; 00146 _M_base() = __x; 00147 return *this; 00148 } 00149 #else 00150 multiset& 00151 operator=(const multiset&) = default; 00152 00153 multiset& 00154 operator=(multiset&&) = default; 00155 00156 multiset& 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)...), 00230 this); 00231 } 00232 00233 template<typename... _Args> 00234 iterator 00235 emplace_hint(const_iterator __pos, _Args&&... __args) 00236 { 00237 __glibcxx_check_insert(__pos); 00238 return iterator(_Base::emplace_hint(__pos.base(), 00239 std::forward<_Args>(__args)...), 00240 this); 00241 } 00242 #endif 00243 00244 iterator 00245 insert(const value_type& __x) 00246 { return iterator(_Base::insert(__x), this); } 00247 00248 #if __cplusplus >= 201103L 00249 iterator 00250 insert(value_type&& __x) 00251 { return iterator(_Base::insert(std::move(__x)), this); } 00252 #endif 00253 00254 iterator 00255 insert(const_iterator __position, const value_type& __x) 00256 { 00257 __glibcxx_check_insert(__position); 00258 return iterator(_Base::insert(__position.base(), __x), this); 00259 } 00260 00261 #if __cplusplus >= 201103L 00262 iterator 00263 insert(const_iterator __position, value_type&& __x) 00264 { 00265 __glibcxx_check_insert(__position); 00266 return iterator(_Base::insert(__position.base(), std::move(__x)), 00267 this); 00268 } 00269 #endif 00270 00271 template<typename _InputIterator> 00272 void 00273 insert(_InputIterator __first, _InputIterator __last) 00274 { 00275 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 00276 __glibcxx_check_valid_range2(__first, __last, __dist); 00277 00278 if (__dist.second >= __gnu_debug::__dp_sign) 00279 _Base::insert(__gnu_debug::__unsafe(__first), 00280 __gnu_debug::__unsafe(__last)); 00281 else 00282 _Base::insert(__first, __last); 00283 } 00284 00285 #if __cplusplus >= 201103L 00286 void 00287 insert(initializer_list<value_type> __l) 00288 { _Base::insert(__l); } 00289 #endif 00290 00291 #if __cplusplus > 201402L 00292 using node_type = typename _Base::node_type; 00293 00294 node_type 00295 extract(const_iterator __position) 00296 { 00297 __glibcxx_check_erase(__position); 00298 this->_M_invalidate_if(_Equal(__position.base())); 00299 return _Base::extract(__position.base()); 00300 } 00301 00302 node_type 00303 extract(const key_type& __key) 00304 { 00305 const auto __position = find(__key); 00306 if (__position != end()) 00307 return extract(__position); 00308 return {}; 00309 } 00310 00311 iterator 00312 insert(node_type&& __nh) 00313 { return iterator(_Base::insert(std::move(__nh)), this); } 00314 00315 iterator 00316 insert(const_iterator __hint, node_type&& __nh) 00317 { 00318 __glibcxx_check_insert(__hint); 00319 return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); 00320 } 00321 00322 using _Base::merge; 00323 #endif // C++17 00324 00325 #if __cplusplus >= 201103L 00326 iterator 00327 erase(const_iterator __position) 00328 { 00329 __glibcxx_check_erase(__position); 00330 this->_M_invalidate_if(_Equal(__position.base())); 00331 return iterator(_Base::erase(__position.base()), this); 00332 } 00333 #else 00334 void 00335 erase(iterator __position) 00336 { 00337 __glibcxx_check_erase(__position); 00338 this->_M_invalidate_if(_Equal(__position.base())); 00339 _Base::erase(__position.base()); 00340 } 00341 #endif 00342 00343 size_type 00344 erase(const key_type& __x) 00345 { 00346 std::pair<_Base_iterator, _Base_iterator> __victims = 00347 _Base::equal_range(__x); 00348 size_type __count = 0; 00349 _Base_iterator __victim = __victims.first; 00350 while (__victim != __victims.second) 00351 { 00352 this->_M_invalidate_if(_Equal(__victim)); 00353 _Base::erase(__victim++); 00354 ++__count; 00355 } 00356 return __count; 00357 } 00358 00359 #if __cplusplus >= 201103L 00360 iterator 00361 erase(const_iterator __first, const_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_const_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 return iterator(_Base::erase(__first.base(), __last.base()), this); 00376 } 00377 #else 00378 void 00379 erase(iterator __first, iterator __last) 00380 { 00381 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00382 // 151. can't currently clear() empty container 00383 __glibcxx_check_erase_range(__first, __last); 00384 for (_Base_iterator __victim = __first.base(); 00385 __victim != __last.base(); ++__victim) 00386 { 00387 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00388 _M_message(__gnu_debug::__msg_valid_range) 00389 ._M_iterator(__first, "first") 00390 ._M_iterator(__last, "last")); 00391 this->_M_invalidate_if(_Equal(__victim)); 00392 } 00393 _Base::erase(__first.base(), __last.base()); 00394 } 00395 #endif 00396 00397 void 00398 swap(multiset& __x) 00399 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 00400 { 00401 _Safe::_M_swap(__x); 00402 _Base::swap(__x); 00403 } 00404 00405 void 00406 clear() _GLIBCXX_NOEXCEPT 00407 { 00408 this->_M_invalidate_all(); 00409 _Base::clear(); 00410 } 00411 00412 // observers: 00413 using _Base::key_comp; 00414 using _Base::value_comp; 00415 00416 // multiset operations: 00417 iterator 00418 find(const key_type& __x) 00419 { return iterator(_Base::find(__x), this); } 00420 00421 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00422 // 214. set::find() missing const overload 00423 const_iterator 00424 find(const key_type& __x) const 00425 { return const_iterator(_Base::find(__x), this); } 00426 00427 #if __cplusplus > 201103L 00428 template<typename _Kt, 00429 typename _Req = 00430 typename __has_is_transparent<_Compare, _Kt>::type> 00431 iterator 00432 find(const _Kt& __x) 00433 { return { _Base::find(__x), this }; } 00434 00435 template<typename _Kt, 00436 typename _Req = 00437 typename __has_is_transparent<_Compare, _Kt>::type> 00438 const_iterator 00439 find(const _Kt& __x) const 00440 { return { _Base::find(__x), this }; } 00441 #endif 00442 00443 using _Base::count; 00444 00445 iterator 00446 lower_bound(const key_type& __x) 00447 { return iterator(_Base::lower_bound(__x), this); } 00448 00449 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00450 // 214. set::find() missing const overload 00451 const_iterator 00452 lower_bound(const key_type& __x) const 00453 { return const_iterator(_Base::lower_bound(__x), this); } 00454 00455 #if __cplusplus > 201103L 00456 template<typename _Kt, 00457 typename _Req = 00458 typename __has_is_transparent<_Compare, _Kt>::type> 00459 iterator 00460 lower_bound(const _Kt& __x) 00461 { return { _Base::lower_bound(__x), this }; } 00462 00463 template<typename _Kt, 00464 typename _Req = 00465 typename __has_is_transparent<_Compare, _Kt>::type> 00466 const_iterator 00467 lower_bound(const _Kt& __x) const 00468 { return { _Base::lower_bound(__x), this }; } 00469 #endif 00470 00471 iterator 00472 upper_bound(const key_type& __x) 00473 { return iterator(_Base::upper_bound(__x), this); } 00474 00475 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00476 // 214. set::find() missing const overload 00477 const_iterator 00478 upper_bound(const key_type& __x) const 00479 { return const_iterator(_Base::upper_bound(__x), this); } 00480 00481 #if __cplusplus > 201103L 00482 template<typename _Kt, 00483 typename _Req = 00484 typename __has_is_transparent<_Compare, _Kt>::type> 00485 iterator 00486 upper_bound(const _Kt& __x) 00487 { return { _Base::upper_bound(__x), this }; } 00488 00489 template<typename _Kt, 00490 typename _Req = 00491 typename __has_is_transparent<_Compare, _Kt>::type> 00492 const_iterator 00493 upper_bound(const _Kt& __x) const 00494 { return { _Base::upper_bound(__x), this }; } 00495 #endif 00496 00497 std::pair<iterator,iterator> 00498 equal_range(const key_type& __x) 00499 { 00500 std::pair<_Base_iterator, _Base_iterator> __res = 00501 _Base::equal_range(__x); 00502 return std::make_pair(iterator(__res.first, this), 00503 iterator(__res.second, this)); 00504 } 00505 00506 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00507 // 214. set::find() missing const overload 00508 std::pair<const_iterator,const_iterator> 00509 equal_range(const key_type& __x) const 00510 { 00511 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00512 _Base::equal_range(__x); 00513 return std::make_pair(const_iterator(__res.first, this), 00514 const_iterator(__res.second, this)); 00515 } 00516 00517 #if __cplusplus > 201103L 00518 template<typename _Kt, 00519 typename _Req = 00520 typename __has_is_transparent<_Compare, _Kt>::type> 00521 std::pair<iterator, iterator> 00522 equal_range(const _Kt& __x) 00523 { 00524 auto __res = _Base::equal_range(__x); 00525 return { { __res.first, this }, { __res.second, this } }; 00526 } 00527 00528 template<typename _Kt, 00529 typename _Req = 00530 typename __has_is_transparent<_Compare, _Kt>::type> 00531 std::pair<const_iterator, const_iterator> 00532 equal_range(const _Kt& __x) const 00533 { 00534 auto __res = _Base::equal_range(__x); 00535 return { { __res.first, this }, { __res.second, this } }; 00536 } 00537 #endif 00538 00539 _Base& 00540 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 00541 00542 const _Base& 00543 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 00544 }; 00545 00546 #if __cpp_deduction_guides >= 201606 00547 00548 template<typename _InputIterator, 00549 typename _Compare = 00550 less<typename iterator_traits<_InputIterator>::value_type>, 00551 typename _Allocator = 00552 allocator<typename iterator_traits<_InputIterator>::value_type>, 00553 typename = _RequireInputIter<_InputIterator>, 00554 typename = _RequireAllocator<_Allocator>> 00555 multiset(_InputIterator, _InputIterator, 00556 _Compare = _Compare(), _Allocator = _Allocator()) 00557 -> multiset<typename iterator_traits<_InputIterator>::value_type, 00558 _Compare, _Allocator>; 00559 00560 template<typename _Key, 00561 typename _Compare = less<_Key>, 00562 typename _Allocator = allocator<_Key>, 00563 typename = _RequireAllocator<_Allocator>> 00564 multiset(initializer_list<_Key>, 00565 _Compare = _Compare(), _Allocator = _Allocator()) 00566 -> multiset<_Key, _Compare, _Allocator>; 00567 00568 template<typename _InputIterator, typename _Allocator, 00569 typename = _RequireInputIter<_InputIterator>, 00570 typename = _RequireAllocator<_Allocator>> 00571 multiset(_InputIterator, _InputIterator, _Allocator) 00572 -> multiset<typename iterator_traits<_InputIterator>::value_type, 00573 less<typename iterator_traits<_InputIterator>::value_type>, 00574 _Allocator>; 00575 00576 template<typename _Key, typename _Allocator, 00577 typename = _RequireAllocator<_Allocator>> 00578 multiset(initializer_list<_Key>, _Allocator) 00579 -> multiset<_Key, less<_Key>, _Allocator>; 00580 00581 #endif 00582 00583 template<typename _Key, typename _Compare, typename _Allocator> 00584 inline bool 00585 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs, 00586 const multiset<_Key, _Compare, _Allocator>& __rhs) 00587 { return __lhs._M_base() == __rhs._M_base(); } 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 void 00621 swap(multiset<_Key, _Compare, _Allocator>& __x, 00622 multiset<_Key, _Compare, _Allocator>& __y) 00623 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 00624 { return __x.swap(__y); } 00625 00626 } // namespace __debug 00627 } // namespace std 00628 00629 #endif