libstdc++-v3/include/bits/list.tcc

   1 // List implementation (out of line) -*- C++ -*-
   2
   3 // Copyright (C) 2001-2013 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /*
  26  *
  27  * Copyright (c) 1994
  28  * Hewlett-Packard Company
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Hewlett-Packard Company makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  *
  38  *
  39  * Copyright (c) 1996,1997
  40  * Silicon Graphics Computer Systems, Inc.
  41  *
  42  * Permission to use, copy, modify, distribute and sell this software
  43  * and its documentation for any purpose is hereby granted without fee,
  44  * provided that the above copyright notice appear in all copies and
  45  * that both that copyright notice and this permission notice appear
  46  * in supporting documentation.  Silicon Graphics makes no
  47  * representations about the suitability of this software for any
  48  * purpose.  It is provided "as is" without express or implied warranty.
  49  */
  50
  51 /** @file bits/list.tcc
  52  *  This is an internal header file, included by other library headers.
  53  *  Do not attempt to use it directly. @headername{list}
  54  */
  55
  56 #ifndef _LIST_TCC
  57 #define _LIST_TCC 1
  58
  59 namespace std _GLIBCXX_VISIBILITY(default)
  60 {
  61 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  62
  63   template<typename _Tp, typename _Alloc>
  64     void
  65     _List_base<_Tp, _Alloc>::
  66     _M_clear() _GLIBCXX_NOEXCEPT
  67     {
  68       typedef _List_node<_Tp>  _Node;
  69       _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next);
  70       while (__cur != &_M_impl._M_node)
  71         {
  72           _Node* __tmp = __cur;
  73           __cur = static_cast<_Node*>(__cur->_M_next);
  74 #if __cplusplus >= 201103L
  75           _M_get_Node_allocator().destroy(__tmp);
  76 #else
  77           _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data));
  78 #endif
  79           _M_put_node(__tmp);
  80         }
  81     }
  82
  83 #if __cplusplus >= 201103L
  84   template<typename _Tp, typename _Alloc>
  85     template<typename... _Args>
  86       typename list<_Tp, _Alloc>::iterator
  87       list<_Tp, _Alloc>::
  88       emplace(const_iterator __position, _Args&&... __args)
  89       {
  90         _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
  91         __tmp->_M_hook(__position._M_const_cast()._M_node);
  92         return iterator(__tmp);
  93       }
  94 #endif
  95
  96   template<typename _Tp, typename _Alloc>
  97     typename list<_Tp, _Alloc>::iterator
  98     list<_Tp, _Alloc>::
  99 #if __cplusplus >= 201103L
 100     insert(const_iterator __position, const value_type& __x)
 101 #else
 102     insert(iterator __position, const value_type& __x)
 103 #endif
 104     {
 105       _Node* __tmp = _M_create_node(__x);
 106       __tmp->_M_hook(__position._M_const_cast()._M_node);
 107       return iterator(__tmp);
 108     }
 109
 110 #if __cplusplus >= 201103L
 111   template<typename _Tp, typename _Alloc>
 112     typename list<_Tp, _Alloc>::iterator
 113     list<_Tp, _Alloc>::
 114     insert(const_iterator __position, size_type __n, const value_type& __x)
 115     {
 116       if (__n)
 117         {
 118           list __tmp(__n, __x, get_allocator());
 119           iterator __it = __tmp.begin();
 120           splice(__position, __tmp);
 121           return __it;
 122         }
 123       return __position._M_const_cast();
 124     }
 125
 126   template<typename _Tp, typename _Alloc>
 127     template<typename _InputIterator, typename>
 128       typename list<_Tp, _Alloc>::iterator
 129       list<_Tp, _Alloc>::
 130       insert(const_iterator __position, _InputIterator __first,
 131              _InputIterator __last)
 132       {
 133         list __tmp(__first, __last, get_allocator());
 134         if (!__tmp.empty())
 135           {
 136             iterator __it = __tmp.begin();
 137             splice(__position, __tmp);
 138             return __it;
 139           }
 140         return __position._M_const_cast();
 141       }
 142 #endif
 143
 144   template<typename _Tp, typename _Alloc>
 145     typename list<_Tp, _Alloc>::iterator
 146     list<_Tp, _Alloc>::
 147 #if __cplusplus >= 201103L
 148     erase(const_iterator __position) noexcept
 149 #else
 150     erase(iterator __position)
 151 #endif
 152     {
 153       iterator __ret = iterator(__position._M_node->_M_next);
 154       _M_erase(__position._M_const_cast());
 155       return __ret;
 156     }
 157
 158 #if __cplusplus >= 201103L
 159   template<typename _Tp, typename _Alloc>
 160     void
 161     list<_Tp, _Alloc>::
 162     _M_default_append(size_type __n)
 163     {
 164       size_type __i = 0;
 165       __try
 166         {
 167           for (; __i < __n; ++__i)
 168             emplace_back();
 169         }
 170       __catch(...)
 171         {
 172           for (; __i; --__i)
 173             pop_back();
 174           __throw_exception_again;
 175         }
 176     }
 177
 178   template<typename _Tp, typename _Alloc>
 179     void
 180     list<_Tp, _Alloc>::
 181     resize(size_type __new_size)
 182     {
 183       iterator __i = begin();
 184       size_type __len = 0;
 185       for (; __i != end() && __len < __new_size; ++__i, ++__len)
 186         ;
 187       if (__len == __new_size)
 188         erase(__i, end());
 189       else                          // __i == end()
 190         _M_default_append(__new_size - __len);
 191     }
 192
 193   template<typename _Tp, typename _Alloc>
 194     void
 195     list<_Tp, _Alloc>::
 196     resize(size_type __new_size, const value_type& __x)
 197     {
 198       iterator __i = begin();
 199       size_type __len = 0;
 200       for (; __i != end() && __len < __new_size; ++__i, ++__len)
 201         ;
 202       if (__len == __new_size)
 203         erase(__i, end());
 204       else                          // __i == end()
 205         insert(end(), __new_size - __len, __x);
 206     }
 207 #else
 208   template<typename _Tp, typename _Alloc>
 209     void
 210     list<_Tp, _Alloc>::
 211     resize(size_type __new_size, value_type __x)
 212     {
 213       iterator __i = begin();
 214       size_type __len = 0;
 215       for (; __i != end() && __len < __new_size; ++__i, ++__len)
 216         ;
 217       if (__len == __new_size)
 218         erase(__i, end());
 219       else                          // __i == end()
 220         insert(end(), __new_size - __len, __x);
 221     }
 222 #endif
 223
 224   template<typename _Tp, typename _Alloc>
 225     list<_Tp, _Alloc>&
 226     list<_Tp, _Alloc>::
 227     operator=(const list& __x)
 228     {
 229       if (this != &__x)
 230         {
 231           iterator __first1 = begin();
 232           iterator __last1 = end();
 233           const_iterator __first2 = __x.begin();
 234           const_iterator __last2 = __x.end();
 235           for (; __first1 != __last1 && __first2 != __last2;
 236                ++__first1, ++__first2)
 237             *__first1 = *__first2;
 238           if (__first2 == __last2)
 239             erase(__first1, __last1);
 240           else
 241             insert(__last1, __first2, __last2);
 242         }
 243       return *this;
 244     }
 245
 246   template<typename _Tp, typename _Alloc>
 247     void
 248     list<_Tp, _Alloc>::
 249     _M_fill_assign(size_type __n, const value_type& __val)
 250     {
 251       iterator __i = begin();
 252       for (; __i != end() && __n > 0; ++__i, --__n)
 253         *__i = __val;
 254       if (__n > 0)
 255         insert(end(), __n, __val);
 256       else
 257         erase(__i, end());
 258     }
 259
 260   template<typename _Tp, typename _Alloc>
 261     template <typename _InputIterator>
 262       void
 263       list<_Tp, _Alloc>::
 264       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
 265                          __false_type)
 266       {
 267         iterator __first1 = begin();
 268         iterator __last1 = end();
 269         for (; __first1 != __last1 && __first2 != __last2;
 270              ++__first1, ++__first2)
 271           *__first1 = *__first2;
 272         if (__first2 == __last2)
 273           erase(__first1, __last1);
 274         else
 275           insert(__last1, __first2, __last2);
 276       }
 277
 278   template<typename _Tp, typename _Alloc>
 279     void
 280     list<_Tp, _Alloc>::
 281     remove(const value_type& __value)
 282     {
 283       iterator __first = begin();
 284       iterator __last = end();
 285       iterator __extra = __last;
 286       while (__first != __last)
 287         {
 288           iterator __next = __first;
 289           ++__next;
 290           if (*__first == __value)
 291             {
 292               // _GLIBCXX_RESOLVE_LIB_DEFECTS
 293               // 526. Is it undefined if a function in the standard changes
 294               // in parameters?
 295               if (std::__addressof(*__first) != std::__addressof(__value))
 296                 _M_erase(__first);
 297               else
 298                 __extra = __first;
 299             }
 300           __first = __next;
 301         }
 302       if (__extra != __last)
 303         _M_erase(__extra);
 304     }
 305
 306   template<typename _Tp, typename _Alloc>
 307     void
 308     list<_Tp, _Alloc>::
 309     unique()
 310     {
 311       iterator __first = begin();
 312       iterator __last = end();
 313       if (__first == __last)
 314         return;
 315       iterator __next = __first;
 316       while (++__next != __last)
 317         {
 318           if (*__first == *__next)
 319             _M_erase(__next);
 320           else
 321             __first = __next;
 322           __next = __first;
 323         }
 324     }
 325
 326   template<typename _Tp, typename _Alloc>
 327     void
 328     list<_Tp, _Alloc>::
 329 #if __cplusplus >= 201103L
 330     merge(list&& __x)
 331 #else
 332     merge(list& __x)
 333 #endif
 334     {
 335       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 336       // 300. list::merge() specification incomplete
 337       if (this != &__x)
 338         {
 339           _M_check_equal_allocators(__x);
 340
 341           iterator __first1 = begin();
 342           iterator __last1 = end();
 343           iterator __first2 = __x.begin();
 344           iterator __last2 = __x.end();
 345           while (__first1 != __last1 && __first2 != __last2)
 346             if (*__first2 < *__first1)
 347               {
 348                 iterator __next = __first2;
 349                 _M_transfer(__first1, __first2, ++__next);
 350                 __first2 = __next;
 351               }
 352             else
 353               ++__first1;
 354           if (__first2 != __last2)
 355             _M_transfer(__last1, __first2, __last2);
 356         }
 357     }
 358
 359   template<typename _Tp, typename _Alloc>
 360     template <typename _StrictWeakOrdering>
 361       void
 362       list<_Tp, _Alloc>::
 363 #if __cplusplus >= 201103L
 364       merge(list&& __x, _StrictWeakOrdering __comp)
 365 #else
 366       merge(list& __x, _StrictWeakOrdering __comp)
 367 #endif
 368       {
 369         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 370         // 300. list::merge() specification incomplete
 371         if (this != &__x)
 372           {
 373             _M_check_equal_allocators(__x);
 374
 375             iterator __first1 = begin();
 376             iterator __last1 = end();
 377             iterator __first2 = __x.begin();
 378             iterator __last2 = __x.end();
 379             while (__first1 != __last1 && __first2 != __last2)
 380               if (__comp(*__first2, *__first1))
 381                 {
 382                   iterator __next = __first2;
 383                   _M_transfer(__first1, __first2, ++__next);
 384                   __first2 = __next;
 385                 }
 386               else
 387                 ++__first1;
 388             if (__first2 != __last2)
 389               _M_transfer(__last1, __first2, __last2);
 390           }
 391       }
 392
 393   template<typename _Tp, typename _Alloc>
 394     void
 395     list<_Tp, _Alloc>::
 396     sort()
 397     {
 398       // Do nothing if the list has length 0 or 1.
 399       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 400           && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 401       {
 402         list __carry;
 403         list __tmp[64];
 404         list * __fill = &__tmp[0];
 405         list * __counter;
 406
 407         do
 408           {
 409             __carry.splice(__carry.begin(), *this, begin());
 410
 411             for(__counter = &__tmp[0];
 412                 __counter != __fill && !__counter->empty();
 413                 ++__counter)
 414               {
 415                 __counter->merge(__carry);
 416                 __carry.swap(*__counter);
 417               }
 418             __carry.swap(*__counter);
 419             if (__counter == __fill)
 420               ++__fill;
 421           }
 422         while ( !empty() );
 423
 424         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
 425           __counter->merge(*(__counter - 1));
 426         swap( *(__fill - 1) );
 427       }
 428     }
 429
 430   template<typename _Tp, typename _Alloc>
 431     template <typename _Predicate>
 432       void
 433       list<_Tp, _Alloc>::
 434       remove_if(_Predicate __pred)
 435       {
 436         iterator __first = begin();
 437         iterator __last = end();
 438         while (__first != __last)
 439           {
 440             iterator __next = __first;
 441             ++__next;
 442             if (__pred(*__first))
 443               _M_erase(__first);
 444             __first = __next;
 445           }
 446       }
 447
 448   template<typename _Tp, typename _Alloc>
 449     template <typename _BinaryPredicate>
 450       void
 451       list<_Tp, _Alloc>::
 452       unique(_BinaryPredicate __binary_pred)
 453       {
 454         iterator __first = begin();
 455         iterator __last = end();
 456         if (__first == __last)
 457           return;
 458         iterator __next = __first;
 459         while (++__next != __last)
 460           {
 461             if (__binary_pred(*__first, *__next))
 462               _M_erase(__next);
 463             else
 464               __first = __next;
 465             __next = __first;
 466           }
 467       }
 468
 469   template<typename _Tp, typename _Alloc>
 470     template <typename _StrictWeakOrdering>
 471       void
 472       list<_Tp, _Alloc>::
 473       sort(_StrictWeakOrdering __comp)
 474       {
 475         // Do nothing if the list has length 0 or 1.
 476         if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 477             && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
 478           {
 479             list __carry;
 480             list __tmp[64];
 481             list * __fill = &__tmp[0];
 482             list * __counter;
 483
 484             do
 485               {
 486                 __carry.splice(__carry.begin(), *this, begin());
 487
 488                 for(__counter = &__tmp[0];
 489                     __counter != __fill && !__counter->empty();
 490                     ++__counter)
 491                   {
 492                     __counter->merge(__carry, __comp);
 493                     __carry.swap(*__counter);
 494                   }
 495                 __carry.swap(*__counter);
 496                 if (__counter == __fill)
 497                   ++__fill;
 498               }
 499             while ( !empty() );
 500
 501             for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
 502               __counter->merge(*(__counter - 1), __comp);
 503             swap(*(__fill - 1));
 504           }
 505       }
 506
 507 _GLIBCXX_END_NAMESPACE_CONTAINER
 508 } // namespace std
 509
 510 #endif /* _LIST_TCC */
 511