libstdc++
forward_list.tcc
Go to the documentation of this file.
1 // <forward_list.tcc> -*- C++ -*-
2 
3 // Copyright (C) 2008-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 /** @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  forward_list __to_destroy(get_allocator());
294 
295  auto __prev_it = cbefore_begin();
296  while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
297  if (*__tmp->_M_valptr() == __val)
298  {
299  __to_destroy.splice_after(__to_destroy.cbefore_begin(),
300  *this, __prev_it);
301  _GLIBCXX20_ONLY( __removed++ );
302  }
303  else
304  ++__prev_it;
305 
306  return _GLIBCXX20_ONLY( __removed );
307  }
308 
309  template<typename _Tp, typename _Alloc>
310  template<typename _Pred>
311  auto
313  remove_if(_Pred __pred) -> __remove_return_type
314  {
315  size_type __removed __attribute__((__unused__)) = 0;
316  forward_list __to_destroy(get_allocator());
317 
318  auto __prev_it = cbefore_begin();
319  while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
320  if (__pred(*__tmp->_M_valptr()))
321  {
322  __to_destroy.splice_after(__to_destroy.cbefore_begin(),
323  *this, __prev_it);
324  _GLIBCXX20_ONLY( __removed++ );
325  }
326  else
327  ++__prev_it;
328 
329  return _GLIBCXX20_ONLY( __removed );
330  }
331 
332  template<typename _Tp, typename _Alloc>
333  template<typename _BinPred>
334  auto
335  forward_list<_Tp, _Alloc>::
336  unique(_BinPred __binary_pred) -> __remove_return_type
337  {
338  iterator __first = begin();
339  iterator __last = end();
340  if (__first == __last)
341  return _GLIBCXX20_ONLY(0);
342 
343  forward_list __to_destroy(get_allocator());
344  size_type __removed __attribute__((__unused__)) = 0;
345  iterator __next = __first;
346  while (++__next != __last)
347  {
348  if (__binary_pred(*__first, *__next))
349  {
350  __to_destroy.splice_after(__to_destroy.cbefore_begin(),
351  *this, __first);
352  _GLIBCXX20_ONLY( __removed++ );
353  }
354  else
355  __first = __next;
356  __next = __first;
357  }
358 
359  return _GLIBCXX20_ONLY( __removed );
360  }
361 
362 #undef _GLIBCXX20_ONLY
363 
364  template<typename _Tp, typename _Alloc>
365  template<typename _Comp>
366  void
368  merge(forward_list&& __list, _Comp __comp)
369  {
370  _Node_base* __node = &this->_M_impl._M_head;
371  while (__node->_M_next && __list._M_impl._M_head._M_next)
372  {
373  if (__comp(*static_cast<_Node*>
374  (__list._M_impl._M_head._M_next)->_M_valptr(),
375  *static_cast<_Node*>
376  (__node->_M_next)->_M_valptr()))
377  __node->_M_transfer_after(&__list._M_impl._M_head,
378  __list._M_impl._M_head._M_next);
379  __node = __node->_M_next;
380  }
381 
382  if (__list._M_impl._M_head._M_next)
383  *__node = std::move(__list._M_impl._M_head);
384  }
385 
386  template<typename _Tp, typename _Alloc>
387  bool
389  const forward_list<_Tp, _Alloc>& __ly)
390  {
391  // We don't have size() so we need to walk through both lists
392  // making sure both iterators are valid.
393  auto __ix = __lx.cbegin();
394  auto __iy = __ly.cbegin();
395  while (__ix != __lx.cend() && __iy != __ly.cend())
396  {
397  if (!(*__ix == *__iy))
398  return false;
399  ++__ix;
400  ++__iy;
401  }
402  if (__ix == __lx.cend() && __iy == __ly.cend())
403  return true;
404  else
405  return false;
406  }
407 
408  template<typename _Tp, class _Alloc>
409  template<typename _Comp>
410  void
412  sort(_Comp __comp)
413  {
414  // If `next' is nullptr, return immediately.
415  _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
416  if (!__list)
417  return;
418 
419  unsigned long __insize = 1;
420 
421  while (1)
422  {
423  _Node* __p = __list;
424  __list = nullptr;
425  _Node* __tail = nullptr;
426 
427  // Count number of merges we do in this pass.
428  unsigned long __nmerges = 0;
429 
430  while (__p)
431  {
432  ++__nmerges;
433  // There exists a merge to be done.
434  // Step `insize' places along from p.
435  _Node* __q = __p;
436  unsigned long __psize = 0;
437  for (unsigned long __i = 0; __i < __insize; ++__i)
438  {
439  ++__psize;
440  __q = static_cast<_Node*>(__q->_M_next);
441  if (!__q)
442  break;
443  }
444 
445  // If q hasn't fallen off end, we have two lists to merge.
446  unsigned long __qsize = __insize;
447 
448  // Now we have two lists; merge them.
449  while (__psize > 0 || (__qsize > 0 && __q))
450  {
451  // Decide whether next node of merge comes from p or q.
452  _Node* __e;
453  if (__psize == 0)
454  {
455  // p is empty; e must come from q.
456  __e = __q;
457  __q = static_cast<_Node*>(__q->_M_next);
458  --__qsize;
459  }
460  else if (__qsize == 0 || !__q)
461  {
462  // q is empty; e must come from p.
463  __e = __p;
464  __p = static_cast<_Node*>(__p->_M_next);
465  --__psize;
466  }
467  else if (!__comp(*__q->_M_valptr(), *__p->_M_valptr()))
468  {
469  // First node of q is not lower; e must come from p.
470  __e = __p;
471  __p = static_cast<_Node*>(__p->_M_next);
472  --__psize;
473  }
474  else
475  {
476  // First node of q is lower; e must come from q.
477  __e = __q;
478  __q = static_cast<_Node*>(__q->_M_next);
479  --__qsize;
480  }
481 
482  // Add the next node to the merged list.
483  if (__tail)
484  __tail->_M_next = __e;
485  else
486  __list = __e;
487  __tail = __e;
488  }
489 
490  // Now p has stepped `insize' places along, and q has too.
491  __p = __q;
492  }
493  __tail->_M_next = nullptr;
494 
495  // If we have done only one merge, we're finished.
496  // Allow for nmerges == 0, the empty list case.
497  if (__nmerges <= 1)
498  {
499  this->_M_impl._M_head._M_next = __list;
500  return;
501  }
502 
503  // Otherwise repeat, merging lists twice the size.
504  __insize *= 2;
505  }
506  }
507 
508 _GLIBCXX_END_NAMESPACE_CONTAINER
509 _GLIBCXX_END_NAMESPACE_VERSION
510 } // namespace std
511 
512 #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:104
bool operator==(const sub_match< _BiIter > &__lhs, const sub_match< _BiIter > &__rhs)
Tests the equivalence of two regular expression submatches.
Definition: regex.h:1037
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
void splice_after(const_iterator __pos, forward_list &&__list) noexcept
Insert contents of another forward_list.
const_iterator cbefore_begin() const noexcept
Definition: forward_list.h:764
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.