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