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