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