libstdc++
|
00001 // Debugging list 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/list 00026 * This file is a GNU debug extension to the Standard C++ Library. 00027 */ 00028 00029 #ifndef _GLIBCXX_DEBUG_LIST 00030 #define _GLIBCXX_DEBUG_LIST 1 00031 00032 #pragma GCC system_header 00033 00034 #include <bits/c++config.h> 00035 namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug { 00036 template<typename _Tp, typename _Allocator> class list; 00037 } } // namespace std::__debug 00038 00039 #include <list> 00040 #include <debug/safe_sequence.h> 00041 #include <debug/safe_container.h> 00042 #include <debug/safe_iterator.h> 00043 00044 namespace std _GLIBCXX_VISIBILITY(default) 00045 { 00046 namespace __debug 00047 { 00048 /// Class std::list with safety/checking/debug instrumentation. 00049 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 00050 class list 00051 : public __gnu_debug::_Safe_container< 00052 list<_Tp, _Allocator>, _Allocator, 00053 __gnu_debug::_Safe_node_sequence>, 00054 public _GLIBCXX_STD_C::list<_Tp, _Allocator> 00055 { 00056 typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base; 00057 typedef __gnu_debug::_Safe_container< 00058 list, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe; 00059 00060 typedef typename _Base::iterator _Base_iterator; 00061 typedef typename _Base::const_iterator _Base_const_iterator; 00062 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 00063 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00064 00065 template<typename _ItT, typename _SeqT, typename _CatT> 00066 friend class ::__gnu_debug::_Safe_iterator; 00067 00068 public: 00069 typedef typename _Base::reference reference; 00070 typedef typename _Base::const_reference const_reference; 00071 00072 typedef __gnu_debug::_Safe_iterator<_Base_iterator, list> 00073 iterator; 00074 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, list> 00075 const_iterator; 00076 00077 typedef typename _Base::size_type size_type; 00078 typedef typename _Base::difference_type difference_type; 00079 00080 typedef _Tp value_type; 00081 typedef _Allocator allocator_type; 00082 typedef typename _Base::pointer pointer; 00083 typedef typename _Base::const_pointer const_pointer; 00084 typedef std::reverse_iterator<iterator> reverse_iterator; 00085 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00086 00087 // 23.2.2.1 construct/copy/destroy: 00088 00089 #if __cplusplus < 201103L 00090 list() 00091 : _Base() { } 00092 00093 list(const list& __x) 00094 : _Base(__x) { } 00095 00096 ~list() { } 00097 #else 00098 list() = default; 00099 list(const list&) = default; 00100 list(list&&) = default; 00101 00102 list(initializer_list<value_type> __l, 00103 const allocator_type& __a = allocator_type()) 00104 : _Base(__l, __a) { } 00105 00106 ~list() = default; 00107 00108 list(const list& __x, const allocator_type& __a) 00109 : _Base(__x, __a) { } 00110 00111 list(list&& __x, const allocator_type& __a) 00112 : _Base(std::move(__x), __a) { } 00113 #endif 00114 00115 explicit 00116 list(const _Allocator& __a) _GLIBCXX_NOEXCEPT 00117 : _Base(__a) { } 00118 00119 #if __cplusplus >= 201103L 00120 explicit 00121 list(size_type __n, const allocator_type& __a = allocator_type()) 00122 : _Base(__n, __a) { } 00123 00124 list(size_type __n, const _Tp& __value, 00125 const _Allocator& __a = _Allocator()) 00126 : _Base(__n, __value, __a) { } 00127 #else 00128 explicit 00129 list(size_type __n, const _Tp& __value = _Tp(), 00130 const _Allocator& __a = _Allocator()) 00131 : _Base(__n, __value, __a) { } 00132 #endif 00133 00134 #if __cplusplus >= 201103L 00135 template<class _InputIterator, 00136 typename = std::_RequireInputIter<_InputIterator>> 00137 #else 00138 template<class _InputIterator> 00139 #endif 00140 list(_InputIterator __first, _InputIterator __last, 00141 const _Allocator& __a = _Allocator()) 00142 : _Base(__gnu_debug::__base( 00143 __glibcxx_check_valid_constructor_range(__first, __last)), 00144 __gnu_debug::__base(__last), __a) 00145 { } 00146 00147 list(const _Base& __x) 00148 : _Base(__x) { } 00149 00150 #if __cplusplus < 201103L 00151 list& 00152 operator=(const list& __x) 00153 { 00154 this->_M_safe() = __x; 00155 _M_base() = __x; 00156 return *this; 00157 } 00158 #else 00159 list& 00160 operator=(const list&) = default; 00161 00162 list& 00163 operator=(list&&) = default; 00164 00165 list& 00166 operator=(initializer_list<value_type> __l) 00167 { 00168 this->_M_invalidate_all(); 00169 _M_base() = __l; 00170 return *this; 00171 } 00172 00173 void 00174 assign(initializer_list<value_type> __l) 00175 { 00176 _Base::assign(__l); 00177 this->_M_invalidate_all(); 00178 } 00179 #endif 00180 00181 #if __cplusplus >= 201103L 00182 template<class _InputIterator, 00183 typename = std::_RequireInputIter<_InputIterator>> 00184 #else 00185 template<class _InputIterator> 00186 #endif 00187 void 00188 assign(_InputIterator __first, _InputIterator __last) 00189 { 00190 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 00191 __glibcxx_check_valid_range2(__first, __last, __dist); 00192 00193 if (__dist.second >= __gnu_debug::__dp_sign) 00194 _Base::assign(__gnu_debug::__unsafe(__first), 00195 __gnu_debug::__unsafe(__last)); 00196 else 00197 _Base::assign(__first, __last); 00198 00199 this->_M_invalidate_all(); 00200 } 00201 00202 void 00203 assign(size_type __n, const _Tp& __t) 00204 { 00205 _Base::assign(__n, __t); 00206 this->_M_invalidate_all(); 00207 } 00208 00209 using _Base::get_allocator; 00210 00211 // iterators: 00212 iterator 00213 begin() _GLIBCXX_NOEXCEPT 00214 { return iterator(_Base::begin(), this); } 00215 00216 const_iterator 00217 begin() const _GLIBCXX_NOEXCEPT 00218 { return const_iterator(_Base::begin(), this); } 00219 00220 iterator 00221 end() _GLIBCXX_NOEXCEPT 00222 { return iterator(_Base::end(), this); } 00223 00224 const_iterator 00225 end() const _GLIBCXX_NOEXCEPT 00226 { return const_iterator(_Base::end(), this); } 00227 00228 reverse_iterator 00229 rbegin() _GLIBCXX_NOEXCEPT 00230 { return reverse_iterator(end()); } 00231 00232 const_reverse_iterator 00233 rbegin() const _GLIBCXX_NOEXCEPT 00234 { return const_reverse_iterator(end()); } 00235 00236 reverse_iterator 00237 rend() _GLIBCXX_NOEXCEPT 00238 { return reverse_iterator(begin()); } 00239 00240 const_reverse_iterator 00241 rend() const _GLIBCXX_NOEXCEPT 00242 { return const_reverse_iterator(begin()); } 00243 00244 #if __cplusplus >= 201103L 00245 const_iterator 00246 cbegin() const noexcept 00247 { return const_iterator(_Base::begin(), this); } 00248 00249 const_iterator 00250 cend() const noexcept 00251 { return const_iterator(_Base::end(), this); } 00252 00253 const_reverse_iterator 00254 crbegin() const noexcept 00255 { return const_reverse_iterator(end()); } 00256 00257 const_reverse_iterator 00258 crend() const noexcept 00259 { return const_reverse_iterator(begin()); } 00260 #endif 00261 00262 // 23.2.2.2 capacity: 00263 using _Base::empty; 00264 using _Base::size; 00265 using _Base::max_size; 00266 00267 #if __cplusplus >= 201103L 00268 void 00269 resize(size_type __sz) 00270 { 00271 this->_M_detach_singular(); 00272 00273 // if __sz < size(), invalidate all iterators in [begin + __sz, end()) 00274 _Base_iterator __victim = _Base::begin(); 00275 _Base_iterator __end = _Base::end(); 00276 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 00277 ++__victim; 00278 00279 for (; __victim != __end; ++__victim) 00280 this->_M_invalidate_if(_Equal(__victim)); 00281 00282 __try 00283 { 00284 _Base::resize(__sz); 00285 } 00286 __catch(...) 00287 { 00288 this->_M_revalidate_singular(); 00289 __throw_exception_again; 00290 } 00291 } 00292 00293 void 00294 resize(size_type __sz, const _Tp& __c) 00295 { 00296 this->_M_detach_singular(); 00297 00298 // if __sz < size(), invalidate all iterators in [begin + __sz, end()) 00299 _Base_iterator __victim = _Base::begin(); 00300 _Base_iterator __end = _Base::end(); 00301 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 00302 ++__victim; 00303 00304 for (; __victim != __end; ++__victim) 00305 this->_M_invalidate_if(_Equal(__victim)); 00306 00307 __try 00308 { 00309 _Base::resize(__sz, __c); 00310 } 00311 __catch(...) 00312 { 00313 this->_M_revalidate_singular(); 00314 __throw_exception_again; 00315 } 00316 } 00317 #else 00318 void 00319 resize(size_type __sz, _Tp __c = _Tp()) 00320 { 00321 this->_M_detach_singular(); 00322 00323 // if __sz < size(), invalidate all iterators in [begin + __sz, end()) 00324 _Base_iterator __victim = _Base::begin(); 00325 _Base_iterator __end = _Base::end(); 00326 for (size_type __i = __sz; __victim != __end && __i > 0; --__i) 00327 ++__victim; 00328 00329 for (; __victim != __end; ++__victim) 00330 this->_M_invalidate_if(_Equal(__victim)); 00331 00332 __try 00333 { 00334 _Base::resize(__sz, __c); 00335 } 00336 __catch(...) 00337 { 00338 this->_M_revalidate_singular(); 00339 __throw_exception_again; 00340 } 00341 } 00342 #endif 00343 00344 // element access: 00345 reference 00346 front() _GLIBCXX_NOEXCEPT 00347 { 00348 __glibcxx_check_nonempty(); 00349 return _Base::front(); 00350 } 00351 00352 const_reference 00353 front() const _GLIBCXX_NOEXCEPT 00354 { 00355 __glibcxx_check_nonempty(); 00356 return _Base::front(); 00357 } 00358 00359 reference 00360 back() _GLIBCXX_NOEXCEPT 00361 { 00362 __glibcxx_check_nonempty(); 00363 return _Base::back(); 00364 } 00365 00366 const_reference 00367 back() const _GLIBCXX_NOEXCEPT 00368 { 00369 __glibcxx_check_nonempty(); 00370 return _Base::back(); 00371 } 00372 00373 // 23.2.2.3 modifiers: 00374 using _Base::push_front; 00375 00376 #if __cplusplus >= 201103L 00377 using _Base::emplace_front; 00378 #endif 00379 00380 void 00381 pop_front() _GLIBCXX_NOEXCEPT 00382 { 00383 __glibcxx_check_nonempty(); 00384 this->_M_invalidate_if(_Equal(_Base::begin())); 00385 _Base::pop_front(); 00386 } 00387 00388 using _Base::push_back; 00389 00390 #if __cplusplus >= 201103L 00391 using _Base::emplace_back; 00392 #endif 00393 00394 void 00395 pop_back() _GLIBCXX_NOEXCEPT 00396 { 00397 __glibcxx_check_nonempty(); 00398 this->_M_invalidate_if(_Equal(--_Base::end())); 00399 _Base::pop_back(); 00400 } 00401 00402 #if __cplusplus >= 201103L 00403 template<typename... _Args> 00404 iterator 00405 emplace(const_iterator __position, _Args&&... __args) 00406 { 00407 __glibcxx_check_insert(__position); 00408 return { _Base::emplace(__position.base(), 00409 std::forward<_Args>(__args)...), this }; 00410 } 00411 #endif 00412 00413 iterator 00414 #if __cplusplus >= 201103L 00415 insert(const_iterator __position, const _Tp& __x) 00416 #else 00417 insert(iterator __position, const _Tp& __x) 00418 #endif 00419 { 00420 __glibcxx_check_insert(__position); 00421 return iterator(_Base::insert(__position.base(), __x), this); 00422 } 00423 00424 #if __cplusplus >= 201103L 00425 iterator 00426 insert(const_iterator __position, _Tp&& __x) 00427 { return emplace(__position, std::move(__x)); } 00428 00429 iterator 00430 insert(const_iterator __p, initializer_list<value_type> __l) 00431 { 00432 __glibcxx_check_insert(__p); 00433 return { _Base::insert(__p.base(), __l), this }; 00434 } 00435 #endif 00436 00437 #if __cplusplus >= 201103L 00438 iterator 00439 insert(const_iterator __position, size_type __n, const _Tp& __x) 00440 { 00441 __glibcxx_check_insert(__position); 00442 return { _Base::insert(__position.base(), __n, __x), this }; 00443 } 00444 #else 00445 void 00446 insert(iterator __position, size_type __n, const _Tp& __x) 00447 { 00448 __glibcxx_check_insert(__position); 00449 _Base::insert(__position.base(), __n, __x); 00450 } 00451 #endif 00452 00453 #if __cplusplus >= 201103L 00454 template<class _InputIterator, 00455 typename = std::_RequireInputIter<_InputIterator>> 00456 iterator 00457 insert(const_iterator __position, _InputIterator __first, 00458 _InputIterator __last) 00459 { 00460 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 00461 __glibcxx_check_insert_range(__position, __first, __last, __dist); 00462 if (__dist.second >= __gnu_debug::__dp_sign) 00463 return 00464 { 00465 _Base::insert(__position.base(), 00466 __gnu_debug::__unsafe(__first), 00467 __gnu_debug::__unsafe(__last)), 00468 this 00469 }; 00470 else 00471 return { _Base::insert(__position.base(), __first, __last), this }; 00472 } 00473 #else 00474 template<class _InputIterator> 00475 void 00476 insert(iterator __position, _InputIterator __first, 00477 _InputIterator __last) 00478 { 00479 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 00480 __glibcxx_check_insert_range(__position, __first, __last, __dist); 00481 00482 if (__dist.second >= __gnu_debug::__dp_sign) 00483 _Base::insert(__position.base(), __gnu_debug::__unsafe(__first), 00484 __gnu_debug::__unsafe(__last)); 00485 else 00486 _Base::insert(__position.base(), __first, __last); 00487 } 00488 #endif 00489 00490 private: 00491 _Base_iterator 00492 #if __cplusplus >= 201103L 00493 _M_erase(_Base_const_iterator __position) noexcept 00494 #else 00495 _M_erase(_Base_iterator __position) 00496 #endif 00497 { 00498 this->_M_invalidate_if(_Equal(__position)); 00499 return _Base::erase(__position); 00500 } 00501 00502 public: 00503 iterator 00504 #if __cplusplus >= 201103L 00505 erase(const_iterator __position) noexcept 00506 #else 00507 erase(iterator __position) 00508 #endif 00509 { 00510 __glibcxx_check_erase(__position); 00511 return iterator(_M_erase(__position.base()), this); 00512 } 00513 00514 iterator 00515 #if __cplusplus >= 201103L 00516 erase(const_iterator __first, const_iterator __last) noexcept 00517 #else 00518 erase(iterator __first, iterator __last) 00519 #endif 00520 { 00521 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00522 // 151. can't currently clear() empty container 00523 __glibcxx_check_erase_range(__first, __last); 00524 for (_Base_const_iterator __victim = __first.base(); 00525 __victim != __last.base(); ++__victim) 00526 { 00527 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00528 _M_message(__gnu_debug::__msg_valid_range) 00529 ._M_iterator(__first, "position") 00530 ._M_iterator(__last, "last")); 00531 this->_M_invalidate_if(_Equal(__victim)); 00532 } 00533 00534 return iterator(_Base::erase(__first.base(), __last.base()), this); 00535 } 00536 00537 void 00538 swap(list& __x) 00539 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 00540 { 00541 _Safe::_M_swap(__x); 00542 _Base::swap(__x); 00543 } 00544 00545 void 00546 clear() _GLIBCXX_NOEXCEPT 00547 { 00548 _Base::clear(); 00549 this->_M_invalidate_all(); 00550 } 00551 00552 // 23.2.2.4 list operations: 00553 void 00554 #if __cplusplus >= 201103L 00555 splice(const_iterator __position, list&& __x) noexcept 00556 #else 00557 splice(iterator __position, list& __x) 00558 #endif 00559 { 00560 _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this, 00561 _M_message(__gnu_debug::__msg_self_splice) 00562 ._M_sequence(*this, "this")); 00563 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end())); 00564 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base())); 00565 } 00566 00567 #if __cplusplus >= 201103L 00568 void 00569 splice(const_iterator __position, list& __x) noexcept 00570 { splice(__position, std::move(__x)); } 00571 #endif 00572 00573 void 00574 #if __cplusplus >= 201103L 00575 splice(const_iterator __position, list&& __x, const_iterator __i) noexcept 00576 #else 00577 splice(iterator __position, list& __x, iterator __i) 00578 #endif 00579 { 00580 __glibcxx_check_insert(__position); 00581 00582 // We used to perform the splice_alloc check: not anymore, redundant 00583 // after implementing the relevant bits of N1599. 00584 00585 _GLIBCXX_DEBUG_VERIFY(__i._M_dereferenceable(), 00586 _M_message(__gnu_debug::__msg_splice_bad) 00587 ._M_iterator(__i, "__i")); 00588 _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(std::__addressof(__x)), 00589 _M_message(__gnu_debug::__msg_splice_other) 00590 ._M_iterator(__i, "__i")._M_sequence(__x, "__x")); 00591 00592 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00593 // 250. splicing invalidates iterators 00594 this->_M_transfer_from_if(__x, _Equal(__i.base())); 00595 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()), 00596 __i.base()); 00597 } 00598 00599 #if __cplusplus >= 201103L 00600 void 00601 splice(const_iterator __position, list& __x, const_iterator __i) noexcept 00602 { splice(__position, std::move(__x), __i); } 00603 #endif 00604 00605 void 00606 #if __cplusplus >= 201103L 00607 splice(const_iterator __position, list&& __x, const_iterator __first, 00608 const_iterator __last) noexcept 00609 #else 00610 splice(iterator __position, list& __x, iterator __first, 00611 iterator __last) 00612 #endif 00613 { 00614 __glibcxx_check_insert(__position); 00615 __glibcxx_check_valid_range(__first, __last); 00616 _GLIBCXX_DEBUG_VERIFY(__first._M_attached_to(std::__addressof(__x)), 00617 _M_message(__gnu_debug::__msg_splice_other) 00618 ._M_sequence(__x, "x") 00619 ._M_iterator(__first, "first")); 00620 00621 // We used to perform the splice_alloc check: not anymore, redundant 00622 // after implementing the relevant bits of N1599. 00623 00624 for (_Base_const_iterator __tmp = __first.base(); 00625 __tmp != __last.base(); ++__tmp) 00626 { 00627 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00628 _M_message(__gnu_debug::__msg_valid_range) 00629 ._M_iterator(__first, "first") 00630 ._M_iterator(__last, "last")); 00631 _GLIBCXX_DEBUG_VERIFY(std::__addressof(__x) != this 00632 || __tmp != __position.base(), 00633 _M_message(__gnu_debug::__msg_splice_overlap) 00634 ._M_iterator(__tmp, "position") 00635 ._M_iterator(__first, "first") 00636 ._M_iterator(__last, "last")); 00637 00638 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00639 // 250. splicing invalidates iterators 00640 this->_M_transfer_from_if(__x, _Equal(__tmp)); 00641 } 00642 00643 _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()), 00644 __first.base(), __last.base()); 00645 } 00646 00647 #if __cplusplus >= 201103L 00648 void 00649 splice(const_iterator __position, list& __x, 00650 const_iterator __first, const_iterator __last) noexcept 00651 { splice(__position, std::move(__x), __first, __last); } 00652 #endif 00653 00654 private: 00655 #if __cplusplus > 201703L 00656 typedef size_type __remove_return_type; 00657 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \ 00658 __attribute__((__abi_tag__("__cxx20"))) 00659 # define _GLIBCXX20_ONLY(__expr) __expr 00660 #else 00661 typedef void __remove_return_type; 00662 # define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG 00663 # define _GLIBCXX20_ONLY(__expr) 00664 #endif 00665 00666 public: 00667 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG 00668 __remove_return_type 00669 remove(const _Tp& __value) 00670 { 00671 if (!this->_M_iterators && !this->_M_const_iterators) 00672 return _Base::remove(__value); 00673 00674 size_type __removed __attribute__((__unused__)) = 0; 00675 _Base_iterator __first = _Base::begin(); 00676 _Base_iterator __last = _Base::end(); 00677 _Base_iterator __extra = __last; 00678 while (__first != __last) 00679 { 00680 if (*__first == __value) 00681 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00682 // 526. Is it undefined if a function in the standard changes 00683 // in parameters? 00684 if (std::__addressof(*__first) != std::__addressof(__value)) 00685 { 00686 __first = _M_erase(__first); 00687 _GLIBCXX20_ONLY( __removed++ ); 00688 } 00689 else 00690 { 00691 __extra = __first; 00692 ++__first; 00693 } 00694 else 00695 ++__first; 00696 } 00697 00698 if (__extra != __last) 00699 { 00700 _M_erase(__extra); 00701 _GLIBCXX20_ONLY( __removed++ ); 00702 } 00703 return _GLIBCXX20_ONLY( __removed ); 00704 } 00705 00706 template<class _Predicate> 00707 __remove_return_type 00708 remove_if(_Predicate __pred) 00709 { 00710 if (!this->_M_iterators && !this->_M_const_iterators) 00711 return _Base::remove_if(__pred); 00712 00713 size_type __removed __attribute__((__unused__)) = 0; 00714 for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); ) 00715 if (__pred(*__x)) 00716 { 00717 __x = _M_erase(__x); 00718 _GLIBCXX20_ONLY( __removed++ ); 00719 } 00720 else 00721 ++__x; 00722 00723 return _GLIBCXX20_ONLY( __removed ); 00724 } 00725 00726 _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG 00727 __remove_return_type 00728 unique() 00729 { 00730 if (!this->_M_iterators && !this->_M_const_iterators) 00731 return _Base::unique(); 00732 00733 if (empty()) 00734 return _GLIBCXX20_ONLY(0); 00735 00736 size_type __removed __attribute__((__unused__)) = 0; 00737 _Base_iterator __first = _Base::begin(); 00738 _Base_iterator __last = _Base::end(); 00739 _Base_iterator __next = __first; 00740 while (++__next != __last) 00741 if (*__first == *__next) 00742 { 00743 _M_erase(__next); 00744 __next = __first; 00745 _GLIBCXX20_ONLY( __removed++ ); 00746 } 00747 else 00748 __first = __next; 00749 00750 return _GLIBCXX20_ONLY( __removed ); 00751 } 00752 00753 template<class _BinaryPredicate> 00754 __remove_return_type 00755 unique(_BinaryPredicate __binary_pred) 00756 { 00757 if (!this->_M_iterators && !this->_M_const_iterators) 00758 return _Base::unique(__binary_pred); 00759 00760 if (empty()) 00761 return _GLIBCXX20_ONLY(0); 00762 00763 size_type __removed __attribute__((__unused__)) = 0; 00764 _Base_iterator __first = _Base::begin(); 00765 _Base_iterator __last = _Base::end(); 00766 _Base_iterator __next = __first;; 00767 while (++__next != __last) 00768 if (__binary_pred(*__first, *__next)) 00769 { 00770 _M_erase(__next); 00771 __next = __first; 00772 _GLIBCXX20_ONLY( __removed++ ); 00773 } 00774 else 00775 __first = __next; 00776 00777 return _GLIBCXX20_ONLY( __removed ); 00778 } 00779 00780 #undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG 00781 #undef _GLIBCXX20_ONLY 00782 00783 void 00784 #if __cplusplus >= 201103L 00785 merge(list&& __x) 00786 #else 00787 merge(list& __x) 00788 #endif 00789 { 00790 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00791 // 300. list::merge() specification incomplete 00792 if (this != std::__addressof(__x)) 00793 { 00794 __glibcxx_check_sorted(_Base::begin(), _Base::end()); 00795 __glibcxx_check_sorted(__x.begin().base(), __x.end().base()); 00796 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end())); 00797 _Base::merge(_GLIBCXX_MOVE(__x._M_base())); 00798 } 00799 } 00800 00801 #if __cplusplus >= 201103L 00802 void 00803 merge(list& __x) 00804 { merge(std::move(__x)); } 00805 #endif 00806 00807 template<class _Compare> 00808 void 00809 #if __cplusplus >= 201103L 00810 merge(list&& __x, _Compare __comp) 00811 #else 00812 merge(list& __x, _Compare __comp) 00813 #endif 00814 { 00815 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00816 // 300. list::merge() specification incomplete 00817 if (this != std::__addressof(__x)) 00818 { 00819 __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), 00820 __comp); 00821 __glibcxx_check_sorted_pred(__x.begin().base(), __x.end().base(), 00822 __comp); 00823 this->_M_transfer_from_if(__x, _Not_equal(__x._M_base().end())); 00824 _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp); 00825 } 00826 } 00827 00828 #if __cplusplus >= 201103L 00829 template<typename _Compare> 00830 void 00831 merge(list& __x, _Compare __comp) 00832 { merge(std::move(__x), __comp); } 00833 #endif 00834 00835 void 00836 sort() { _Base::sort(); } 00837 00838 template<typename _StrictWeakOrdering> 00839 void 00840 sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); } 00841 00842 using _Base::reverse; 00843 00844 _Base& 00845 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 00846 00847 const _Base& 00848 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 00849 }; 00850 00851 #if __cpp_deduction_guides >= 201606 00852 template<typename _InputIterator, typename _ValT 00853 = typename iterator_traits<_InputIterator>::value_type, 00854 typename _Allocator = allocator<_ValT>, 00855 typename = _RequireInputIter<_InputIterator>, 00856 typename = _RequireAllocator<_Allocator>> 00857 list(_InputIterator, _InputIterator, _Allocator = _Allocator()) 00858 -> list<_ValT, _Allocator>; 00859 #endif 00860 00861 template<typename _Tp, typename _Alloc> 00862 inline bool 00863 operator==(const list<_Tp, _Alloc>& __lhs, 00864 const list<_Tp, _Alloc>& __rhs) 00865 { return __lhs._M_base() == __rhs._M_base(); } 00866 00867 template<typename _Tp, typename _Alloc> 00868 inline bool 00869 operator!=(const list<_Tp, _Alloc>& __lhs, 00870 const list<_Tp, _Alloc>& __rhs) 00871 { return __lhs._M_base() != __rhs._M_base(); } 00872 00873 template<typename _Tp, typename _Alloc> 00874 inline bool 00875 operator<(const list<_Tp, _Alloc>& __lhs, 00876 const list<_Tp, _Alloc>& __rhs) 00877 { return __lhs._M_base() < __rhs._M_base(); } 00878 00879 template<typename _Tp, typename _Alloc> 00880 inline bool 00881 operator<=(const list<_Tp, _Alloc>& __lhs, 00882 const list<_Tp, _Alloc>& __rhs) 00883 { return __lhs._M_base() <= __rhs._M_base(); } 00884 00885 template<typename _Tp, typename _Alloc> 00886 inline bool 00887 operator>=(const list<_Tp, _Alloc>& __lhs, 00888 const list<_Tp, _Alloc>& __rhs) 00889 { return __lhs._M_base() >= __rhs._M_base(); } 00890 00891 template<typename _Tp, typename _Alloc> 00892 inline bool 00893 operator>(const list<_Tp, _Alloc>& __lhs, 00894 const list<_Tp, _Alloc>& __rhs) 00895 { return __lhs._M_base() > __rhs._M_base(); } 00896 00897 template<typename _Tp, typename _Alloc> 00898 inline void 00899 swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs) 00900 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs))) 00901 { __lhs.swap(__rhs); } 00902 00903 } // namespace __debug 00904 } // namespace std 00905 00906 namespace __gnu_debug 00907 { 00908 #ifndef _GLIBCXX_USE_CXX11_ABI 00909 // If not using C++11 list::size() is not in O(1) so we do not use it. 00910 template<typename _Tp, typename _Alloc> 00911 struct _Sequence_traits<std::__debug::list<_Tp, _Alloc> > 00912 { 00913 typedef typename std::__debug::list<_Tp, _Alloc>::iterator _It; 00914 00915 static typename _Distance_traits<_It>::__type 00916 _S_size(const std::__debug::list<_Tp, _Alloc>& __seq) 00917 { 00918 return __seq.empty() 00919 ? std::make_pair(0, __dp_exact) : std::make_pair(1, __dp_equality); 00920 } 00921 }; 00922 #endif 00923 00924 #ifndef _GLIBCXX_DEBUG_PEDANTIC 00925 template<class _Tp, class _Alloc> 00926 struct _Insert_range_from_self_is_safe<std::__debug::list<_Tp, _Alloc> > 00927 { enum { __value = 1 }; }; 00928 #endif 00929 } 00930 00931 #endif