libstdc++
forward_list.tcc
Go to the documentation of this file.
1 // <forward_list.tcc> -*- C++ -*-
2 
3 // Copyright (C) 2008-2019 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>&
139  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
181  forward_list<_Tp, _Alloc>::
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
238  forward_list<_Tp, _Alloc>::
239  splice_after(const_iterator __pos, forward_list&&,
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
372  forward_list<_Tp, _Alloc>::
373  merge(forward_list&& __list, _Comp __comp)
374  {
375  _Node_base* __node = &this->_M_impl._M_head;
376  while (__node->_M_next && __list._M_impl._M_head._M_next)
377  {
378  if (__comp(*static_cast<_Node*>
379  (__list._M_impl._M_head._M_next)->_M_valptr(),
380  *static_cast<_Node*>
381  (__node->_M_next)->_M_valptr()))
382  __node->_M_transfer_after(&__list._M_impl._M_head,
383  __list._M_impl._M_head._M_next);
384  __node = __node->_M_next;
385  }
386 
387  if (__list._M_impl._M_head._M_next)
388  *__node = std::move(__list._M_impl._M_head);
389  }
390 
391  template<typename _Tp, typename _Alloc>
392  bool
393  operator==(const forward_list<_Tp, _Alloc>& __lx,
394  const forward_list<_Tp, _Alloc>& __ly)
395  {
396  // We don't have size() so we need to walk through both lists
397  // making sure both iterators are valid.
398  auto __ix = __lx.cbegin();
399  auto __iy = __ly.cbegin();
400  while (__ix != __lx.cend() && __iy != __ly.cend())
401  {
402  if (!(*__ix == *__iy))
403  return false;
404  ++__ix;
405  ++__iy;
406  }
407  if (__ix == __lx.cend() && __iy == __ly.cend())
408  return true;
409  else
410  return false;
411  }
412 
413  template<typename _Tp, class _Alloc>
414  template<typename _Comp>
415  void
416  forward_list<_Tp, _Alloc>::
417  sort(_Comp __comp)
418  {
419  // If `next' is nullptr, return immediately.
420  _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
421  if (!__list)
422  return;
423 
424  unsigned long __insize = 1;
425 
426  while (1)
427  {
428  _Node* __p = __list;
429  __list = nullptr;
430  _Node* __tail = nullptr;
431 
432  // Count number of merges we do in this pass.
433  unsigned long __nmerges = 0;
434 
435  while (__p)
436  {
437  ++__nmerges;
438  // There exists a merge to be done.
439  // Step `insize' places along from p.
440  _Node* __q = __p;
441  unsigned long __psize = 0;
442  for (unsigned long __i = 0; __i < __insize; ++__i)
443  {
444  ++__psize;
445  __q = static_cast<_Node*>(__q->_M_next);
446  if (!__q)
447  break;
448  }
449 
450  // If q hasn't fallen off end, we have two lists to merge.
451  unsigned long __qsize = __insize;
452 
453  // Now we have two lists; merge them.
454  while (__psize > 0 || (__qsize > 0 && __q))
455  {
456  // Decide whether next node of merge comes from p or q.
457  _Node* __e;
458  if (__psize == 0)
459  {
460  // p is empty; e must come from q.
461  __e = __q;
462  __q = static_cast<_Node*>(__q->_M_next);
463  --__qsize;
464  }
465  else if (__qsize == 0 || !__q)
466  {
467  // q is empty; e must come from p.
468  __e = __p;
469  __p = static_cast<_Node*>(__p->_M_next);
470  --__psize;
471  }
472  else if (!__comp(*__q->_M_valptr(), *__p->_M_valptr()))
473  {
474  // First node of q is not lower; e must come from p.
475  __e = __p;
476  __p = static_cast<_Node*>(__p->_M_next);
477  --__psize;
478  }
479  else
480  {
481  // First node of q is lower; e must come from q.
482  __e = __q;
483  __q = static_cast<_Node*>(__q->_M_next);
484  --__qsize;
485  }
486 
487  // Add the next node to the merged list.
488  if (__tail)
489  __tail->_M_next = __e;
490  else
491  __list = __e;
492  __tail = __e;
493  }
494 
495  // Now p has stepped `insize' places along, and q has too.
496  __p = __q;
497  }
498  __tail->_M_next = nullptr;
499 
500  // If we have done only one merge, we're finished.
501  // Allow for nmerges == 0, the empty list case.
502  if (__nmerges <= 1)
503  {
504  this->_M_impl._M_head._M_next = __list;
505  return;
506  }
507 
508  // Otherwise repeat, merging lists twice the size.
509  __insize *= 2;
510  }
511  }
512 
513 _GLIBCXX_END_NAMESPACE_CONTAINER
514 _GLIBCXX_END_NAMESPACE_VERSION
515 } // namespace std
516 
517 #endif /* _FORWARD_LIST_TCC */
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
ISO C++ entities toplevel namespace is std.
A helper node class for forward_list. This is just a linked list with uninitialized storage for a dat...
Definition: forward_list.h:113
A helper basic node class for forward_list. This is just a linked list with nothing inside it...
Definition: forward_list.h:54
const_iterator cend() const noexcept
Definition: forward_list.h:770
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
_GLIBCXX_NODISCARD bool empty() const noexcept
Definition: forward_list.h:778
iterator before_begin() noexcept
Definition: forward_list.h:699
Common iterator class.
iterator end() noexcept
Definition: forward_list.h:734
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition: forward_list.h:420
A forward_list::const_iterator.
Definition: forward_list.h:209
const_iterator cbegin() const noexcept
Definition: forward_list.h:752
A forward_list::iterator.
Definition: forward_list.h:135