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