libstdc++
list.tcc
Go to the documentation of this file.
1 // List implementation (out of line) -*- C++ -*-
2 
3 // Copyright (C) 2001-2021 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_VERSION
62 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
63 
64  template<typename _Tp, typename _Alloc>
65  void
66  _List_base<_Tp, _Alloc>::
67  _M_clear() _GLIBCXX_NOEXCEPT
68  {
69  typedef _List_node<_Tp> _Node;
70  __detail::_List_node_base* __cur = _M_impl._M_node._M_next;
71  while (__cur != &_M_impl._M_node)
72  {
73  _Node* __tmp = static_cast<_Node*>(__cur);
74  __cur = __tmp->_M_next;
75  _Tp* __val = __tmp->_M_valptr();
76 #if __cplusplus >= 201103L
77  _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val);
78 #else
79  _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);
80 #endif
81  _M_put_node(__tmp);
82  }
83  }
84 
85 #if __cplusplus >= 201103L
86  template<typename _Tp, typename _Alloc>
87  template<typename... _Args>
88  typename list<_Tp, _Alloc>::iterator
90  emplace(const_iterator __position, _Args&&... __args)
91  {
92  _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
93  __tmp->_M_hook(__position._M_const_cast()._M_node);
94  this->_M_inc_size(1);
95  return iterator(__tmp);
96  }
97 #endif
98 
99  template<typename _Tp, typename _Alloc>
102 #if __cplusplus >= 201103L
103  insert(const_iterator __position, const value_type& __x)
104 #else
105  insert(iterator __position, const value_type& __x)
106 #endif
107  {
108  _Node* __tmp = _M_create_node(__x);
109  __tmp->_M_hook(__position._M_const_cast()._M_node);
110  this->_M_inc_size(1);
111  return iterator(__tmp);
112  }
113 
114 #if __cplusplus >= 201103L
115  template<typename _Tp, typename _Alloc>
118  insert(const_iterator __position, size_type __n, const value_type& __x)
119  {
120  if (__n)
121  {
122  list __tmp(__n, __x, get_allocator());
123  iterator __it = __tmp.begin();
124  splice(__position, __tmp);
125  return __it;
126  }
127  return __position._M_const_cast();
128  }
129 
130  template<typename _Tp, typename _Alloc>
131  template<typename _InputIterator, typename>
134  insert(const_iterator __position, _InputIterator __first,
135  _InputIterator __last)
136  {
137  list __tmp(__first, __last, get_allocator());
138  if (!__tmp.empty())
139  {
140  iterator __it = __tmp.begin();
141  splice(__position, __tmp);
142  return __it;
143  }
144  return __position._M_const_cast();
145  }
146 #endif
147 
148  template<typename _Tp, typename _Alloc>
151 #if __cplusplus >= 201103L
152  erase(const_iterator __position) noexcept
153 #else
154  erase(iterator __position)
155 #endif
156  {
157  iterator __ret = iterator(__position._M_node->_M_next);
158  _M_erase(__position._M_const_cast());
159  return __ret;
160  }
161 
162  // Return a const_iterator indicating the position to start inserting or
163  // erasing elements (depending whether the list is growing or shrinking),
164  // and set __new_size to the number of new elements that must be appended.
165  // Equivalent to the following, but performed optimally:
166  // if (__new_size < size()) {
167  // __new_size = 0;
168  // return std::next(begin(), __new_size);
169  // } else {
170  // __newsize -= size();
171  // return end();
172  // }
173  template<typename _Tp, typename _Alloc>
176  _M_resize_pos(size_type& __new_size) const
177  {
178  const_iterator __i;
179 #if _GLIBCXX_USE_CXX11_ABI
180  const size_type __len = size();
181  if (__new_size < __len)
182  {
183  if (__new_size <= __len / 2)
184  {
185  __i = begin();
186  std::advance(__i, __new_size);
187  }
188  else
189  {
190  __i = end();
191  ptrdiff_t __num_erase = __len - __new_size;
192  std::advance(__i, -__num_erase);
193  }
194  __new_size = 0;
195  return __i;
196  }
197  else
198  __i = end();
199 #else
200  size_type __len = 0;
201  for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)
202  ;
203 #endif
204  __new_size -= __len;
205  return __i;
206  }
207 
208 #if __cplusplus >= 201103L
209  template<typename _Tp, typename _Alloc>
210  void
211  list<_Tp, _Alloc>::
212  _M_default_append(size_type __n)
213  {
214  size_type __i = 0;
215  __try
216  {
217  for (; __i < __n; ++__i)
218  emplace_back();
219  }
220  __catch(...)
221  {
222  for (; __i; --__i)
223  pop_back();
224  __throw_exception_again;
225  }
226  }
227 
228  template<typename _Tp, typename _Alloc>
229  void
231  resize(size_type __new_size)
232  {
233  const_iterator __i = _M_resize_pos(__new_size);
234  if (__new_size)
235  _M_default_append(__new_size);
236  else
237  erase(__i, end());
238  }
239 
240  template<typename _Tp, typename _Alloc>
241  void
243  resize(size_type __new_size, const value_type& __x)
244  {
245  const_iterator __i = _M_resize_pos(__new_size);
246  if (__new_size)
247  insert(end(), __new_size, __x);
248  else
249  erase(__i, end());
250  }
251 #else
252  template<typename _Tp, typename _Alloc>
253  void
255  resize(size_type __new_size, value_type __x)
256  {
257  const_iterator __i = _M_resize_pos(__new_size);
258  if (__new_size)
259  insert(end(), __new_size, __x);
260  else
261  erase(__i._M_const_cast(), end());
262  }
263 #endif
264 
265  template<typename _Tp, typename _Alloc>
266  list<_Tp, _Alloc>&
268  operator=(const list& __x)
269  {
270  if (this != std::__addressof(__x))
271  {
272 #if __cplusplus >= 201103L
273  if (_Node_alloc_traits::_S_propagate_on_copy_assign())
274  {
275  auto& __this_alloc = this->_M_get_Node_allocator();
276  auto& __that_alloc = __x._M_get_Node_allocator();
277  if (!_Node_alloc_traits::_S_always_equal()
278  && __this_alloc != __that_alloc)
279  {
280  // replacement allocator cannot free existing storage
281  clear();
282  }
283  std::__alloc_on_copy(__this_alloc, __that_alloc);
284  }
285 #endif
286  _M_assign_dispatch(__x.begin(), __x.end(), __false_type());
287  }
288  return *this;
289  }
290 
291  template<typename _Tp, typename _Alloc>
292  void
294  _M_fill_assign(size_type __n, const value_type& __val)
295  {
296  iterator __i = begin();
297  for (; __i != end() && __n > 0; ++__i, --__n)
298  *__i = __val;
299  if (__n > 0)
300  insert(end(), __n, __val);
301  else
302  erase(__i, end());
303  }
304 
305  template<typename _Tp, typename _Alloc>
306  template <typename _InputIterator>
307  void
308  list<_Tp, _Alloc>::
309  _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
310  __false_type)
311  {
312  iterator __first1 = begin();
313  iterator __last1 = end();
314  for (; __first1 != __last1 && __first2 != __last2;
315  ++__first1, (void)++__first2)
316  *__first1 = *__first2;
317  if (__first2 == __last2)
318  erase(__first1, __last1);
319  else
320  insert(__last1, __first2, __last2);
321  }
322 
323 #if __cplusplus > 201703L
324 # define _GLIBCXX20_ONLY(__expr) __expr
325 #else
326 # define _GLIBCXX20_ONLY(__expr)
327 #endif
328 
329  template<typename _Tp, typename _Alloc>
330  typename list<_Tp, _Alloc>::__remove_return_type
332  remove(const value_type& __value)
333  {
334 #if !_GLIBCXX_USE_CXX11_ABI
335  size_type __removed __attribute__((__unused__)) = 0;
336 #endif
337  list __to_destroy(get_allocator());
338  iterator __first = begin();
339  iterator __last = end();
340  while (__first != __last)
341  {
342  iterator __next = __first;
343  ++__next;
344  if (*__first == __value)
345  {
346  // _GLIBCXX_RESOLVE_LIB_DEFECTS
347  // 526. Is it undefined if a function in the standard changes
348  // in parameters?
349  __to_destroy.splice(__to_destroy.begin(), *this, __first);
350 #if !_GLIBCXX_USE_CXX11_ABI
351  _GLIBCXX20_ONLY( __removed++ );
352 #endif
353  }
354 
355  __first = __next;
356  }
357 
358 #if !_GLIBCXX_USE_CXX11_ABI
359  return _GLIBCXX20_ONLY( __removed );
360 #else
361  return _GLIBCXX20_ONLY( __to_destroy.size() );
362 #endif
363  }
364 
365  template<typename _Tp, typename _Alloc>
366  typename list<_Tp, _Alloc>::__remove_return_type
368  unique()
369  {
370  iterator __first = begin();
371  iterator __last = end();
372  if (__first == __last)
373  return _GLIBCXX20_ONLY( 0 );
374 #if !_GLIBCXX_USE_CXX11_ABI
375  size_type __removed __attribute__((__unused__)) = 0;
376 #endif
377  list __to_destroy(get_allocator());
378  iterator __next = __first;
379  while (++__next != __last)
380  {
381  if (*__first == *__next)
382  {
383  __to_destroy.splice(__to_destroy.begin(), *this, __next);
384 #if !_GLIBCXX_USE_CXX11_ABI
385  _GLIBCXX20_ONLY( __removed++ );
386 #endif
387  }
388  else
389  __first = __next;
390  __next = __first;
391  }
392 
393 #if !_GLIBCXX_USE_CXX11_ABI
394  return _GLIBCXX20_ONLY( __removed );
395 #else
396  return _GLIBCXX20_ONLY( __to_destroy.size() );
397 #endif
398  }
399 
400  template<typename _Tp, typename _Alloc>
401  void
403 #if __cplusplus >= 201103L
404  merge(list&& __x)
405 #else
406  merge(list& __x)
407 #endif
408  {
409  // _GLIBCXX_RESOLVE_LIB_DEFECTS
410  // 300. list::merge() specification incomplete
411  if (this != std::__addressof(__x))
412  {
413  _M_check_equal_allocators(__x);
414 
415  iterator __first1 = begin();
416  iterator __last1 = end();
417  iterator __first2 = __x.begin();
418  iterator __last2 = __x.end();
419  const size_t __orig_size = __x.size();
420  __try {
421  while (__first1 != __last1 && __first2 != __last2)
422  if (*__first2 < *__first1)
423  {
424  iterator __next = __first2;
425  _M_transfer(__first1, __first2, ++__next);
426  __first2 = __next;
427  }
428  else
429  ++__first1;
430  if (__first2 != __last2)
431  _M_transfer(__last1, __first2, __last2);
432 
433  this->_M_inc_size(__x._M_get_size());
434  __x._M_set_size(0);
435  }
436  __catch(...)
437  {
438  const size_t __dist = std::distance(__first2, __last2);
439  this->_M_inc_size(__orig_size - __dist);
440  __x._M_set_size(__dist);
441  __throw_exception_again;
442  }
443  }
444  }
445 
446  template<typename _Tp, typename _Alloc>
447  template <typename _StrictWeakOrdering>
448  void
450 #if __cplusplus >= 201103L
451  merge(list&& __x, _StrictWeakOrdering __comp)
452 #else
453  merge(list& __x, _StrictWeakOrdering __comp)
454 #endif
455  {
456  // _GLIBCXX_RESOLVE_LIB_DEFECTS
457  // 300. list::merge() specification incomplete
458  if (this != std::__addressof(__x))
459  {
460  _M_check_equal_allocators(__x);
461 
462  iterator __first1 = begin();
463  iterator __last1 = end();
464  iterator __first2 = __x.begin();
465  iterator __last2 = __x.end();
466  const size_t __orig_size = __x.size();
467  __try
468  {
469  while (__first1 != __last1 && __first2 != __last2)
470  if (__comp(*__first2, *__first1))
471  {
472  iterator __next = __first2;
473  _M_transfer(__first1, __first2, ++__next);
474  __first2 = __next;
475  }
476  else
477  ++__first1;
478  if (__first2 != __last2)
479  _M_transfer(__last1, __first2, __last2);
480 
481  this->_M_inc_size(__x._M_get_size());
482  __x._M_set_size(0);
483  }
484  __catch(...)
485  {
486  const size_t __dist = std::distance(__first2, __last2);
487  this->_M_inc_size(__orig_size - __dist);
488  __x._M_set_size(__dist);
489  __throw_exception_again;
490  }
491  }
492  }
493 
494  template<typename _Tp, typename _Alloc>
495  void
497  sort()
498  {
499  // Do nothing if the list has length 0 or 1.
500  if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
501  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
502  {
503  list __carry;
504  list __tmp[64];
505  list * __fill = __tmp;
506  list * __counter;
507  __try
508  {
509  do
510  {
511  __carry.splice(__carry.begin(), *this, begin());
512 
513  for(__counter = __tmp;
514  __counter != __fill && !__counter->empty();
515  ++__counter)
516  {
517  __counter->merge(__carry);
518  __carry.swap(*__counter);
519  }
520  __carry.swap(*__counter);
521  if (__counter == __fill)
522  ++__fill;
523  }
524  while ( !empty() );
525 
526  for (__counter = __tmp + 1; __counter != __fill; ++__counter)
527  __counter->merge(*(__counter - 1));
528  swap( *(__fill - 1) );
529  }
530  __catch(...)
531  {
532  this->splice(this->end(), __carry);
533  for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
534  this->splice(this->end(), __tmp[__i]);
535  __throw_exception_again;
536  }
537  }
538  }
539 
540  template<typename _Tp, typename _Alloc>
541  template <typename _Predicate>
542  typename list<_Tp, _Alloc>::__remove_return_type
544  remove_if(_Predicate __pred)
545  {
546 #if !_GLIBCXX_USE_CXX11_ABI
547  size_type __removed __attribute__((__unused__)) = 0;
548 #endif
549  list __to_destroy(get_allocator());
550  iterator __first = begin();
551  iterator __last = end();
552  while (__first != __last)
553  {
554  iterator __next = __first;
555  ++__next;
556  if (__pred(*__first))
557  {
558  __to_destroy.splice(__to_destroy.begin(), *this, __first);
559 #if !_GLIBCXX_USE_CXX11_ABI
560  _GLIBCXX20_ONLY( __removed++ );
561 #endif
562  }
563  __first = __next;
564  }
565 
566 #if !_GLIBCXX_USE_CXX11_ABI
567  return _GLIBCXX20_ONLY( __removed );
568 #else
569  return _GLIBCXX20_ONLY( __to_destroy.size() );
570 #endif
571  }
572 
573  template<typename _Tp, typename _Alloc>
574  template <typename _BinaryPredicate>
575  typename list<_Tp, _Alloc>::__remove_return_type
577  unique(_BinaryPredicate __binary_pred)
578  {
579  iterator __first = begin();
580  iterator __last = end();
581  if (__first == __last)
582  return _GLIBCXX20_ONLY(0);
583 #if !_GLIBCXX_USE_CXX11_ABI
584  size_type __removed __attribute__((__unused__)) = 0;
585 #endif
586  list __to_destroy(get_allocator());
587  iterator __next = __first;
588  while (++__next != __last)
589  {
590  if (__binary_pred(*__first, *__next))
591  {
592  __to_destroy.splice(__to_destroy.begin(), *this, __next);
593 #if !_GLIBCXX_USE_CXX11_ABI
594  _GLIBCXX20_ONLY( __removed++ );
595 #endif
596  }
597  else
598  __first = __next;
599  __next = __first;
600  }
601 
602 #if !_GLIBCXX_USE_CXX11_ABI
603  return _GLIBCXX20_ONLY( __removed );
604 #else
605  return _GLIBCXX20_ONLY( __to_destroy.size() );
606 #endif
607  }
608 
609 #undef _GLIBCXX20_ONLY
610 
611  template<typename _Tp, typename _Alloc>
612  template <typename _StrictWeakOrdering>
613  void
615  sort(_StrictWeakOrdering __comp)
616  {
617  // Do nothing if the list has length 0 or 1.
618  if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
619  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
620  {
621  list __carry;
622  list __tmp[64];
623  list * __fill = __tmp;
624  list * __counter;
625  __try
626  {
627  do
628  {
629  __carry.splice(__carry.begin(), *this, begin());
630 
631  for(__counter = __tmp;
632  __counter != __fill && !__counter->empty();
633  ++__counter)
634  {
635  __counter->merge(__carry, __comp);
636  __carry.swap(*__counter);
637  }
638  __carry.swap(*__counter);
639  if (__counter == __fill)
640  ++__fill;
641  }
642  while ( !empty() );
643 
644  for (__counter = __tmp + 1; __counter != __fill; ++__counter)
645  __counter->merge(*(__counter - 1), __comp);
646  swap(*(__fill - 1));
647  }
648  __catch(...)
649  {
650  this->splice(this->end(), __carry);
651  for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
652  this->splice(this->end(), __tmp[__i]);
653  __throw_exception_again;
654  }
655  }
656  }
657 
658 _GLIBCXX_END_NAMESPACE_CONTAINER
659 _GLIBCXX_END_NAMESPACE_VERSION
660 } // namespace std
661 
662 #endif /* _LIST_TCC */
663 
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:49
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
Definition: any:422
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1214
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1234
ISO C++ entities toplevel namespace is std.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:263
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:245
A list::iterator.
Definition: stl_list.h:186
A list::const_iterator.
Definition: stl_list.h:267
Common iterator class.
An actual node in the list.
Definition: stl_list.h:167
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition: stl_list.h:557
void resize(size_type __new_size)
Resizes the list to the specified number of elements.
Definition: list.tcc:231
iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into list before specified iterator.
Definition: list.tcc:103
void sort()
Sort the elements.
Definition: list.tcc:497
iterator begin() noexcept
Definition: stl_list.h:945
iterator emplace(const_iterator __position, _Args &&... __args)
Constructs object in list before specified iterator.
Definition: list.tcc:90
list & operator=(const list &__x)
List assignment operator.
Definition: list.tcc:268
__remove_return_type unique()
Remove consecutive duplicate elements.
Definition: list.tcc:368
size_type size() const noexcept
Definition: stl_list.h:1060
void merge(list &&__x)
Merge sorted lists.
Definition: list.tcc:404
__remove_return_type remove(const _Tp &__value)
Remove all elements equal to value.
Definition: list.tcc:332
__remove_return_type remove_if(_Predicate)
Remove all elements satisfying a predicate.
Definition: list.tcc:544
iterator end() noexcept
Definition: stl_list.h:963
void splice(const_iterator __position, list &&__x) noexcept
Insert contents of another list.
Definition: stl_list.h:1518
bool empty() const noexcept
Definition: stl_list.h:1055
void swap(list &__x) noexcept
Swaps data with another list.
Definition: stl_list.h:1478