libstdc++
list.tcc
Go to the documentation of this file.
1 // List implementation (out of line) -*- C++ -*-
2 
3 // Copyright (C) 2001-2015 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 #if __cplusplus >= 201103L
75  _M_get_Node_allocator().destroy(__tmp);
76 #else
77  _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data));
78 #endif
79  _M_put_node(__tmp);
80  }
81  }
82 
83 #if __cplusplus >= 201103L
84  template<typename _Tp, typename _Alloc>
85  template<typename... _Args>
86  typename list<_Tp, _Alloc>::iterator
88  emplace(const_iterator __position, _Args&&... __args)
89  {
90  _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
91  __tmp->_M_hook(__position._M_const_cast()._M_node);
92  this->_M_inc_size(1);
93  return iterator(__tmp);
94  }
95 #endif
96 
97  template<typename _Tp, typename _Alloc>
100 #if __cplusplus >= 201103L
101  insert(const_iterator __position, const value_type& __x)
102 #else
103  insert(iterator __position, const value_type& __x)
104 #endif
105  {
106  _Node* __tmp = _M_create_node(__x);
107  __tmp->_M_hook(__position._M_const_cast()._M_node);
108  this->_M_inc_size(1);
109  return iterator(__tmp);
110  }
111 
112 #if __cplusplus >= 201103L
113  template<typename _Tp, typename _Alloc>
116  insert(const_iterator __position, size_type __n, const value_type& __x)
117  {
118  if (__n)
119  {
120  list __tmp(__n, __x, get_allocator());
121  iterator __it = __tmp.begin();
122  splice(__position, __tmp);
123  return __it;
124  }
125  return __position._M_const_cast();
126  }
127 
128  template<typename _Tp, typename _Alloc>
129  template<typename _InputIterator, typename>
132  insert(const_iterator __position, _InputIterator __first,
133  _InputIterator __last)
134  {
135  list __tmp(__first, __last, get_allocator());
136  if (!__tmp.empty())
137  {
138  iterator __it = __tmp.begin();
139  splice(__position, __tmp);
140  return __it;
141  }
142  return __position._M_const_cast();
143  }
144 #endif
145 
146  template<typename _Tp, typename _Alloc>
149 #if __cplusplus >= 201103L
150  erase(const_iterator __position) noexcept
151 #else
152  erase(iterator __position)
153 #endif
154  {
155  iterator __ret = iterator(__position._M_node->_M_next);
156  _M_erase(__position._M_const_cast());
157  return __ret;
158  }
159 
160 #if __cplusplus >= 201103L
161  template<typename _Tp, typename _Alloc>
162  void
164  _M_default_append(size_type __n)
165  {
166  size_type __i = 0;
167  __try
168  {
169  for (; __i < __n; ++__i)
170  emplace_back();
171  }
172  __catch(...)
173  {
174  for (; __i; --__i)
175  pop_back();
176  __throw_exception_again;
177  }
178  }
179 
180  template<typename _Tp, typename _Alloc>
181  void
183  resize(size_type __new_size)
184  {
185  iterator __i = begin();
186  size_type __len = 0;
187  for (; __i != end() && __len < __new_size; ++__i, ++__len)
188  ;
189  if (__len == __new_size)
190  erase(__i, end());
191  else // __i == end()
192  _M_default_append(__new_size - __len);
193  }
194 
195  template<typename _Tp, typename _Alloc>
196  void
198  resize(size_type __new_size, const value_type& __x)
199  {
200  iterator __i = begin();
201  size_type __len = 0;
202  for (; __i != end() && __len < __new_size; ++__i, ++__len)
203  ;
204  if (__len == __new_size)
205  erase(__i, end());
206  else // __i == end()
207  insert(end(), __new_size - __len, __x);
208  }
209 #else
210  template<typename _Tp, typename _Alloc>
211  void
213  resize(size_type __new_size, value_type __x)
214  {
215  iterator __i = begin();
216  size_type __len = 0;
217  for (; __i != end() && __len < __new_size; ++__i, ++__len)
218  ;
219  if (__len == __new_size)
220  erase(__i, end());
221  else // __i == end()
222  insert(end(), __new_size - __len, __x);
223  }
224 #endif
225 
226  template<typename _Tp, typename _Alloc>
229  operator=(const list& __x)
230  {
231  if (this != &__x)
232  {
233  iterator __first1 = begin();
234  iterator __last1 = end();
235  const_iterator __first2 = __x.begin();
236  const_iterator __last2 = __x.end();
237  for (; __first1 != __last1 && __first2 != __last2;
238  ++__first1, ++__first2)
239  *__first1 = *__first2;
240  if (__first2 == __last2)
241  erase(__first1, __last1);
242  else
243  insert(__last1, __first2, __last2);
244  }
245  return *this;
246  }
247 
248  template<typename _Tp, typename _Alloc>
249  void
251  _M_fill_assign(size_type __n, const value_type& __val)
252  {
253  iterator __i = begin();
254  for (; __i != end() && __n > 0; ++__i, --__n)
255  *__i = __val;
256  if (__n > 0)
257  insert(end(), __n, __val);
258  else
259  erase(__i, end());
260  }
261 
262  template<typename _Tp, typename _Alloc>
263  template <typename _InputIterator>
264  void
266  _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
267  __false_type)
268  {
269  iterator __first1 = begin();
270  iterator __last1 = end();
271  for (; __first1 != __last1 && __first2 != __last2;
272  ++__first1, ++__first2)
273  *__first1 = *__first2;
274  if (__first2 == __last2)
275  erase(__first1, __last1);
276  else
277  insert(__last1, __first2, __last2);
278  }
279 
280  template<typename _Tp, typename _Alloc>
281  void
283  remove(const value_type& __value)
284  {
285  iterator __first = begin();
286  iterator __last = end();
287  iterator __extra = __last;
288  while (__first != __last)
289  {
290  iterator __next = __first;
291  ++__next;
292  if (*__first == __value)
293  {
294  // _GLIBCXX_RESOLVE_LIB_DEFECTS
295  // 526. Is it undefined if a function in the standard changes
296  // in parameters?
297  if (std::__addressof(*__first) != std::__addressof(__value))
298  _M_erase(__first);
299  else
300  __extra = __first;
301  }
302  __first = __next;
303  }
304  if (__extra != __last)
305  _M_erase(__extra);
306  }
307 
308  template<typename _Tp, typename _Alloc>
309  void
312  {
313  iterator __first = begin();
314  iterator __last = end();
315  if (__first == __last)
316  return;
317  iterator __next = __first;
318  while (++__next != __last)
319  {
320  if (*__first == *__next)
321  _M_erase(__next);
322  else
323  __first = __next;
324  __next = __first;
325  }
326  }
327 
328  template<typename _Tp, typename _Alloc>
329  void
331 #if __cplusplus >= 201103L
332  merge(list&& __x)
333 #else
334  merge(list& __x)
335 #endif
336  {
337  // _GLIBCXX_RESOLVE_LIB_DEFECTS
338  // 300. list::merge() specification incomplete
339  if (this != &__x)
340  {
341  _M_check_equal_allocators(__x);
342 
343  iterator __first1 = begin();
344  iterator __last1 = end();
345  iterator __first2 = __x.begin();
346  iterator __last2 = __x.end();
347  const size_t __orig_size = __x.size();
348  __try {
349  while (__first1 != __last1 && __first2 != __last2)
350  if (*__first2 < *__first1)
351  {
352  iterator __next = __first2;
353  _M_transfer(__first1, __first2, ++__next);
354  __first2 = __next;
355  }
356  else
357  ++__first1;
358  if (__first2 != __last2)
359  _M_transfer(__last1, __first2, __last2);
360 
361  this->_M_inc_size(__x._M_get_size());
362  __x._M_set_size(0);
363  }
364  __catch(...)
365  {
366  const size_t __dist = std::distance(__first2, __last2);
367  this->_M_inc_size(__orig_size - __dist);
368  __x._M_set_size(__dist);
369  __throw_exception_again;
370  }
371  }
372  }
373 
374  template<typename _Tp, typename _Alloc>
375  template <typename _StrictWeakOrdering>
376  void
378 #if __cplusplus >= 201103L
379  merge(list&& __x, _StrictWeakOrdering __comp)
380 #else
381  merge(list& __x, _StrictWeakOrdering __comp)
382 #endif
383  {
384  // _GLIBCXX_RESOLVE_LIB_DEFECTS
385  // 300. list::merge() specification incomplete
386  if (this != &__x)
387  {
388  _M_check_equal_allocators(__x);
389 
390  iterator __first1 = begin();
391  iterator __last1 = end();
392  iterator __first2 = __x.begin();
393  iterator __last2 = __x.end();
394  const size_t __orig_size = __x.size();
395  __try
396  {
397  while (__first1 != __last1 && __first2 != __last2)
398  if (__comp(*__first2, *__first1))
399  {
400  iterator __next = __first2;
401  _M_transfer(__first1, __first2, ++__next);
402  __first2 = __next;
403  }
404  else
405  ++__first1;
406  if (__first2 != __last2)
407  _M_transfer(__last1, __first2, __last2);
408 
409  this->_M_inc_size(__x._M_get_size());
410  __x._M_set_size(0);
411  }
412  __catch(...)
413  {
414  const size_t __dist = std::distance(__first2, __last2);
415  this->_M_inc_size(__orig_size - __dist);
416  __x._M_set_size(__dist);
417  __throw_exception_again;
418  }
419  }
420  }
421 
422  template<typename _Tp, typename _Alloc>
423  void
426  {
427  // Do nothing if the list has length 0 or 1.
428  if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
429  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
430  {
431  list __carry;
432  list __tmp[64];
433  list * __fill = &__tmp[0];
434  list * __counter;
435 
436  do
437  {
438  __carry.splice(__carry.begin(), *this, begin());
439 
440  for(__counter = &__tmp[0];
441  __counter != __fill && !__counter->empty();
442  ++__counter)
443  {
444  __counter->merge(__carry);
445  __carry.swap(*__counter);
446  }
447  __carry.swap(*__counter);
448  if (__counter == __fill)
449  ++__fill;
450  }
451  while ( !empty() );
452 
453  for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
454  __counter->merge(*(__counter - 1));
455  swap( *(__fill - 1) );
456  }
457  }
458 
459  template<typename _Tp, typename _Alloc>
460  template <typename _Predicate>
461  void
463  remove_if(_Predicate __pred)
464  {
465  iterator __first = begin();
466  iterator __last = end();
467  while (__first != __last)
468  {
469  iterator __next = __first;
470  ++__next;
471  if (__pred(*__first))
472  _M_erase(__first);
473  __first = __next;
474  }
475  }
476 
477  template<typename _Tp, typename _Alloc>
478  template <typename _BinaryPredicate>
479  void
481  unique(_BinaryPredicate __binary_pred)
482  {
483  iterator __first = begin();
484  iterator __last = end();
485  if (__first == __last)
486  return;
487  iterator __next = __first;
488  while (++__next != __last)
489  {
490  if (__binary_pred(*__first, *__next))
491  _M_erase(__next);
492  else
493  __first = __next;
494  __next = __first;
495  }
496  }
497 
498  template<typename _Tp, typename _Alloc>
499  template <typename _StrictWeakOrdering>
500  void
502  sort(_StrictWeakOrdering __comp)
503  {
504  // Do nothing if the list has length 0 or 1.
505  if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
506  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
507  {
508  list __carry;
509  list __tmp[64];
510  list * __fill = &__tmp[0];
511  list * __counter;
512 
513  do
514  {
515  __carry.splice(__carry.begin(), *this, begin());
516 
517  for(__counter = &__tmp[0];
518  __counter != __fill && !__counter->empty();
519  ++__counter)
520  {
521  __counter->merge(__carry, __comp);
522  __carry.swap(*__counter);
523  }
524  __carry.swap(*__counter);
525  if (__counter == __fill)
526  ++__fill;
527  }
528  while ( !empty() );
529 
530  for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
531  __counter->merge(*(__counter - 1), __comp);
532  swap(*(__fill - 1));
533  }
534  }
535 
536 _GLIBCXX_END_NAMESPACE_CONTAINER
537 } // namespace std
538 
539 #endif /* _LIST_TCC */
540 
void splice(const_iterator __position, list &&__x) noexcept
Insert contents of another list.
Definition: stl_list.h:1386
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
void resize(size_type __new_size)
Resizes the list to the specified number of elements.
Definition: list.tcc:183
iterator begin() noexcept
Definition: stl_list.h:831
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition: stl_list.h:507
iterator end() noexcept
Definition: stl_list.h:849
void remove_if(_Predicate)
Remove all elements satisfying a predicate.
Definition: list.tcc:463
void unique()
Remove consecutive duplicate elements.
Definition: list.tcc:311
A list::const_iterator.
Definition: stl_list.h:204
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
ISO C++ entities toplevel namespace is std.
list & operator=(const list &__x)
List assignment operator.
Definition: list.tcc:229
iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into list before specified iterator.
Definition: list.tcc:101
A list::iterator.
Definition: stl_list.h:125
void merge(list &&__x)
Merge sorted lists.
Definition: list.tcc:332
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
void swap(list &__x)
Swaps data with another list.
Definition: stl_list.h:1344
void remove(const _Tp &__value)
Remove all elements equal to value.
Definition: list.tcc:283
bool empty() const noexcept
Definition: stl_list.h:941
void sort()
Sort the elements.
Definition: list.tcc:425
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
size_type size() const noexcept
Definition: stl_list.h:946
iterator emplace(const_iterator __position, _Args &&... __args)
Constructs object in list before specified iterator.
Definition: list.tcc:88