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