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