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