libstdc++
list.tcc
Go to the documentation of this file.
1 // List implementation (out of line) -*- C++ -*-
2 
3 // Copyright (C) 2001-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 /*
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_CONTAINER
62 
63  template<typename _Tp, typename _Alloc>
64  void
65  _List_base<_Tp, _Alloc>::
66  _M_clear() _GLIBCXX_NOEXCEPT
67  {
68  typedef _List_node<_Tp> _Node;
69  __detail::_List_node_base* __cur = _M_impl._M_node._M_next;
70  while (__cur != &_M_impl._M_node)
71  {
72  _Node* __tmp = static_cast<_Node*>(__cur);
73  __cur = __tmp->_M_next;
74  _Tp* __val = __tmp->_M_valptr();
75 #if __cplusplus >= 201103L
76  _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val);
77 #else
78  _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);
79 #endif
80  _M_put_node(__tmp);
81  }
82  }
83 
84 #if __cplusplus >= 201103L
85  template<typename _Tp, typename _Alloc>
86  template<typename... _Args>
87  typename list<_Tp, _Alloc>::iterator
89  emplace(const_iterator __position, _Args&&... __args)
90  {
91  _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
92  __tmp->_M_hook(__position._M_const_cast()._M_node);
93  this->_M_inc_size(1);
94  return iterator(__tmp);
95  }
96 #endif
97 
98  template<typename _Tp, typename _Alloc>
101 #if __cplusplus >= 201103L
102  insert(const_iterator __position, const value_type& __x)
103 #else
104  insert(iterator __position, const value_type& __x)
105 #endif
106  {
107  _Node* __tmp = _M_create_node(__x);
108  __tmp->_M_hook(__position._M_const_cast()._M_node);
109  this->_M_inc_size(1);
110  return iterator(__tmp);
111  }
112 
113 #if __cplusplus >= 201103L
114  template<typename _Tp, typename _Alloc>
117  insert(const_iterator __position, size_type __n, const value_type& __x)
118  {
119  if (__n)
120  {
121  list __tmp(__n, __x, get_allocator());
122  iterator __it = __tmp.begin();
123  splice(__position, __tmp);
124  return __it;
125  }
126  return __position._M_const_cast();
127  }
128 
129  template<typename _Tp, typename _Alloc>
130  template<typename _InputIterator, typename>
133  insert(const_iterator __position, _InputIterator __first,
134  _InputIterator __last)
135  {
136  list __tmp(__first, __last, get_allocator());
137  if (!__tmp.empty())
138  {
139  iterator __it = __tmp.begin();
140  splice(__position, __tmp);
141  return __it;
142  }
143  return __position._M_const_cast();
144  }
145 #endif
146 
147  template<typename _Tp, typename _Alloc>
150 #if __cplusplus >= 201103L
151  erase(const_iterator __position) noexcept
152 #else
153  erase(iterator __position)
154 #endif
155  {
156  iterator __ret = iterator(__position._M_node->_M_next);
157  _M_erase(__position._M_const_cast());
158  return __ret;
159  }
160 
161  // Return a const_iterator indicating the position to start inserting or
162  // erasing elements (depending whether the list is growing or shrinking),
163  // and set __new_size to the number of new elements that must be appended.
164  // Equivalent to the following, but performed optimally:
165  // if (__new_size < size()) {
166  // __new_size = 0;
167  // return std::next(begin(), __new_size);
168  // } else {
169  // __newsize -= size();
170  // return end();
171  // }
172  template<typename _Tp, typename _Alloc>
175  _M_resize_pos(size_type& __new_size) const
176  {
177  const_iterator __i;
178 #if _GLIBCXX_USE_CXX11_ABI
179  const size_type __len = size();
180  if (__new_size < __len)
181  {
182  if (__new_size <= __len / 2)
183  {
184  __i = begin();
185  std::advance(__i, __new_size);
186  }
187  else
188  {
189  __i = end();
190  ptrdiff_t __num_erase = __len - __new_size;
191  std::advance(__i, -__num_erase);
192  }
193  __new_size = 0;
194  return __i;
195  }
196  else
197  __i = end();
198 #else
199  size_type __len = 0;
200  for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)
201  ;
202 #endif
203  __new_size -= __len;
204  return __i;
205  }
206 
207 #if __cplusplus >= 201103L
208  template<typename _Tp, typename _Alloc>
209  void
211  _M_default_append(size_type __n)
212  {
213  size_type __i = 0;
214  __try
215  {
216  for (; __i < __n; ++__i)
217  emplace_back();
218  }
219  __catch(...)
220  {
221  for (; __i; --__i)
222  pop_back();
223  __throw_exception_again;
224  }
225  }
226 
227  template<typename _Tp, typename _Alloc>
228  void
230  resize(size_type __new_size)
231  {
232  const_iterator __i = _M_resize_pos(__new_size);
233  if (__new_size)
234  _M_default_append(__new_size);
235  else
236  erase(__i, end());
237  }
238 
239  template<typename _Tp, typename _Alloc>
240  void
242  resize(size_type __new_size, const value_type& __x)
243  {
244  const_iterator __i = _M_resize_pos(__new_size);
245  if (__new_size)
246  insert(end(), __new_size, __x);
247  else
248  erase(__i, end());
249  }
250 #else
251  template<typename _Tp, typename _Alloc>
252  void
254  resize(size_type __new_size, value_type __x)
255  {
256  const_iterator __i = _M_resize_pos(__new_size);
257  if (__new_size)
258  insert(end(), __new_size, __x);
259  else
260  erase(__i._M_const_cast(), end());
261  }
262 #endif
263 
264  template<typename _Tp, typename _Alloc>
267  operator=(const list& __x)
268  {
269  if (this != std::__addressof(__x))
270  {
271 #if __cplusplus >= 201103L
272  if (_Node_alloc_traits::_S_propagate_on_copy_assign())
273  {
274  auto& __this_alloc = this->_M_get_Node_allocator();
275  auto& __that_alloc = __x._M_get_Node_allocator();
276  if (!_Node_alloc_traits::_S_always_equal()
277  && __this_alloc != __that_alloc)
278  {
279  // replacement allocator cannot free existing storage
280  clear();
281  }
282  std::__alloc_on_copy(__this_alloc, __that_alloc);
283  }
284 #endif
285  _M_assign_dispatch(__x.begin(), __x.end(), __false_type());
286  }
287  return *this;
288  }
289 
290  template<typename _Tp, typename _Alloc>
291  void
293  _M_fill_assign(size_type __n, const value_type& __val)
294  {
295  iterator __i = begin();
296  for (; __i != end() && __n > 0; ++__i, --__n)
297  *__i = __val;
298  if (__n > 0)
299  insert(end(), __n, __val);
300  else
301  erase(__i, end());
302  }
303 
304  template<typename _Tp, typename _Alloc>
305  template <typename _InputIterator>
306  void
308  _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
309  __false_type)
310  {
311  iterator __first1 = begin();
312  iterator __last1 = end();
313  for (; __first1 != __last1 && __first2 != __last2;
314  ++__first1, ++__first2)
315  *__first1 = *__first2;
316  if (__first2 == __last2)
317  erase(__first1, __last1);
318  else
319  insert(__last1, __first2, __last2);
320  }
321 
322  template<typename _Tp, typename _Alloc>
323  void
325  remove(const value_type& __value)
326  {
327  iterator __first = begin();
328  iterator __last = end();
329  iterator __extra = __last;
330  while (__first != __last)
331  {
332  iterator __next = __first;
333  ++__next;
334  if (*__first == __value)
335  {
336  // _GLIBCXX_RESOLVE_LIB_DEFECTS
337  // 526. Is it undefined if a function in the standard changes
338  // in parameters?
339  if (std::__addressof(*__first) != std::__addressof(__value))
340  _M_erase(__first);
341  else
342  __extra = __first;
343  }
344  __first = __next;
345  }
346  if (__extra != __last)
347  _M_erase(__extra);
348  }
349 
350  template<typename _Tp, typename _Alloc>
351  void
354  {
355  iterator __first = begin();
356  iterator __last = end();
357  if (__first == __last)
358  return;
359  iterator __next = __first;
360  while (++__next != __last)
361  {
362  if (*__first == *__next)
363  _M_erase(__next);
364  else
365  __first = __next;
366  __next = __first;
367  }
368  }
369 
370  template<typename _Tp, typename _Alloc>
371  void
373 #if __cplusplus >= 201103L
374  merge(list&& __x)
375 #else
376  merge(list& __x)
377 #endif
378  {
379  // _GLIBCXX_RESOLVE_LIB_DEFECTS
380  // 300. list::merge() specification incomplete
381  if (this != std::__addressof(__x))
382  {
383  _M_check_equal_allocators(__x);
384 
385  iterator __first1 = begin();
386  iterator __last1 = end();
387  iterator __first2 = __x.begin();
388  iterator __last2 = __x.end();
389  const size_t __orig_size = __x.size();
390  __try {
391  while (__first1 != __last1 && __first2 != __last2)
392  if (*__first2 < *__first1)
393  {
394  iterator __next = __first2;
395  _M_transfer(__first1, __first2, ++__next);
396  __first2 = __next;
397  }
398  else
399  ++__first1;
400  if (__first2 != __last2)
401  _M_transfer(__last1, __first2, __last2);
402 
403  this->_M_inc_size(__x._M_get_size());
404  __x._M_set_size(0);
405  }
406  __catch(...)
407  {
408  const size_t __dist = std::distance(__first2, __last2);
409  this->_M_inc_size(__orig_size - __dist);
410  __x._M_set_size(__dist);
411  __throw_exception_again;
412  }
413  }
414  }
415 
416  template<typename _Tp, typename _Alloc>
417  template <typename _StrictWeakOrdering>
418  void
420 #if __cplusplus >= 201103L
421  merge(list&& __x, _StrictWeakOrdering __comp)
422 #else
423  merge(list& __x, _StrictWeakOrdering __comp)
424 #endif
425  {
426  // _GLIBCXX_RESOLVE_LIB_DEFECTS
427  // 300. list::merge() specification incomplete
428  if (this != std::__addressof(__x))
429  {
430  _M_check_equal_allocators(__x);
431 
432  iterator __first1 = begin();
433  iterator __last1 = end();
434  iterator __first2 = __x.begin();
435  iterator __last2 = __x.end();
436  const size_t __orig_size = __x.size();
437  __try
438  {
439  while (__first1 != __last1 && __first2 != __last2)
440  if (__comp(*__first2, *__first1))
441  {
442  iterator __next = __first2;
443  _M_transfer(__first1, __first2, ++__next);
444  __first2 = __next;
445  }
446  else
447  ++__first1;
448  if (__first2 != __last2)
449  _M_transfer(__last1, __first2, __last2);
450 
451  this->_M_inc_size(__x._M_get_size());
452  __x._M_set_size(0);
453  }
454  __catch(...)
455  {
456  const size_t __dist = std::distance(__first2, __last2);
457  this->_M_inc_size(__orig_size - __dist);
458  __x._M_set_size(__dist);
459  __throw_exception_again;
460  }
461  }
462  }
463 
464  template<typename _Tp, typename _Alloc>
465  void
468  {
469  // Do nothing if the list has length 0 or 1.
470  if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
471  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
472  {
473  list __carry;
474  list __tmp[64];
475  list * __fill = __tmp;
476  list * __counter;
477  __try
478  {
479  do
480  {
481  __carry.splice(__carry.begin(), *this, begin());
482 
483  for(__counter = __tmp;
484  __counter != __fill && !__counter->empty();
485  ++__counter)
486  {
487  __counter->merge(__carry);
488  __carry.swap(*__counter);
489  }
490  __carry.swap(*__counter);
491  if (__counter == __fill)
492  ++__fill;
493  }
494  while ( !empty() );
495 
496  for (__counter = __tmp + 1; __counter != __fill; ++__counter)
497  __counter->merge(*(__counter - 1));
498  swap( *(__fill - 1) );
499  }
500  __catch(...)
501  {
502  this->splice(this->end(), __carry);
503  for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
504  this->splice(this->end(), __tmp[__i]);
505  __throw_exception_again;
506  }
507  }
508  }
509 
510  template<typename _Tp, typename _Alloc>
511  template <typename _Predicate>
512  void
514  remove_if(_Predicate __pred)
515  {
516  iterator __first = begin();
517  iterator __last = end();
518  while (__first != __last)
519  {
520  iterator __next = __first;
521  ++__next;
522  if (__pred(*__first))
523  _M_erase(__first);
524  __first = __next;
525  }
526  }
527 
528  template<typename _Tp, typename _Alloc>
529  template <typename _BinaryPredicate>
530  void
532  unique(_BinaryPredicate __binary_pred)
533  {
534  iterator __first = begin();
535  iterator __last = end();
536  if (__first == __last)
537  return;
538  iterator __next = __first;
539  while (++__next != __last)
540  {
541  if (__binary_pred(*__first, *__next))
542  _M_erase(__next);
543  else
544  __first = __next;
545  __next = __first;
546  }
547  }
548 
549  template<typename _Tp, typename _Alloc>
550  template <typename _StrictWeakOrdering>
551  void
553  sort(_StrictWeakOrdering __comp)
554  {
555  // Do nothing if the list has length 0 or 1.
556  if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
557  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
558  {
559  list __carry;
560  list __tmp[64];
561  list * __fill = __tmp;
562  list * __counter;
563  __try
564  {
565  do
566  {
567  __carry.splice(__carry.begin(), *this, begin());
568 
569  for(__counter = __tmp;
570  __counter != __fill && !__counter->empty();
571  ++__counter)
572  {
573  __counter->merge(__carry, __comp);
574  __carry.swap(*__counter);
575  }
576  __carry.swap(*__counter);
577  if (__counter == __fill)
578  ++__fill;
579  }
580  while ( !empty() );
581 
582  for (__counter = __tmp + 1; __counter != __fill; ++__counter)
583  __counter->merge(*(__counter - 1), __comp);
584  swap(*(__fill - 1));
585  }
586  __catch(...)
587  {
588  this->splice(this->end(), __carry);
589  for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
590  this->splice(this->end(), __tmp[__i]);
591  __throw_exception_again;
592  }
593  }
594  }
595 
596 _GLIBCXX_END_NAMESPACE_CONTAINER
597 } // namespace std
598 
599 #endif /* _LIST_TCC */
600 
iterator begin() noexcept
Definition: stl_list.h:851
iterator end() noexcept
Definition: stl_list.h:869
void swap(list &__x) noexcept
Swaps data with another list.
Definition: stl_list.h:1384
void unique()
Remove consecutive duplicate elements.
Definition: list.tcc:353
void resize(size_type __new_size)
Resizes the list to the specified number of elements.
Definition: list.tcc:230
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
A list::const_iterator.
bool empty() const noexcept
Definition: stl_list.h:961
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.
void splice(const_iterator __position, list &&__x) noexcept
Insert contents of another list.
Definition: stl_list.h:1424
void merge(list &&__x)
Merge sorted lists.
Definition: list.tcc:374
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
list & operator=(const list &__x)
List assignment operator.
Definition: list.tcc:267
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into list before specified iterator.
Definition: list.tcc:102
void remove(const _Tp &__value)
Remove all elements equal to value.
Definition: list.tcc:325
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition: stl_list.h:503
void remove_if(_Predicate)
Remove all elements satisfying a predicate.
Definition: list.tcc:514
void sort()
Sort the elements.
Definition: list.tcc:467
iterator emplace(const_iterator __position, _Args &&...__args)
Constructs object in list before specified iterator.
Definition: list.tcc:89
size_type size() const noexcept
Definition: stl_list.h:966