libstdc++
list.tcc
Go to the documentation of this file.
00001 // List implementation (out of line) -*- C++ -*-
00002 
00003 // Copyright (C) 2001-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 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1996,1997
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file bits/list.tcc
00052  *  This is an internal header file, included by other library headers.
00053  *  Do not attempt to use it directly. @headername{list}
00054  */
00055 
00056 #ifndef _LIST_TCC
00057 #define _LIST_TCC 1
00058 
00059 namespace std _GLIBCXX_VISIBILITY(default)
00060 {
00061 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00062 
00063   template<typename _Tp, typename _Alloc>
00064     void
00065     _List_base<_Tp, _Alloc>::
00066     _M_clear() _GLIBCXX_NOEXCEPT
00067     {
00068       typedef _List_node<_Tp>  _Node;
00069       _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next);
00070       while (__cur != &_M_impl._M_node)
00071     {
00072       _Node* __tmp = __cur;
00073       __cur = static_cast<_Node*>(__cur->_M_next);
00074 #if __cplusplus >= 201103L
00075       _M_get_Node_allocator().destroy(__tmp);
00076 #else
00077       _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data));
00078 #endif
00079       _M_put_node(__tmp);
00080     }
00081     }
00082 
00083 #if __cplusplus >= 201103L
00084   template<typename _Tp, typename _Alloc>
00085     template<typename... _Args>
00086       typename list<_Tp, _Alloc>::iterator
00087       list<_Tp, _Alloc>::
00088       emplace(const_iterator __position, _Args&&... __args)
00089       {
00090     _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
00091     __tmp->_M_hook(__position._M_const_cast()._M_node);
00092     return iterator(__tmp);
00093       }
00094 #endif
00095 
00096   template<typename _Tp, typename _Alloc>
00097     typename list<_Tp, _Alloc>::iterator
00098     list<_Tp, _Alloc>::
00099 #if __cplusplus >= 201103L
00100     insert(const_iterator __position, const value_type& __x)
00101 #else
00102     insert(iterator __position, const value_type& __x)
00103 #endif
00104     {
00105       _Node* __tmp = _M_create_node(__x);
00106       __tmp->_M_hook(__position._M_const_cast()._M_node);
00107       return iterator(__tmp);
00108     }
00109 
00110 #if __cplusplus >= 201103L
00111   template<typename _Tp, typename _Alloc>
00112     typename list<_Tp, _Alloc>::iterator
00113     list<_Tp, _Alloc>::
00114     insert(const_iterator __position, size_type __n, const value_type& __x)
00115     {
00116       if (__n)
00117     {
00118       list __tmp(__n, __x, get_allocator());
00119       iterator __it = __tmp.begin();
00120       splice(__position, __tmp);
00121       return __it;
00122     }
00123       return __position._M_const_cast();
00124     }
00125 
00126   template<typename _Tp, typename _Alloc>
00127     template<typename _InputIterator, typename>
00128       typename list<_Tp, _Alloc>::iterator
00129       list<_Tp, _Alloc>::
00130       insert(const_iterator __position, _InputIterator __first,
00131          _InputIterator __last)
00132       {
00133     list __tmp(__first, __last, get_allocator());
00134     if (!__tmp.empty())
00135       {
00136         iterator __it = __tmp.begin();
00137         splice(__position, __tmp);
00138         return __it;
00139       }
00140     return __position._M_const_cast();
00141       }
00142 #endif
00143 
00144   template<typename _Tp, typename _Alloc>
00145     typename list<_Tp, _Alloc>::iterator
00146     list<_Tp, _Alloc>::
00147 #if __cplusplus >= 201103L
00148     erase(const_iterator __position) noexcept
00149 #else
00150     erase(iterator __position)
00151 #endif
00152     {
00153       iterator __ret = iterator(__position._M_node->_M_next);
00154       _M_erase(__position._M_const_cast());
00155       return __ret;
00156     }
00157 
00158 #if __cplusplus >= 201103L
00159   template<typename _Tp, typename _Alloc>
00160     void
00161     list<_Tp, _Alloc>::
00162     _M_default_append(size_type __n)
00163     {
00164       size_type __i = 0;
00165       __try
00166     {
00167       for (; __i < __n; ++__i)
00168         emplace_back();
00169     }
00170       __catch(...)
00171     {
00172       for (; __i; --__i)
00173         pop_back();
00174       __throw_exception_again;
00175     }
00176     }
00177 
00178   template<typename _Tp, typename _Alloc>
00179     void
00180     list<_Tp, _Alloc>::
00181     resize(size_type __new_size)
00182     {
00183       iterator __i = begin();
00184       size_type __len = 0;
00185       for (; __i != end() && __len < __new_size; ++__i, ++__len)
00186         ;
00187       if (__len == __new_size)
00188         erase(__i, end());
00189       else                          // __i == end()
00190     _M_default_append(__new_size - __len);
00191     }
00192 
00193   template<typename _Tp, typename _Alloc>
00194     void
00195     list<_Tp, _Alloc>::
00196     resize(size_type __new_size, const value_type& __x)
00197     {
00198       iterator __i = begin();
00199       size_type __len = 0;
00200       for (; __i != end() && __len < __new_size; ++__i, ++__len)
00201         ;
00202       if (__len == __new_size)
00203         erase(__i, end());
00204       else                          // __i == end()
00205         insert(end(), __new_size - __len, __x);
00206     }
00207 #else
00208   template<typename _Tp, typename _Alloc>
00209     void
00210     list<_Tp, _Alloc>::
00211     resize(size_type __new_size, value_type __x)
00212     {
00213       iterator __i = begin();
00214       size_type __len = 0;
00215       for (; __i != end() && __len < __new_size; ++__i, ++__len)
00216         ;
00217       if (__len == __new_size)
00218         erase(__i, end());
00219       else                          // __i == end()
00220         insert(end(), __new_size - __len, __x);
00221     }
00222 #endif
00223 
00224   template<typename _Tp, typename _Alloc>
00225     list<_Tp, _Alloc>&
00226     list<_Tp, _Alloc>::
00227     operator=(const list& __x)
00228     {
00229       if (this != &__x)
00230     {
00231       iterator __first1 = begin();
00232       iterator __last1 = end();
00233       const_iterator __first2 = __x.begin();
00234       const_iterator __last2 = __x.end();
00235       for (; __first1 != __last1 && __first2 != __last2;
00236            ++__first1, ++__first2)
00237         *__first1 = *__first2;
00238       if (__first2 == __last2)
00239         erase(__first1, __last1);
00240       else
00241         insert(__last1, __first2, __last2);
00242     }
00243       return *this;
00244     }
00245 
00246   template<typename _Tp, typename _Alloc>
00247     void
00248     list<_Tp, _Alloc>::
00249     _M_fill_assign(size_type __n, const value_type& __val)
00250     {
00251       iterator __i = begin();
00252       for (; __i != end() && __n > 0; ++__i, --__n)
00253         *__i = __val;
00254       if (__n > 0)
00255         insert(end(), __n, __val);
00256       else
00257         erase(__i, end());
00258     }
00259 
00260   template<typename _Tp, typename _Alloc>
00261     template <typename _InputIterator>
00262       void
00263       list<_Tp, _Alloc>::
00264       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
00265              __false_type)
00266       {
00267         iterator __first1 = begin();
00268         iterator __last1 = end();
00269         for (; __first1 != __last1 && __first2 != __last2;
00270          ++__first1, ++__first2)
00271           *__first1 = *__first2;
00272         if (__first2 == __last2)
00273           erase(__first1, __last1);
00274         else
00275           insert(__last1, __first2, __last2);
00276       }
00277 
00278   template<typename _Tp, typename _Alloc>
00279     void
00280     list<_Tp, _Alloc>::
00281     remove(const value_type& __value)
00282     {
00283       iterator __first = begin();
00284       iterator __last = end();
00285       iterator __extra = __last;
00286       while (__first != __last)
00287     {
00288       iterator __next = __first;
00289       ++__next;
00290       if (*__first == __value)
00291         {
00292           // _GLIBCXX_RESOLVE_LIB_DEFECTS
00293           // 526. Is it undefined if a function in the standard changes
00294           // in parameters?
00295           if (std::__addressof(*__first) != std::__addressof(__value))
00296         _M_erase(__first);
00297           else
00298         __extra = __first;
00299         }
00300       __first = __next;
00301     }
00302       if (__extra != __last)
00303     _M_erase(__extra);
00304     }
00305 
00306   template<typename _Tp, typename _Alloc>
00307     void
00308     list<_Tp, _Alloc>::
00309     unique()
00310     {
00311       iterator __first = begin();
00312       iterator __last = end();
00313       if (__first == __last)
00314     return;
00315       iterator __next = __first;
00316       while (++__next != __last)
00317     {
00318       if (*__first == *__next)
00319         _M_erase(__next);
00320       else
00321         __first = __next;
00322       __next = __first;
00323     }
00324     }
00325 
00326   template<typename _Tp, typename _Alloc>
00327     void
00328     list<_Tp, _Alloc>::
00329 #if __cplusplus >= 201103L
00330     merge(list&& __x)
00331 #else
00332     merge(list& __x)
00333 #endif
00334     {
00335       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00336       // 300. list::merge() specification incomplete
00337       if (this != &__x)
00338     {
00339       _M_check_equal_allocators(__x); 
00340 
00341       iterator __first1 = begin();
00342       iterator __last1 = end();
00343       iterator __first2 = __x.begin();
00344       iterator __last2 = __x.end();
00345       while (__first1 != __last1 && __first2 != __last2)
00346         if (*__first2 < *__first1)
00347           {
00348         iterator __next = __first2;
00349         _M_transfer(__first1, __first2, ++__next);
00350         __first2 = __next;
00351           }
00352         else
00353           ++__first1;
00354       if (__first2 != __last2)
00355         _M_transfer(__last1, __first2, __last2);
00356     }
00357     }
00358 
00359   template<typename _Tp, typename _Alloc>
00360     template <typename _StrictWeakOrdering>
00361       void
00362       list<_Tp, _Alloc>::
00363 #if __cplusplus >= 201103L
00364       merge(list&& __x, _StrictWeakOrdering __comp)
00365 #else
00366       merge(list& __x, _StrictWeakOrdering __comp)
00367 #endif
00368       {
00369     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00370     // 300. list::merge() specification incomplete
00371     if (this != &__x)
00372       {
00373         _M_check_equal_allocators(__x);
00374 
00375         iterator __first1 = begin();
00376         iterator __last1 = end();
00377         iterator __first2 = __x.begin();
00378         iterator __last2 = __x.end();
00379         while (__first1 != __last1 && __first2 != __last2)
00380           if (__comp(*__first2, *__first1))
00381         {
00382           iterator __next = __first2;
00383           _M_transfer(__first1, __first2, ++__next);
00384           __first2 = __next;
00385         }
00386           else
00387         ++__first1;
00388         if (__first2 != __last2)
00389           _M_transfer(__last1, __first2, __last2);
00390       }
00391       }
00392 
00393   template<typename _Tp, typename _Alloc>
00394     void
00395     list<_Tp, _Alloc>::
00396     sort()
00397     {
00398       // Do nothing if the list has length 0 or 1.
00399       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00400       && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00401       {
00402         list __carry;
00403         list __tmp[64];
00404         list * __fill = &__tmp[0];
00405         list * __counter;
00406 
00407         do
00408       {
00409         __carry.splice(__carry.begin(), *this, begin());
00410 
00411         for(__counter = &__tmp[0];
00412         __counter != __fill && !__counter->empty();
00413         ++__counter)
00414           {
00415         __counter->merge(__carry);
00416         __carry.swap(*__counter);
00417           }
00418         __carry.swap(*__counter);
00419         if (__counter == __fill)
00420           ++__fill;
00421       }
00422     while ( !empty() );
00423 
00424         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
00425           __counter->merge(*(__counter - 1));
00426         swap( *(__fill - 1) );
00427       }
00428     }
00429 
00430   template<typename _Tp, typename _Alloc>
00431     template <typename _Predicate>
00432       void
00433       list<_Tp, _Alloc>::
00434       remove_if(_Predicate __pred)
00435       {
00436         iterator __first = begin();
00437         iterator __last = end();
00438         while (__first != __last)
00439       {
00440         iterator __next = __first;
00441         ++__next;
00442         if (__pred(*__first))
00443           _M_erase(__first);
00444         __first = __next;
00445       }
00446       }
00447 
00448   template<typename _Tp, typename _Alloc>
00449     template <typename _BinaryPredicate>
00450       void
00451       list<_Tp, _Alloc>::
00452       unique(_BinaryPredicate __binary_pred)
00453       {
00454         iterator __first = begin();
00455         iterator __last = end();
00456         if (__first == __last)
00457       return;
00458         iterator __next = __first;
00459         while (++__next != __last)
00460       {
00461         if (__binary_pred(*__first, *__next))
00462           _M_erase(__next);
00463         else
00464           __first = __next;
00465         __next = __first;
00466       }
00467       }
00468 
00469   template<typename _Tp, typename _Alloc>
00470     template <typename _StrictWeakOrdering>
00471       void
00472       list<_Tp, _Alloc>::
00473       sort(_StrictWeakOrdering __comp)
00474       {
00475     // Do nothing if the list has length 0 or 1.
00476     if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
00477         && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
00478       {
00479         list __carry;
00480         list __tmp[64];
00481         list * __fill = &__tmp[0];
00482         list * __counter;
00483 
00484         do
00485           {
00486         __carry.splice(__carry.begin(), *this, begin());
00487 
00488         for(__counter = &__tmp[0];
00489             __counter != __fill && !__counter->empty();
00490             ++__counter)
00491           {
00492             __counter->merge(__carry, __comp);
00493             __carry.swap(*__counter);
00494           }
00495         __carry.swap(*__counter);
00496         if (__counter == __fill)
00497           ++__fill;
00498           }
00499         while ( !empty() );
00500 
00501         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
00502           __counter->merge(*(__counter - 1), __comp);
00503         swap(*(__fill - 1));
00504       }
00505       }
00506 
00507 _GLIBCXX_END_NAMESPACE_CONTAINER
00508 } // namespace std
00509 
00510 #endif /* _LIST_TCC */
00511