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