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