libstdc++
list
Go to the documentation of this file.
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