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 
420  const _Finalize_merge __fin(*this, __x, __first2);
421 
422  while (__first1 != __last1 && __first2 != __last2)
423  if (*__first2 < *__first1)
424  {
425  iterator __next = __first2;
426  _M_transfer(__first1, __first2, ++__next);
427  __first2 = __next;
428  }
429  else
430  ++__first1;
431  if (__first2 != __last2)
432  {
433  _M_transfer(__last1, __first2, __last2);
434  __first2 = __last2;
435  }
436  }
437  }
438 
439  template<typename _Tp, typename _Alloc>
440  template <typename _StrictWeakOrdering>
441  void
443 #if __cplusplus >= 201103L
444  merge(list&& __x, _StrictWeakOrdering __comp)
445 #else
446  merge(list& __x, _StrictWeakOrdering __comp)
447 #endif
448  {
449  // _GLIBCXX_RESOLVE_LIB_DEFECTS
450  // 300. list::merge() specification incomplete
451  if (this != std::__addressof(__x))
452  {
453  _M_check_equal_allocators(__x);
454 
455  iterator __first1 = begin();
456  iterator __last1 = end();
457  iterator __first2 = __x.begin();
458  iterator __last2 = __x.end();
459 
460  const _Finalize_merge __fin(*this, __x, __first2);
461 
462  while (__first1 != __last1 && __first2 != __last2)
463  if (__comp(*__first2, *__first1))
464  {
465  iterator __next = __first2;
466  _M_transfer(__first1, __first2, ++__next);
467  __first2 = __next;
468  }
469  else
470  ++__first1;
471  if (__first2 != __last2)
472  {
473  _M_transfer(__last1, __first2, __last2);
474  __first2 = __last2;
475  }
476  }
477  }
478 
479  template<typename _Tp, typename _Alloc>
480  void
482  sort()
483  {
484  // Do nothing if the list has length 0 or 1.
485  if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
486  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
487  {
488  list __carry;
489  list __tmp[64];
490  list * __fill = __tmp;
491  list * __counter;
492  __try
493  {
494  do
495  {
496  __carry.splice(__carry.begin(), *this, begin());
497 
498  for(__counter = __tmp;
499  __counter != __fill && !__counter->empty();
500  ++__counter)
501  {
502  __counter->merge(__carry);
503  __carry.swap(*__counter);
504  }
505  __carry.swap(*__counter);
506  if (__counter == __fill)
507  ++__fill;
508  }
509  while ( !empty() );
510 
511  for (__counter = __tmp + 1; __counter != __fill; ++__counter)
512  __counter->merge(*(__counter - 1));
513  swap( *(__fill - 1) );
514  }
515  __catch(...)
516  {
517  this->splice(this->end(), __carry);
518  for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
519  this->splice(this->end(), __tmp[__i]);
520  __throw_exception_again;
521  }
522  }
523  }
524 
525  template<typename _Tp, typename _Alloc>
526  template <typename _Predicate>
527  typename list<_Tp, _Alloc>::__remove_return_type
529  remove_if(_Predicate __pred)
530  {
531 #if !_GLIBCXX_USE_CXX11_ABI
532  size_type __removed __attribute__((__unused__)) = 0;
533 #endif
534  list __to_destroy(get_allocator());
535  iterator __first = begin();
536  iterator __last = end();
537  while (__first != __last)
538  {
539  iterator __next = __first;
540  ++__next;
541  if (__pred(*__first))
542  {
543  __to_destroy.splice(__to_destroy.begin(), *this, __first);
544 #if !_GLIBCXX_USE_CXX11_ABI
545  _GLIBCXX20_ONLY( __removed++ );
546 #endif
547  }
548  __first = __next;
549  }
550 
551 #if !_GLIBCXX_USE_CXX11_ABI
552  return _GLIBCXX20_ONLY( __removed );
553 #else
554  return _GLIBCXX20_ONLY( __to_destroy.size() );
555 #endif
556  }
557 
558  template<typename _Tp, typename _Alloc>
559  template <typename _BinaryPredicate>
560  typename list<_Tp, _Alloc>::__remove_return_type
562  unique(_BinaryPredicate __binary_pred)
563  {
564  iterator __first = begin();
565  iterator __last = end();
566  if (__first == __last)
567  return _GLIBCXX20_ONLY(0);
568 #if !_GLIBCXX_USE_CXX11_ABI
569  size_type __removed __attribute__((__unused__)) = 0;
570 #endif
571  list __to_destroy(get_allocator());
572  iterator __next = __first;
573  while (++__next != __last)
574  {
575  if (__binary_pred(*__first, *__next))
576  {
577  __to_destroy.splice(__to_destroy.begin(), *this, __next);
578 #if !_GLIBCXX_USE_CXX11_ABI
579  _GLIBCXX20_ONLY( __removed++ );
580 #endif
581  }
582  else
583  __first = __next;
584  __next = __first;
585  }
586 
587 #if !_GLIBCXX_USE_CXX11_ABI
588  return _GLIBCXX20_ONLY( __removed );
589 #else
590  return _GLIBCXX20_ONLY( __to_destroy.size() );
591 #endif
592  }
593 
594 #undef _GLIBCXX20_ONLY
595 
596  template<typename _Tp, typename _Alloc>
597  template <typename _StrictWeakOrdering>
598  void
600  sort(_StrictWeakOrdering __comp)
601  {
602  // Do nothing if the list has length 0 or 1.
603  if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
604  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
605  {
606  list __carry;
607  list __tmp[64];
608  list * __fill = __tmp;
609  list * __counter;
610  __try
611  {
612  do
613  {
614  __carry.splice(__carry.begin(), *this, begin());
615 
616  for(__counter = __tmp;
617  __counter != __fill && !__counter->empty();
618  ++__counter)
619  {
620  __counter->merge(__carry, __comp);
621  __carry.swap(*__counter);
622  }
623  __carry.swap(*__counter);
624  if (__counter == __fill)
625  ++__fill;
626  }
627  while ( !empty() );
628 
629  for (__counter = __tmp + 1; __counter != __fill; ++__counter)
630  __counter->merge(*(__counter - 1), __comp);
631  swap(*(__fill - 1));
632  }
633  __catch(...)
634  {
635  this->splice(this->end(), __carry);
636  for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
637  this->splice(this->end(), __tmp[__i]);
638  __throw_exception_again;
639  }
640  }
641  }
642 
643 _GLIBCXX_END_NAMESPACE_CONTAINER
644 _GLIBCXX_END_NAMESPACE_VERSION
645 } // namespace std
646 
647 #endif /* _LIST_TCC */
648 
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:428
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1239
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1217
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
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
A list::iterator.
Definition: stl_list.h:187
A list::const_iterator.
Definition: stl_list.h:268
Common iterator class.
An actual node in the list.
Definition: stl_list.h:168
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition: stl_list.h:558
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:482
iterator begin() noexcept
Definition: stl_list.h:946
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:1061
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:529
iterator end() noexcept
Definition: stl_list.h:964
void splice(const_iterator __position, list &&__x) noexcept
Insert contents of another list.
Definition: stl_list.h:1519
bool empty() const noexcept
Definition: stl_list.h:1056
void swap(list &__x) noexcept
Swaps data with another list.
Definition: stl_list.h:1479