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