libstdc++
forward_list.tcc
Go to the documentation of this file.
1 // <forward_list.tcc> -*- C++ -*-
2 
3 // Copyright (C) 2008-2020 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 /** @file bits/forward_list.tcc
26  * This is an internal header file, included by other library headers.
27  * Do not attempt to use it directly. @headername{forward_list}
28  */
29 
30 #ifndef _FORWARD_LIST_TCC
31 #define _FORWARD_LIST_TCC 1
32 
33 namespace std _GLIBCXX_VISIBILITY(default)
34 {
35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
36 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
37 
38  template<typename _Tp, typename _Alloc>
39  _Fwd_list_base<_Tp, _Alloc>::
40  _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a)
41  : _M_impl(std::move(__a))
42  {
43  if (__lst._M_get_Node_allocator() == _M_get_Node_allocator())
44  this->_M_impl._M_head = std::move(__lst._M_impl._M_head);
45  }
46 
47  template<typename _Tp, typename _Alloc>
48  template<typename... _Args>
49  _Fwd_list_node_base*
50  _Fwd_list_base<_Tp, _Alloc>::
51  _M_insert_after(const_iterator __pos, _Args&&... __args)
52  {
53  _Fwd_list_node_base* __to
54  = const_cast<_Fwd_list_node_base*>(__pos._M_node);
55  _Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
56  __thing->_M_next = __to->_M_next;
57  __to->_M_next = __thing;
58  return __to->_M_next;
59  }
60 
61  template<typename _Tp, typename _Alloc>
62  _Fwd_list_node_base*
63  _Fwd_list_base<_Tp, _Alloc>::
64  _M_erase_after(_Fwd_list_node_base* __pos)
65  {
66  _Node* __curr = static_cast<_Node*>(__pos->_M_next);
67  __pos->_M_next = __curr->_M_next;
68  _Node_alloc_traits::destroy(_M_get_Node_allocator(),
69  __curr->_M_valptr());
70  __curr->~_Node();
71  _M_put_node(__curr);
72  return __pos->_M_next;
73  }
74 
75  template<typename _Tp, typename _Alloc>
76  _Fwd_list_node_base*
77  _Fwd_list_base<_Tp, _Alloc>::
78  _M_erase_after(_Fwd_list_node_base* __pos,
79  _Fwd_list_node_base* __last)
80  {
81  _Node* __curr = static_cast<_Node*>(__pos->_M_next);
82  while (__curr != __last)
83  {
84  _Node* __temp = __curr;
85  __curr = static_cast<_Node*>(__curr->_M_next);
86  _Node_alloc_traits::destroy(_M_get_Node_allocator(),
87  __temp->_M_valptr());
88  __temp->~_Node();
89  _M_put_node(__temp);
90  }
91  __pos->_M_next = __last;
92  return __last;
93  }
94 
95  // Called by the range constructor to implement [23.3.4.2]/9
96  template<typename _Tp, typename _Alloc>
97  template<typename _InputIterator>
98  void
99  forward_list<_Tp, _Alloc>::
100  _M_range_initialize(_InputIterator __first, _InputIterator __last)
101  {
102  _Node_base* __to = &this->_M_impl._M_head;
103  for (; __first != __last; ++__first)
104  {
105  __to->_M_next = this->_M_create_node(*__first);
106  __to = __to->_M_next;
107  }
108  }
109 
110  // Called by forward_list(n,v,a).
111  template<typename _Tp, typename _Alloc>
112  void
113  forward_list<_Tp, _Alloc>::
114  _M_fill_initialize(size_type __n, const value_type& __value)
115  {
116  _Node_base* __to = &this->_M_impl._M_head;
117  for (; __n; --__n)
118  {
119  __to->_M_next = this->_M_create_node(__value);
120  __to = __to->_M_next;
121  }
122  }
123 
124  template<typename _Tp, typename _Alloc>
125  void
126  forward_list<_Tp, _Alloc>::
127  _M_default_initialize(size_type __n)
128  {
129  _Node_base* __to = &this->_M_impl._M_head;
130  for (; __n; --__n)
131  {
132  __to->_M_next = this->_M_create_node();
133  __to = __to->_M_next;
134  }
135  }
136 
137  template<typename _Tp, typename _Alloc>
138  forward_list<_Tp, _Alloc>&
140  operator=(const forward_list& __list)
141  {
142  if (std::__addressof(__list) != this)
143  {
144  if (_Node_alloc_traits::_S_propagate_on_copy_assign())
145  {
146  auto& __this_alloc = this->_M_get_Node_allocator();
147  auto& __that_alloc = __list._M_get_Node_allocator();
148  if (!_Node_alloc_traits::_S_always_equal()
149  && __this_alloc != __that_alloc)
150  {
151  // replacement allocator cannot free existing storage
152  clear();
153  }
154  std::__alloc_on_copy(__this_alloc, __that_alloc);
155  }
156  assign(__list.cbegin(), __list.cend());
157  }
158  return *this;
159  }
160 
161  template<typename _Tp, typename _Alloc>
162  void
164  _M_default_insert_after(const_iterator __pos, size_type __n)
165  {
166  const_iterator __saved_pos = __pos;
167  __try
168  {
169  for (; __n; --__n)
170  __pos = emplace_after(__pos);
171  }
172  __catch(...)
173  {
174  erase_after(__saved_pos, ++__pos);
175  __throw_exception_again;
176  }
177  }
178 
179  template<typename _Tp, typename _Alloc>
180  void
182  resize(size_type __sz)
183  {
184  iterator __k = before_begin();
185 
186  size_type __len = 0;
187  while (__k._M_next() != end() && __len < __sz)
188  {
189  ++__k;
190  ++__len;
191  }
192  if (__len == __sz)
193  erase_after(__k, end());
194  else
195  _M_default_insert_after(__k, __sz - __len);
196  }
197 
198  template<typename _Tp, typename _Alloc>
199  void
201  resize(size_type __sz, const value_type& __val)
202  {
203  iterator __k = before_begin();
204 
205  size_type __len = 0;
206  while (__k._M_next() != end() && __len < __sz)
207  {
208  ++__k;
209  ++__len;
210  }
211  if (__len == __sz)
212  erase_after(__k, end());
213  else
214  insert_after(__k, __sz - __len, __val);
215  }
216 
217  template<typename _Tp, typename _Alloc>
220  _M_splice_after(const_iterator __pos,
221  const_iterator __before, const_iterator __last)
222  {
223  _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
224  _Node_base* __b = const_cast<_Node_base*>(__before._M_node);
225  _Node_base* __end = __b;
226 
227  while (__end && __end->_M_next != __last._M_node)
228  __end = __end->_M_next;
229 
230  if (__b != __end)
231  return iterator(__tmp->_M_transfer_after(__b, __end));
232  else
233  return iterator(__tmp);
234  }
235 
236  template<typename _Tp, typename _Alloc>
237  void
240  const_iterator __i) noexcept
241  {
242  const_iterator __j = __i;
243  ++__j;
244 
245  if (__pos == __i || __pos == __j)
246  return;
247 
248  _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
249  __tmp->_M_transfer_after(const_cast<_Node_base*>(__i._M_node),
250  const_cast<_Node_base*>(__j._M_node));
251  }
252 
253  template<typename _Tp, typename _Alloc>
256  insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
257  {
258  if (__n)
259  {
260  forward_list __tmp(__n, __val, get_allocator());
261  return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
262  }
263  else
264  return iterator(const_cast<_Node_base*>(__pos._M_node));
265  }
266 
267  template<typename _Tp, typename _Alloc>
268  template<typename _InputIterator, typename>
272  _InputIterator __first, _InputIterator __last)
273  {
274  forward_list __tmp(__first, __last, get_allocator());
275  if (!__tmp.empty())
276  return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
277  else
278  return iterator(const_cast<_Node_base*>(__pos._M_node));
279  }
280 
281 #if __cplusplus > 201703L
282 # define _GLIBCXX20_ONLY(__expr) __expr
283 #else
284 # define _GLIBCXX20_ONLY(__expr)
285 #endif
286 
287  template<typename _Tp, typename _Alloc>
288  auto
290  remove(const _Tp& __val) -> __remove_return_type
291  {
292  size_type __removed __attribute__((__unused__)) = 0;
293  _Node_base* __curr = &this->_M_impl._M_head;
294  _Node_base* __extra = nullptr;
295 
296  while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
297  {
298  if (*__tmp->_M_valptr() == __val)
299  {
300  if (__tmp->_M_valptr() != std::__addressof(__val))
301  {
302  this->_M_erase_after(__curr);
303  _GLIBCXX20_ONLY( __removed++ );
304  continue;
305  }
306  else
307  __extra = __curr;
308  }
309  __curr = __curr->_M_next;
310  }
311 
312  if (__extra)
313  {
314  this->_M_erase_after(__extra);
315  _GLIBCXX20_ONLY( __removed++ );
316  }
317  return _GLIBCXX20_ONLY( __removed );
318  }
319 
320  template<typename _Tp, typename _Alloc>
321  template<typename _Pred>
322  auto
324  remove_if(_Pred __pred) -> __remove_return_type
325  {
326  size_type __removed __attribute__((__unused__)) = 0;
327  _Node_base* __curr = &this->_M_impl._M_head;
328  while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
329  {
330  if (__pred(*__tmp->_M_valptr()))
331  {
332  this->_M_erase_after(__curr);
333  _GLIBCXX20_ONLY( __removed++ );
334  }
335  else
336  __curr = __curr->_M_next;
337  }
338  return _GLIBCXX20_ONLY( __removed );
339  }
340 
341  template<typename _Tp, typename _Alloc>
342  template<typename _BinPred>
343  auto
344  forward_list<_Tp, _Alloc>::
345  unique(_BinPred __binary_pred) -> __remove_return_type
346  {
347  iterator __first = begin();
348  iterator __last = end();
349  if (__first == __last)
350  return _GLIBCXX20_ONLY(0);
351  size_type __removed __attribute__((__unused__)) = 0;
352  iterator __next = __first;
353  while (++__next != __last)
354  {
355  if (__binary_pred(*__first, *__next))
356  {
357  erase_after(__first);
358  _GLIBCXX20_ONLY( __removed++ );
359  }
360  else
361  __first = __next;
362  __next = __first;
363  }
364  return _GLIBCXX20_ONLY( __removed );
365  }
366 
367 #undef _GLIBCXX20_ONLY
368 
369  template<typename _Tp, typename _Alloc>
370  template<typename _Comp>
371  void
373  merge(forward_list&& __list, _Comp __comp)
374  {
375  // _GLIBCXX_RESOLVE_LIB_DEFECTS
376  // 3088. forward_list::merge behavior unclear when passed *this
377  if (std::__addressof(__list) == this)
378  return;
379 
380  _Node_base* __node = &this->_M_impl._M_head;
381  while (__node->_M_next && __list._M_impl._M_head._M_next)
382  {
383  if (__comp(*static_cast<_Node*>
384  (__list._M_impl._M_head._M_next)->_M_valptr(),
385  *static_cast<_Node*>
386  (__node->_M_next)->_M_valptr()))
387  __node->_M_transfer_after(&__list._M_impl._M_head,
388  __list._M_impl._M_head._M_next);
389  __node = __node->_M_next;
390  }
391 
392  if (__list._M_impl._M_head._M_next)
393  *__node = std::move(__list._M_impl._M_head);
394  }
395 
396  template<typename _Tp, typename _Alloc>
397  bool
399  const forward_list<_Tp, _Alloc>& __ly)
400  {
401  // We don't have size() so we need to walk through both lists
402  // making sure both iterators are valid.
403  auto __ix = __lx.cbegin();
404  auto __iy = __ly.cbegin();
405  while (__ix != __lx.cend() && __iy != __ly.cend())
406  {
407  if (!(*__ix == *__iy))
408  return false;
409  ++__ix;
410  ++__iy;
411  }
412  if (__ix == __lx.cend() && __iy == __ly.cend())
413  return true;
414  else
415  return false;
416  }
417 
418  template<typename _Tp, class _Alloc>
419  template<typename _Comp>
420  void
422  sort(_Comp __comp)
423  {
424  // If `next' is nullptr, return immediately.
425  _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
426  if (!__list)
427  return;
428 
429  unsigned long __insize = 1;
430 
431  while (1)
432  {
433  _Node* __p = __list;
434  __list = nullptr;
435  _Node* __tail = nullptr;
436 
437  // Count number of merges we do in this pass.
438  unsigned long __nmerges = 0;
439 
440  while (__p)
441  {
442  ++__nmerges;
443  // There exists a merge to be done.
444  // Step `insize' places along from p.
445  _Node* __q = __p;
446  unsigned long __psize = 0;
447  for (unsigned long __i = 0; __i < __insize; ++__i)
448  {
449  ++__psize;
450  __q = static_cast<_Node*>(__q->_M_next);
451  if (!__q)
452  break;
453  }
454 
455  // If q hasn't fallen off end, we have two lists to merge.
456  unsigned long __qsize = __insize;
457 
458  // Now we have two lists; merge them.
459  while (__psize > 0 || (__qsize > 0 && __q))
460  {
461  // Decide whether next node of merge comes from p or q.
462  _Node* __e;
463  if (__psize == 0)
464  {
465  // p is empty; e must come from q.
466  __e = __q;
467  __q = static_cast<_Node*>(__q->_M_next);
468  --__qsize;
469  }
470  else if (__qsize == 0 || !__q)
471  {
472  // q is empty; e must come from p.
473  __e = __p;
474  __p = static_cast<_Node*>(__p->_M_next);
475  --__psize;
476  }
477  else if (!__comp(*__q->_M_valptr(), *__p->_M_valptr()))
478  {
479  // First node of q is not lower; e must come from p.
480  __e = __p;
481  __p = static_cast<_Node*>(__p->_M_next);
482  --__psize;
483  }
484  else
485  {
486  // First node of q is lower; e must come from q.
487  __e = __q;
488  __q = static_cast<_Node*>(__q->_M_next);
489  --__qsize;
490  }
491 
492  // Add the next node to the merged list.
493  if (__tail)
494  __tail->_M_next = __e;
495  else
496  __list = __e;
497  __tail = __e;
498  }
499 
500  // Now p has stepped `insize' places along, and q has too.
501  __p = __q;
502  }
503  __tail->_M_next = nullptr;
504 
505  // If we have done only one merge, we're finished.
506  // Allow for nmerges == 0, the empty list case.
507  if (__nmerges <= 1)
508  {
509  this->_M_impl._M_head._M_next = __list;
510  return;
511  }
512 
513  // Otherwise repeat, merging lists twice the size.
514  __insize *= 2;
515  }
516  }
517 
518 _GLIBCXX_END_NAMESPACE_CONTAINER
519 _GLIBCXX_END_NAMESPACE_VERSION
520 } // namespace std
521 
522 #endif /* _FORWARD_LIST_TCC */
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:49
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
bool operator==(const sub_match< _BiIter > &__lhs, const sub_match< _BiIter > &__rhs)
Tests the equivalence of two regular expression submatches.
Definition: regex.h:1035
ISO C++ entities toplevel namespace is std.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list.
A helper basic node class for forward_list. This is just a linked list with nothing inside it....
Definition: forward_list.h:55
A helper node class for forward_list. This is just a linked list with uninitialized storage for a dat...
Definition: forward_list.h:115
A forward_list::iterator.
Definition: forward_list.h:136
A forward_list::const_iterator.
Definition: forward_list.h:211
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition: forward_list.h:424
iterator before_begin() noexcept
Definition: forward_list.h:702
iterator end() noexcept
Definition: forward_list.h:737
const_iterator cend() const noexcept
Definition: forward_list.h:773
bool empty() const noexcept
Definition: forward_list.h:781
const_iterator cbegin() const noexcept
Definition: forward_list.h:755
Common iterator class.