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