1// List implementation -*- C++ -*-
2
3// Copyright (C) 2001-2018 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/stl_list.h
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 _STL_LIST_H
57#define _STL_LIST_H 1
58
59#include <bits/concept_check.h>
60#include <ext/alloc_traits.h>
61#if __cplusplus >= 201103L
62#include <initializer_list>
63#include <bits/allocated_ptr.h>
64#include <ext/aligned_buffer.h>
65#endif
66
67namespace std _GLIBCXX_VISIBILITY(default)
68{
69_GLIBCXX_BEGIN_NAMESPACE_VERSION
70
71 namespace __detail
72 {
73 // Supporting structures are split into common and templated
74 // types; the latter publicly inherits from the former in an
75 // effort to reduce code duplication. This results in some
76 // "needless" static_cast'ing later on, but it's all safe
77 // downcasting.
78
79 /// Common part of a node in the %list.
80 struct _List_node_base
81 {
82 _List_node_base* _M_next;
83 _List_node_base* _M_prev;
84
85 static void
86 swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT;
87
88 void
89 _M_transfer(_List_node_base* const __first,
90 _List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT;
91
92 void
93 _M_reverse() _GLIBCXX_USE_NOEXCEPT;
94
95 void
96 _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;
97
98 void
99 _M_unhook() _GLIBCXX_USE_NOEXCEPT;
100 };
101
102 /// The %list node header.
103 struct _List_node_header : public _List_node_base
104 {
105#if _GLIBCXX_USE_CXX11_ABI
106 std::size_t _M_size;
107#endif
108
109 _List_node_header() _GLIBCXX_NOEXCEPT
110 { _M_init(); }
111
112#if __cplusplus >= 201103L
113 _List_node_header(_List_node_header&& __x) noexcept
114 : _List_node_base{ __x._M_next, __x._M_prev }
115# if _GLIBCXX_USE_CXX11_ABI
116 , _M_size(__x._M_size)
117# endif
118 {
119 if (__x._M_base()->_M_next == __x._M_base())
120 this->_M_next = this->_M_prev = this;
121 else
122 {
123 this->_M_next->_M_prev = this->_M_prev->_M_next = this->_M_base();
124 __x._M_init();
125 }
126 }
127
128 void
129 _M_move_nodes(_List_node_header&& __x)
130 {
131 _List_node_base* const __xnode = __x._M_base();
132 if (__xnode->_M_next == __xnode)
133 _M_init();
134 else
135 {
136 _List_node_base* const __node = this->_M_base();
137 __node->_M_next = __xnode->_M_next;
138 __node->_M_prev = __xnode->_M_prev;
139 __node->_M_next->_M_prev = __node->_M_prev->_M_next = __node;
140# if _GLIBCXX_USE_CXX11_ABI
141 _M_size = __x._M_size;
142# endif
143 __x._M_init();
144 }
145 }
146#endif
147
148 void
149 _M_init() _GLIBCXX_NOEXCEPT
150 {
151 this->_M_next = this->_M_prev = this;
152#if _GLIBCXX_USE_CXX11_ABI
153 this->_M_size = 0;
154#endif
155 }
156
157 private:
158 _List_node_base* _M_base() { return this; }
159 };
160 } // namespace detail
161
162_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
163
164 /// An actual node in the %list.
165 template<typename _Tp>
166 struct _List_node : public __detail::_List_node_base
167 {
168#if __cplusplus >= 201103L
169 __gnu_cxx::__aligned_membuf<_Tp> _M_storage;
170 _Tp* _M_valptr() { return _M_storage._M_ptr(); }
171 _Tp const* _M_valptr() const { return _M_storage._M_ptr(); }
172#else
173 _Tp _M_data;
174 _Tp* _M_valptr() { return std::__addressof(_M_data); }
175 _Tp const* _M_valptr() const { return std::__addressof(_M_data); }
176#endif
177 };
178
179 /**
180 * @brief A list::iterator.
181 *
182 * All the functions are op overloads.
183 */
184 template<typename _Tp>
185 struct _List_iterator
186 {
187 typedef _List_iterator<_Tp> _Self;
188 typedef _List_node<_Tp> _Node;
189
190 typedef ptrdiff_t difference_type;
191 typedef std::bidirectional_iterator_tag iterator_category;
192 typedef _Tp value_type;
193 typedef _Tp* pointer;
194 typedef _Tp& reference;
195
196 _List_iterator() _GLIBCXX_NOEXCEPT
197 : _M_node() { }
198
199 explicit
200 _List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT
201 : _M_node(__x) { }
202
203 _Self
204 _M_const_cast() const _GLIBCXX_NOEXCEPT
205 { return *this; }
206
207 // Must downcast from _List_node_base to _List_node to get to value.
208 reference
209 operator*() const _GLIBCXX_NOEXCEPT
210 { return *static_cast<_Node*>(_M_node)->_M_valptr(); }
211
212 pointer
213 operator->() const _GLIBCXX_NOEXCEPT
214 { return static_cast<_Node*>(_M_node)->_M_valptr(); }
215
216 _Self&
217 operator++() _GLIBCXX_NOEXCEPT
218 {
219 _M_node = _M_node->_M_next;
220 return *this;
221 }
222
223 _Self
224 operator++(int) _GLIBCXX_NOEXCEPT
225 {
226 _Self __tmp = *this;
227 _M_node = _M_node->_M_next;
228 return __tmp;
229 }
230
231 _Self&
232 operator--() _GLIBCXX_NOEXCEPT
233 {
234 _M_node = _M_node->_M_prev;
235 return *this;
236 }
237
238 _Self
239 operator--(int) _GLIBCXX_NOEXCEPT
240 {
241 _Self __tmp = *this;
242 _M_node = _M_node->_M_prev;
243 return __tmp;
244 }
245
246 bool
247 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
248 { return _M_node == __x._M_node; }
249
250 bool
251 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
252 { return _M_node != __x._M_node; }
253
254 // The only member points to the %list element.
255 __detail::_List_node_base* _M_node;
256 };
257
258 /**
259 * @brief A list::const_iterator.
260 *
261 * All the functions are op overloads.
262 */
263 template<typename _Tp>
264 struct _List_const_iterator
265 {
266 typedef _List_const_iterator<_Tp> _Self;
267 typedef const _List_node<_Tp> _Node;
268 typedef _List_iterator<_Tp> iterator;
269
270 typedef ptrdiff_t difference_type;
271 typedef std::bidirectional_iterator_tag iterator_category;
272 typedef _Tp value_type;
273 typedef const _Tp* pointer;
274 typedef const _Tp& reference;
275
276 _List_const_iterator() _GLIBCXX_NOEXCEPT
277 : _M_node() { }
278
279 explicit
280 _List_const_iterator(const __detail::_List_node_base* __x)
281 _GLIBCXX_NOEXCEPT
282 : _M_node(__x) { }
283
284 _List_const_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT
285 : _M_node(__x._M_node) { }
286
287 iterator
288 _M_const_cast() const _GLIBCXX_NOEXCEPT
289 { return iterator(const_cast<__detail::_List_node_base*>(_M_node)); }
290
291 // Must downcast from List_node_base to _List_node to get to value.
292 reference
293 operator*() const _GLIBCXX_NOEXCEPT
294 { return *static_cast<_Node*>(_M_node)->_M_valptr(); }
295
296 pointer
297 operator->() const _GLIBCXX_NOEXCEPT
298 { return static_cast<_Node*>(_M_node)->_M_valptr(); }
299
300 _Self&
301 operator++() _GLIBCXX_NOEXCEPT
302 {
303 _M_node = _M_node->_M_next;
304 return *this;
305 }
306
307 _Self
308 operator++(int) _GLIBCXX_NOEXCEPT
309 {
310 _Self __tmp = *this;
311 _M_node = _M_node->_M_next;
312 return __tmp;
313 }
314
315 _Self&
316 operator--() _GLIBCXX_NOEXCEPT
317 {
318 _M_node = _M_node->_M_prev;
319 return *this;
320 }
321
322 _Self
323 operator--(int) _GLIBCXX_NOEXCEPT
324 {
325 _Self __tmp = *this;
326 _M_node = _M_node->_M_prev;
327 return __tmp;
328 }
329
330 bool
331 operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
332 { return _M_node == __x._M_node; }
333
334 bool
335 operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
336 { return _M_node != __x._M_node; }
337
338 // The only member points to the %list element.
339 const __detail::_List_node_base* _M_node;
340 };
341
342 template<typename _Val>
343 inline bool
344 operator==(const _List_iterator<_Val>& __x,
345 const _List_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
346 { return __x._M_node == __y._M_node; }
347
348 template<typename _Val>
349 inline bool
350 operator!=(const _List_iterator<_Val>& __x,
351 const _List_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
352 { return __x._M_node != __y._M_node; }
353
354_GLIBCXX_BEGIN_NAMESPACE_CXX11
355 /// See bits/stl_deque.h's _Deque_base for an explanation.
356 template<typename _Tp, typename _Alloc>
357 class _List_base
358 {
359 protected:
360 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
361 rebind<_Tp>::other _Tp_alloc_type;
362 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tp_alloc_traits;
363 typedef typename _Tp_alloc_traits::template
364 rebind<_List_node<_Tp> >::other _Node_alloc_type;
365 typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
366
367#if !_GLIBCXX_INLINE_VERSION
368 static size_t
369 _S_distance(const __detail::_List_node_base* __first,
370 const __detail::_List_node_base* __last)
371 {
372 size_t __n = 0;
373 while (__first != __last)
374 {
375 __first = __first->_M_next;
376 ++__n;
377 }
378 return __n;
379 }
380#endif
381
382 struct _List_impl
383 : public _Node_alloc_type
384 {
385 __detail::_List_node_header _M_node;
386
387 _List_impl() _GLIBCXX_NOEXCEPT_IF(
388 is_nothrow_default_constructible<_Node_alloc_type>::value)
389 : _Node_alloc_type()
390 { }
391
392 _List_impl(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
393 : _Node_alloc_type(__a)
394 { }
395
396#if __cplusplus >= 201103L
397 _List_impl(_List_impl&&) = default;
398
399 _List_impl(_Node_alloc_type&& __a, _List_impl&& __x)
400 : _Node_alloc_type(std::move(__a)), _M_node(std::move(__x._M_node))
401 { }
402
403 _List_impl(_Node_alloc_type&& __a) noexcept
404 : _Node_alloc_type(std::move(__a))
405 { }
406#endif
407 };
408
409 _List_impl _M_impl;
410
411#if _GLIBCXX_USE_CXX11_ABI
412 size_t _M_get_size() const { return _M_impl._M_node._M_size; }
413
414 void _M_set_size(size_t __n) { _M_impl._M_node._M_size = __n; }
415
416 void _M_inc_size(size_t __n) { _M_impl._M_node._M_size += __n; }
417
418 void _M_dec_size(size_t __n) { _M_impl._M_node._M_size -= __n; }
419
420# if !_GLIBCXX_INLINE_VERSION
421 size_t
422 _M_distance(const __detail::_List_node_base* __first,
423 const __detail::_List_node_base* __last) const
424 { return _S_distance(__first, __last); }
425
426 // return the stored size
427 size_t _M_node_count() const { return _M_get_size(); }
428# endif
429#else
430 // dummy implementations used when the size is not stored
431 size_t _M_get_size() const { return 0; }
432 void _M_set_size(size_t) { }
433 void _M_inc_size(size_t) { }
434 void _M_dec_size(size_t) { }
435
436# if !_GLIBCXX_INLINE_VERSION
437 size_t _M_distance(const void*, const void*) const { return 0; }
438
439 // count the number of nodes
440 size_t _M_node_count() const
441 {
442 return _S_distance(_M_impl._M_node._M_next,
443 std::__addressof(_M_impl._M_node));
444 }
445# endif
446#endif
447
448 typename _Node_alloc_traits::pointer
449 _M_get_node()
450 { return _Node_alloc_traits::allocate(_M_impl, 1); }
451
452 void
453 _M_put_node(typename _Node_alloc_traits::pointer __p) _GLIBCXX_NOEXCEPT
454 { _Node_alloc_traits::deallocate(_M_impl, __p, 1); }
455
456 public:
457 typedef _Alloc allocator_type;
458
459 _Node_alloc_type&
460 _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
461 { return _M_impl; }
462
463 const _Node_alloc_type&
464 _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
465 { return _M_impl; }
466
467#if __cplusplus >= 201103L
468 _List_base() = default;
469#else
470 _List_base() { }
471#endif
472
473 _List_base(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
474 : _M_impl(__a)
475 { }
476
477#if __cplusplus >= 201103L
478 _List_base(_List_base&&) = default;
479
480# if !_GLIBCXX_INLINE_VERSION
481 _List_base(_List_base&& __x, _Node_alloc_type&& __a)
482 : _M_impl(std::move(__a))
483 {
484 if (__x._M_get_Node_allocator() == _M_get_Node_allocator())
485 _M_move_nodes(std::move(__x));
486 // else caller must move individual elements.
487 }
488# endif
489
490 // Used when allocator is_always_equal.
491 _List_base(_Node_alloc_type&& __a, _List_base&& __x)
492 : _M_impl(std::move(__a), std::move(__x._M_impl))
493 { }
494
495 // Used when allocator !is_always_equal.
496 _List_base(_Node_alloc_type&& __a)
497 : _M_impl(std::move(__a))
498 { }
499
500 void
501 _M_move_nodes(_List_base&& __x)
502 { _M_impl._M_node._M_move_nodes(std::move(__x._M_impl._M_node)); }
503#endif
504
505 // This is what actually destroys the list.
506 ~_List_base() _GLIBCXX_NOEXCEPT
507 { _M_clear(); }
508
509 void
510 _M_clear() _GLIBCXX_NOEXCEPT;
511
512 void
513 _M_init() _GLIBCXX_NOEXCEPT
514 { this->_M_impl._M_node._M_init(); }
515 };
516
517 /**
518 * @brief A standard container with linear time access to elements,
519 * and fixed time insertion/deletion at any point in the sequence.
520 *
521 * @ingroup sequences
522 *
523 * @tparam _Tp Type of element.
524 * @tparam _Alloc Allocator type, defaults to allocator<_Tp>.
525 *
526 * Meets the requirements of a <a href="tables.html#65">container</a>, a
527 * <a href="tables.html#66">reversible container</a>, and a
528 * <a href="tables.html#67">sequence</a>, including the
529 * <a href="tables.html#68">optional sequence requirements</a> with the
530 * %exception of @c at and @c operator[].
531 *
532 * This is a @e doubly @e linked %list. Traversal up and down the
533 * %list requires linear time, but adding and removing elements (or
534 * @e nodes) is done in constant time, regardless of where the
535 * change takes place. Unlike std::vector and std::deque,
536 * random-access iterators are not provided, so subscripting ( @c
537 * [] ) access is not allowed. For algorithms which only need
538 * sequential access, this lack makes no difference.
539 *
540 * Also unlike the other standard containers, std::list provides
541 * specialized algorithms %unique to linked lists, such as
542 * splicing, sorting, and in-place reversal.
543 *
544 * A couple points on memory allocation for list<Tp>:
545 *
546 * First, we never actually allocate a Tp, we allocate
547 * List_node<Tp>'s and trust [20.1.5]/4 to DTRT. This is to ensure
548 * that after elements from %list<X,Alloc1> are spliced into
549 * %list<X,Alloc2>, destroying the memory of the second %list is a
550 * valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.
551 *
552 * Second, a %list conceptually represented as
553 * @code
554 * A <---> B <---> C <---> D
555 * @endcode
556 * is actually circular; a link exists between A and D. The %list
557 * class holds (as its only data member) a private list::iterator
558 * pointing to @e D, not to @e A! To get to the head of the %list,
559 * we start at the tail and move forward by one. When this member
560 * iterator's next/previous pointers refer to itself, the %list is
561 * %empty.
562 */
563 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
564 class list : protected _List_base<_Tp, _Alloc>
565 {
566#ifdef _GLIBCXX_CONCEPT_CHECKS
567 // concept requirements
568 typedef typename _Alloc::value_type _Alloc_value_type;
569# if __cplusplus < 201103L
570 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
571# endif
572 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
573#endif
574
575#if __cplusplus >= 201103L
576 static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,
577 "std::list must have a non-const, non-volatile value_type");
578# ifdef __STRICT_ANSI__
579 static_assert(is_same<typename _Alloc::value_type, _Tp>::value,
580 "std::list must have the same value_type as its allocator");
581# endif
582#endif
583
584 typedef _List_base<_Tp, _Alloc> _Base;
585 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
586 typedef typename _Base::_Tp_alloc_traits _Tp_alloc_traits;
587 typedef typename _Base::_Node_alloc_type _Node_alloc_type;
588 typedef typename _Base::_Node_alloc_traits _Node_alloc_traits;
589
590 public:
591 typedef _Tp value_type;
592 typedef typename _Tp_alloc_traits::pointer pointer;
593 typedef typename _Tp_alloc_traits::const_pointer const_pointer;
594 typedef typename _Tp_alloc_traits::reference reference;
595 typedef typename _Tp_alloc_traits::const_reference const_reference;
596 typedef _List_iterator<_Tp> iterator;
597 typedef _List_const_iterator<_Tp> const_iterator;
598 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
599 typedef std::reverse_iterator<iterator> reverse_iterator;
600 typedef size_t size_type;
601 typedef ptrdiff_t difference_type;
602 typedef _Alloc allocator_type;
603
604 protected:
605 // Note that pointers-to-_Node's can be ctor-converted to
606 // iterator types.
607 typedef _List_node<_Tp> _Node;
608
609 using _Base::_M_impl;
610 using _Base::_M_put_node;
611 using _Base::_M_get_node;
612 using _Base::_M_get_Node_allocator;
613
614 /**
615 * @param __args An instance of user data.
616 *
617 * Allocates space for a new node and constructs a copy of
618 * @a __args in it.
619 */
620#if __cplusplus < 201103L
621 _Node*
622 _M_create_node(const value_type& __x)
623 {
624 _Node* __p = this->_M_get_node();
625 __try
626 {
627 _Tp_alloc_type __alloc(_M_get_Node_allocator());
628 __alloc.construct(__p->_M_valptr(), __x);
629 }
630 __catch(...)
631 {
632 _M_put_node(__p);
633 __throw_exception_again;
634 }
635 return __p;
636 }
637#else
638 template<typename... _Args>
639 _Node*
640 _M_create_node(_Args&&... __args)
641 {
642 auto __p = this->_M_get_node();
643 auto& __alloc = _M_get_Node_allocator();
644 __allocated_ptr<_Node_alloc_type> __guard{__alloc, __p};
645 _Node_alloc_traits::construct(__alloc, __p->_M_valptr(),
646 std::forward<_Args>(__args)...);
647 __guard = nullptr;
648 return __p;
649 }
650#endif
651
652#if _GLIBCXX_USE_CXX11_ABI
653 static size_t
654 _S_distance(const_iterator __first, const_iterator __last)
655 { return std::distance(__first, __last); }
656
657 // return the stored size
658 size_t
659 _M_node_count() const
660 { return this->_M_get_size(); }
661#else
662 // dummy implementations used when the size is not stored
663 static size_t
664 _S_distance(const_iterator, const_iterator)
665 { return 0; }
666
667 // count the number of nodes
668 size_t
669 _M_node_count() const
670 { return std::distance(begin(), end()); }
671#endif
672
673 public:
674 // [23.2.2.1] construct/copy/destroy
675 // (assign() and get_allocator() are also listed in this section)
676
677 /**
678 * @brief Creates a %list with no elements.
679 */
680#if __cplusplus >= 201103L
681 list() = default;
682#else
683 list() { }
684#endif
685
686 /**
687 * @brief Creates a %list with no elements.
688 * @param __a An allocator object.
689 */
690 explicit
691 list(const allocator_type& __a) _GLIBCXX_NOEXCEPT
692 : _Base(_Node_alloc_type(__a)) { }
693
694#if __cplusplus >= 201103L
695 /**
696 * @brief Creates a %list with default constructed elements.
697 * @param __n The number of elements to initially create.
698 * @param __a An allocator object.
699 *
700 * This constructor fills the %list with @a __n default
701 * constructed elements.
702 */
703 explicit
704 list(size_type __n, const allocator_type& __a = allocator_type())
705 : _Base(_Node_alloc_type(__a))
706 { _M_default_initialize(__n); }
707
708 /**
709 * @brief Creates a %list with copies of an exemplar element.
710 * @param __n The number of elements to initially create.
711 * @param __value An element to copy.
712 * @param __a An allocator object.
713 *
714 * This constructor fills the %list with @a __n copies of @a __value.
715 */
716 list(size_type __n, const value_type& __value,
717 const allocator_type& __a = allocator_type())
718 : _Base(_Node_alloc_type(__a))
719 { _M_fill_initialize(__n, __value); }
720#else
721 /**
722 * @brief Creates a %list with copies of an exemplar element.
723 * @param __n The number of elements to initially create.
724 * @param __value An element to copy.
725 * @param __a An allocator object.
726 *
727 * This constructor fills the %list with @a __n copies of @a __value.
728 */
729 explicit
730 list(size_type __n, const value_type& __value = value_type(),
731 const allocator_type& __a = allocator_type())
732 : _Base(_Node_alloc_type(__a))
733 { _M_fill_initialize(__n, __value); }
734#endif
735
736 /**
737 * @brief %List copy constructor.
738 * @param __x A %list of identical element and allocator types.
739 *
740 * The newly-created %list uses a copy of the allocation object used
741 * by @a __x (unless the allocator traits dictate a different object).
742 */
743 list(const list& __x)
744 : _Base(_Node_alloc_traits::
745 _S_select_on_copy(__x._M_get_Node_allocator()))
746 { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
747
748#if __cplusplus >= 201103L
749 /**
750 * @brief %List move constructor.
751 *
752 * The newly-created %list contains the exact contents of the moved
753 * instance. The contents of the moved instance are a valid, but
754 * unspecified %list.
755 */
756 list(list&&) = default;
757
758 /**
759 * @brief Builds a %list from an initializer_list
760 * @param __l An initializer_list of value_type.
761 * @param __a An allocator object.
762 *
763 * Create a %list consisting of copies of the elements in the
764 * initializer_list @a __l. This is linear in __l.size().
765 */
766 list(initializer_list<value_type> __l,
767 const allocator_type& __a = allocator_type())
768 : _Base(_Node_alloc_type(__a))
769 { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); }
770
771 list(const list& __x, const allocator_type& __a)
772 : _Base(_Node_alloc_type(__a))
773 { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
774
775 private:
776 list(list&& __x, const allocator_type& __a, true_type) noexcept
777 : _Base(_Node_alloc_type(__a), std::move(__x))
778 { }
779
780 list(list&& __x, const allocator_type& __a, false_type)
781 : _Base(_Node_alloc_type(__a))
782 {
783 if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator())
784 this->_M_move_nodes(std::move(__x));
785 else
786 insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()),
787 std::__make_move_if_noexcept_iterator(__x.end()));
788 }
789
790 public:
791 list(list&& __x, const allocator_type& __a)
792 noexcept(_Node_alloc_traits::_S_always_equal())
793 : list(std::move(__x), __a,
794 typename _Node_alloc_traits::is_always_equal{})
795 { }
796#endif
797
798 /**
799 * @brief Builds a %list from a range.
800 * @param __first An input iterator.
801 * @param __last An input iterator.
802 * @param __a An allocator object.
803 *
804 * Create a %list consisting of copies of the elements from
805 * [@a __first,@a __last). This is linear in N (where N is
806 * distance(@a __first,@a __last)).
807 */
808#if __cplusplus >= 201103L
809 template<typename _InputIterator,
810 typename = std::_RequireInputIter<_InputIterator>>
811 list(_InputIterator __first, _InputIterator __last,
812 const allocator_type& __a = allocator_type())
813 : _Base(_Node_alloc_type(__a))
814 { _M_initialize_dispatch(__first, __last, __false_type()); }
815#else
816 template<typename _InputIterator>
817 list(_InputIterator __first, _InputIterator __last,
818 const allocator_type& __a = allocator_type())
819 : _Base(_Node_alloc_type(__a))
820 {
821 // Check whether it's an integral type. If so, it's not an iterator.
822 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
823 _M_initialize_dispatch(__first, __last, _Integral());
824 }
825#endif
826
827#if __cplusplus >= 201103L
828 /**
829 * No explicit dtor needed as the _Base dtor takes care of
830 * things. The _Base dtor only erases the elements, and note
831 * that if the elements themselves are pointers, the pointed-to
832 * memory is not touched in any way. Managing the pointer is
833 * the user's responsibility.
834 */
835 ~list() = default;
836#endif
837
838 /**
839 * @brief %List assignment operator.
840 * @param __x A %list of identical element and allocator types.
841 *
842 * All the elements of @a __x are copied.
843 *
844 * Whether the allocator is copied depends on the allocator traits.
845 */
846 list&
847 operator=(const list& __x);
848
849#if __cplusplus >= 201103L
850 /**
851 * @brief %List move assignment operator.
852 * @param __x A %list of identical element and allocator types.
853 *
854 * The contents of @a __x are moved into this %list (without copying).
855 *
856 * Afterwards @a __x is a valid, but unspecified %list
857 *
858 * Whether the allocator is moved depends on the allocator traits.
859 */
860 list&
861 operator=(list&& __x)
862 noexcept(_Node_alloc_traits::_S_nothrow_move())
863 {
864 constexpr bool __move_storage =
865 _Node_alloc_traits::_S_propagate_on_move_assign()
866 || _Node_alloc_traits::_S_always_equal();
867 _M_move_assign(std::move(__x), __bool_constant<__move_storage>());
868 return *this;
869 }
870
871 /**
872 * @brief %List initializer list assignment operator.
873 * @param __l An initializer_list of value_type.
874 *
875 * Replace the contents of the %list with copies of the elements
876 * in the initializer_list @a __l. This is linear in l.size().
877 */
878 list&
879 operator=(initializer_list<value_type> __l)
880 {
881 this->assign(__l.begin(), __l.end());
882 return *this;
883 }
884#endif
885
886 /**
887 * @brief Assigns a given value to a %list.
888 * @param __n Number of elements to be assigned.
889 * @param __val Value to be assigned.
890 *
891 * This function fills a %list with @a __n copies of the given
892 * value. Note that the assignment completely changes the %list
893 * and that the resulting %list's size is the same as the number
894 * of elements assigned.
895 */
896 void
897 assign(size_type __n, const value_type& __val)
898 { _M_fill_assign(__n, __val); }
899
900 /**
901 * @brief Assigns a range to a %list.
902 * @param __first An input iterator.
903 * @param __last An input iterator.
904 *
905 * This function fills a %list with copies of the elements in the
906 * range [@a __first,@a __last).
907 *
908 * Note that the assignment completely changes the %list and
909 * that the resulting %list's size is the same as the number of
910 * elements assigned.
911 */
912#if __cplusplus >= 201103L
913 template<typename _InputIterator,
914 typename = std::_RequireInputIter<_InputIterator>>
915 void
916 assign(_InputIterator __first, _InputIterator __last)
917 { _M_assign_dispatch(__first, __last, __false_type()); }
918#else
919 template<typename _InputIterator>
920 void
921 assign(_InputIterator __first, _InputIterator __last)
922 {
923 // Check whether it's an integral type. If so, it's not an iterator.
924 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
925 _M_assign_dispatch(__first, __last, _Integral());
926 }
927#endif
928
929#if __cplusplus >= 201103L
930 /**
931 * @brief Assigns an initializer_list to a %list.
932 * @param __l An initializer_list of value_type.
933 *
934 * Replace the contents of the %list with copies of the elements
935 * in the initializer_list @a __l. This is linear in __l.size().
936 */
937 void
938 assign(initializer_list<value_type> __l)
939 { this->_M_assign_dispatch(__l.begin(), __l.end(), __false_type()); }
940#endif
941
942 /// Get a copy of the memory allocation object.
943 allocator_type
944 get_allocator() const _GLIBCXX_NOEXCEPT
945 { return allocator_type(_Base::_M_get_Node_allocator()); }
946
947 // iterators
948 /**
949 * Returns a read/write iterator that points to the first element in the
950 * %list. Iteration is done in ordinary element order.
951 */
952 iterator
953 begin() _GLIBCXX_NOEXCEPT
954 { return iterator(this->_M_impl._M_node._M_next); }
955
956 /**
957 * Returns a read-only (constant) iterator that points to the
958 * first element in the %list. Iteration is done in ordinary
959 * element order.
960 */
961 const_iterator
962 begin() const _GLIBCXX_NOEXCEPT
963 { return const_iterator(this->_M_impl._M_node._M_next); }
964
965 /**
966 * Returns a read/write iterator that points one past the last
967 * element in the %list. Iteration is done in ordinary element
968 * order.
969 */
970 iterator
971 end() _GLIBCXX_NOEXCEPT
972 { return iterator(&this->_M_impl._M_node); }
973
974 /**
975 * Returns a read-only (constant) iterator that points one past
976 * the last element in the %list. Iteration is done in ordinary
977 * element order.
978 */
979 const_iterator
980 end() const _GLIBCXX_NOEXCEPT
981 { return const_iterator(&this->_M_impl._M_node); }
982
983 /**
984 * Returns a read/write reverse iterator that points to the last
985 * element in the %list. Iteration is done in reverse element
986 * order.
987 */
988 reverse_iterator
989 rbegin() _GLIBCXX_NOEXCEPT
990 { return reverse_iterator(end()); }
991
992 /**
993 * Returns a read-only (constant) reverse iterator that points to
994 * the last element in the %list. Iteration is done in reverse
995 * element order.
996 */
997 const_reverse_iterator
998 rbegin() const _GLIBCXX_NOEXCEPT
999 { return const_reverse_iterator(end()); }
1000
1001 /**
1002 * Returns a read/write reverse iterator that points to one
1003 * before the first element in the %list. Iteration is done in
1004 * reverse element order.
1005 */
1006 reverse_iterator
1007 rend() _GLIBCXX_NOEXCEPT
1008 { return reverse_iterator(begin()); }
1009
1010 /**
1011 * Returns a read-only (constant) reverse iterator that points to one
1012 * before the first element in the %list. Iteration is done in reverse
1013 * element order.
1014 */
1015 const_reverse_iterator
1016 rend() const _GLIBCXX_NOEXCEPT
1017 { return const_reverse_iterator(begin()); }
1018
1019#if __cplusplus >= 201103L
1020 /**
1021 * Returns a read-only (constant) iterator that points to the
1022 * first element in the %list. Iteration is done in ordinary
1023 * element order.
1024 */
1025 const_iterator
1026 cbegin() const noexcept
1027 { return const_iterator(this->_M_impl._M_node._M_next); }
1028
1029 /**
1030 * Returns a read-only (constant) iterator that points one past
1031 * the last element in the %list. Iteration is done in ordinary
1032 * element order.
1033 */
1034 const_iterator
1035 cend() const noexcept
1036 { return const_iterator(&this->_M_impl._M_node); }
1037
1038 /**
1039 * Returns a read-only (constant) reverse iterator that points to
1040 * the last element in the %list. Iteration is done in reverse
1041 * element order.
1042 */
1043 const_reverse_iterator
1044 crbegin() const noexcept
1045 { return const_reverse_iterator(end()); }
1046
1047 /**
1048 * Returns a read-only (constant) reverse iterator that points to one
1049 * before the first element in the %list. Iteration is done in reverse
1050 * element order.
1051 */
1052 const_reverse_iterator
1053 crend() const noexcept
1054 { return const_reverse_iterator(begin()); }
1055#endif
1056
1057 // [23.2.2.2] capacity
1058 /**
1059 * Returns true if the %list is empty. (Thus begin() would equal
1060 * end().)
1061 */
1062 bool
1063 empty() const _GLIBCXX_NOEXCEPT
1064 { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
1065
1066 /** Returns the number of elements in the %list. */
1067 size_type
1068 size() const _GLIBCXX_NOEXCEPT
1069 { return _M_node_count(); }
1070
1071 /** Returns the size() of the largest possible %list. */
1072 size_type
1073 max_size() const _GLIBCXX_NOEXCEPT
1074 { return _Node_alloc_traits::max_size(_M_get_Node_allocator()); }
1075
1076#if __cplusplus >= 201103L
1077 /**
1078 * @brief Resizes the %list to the specified number of elements.
1079 * @param __new_size Number of elements the %list should contain.
1080 *
1081 * This function will %resize the %list to the specified number
1082 * of elements. If the number is smaller than the %list's
1083 * current size the %list is truncated, otherwise default
1084 * constructed elements are appended.
1085 */
1086 void
1087 resize(size_type __new_size);
1088
1089 /**
1090 * @brief Resizes the %list to the specified number of elements.
1091 * @param __new_size Number of elements the %list should contain.
1092 * @param __x Data with which new elements should be populated.
1093 *
1094 * This function will %resize the %list to the specified number
1095 * of elements. If the number is smaller than the %list's
1096 * current size the %list is truncated, otherwise the %list is
1097 * extended and new elements are populated with given data.
1098 */
1099 void
1100 resize(size_type __new_size, const value_type& __x);
1101#else
1102 /**
1103 * @brief Resizes the %list to the specified number of elements.
1104 * @param __new_size Number of elements the %list should contain.
1105 * @param __x Data with which new elements should be populated.
1106 *
1107 * This function will %resize the %list to the specified number
1108 * of elements. If the number is smaller than the %list's
1109 * current size the %list is truncated, otherwise the %list is
1110 * extended and new elements are populated with given data.
1111 */
1112 void
1113 resize(size_type __new_size, value_type __x = value_type());
1114#endif
1115
1116 // element access
1117 /**
1118 * Returns a read/write reference to the data at the first
1119 * element of the %list.
1120 */
1121 reference
1122 front() _GLIBCXX_NOEXCEPT
1123 { return *begin(); }
1124
1125 /**
1126 * Returns a read-only (constant) reference to the data at the first
1127 * element of the %list.
1128 */
1129 const_reference
1130 front() const _GLIBCXX_NOEXCEPT
1131 { return *begin(); }
1132
1133 /**
1134 * Returns a read/write reference to the data at the last element
1135 * of the %list.
1136 */
1137 reference
1138 back() _GLIBCXX_NOEXCEPT
1139 {
1140 iterator __tmp = end();
1141 --__tmp;
1142 return *__tmp;
1143 }
1144
1145 /**
1146 * Returns a read-only (constant) reference to the data at the last
1147 * element of the %list.
1148 */
1149 const_reference
1150 back() const _GLIBCXX_NOEXCEPT
1151 {
1152 const_iterator __tmp = end();
1153 --__tmp;
1154 return *__tmp;
1155 }
1156
1157 // [23.2.2.3] modifiers
1158 /**
1159 * @brief Add data to the front of the %list.
1160 * @param __x Data to be added.
1161 *
1162 * This is a typical stack operation. The function creates an
1163 * element at the front of the %list and assigns the given data
1164 * to it. Due to the nature of a %list this operation can be
1165 * done in constant time, and does not invalidate iterators and
1166 * references.
1167 */
1168 void
1169 push_front(const value_type& __x)
1170 { this->_M_insert(begin(), __x); }
1171
1172#if __cplusplus >= 201103L
1173 void
1174 push_front(value_type&& __x)
1175 { this->_M_insert(begin(), std::move(__x)); }
1176
1177 template<typename... _Args>
1178#if __cplusplus > 201402L
1179 reference
1180#else
1181 void
1182#endif
1183 emplace_front(_Args&&... __args)
1184 {
1185 this->_M_insert(begin(), std::forward<_Args>(__args)...);
1186#if __cplusplus > 201402L
1187 return front();
1188#endif
1189 }
1190#endif
1191
1192 /**
1193 * @brief Removes first element.
1194 *
1195 * This is a typical stack operation. It shrinks the %list by
1196 * one. Due to the nature of a %list this operation can be done
1197 * in constant time, and only invalidates iterators/references to
1198 * the element being removed.
1199 *
1200 * Note that no data is returned, and if the first element's data
1201 * is needed, it should be retrieved before pop_front() is
1202 * called.
1203 */
1204 void
1205 pop_front() _GLIBCXX_NOEXCEPT
1206 { this->_M_erase(begin()); }
1207
1208 /**
1209 * @brief Add data to the end of the %list.
1210 * @param __x Data to be added.
1211 *
1212 * This is a typical stack operation. The function creates an
1213 * element at the end of the %list and assigns the given data to
1214 * it. Due to the nature of a %list this operation can be done
1215 * in constant time, and does not invalidate iterators and
1216 * references.
1217 */
1218 void
1219 push_back(const value_type& __x)
1220 { this->_M_insert(end(), __x); }
1221
1222#if __cplusplus >= 201103L
1223 void
1224 push_back(value_type&& __x)
1225 { this->_M_insert(end(), std::move(__x)); }
1226
1227 template<typename... _Args>
1228#if __cplusplus > 201402L
1229 reference
1230#else
1231 void
1232#endif
1233 emplace_back(_Args&&... __args)
1234 {
1235 this->_M_insert(end(), std::forward<_Args>(__args)...);
1236#if __cplusplus > 201402L
1237 return back();
1238#endif
1239 }
1240#endif
1241
1242 /**
1243 * @brief Removes last element.
1244 *
1245 * This is a typical stack operation. It shrinks the %list by
1246 * one. Due to the nature of a %list this operation can be done
1247 * in constant time, and only invalidates iterators/references to
1248 * the element being removed.
1249 *
1250 * Note that no data is returned, and if the last element's data
1251 * is needed, it should be retrieved before pop_back() is called.
1252 */
1253 void
1254 pop_back() _GLIBCXX_NOEXCEPT
1255 { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }
1256
1257#if __cplusplus >= 201103L
1258 /**
1259 * @brief Constructs object in %list before specified iterator.
1260 * @param __position A const_iterator into the %list.
1261 * @param __args Arguments.
1262 * @return An iterator that points to the inserted data.
1263 *
1264 * This function will insert an object of type T constructed
1265 * with T(std::forward<Args>(args)...) before the specified
1266 * location. Due to the nature of a %list this operation can
1267 * be done in constant time, and does not invalidate iterators
1268 * and references.
1269 */
1270 template<typename... _Args>
1271 iterator
1272 emplace(const_iterator __position, _Args&&... __args);
1273
1274 /**
1275 * @brief Inserts given value into %list before specified iterator.
1276 * @param __position A const_iterator into the %list.
1277 * @param __x Data to be inserted.
1278 * @return An iterator that points to the inserted data.
1279 *
1280 * This function will insert a copy of the given value before
1281 * the specified location. Due to the nature of a %list this
1282 * operation can be done in constant time, and does not
1283 * invalidate iterators and references.
1284 */
1285 iterator
1286 insert(const_iterator __position, const value_type& __x);
1287#else
1288 /**
1289 * @brief Inserts given value into %list before specified iterator.
1290 * @param __position An iterator into the %list.
1291 * @param __x Data to be inserted.
1292 * @return An iterator that points to the inserted data.
1293 *
1294 * This function will insert a copy of the given value before
1295 * the specified location. Due to the nature of a %list this
1296 * operation can be done in constant time, and does not
1297 * invalidate iterators and references.
1298 */
1299 iterator
1300 insert(iterator __position, const value_type& __x);
1301#endif
1302
1303#if __cplusplus >= 201103L
1304 /**
1305 * @brief Inserts given rvalue into %list before specified iterator.
1306 * @param __position A const_iterator into the %list.
1307 * @param __x Data to be inserted.
1308 * @return An iterator that points to the inserted data.
1309 *
1310 * This function will insert a copy of the given rvalue before
1311 * the specified location. Due to the nature of a %list this
1312 * operation can be done in constant time, and does not
1313 * invalidate iterators and references.
1314 */
1315 iterator
1316 insert(const_iterator __position, value_type&& __x)
1317 { return emplace(__position, std::move(__x)); }
1318
1319 /**
1320 * @brief Inserts the contents of an initializer_list into %list
1321 * before specified const_iterator.
1322 * @param __p A const_iterator into the %list.
1323 * @param __l An initializer_list of value_type.
1324 * @return An iterator pointing to the first element inserted
1325 * (or __position).
1326 *
1327 * This function will insert copies of the data in the
1328 * initializer_list @a l into the %list before the location
1329 * specified by @a p.
1330 *
1331 * This operation is linear in the number of elements inserted and
1332 * does not invalidate iterators and references.
1333 */
1334 iterator
1335 insert(const_iterator __p, initializer_list<value_type> __l)
1336 { return this->insert(__p, __l.begin(), __l.end()); }
1337#endif
1338
1339#if __cplusplus >= 201103L
1340 /**
1341 * @brief Inserts a number of copies of given data into the %list.
1342 * @param __position A const_iterator into the %list.
1343 * @param __n Number of elements to be inserted.
1344 * @param __x Data to be inserted.
1345 * @return An iterator pointing to the first element inserted
1346 * (or __position).
1347 *
1348 * This function will insert a specified number of copies of the
1349 * given data before the location specified by @a position.
1350 *
1351 * This operation is linear in the number of elements inserted and
1352 * does not invalidate iterators and references.
1353 */
1354 iterator
1355 insert(const_iterator __position, size_type __n, const value_type& __x);
1356#else
1357 /**
1358 * @brief Inserts a number of copies of given data into the %list.
1359 * @param __position An iterator into the %list.
1360 * @param __n Number of elements to be inserted.
1361 * @param __x Data to be inserted.
1362 *
1363 * This function will insert a specified number of copies of the
1364 * given data before the location specified by @a position.
1365 *
1366 * This operation is linear in the number of elements inserted and
1367 * does not invalidate iterators and references.
1368 */
1369 void
1370 insert(iterator __position, size_type __n, const value_type& __x)
1371 {
1372 list __tmp(__n, __x, get_allocator());
1373 splice(__position, __tmp);
1374 }
1375#endif
1376
1377#if __cplusplus >= 201103L
1378 /**
1379 * @brief Inserts a range into the %list.
1380 * @param __position A const_iterator into the %list.
1381 * @param __first An input iterator.
1382 * @param __last An input iterator.
1383 * @return An iterator pointing to the first element inserted
1384 * (or __position).
1385 *
1386 * This function will insert copies of the data in the range [@a
1387 * first,@a last) into the %list before the location specified by
1388 * @a position.
1389 *
1390 * This operation is linear in the number of elements inserted and
1391 * does not invalidate iterators and references.
1392 */
1393 template<typename _InputIterator,
1394 typename = std::_RequireInputIter<_InputIterator>>
1395 iterator
1396 insert(const_iterator __position, _InputIterator __first,
1397 _InputIterator __last);
1398#else
1399 /**
1400 * @brief Inserts a range into the %list.
1401 * @param __position An iterator into the %list.
1402 * @param __first An input iterator.
1403 * @param __last An input iterator.
1404 *
1405 * This function will insert copies of the data in the range [@a
1406 * first,@a last) into the %list before the location specified by
1407 * @a position.
1408 *
1409 * This operation is linear in the number of elements inserted and
1410 * does not invalidate iterators and references.
1411 */
1412 template<typename _InputIterator>
1413 void
1414 insert(iterator __position, _InputIterator __first,
1415 _InputIterator __last)
1416 {
1417 list __tmp(__first, __last, get_allocator());
1418 splice(__position, __tmp);
1419 }
1420#endif
1421
1422 /**
1423 * @brief Remove element at given position.
1424 * @param __position Iterator pointing to element to be erased.
1425 * @return An iterator pointing to the next element (or end()).
1426 *
1427 * This function will erase the element at the given position and thus
1428 * shorten the %list by one.
1429 *
1430 * Due to the nature of a %list this operation can be done in
1431 * constant time, and only invalidates iterators/references to
1432 * the element being removed. The user is also cautioned that
1433 * this function only erases the element, and that if the element
1434 * is itself a pointer, the pointed-to memory is not touched in
1435 * any way. Managing the pointer is the user's responsibility.
1436 */
1437 iterator
1438#if __cplusplus >= 201103L
1439 erase(const_iterator __position) noexcept;
1440#else
1441 erase(iterator __position);
1442#endif
1443
1444 /**
1445 * @brief Remove a range of elements.
1446 * @param __first Iterator pointing to the first element to be erased.
1447 * @param __last Iterator pointing to one past the last element to be
1448 * erased.
1449 * @return An iterator pointing to the element pointed to by @a last
1450 * prior to erasing (or end()).
1451 *
1452 * This function will erase the elements in the range @a
1453 * [first,last) and shorten the %list accordingly.
1454 *
1455 * This operation is linear time in the size of the range and only
1456 * invalidates iterators/references to the element being removed.
1457 * The user is also cautioned that this function only erases the
1458 * elements, and that if the elements themselves are pointers, the
1459 * pointed-to memory is not touched in any way. Managing the pointer
1460 * is the user's responsibility.
1461 */
1462 iterator
1463#if __cplusplus >= 201103L
1464 erase(const_iterator __first, const_iterator __last) noexcept
1465#else
1466 erase(iterator __first, iterator __last)
1467#endif
1468 {
1469 while (__first != __last)
1470 __first = erase(__first);
1471 return __last._M_const_cast();
1472 }
1473
1474 /**
1475 * @brief Swaps data with another %list.
1476 * @param __x A %list of the same element and allocator types.
1477 *
1478 * This exchanges the elements between two lists in constant
1479 * time. Note that the global std::swap() function is
1480 * specialized such that std::swap(l1,l2) will feed to this
1481 * function.
1482 *
1483 * Whether the allocators are swapped depends on the allocator traits.
1484 */
1485 void
1486 swap(list& __x) _GLIBCXX_NOEXCEPT
1487 {
1488 __detail::_List_node_base::swap(this->_M_impl._M_node,
1489 __x._M_impl._M_node);
1490
1491 size_t __xsize = __x._M_get_size();
1492 __x._M_set_size(this->_M_get_size());
1493 this->_M_set_size(__xsize);
1494
1495 _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),
1496 __x._M_get_Node_allocator());
1497 }
1498
1499 /**
1500 * Erases all the elements. Note that this function only erases
1501 * the elements, and that if the elements themselves are
1502 * pointers, the pointed-to memory is not touched in any way.
1503 * Managing the pointer is the user's responsibility.
1504 */
1505 void
1506 clear() _GLIBCXX_NOEXCEPT
1507 {
1508 _Base::_M_clear();
1509 _Base::_M_init();
1510 }
1511
1512 // [23.2.2.4] list operations
1513 /**
1514 * @brief Insert contents of another %list.
1515 * @param __position Iterator referencing the element to insert before.
1516 * @param __x Source list.
1517 *
1518 * The elements of @a __x are inserted in constant time in front of
1519 * the element referenced by @a __position. @a __x becomes an empty
1520 * list.
1521 *
1522 * Requires this != @a __x.
1523 */
1524 void
1525#if __cplusplus >= 201103L
1526 splice(const_iterator __position, list&& __x) noexcept
1527#else
1528 splice(iterator __position, list& __x)
1529#endif
1530 {
1531 if (!__x.empty())
1532 {
1533 _M_check_equal_allocators(__x);
1534
1535 this->_M_transfer(__position._M_const_cast(),
1536 __x.begin(), __x.end());
1537
1538 this->_M_inc_size(__x._M_get_size());
1539 __x._M_set_size(0);
1540 }
1541 }
1542
1543#if __cplusplus >= 201103L
1544 void
1545 splice(const_iterator __position, list& __x) noexcept
1546 { splice(__position, std::move(__x)); }
1547#endif
1548
1549#if __cplusplus >= 201103L
1550 /**
1551 * @brief Insert element from another %list.
1552 * @param __position Const_iterator referencing the element to
1553 * insert before.
1554 * @param __x Source list.
1555 * @param __i Const_iterator referencing the element to move.
1556 *
1557 * Removes the element in list @a __x referenced by @a __i and
1558 * inserts it into the current list before @a __position.
1559 */
1560 void
1561 splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
1562#else
1563 /**
1564 * @brief Insert element from another %list.
1565 * @param __position Iterator referencing the element to insert before.
1566 * @param __x Source list.
1567 * @param __i Iterator referencing the element to move.
1568 *
1569 * Removes the element in list @a __x referenced by @a __i and
1570 * inserts it into the current list before @a __position.
1571 */
1572 void
1573 splice(iterator __position, list& __x, iterator __i)
1574#endif
1575 {
1576 iterator __j = __i._M_const_cast();
1577 ++__j;
1578 if (__position == __i || __position == __j)
1579 return;
1580
1581 if (this != std::__addressof(__x))
1582 _M_check_equal_allocators(__x);
1583
1584 this->_M_transfer(__position._M_const_cast(),
1585 __i._M_const_cast(), __j);
1586
1587 this->_M_inc_size(1);
1588 __x._M_dec_size(1);
1589 }
1590
1591#if __cplusplus >= 201103L
1592 /**
1593 * @brief Insert element from another %list.
1594 * @param __position Const_iterator referencing the element to
1595 * insert before.
1596 * @param __x Source list.
1597 * @param __i Const_iterator referencing the element to move.
1598 *
1599 * Removes the element in list @a __x referenced by @a __i and
1600 * inserts it into the current list before @a __position.
1601 */
1602 void
1603 splice(const_iterator __position, list& __x, const_iterator __i) noexcept
1604 { splice(__position, std::move(__x), __i); }
1605#endif
1606
1607#if __cplusplus >= 201103L
1608 /**
1609 * @brief Insert range from another %list.
1610 * @param __position Const_iterator referencing the element to
1611 * insert before.
1612 * @param __x Source list.
1613 * @param __first Const_iterator referencing the start of range in x.
1614 * @param __last Const_iterator referencing the end of range in x.
1615 *
1616 * Removes elements in the range [__first,__last) and inserts them
1617 * before @a __position in constant time.
1618 *
1619 * Undefined if @a __position is in [__first,__last).
1620 */
1621 void
1622 splice(const_iterator __position, list&& __x, const_iterator __first,
1623 const_iterator __last) noexcept
1624#else
1625 /**
1626 * @brief Insert range from another %list.
1627 * @param __position Iterator referencing the element to insert before.
1628 * @param __x Source list.
1629 * @param __first Iterator referencing the start of range in x.
1630 * @param __last Iterator referencing the end of range in x.
1631 *
1632 * Removes elements in the range [__first,__last) and inserts them
1633 * before @a __position in constant time.
1634 *
1635 * Undefined if @a __position is in [__first,__last).
1636 */
1637 void
1638 splice(iterator __position, list& __x, iterator __first,
1639 iterator __last)
1640#endif
1641 {
1642 if (__first != __last)
1643 {
1644 if (this != std::__addressof(__x))
1645 _M_check_equal_allocators(__x);
1646
1647 size_t __n = _S_distance(__first, __last);
1648 this->_M_inc_size(__n);
1649 __x._M_dec_size(__n);
1650
1651 this->_M_transfer(__position._M_const_cast(),
1652 __first._M_const_cast(),
1653 __last._M_const_cast());
1654 }
1655 }
1656
1657#if __cplusplus >= 201103L
1658 /**
1659 * @brief Insert range from another %list.
1660 * @param __position Const_iterator referencing the element to
1661 * insert before.
1662 * @param __x Source list.
1663 * @param __first Const_iterator referencing the start of range in x.
1664 * @param __last Const_iterator referencing the end of range in x.
1665 *
1666 * Removes elements in the range [__first,__last) and inserts them
1667 * before @a __position in constant time.
1668 *
1669 * Undefined if @a __position is in [__first,__last).
1670 */
1671 void
1672 splice(const_iterator __position, list& __x, const_iterator __first,
1673 const_iterator __last) noexcept
1674 { splice(__position, std::move(__x), __first, __last); }
1675#endif
1676
1677 /**
1678 * @brief Remove all elements equal to value.
1679 * @param __value The value to remove.
1680 *
1681 * Removes every element in the list equal to @a value.
1682 * Remaining elements stay in list order. Note that this
1683 * function only erases the elements, and that if the elements
1684 * themselves are pointers, the pointed-to memory is not
1685 * touched in any way. Managing the pointer is the user's
1686 * responsibility.
1687 */
1688 void
1689 remove(const _Tp& __value);
1690
1691 /**
1692 * @brief Remove all elements satisfying a predicate.
1693 * @tparam _Predicate Unary predicate function or object.
1694 *
1695 * Removes every element in the list for which the predicate
1696 * returns true. Remaining elements stay in list order. Note
1697 * that this function only erases the elements, and that if the
1698 * elements themselves are pointers, the pointed-to memory is
1699 * not touched in any way. Managing the pointer is the user's
1700 * responsibility.
1701 */
1702 template<typename _Predicate>
1703 void
1704 remove_if(_Predicate);
1705
1706 /**
1707 * @brief Remove consecutive duplicate elements.
1708 *
1709 * For each consecutive set of elements with the same value,
1710 * remove all but the first one. Remaining elements stay in
1711 * list order. Note that this function only erases the
1712 * elements, and that if the elements themselves are pointers,
1713 * the pointed-to memory is not touched in any way. Managing
1714 * the pointer is the user's responsibility.
1715 */
1716 void
1717 unique();
1718
1719 /**
1720 * @brief Remove consecutive elements satisfying a predicate.
1721 * @tparam _BinaryPredicate Binary predicate function or object.
1722 *
1723 * For each consecutive set of elements [first,last) that
1724 * satisfy predicate(first,i) where i is an iterator in
1725 * [first,last), remove all but the first one. Remaining
1726 * elements stay in list order. Note that this function only
1727 * erases the elements, and that if the elements themselves are
1728 * pointers, the pointed-to memory is not touched in any way.
1729 * Managing the pointer is the user's responsibility.
1730 */
1731 template<typename _BinaryPredicate>
1732 void
1733 unique(_BinaryPredicate);
1734
1735 /**
1736 * @brief Merge sorted lists.
1737 * @param __x Sorted list to merge.
1738 *
1739 * Assumes that both @a __x and this list are sorted according to
1740 * operator<(). Merges elements of @a __x into this list in
1741 * sorted order, leaving @a __x empty when complete. Elements in
1742 * this list precede elements in @a __x that are equal.
1743 */
1744#if __cplusplus >= 201103L
1745 void
1746 merge(list&& __x);
1747
1748 void
1749 merge(list& __x)
1750 { merge(std::move(__x)); }
1751#else
1752 void
1753 merge(list& __x);
1754#endif
1755
1756 /**
1757 * @brief Merge sorted lists according to comparison function.
1758 * @tparam _StrictWeakOrdering Comparison function defining
1759 * sort order.
1760 * @param __x Sorted list to merge.
1761 * @param __comp Comparison functor.
1762 *
1763 * Assumes that both @a __x and this list are sorted according to
1764 * StrictWeakOrdering. Merges elements of @a __x into this list
1765 * in sorted order, leaving @a __x empty when complete. Elements
1766 * in this list precede elements in @a __x that are equivalent
1767 * according to StrictWeakOrdering().
1768 */
1769#if __cplusplus >= 201103L
1770 template<typename _StrictWeakOrdering>
1771 void
1772 merge(list&& __x, _StrictWeakOrdering __comp);
1773
1774 template<typename _StrictWeakOrdering>
1775 void
1776 merge(list& __x, _StrictWeakOrdering __comp)
1777 { merge(std::move(__x), __comp); }
1778#else
1779 template<typename _StrictWeakOrdering>
1780 void
1781 merge(list& __x, _StrictWeakOrdering __comp);
1782#endif
1783
1784 /**
1785 * @brief Reverse the elements in list.
1786 *
1787 * Reverse the order of elements in the list in linear time.
1788 */
1789 void
1790 reverse() _GLIBCXX_NOEXCEPT
1791 { this->_M_impl._M_node._M_reverse(); }
1792
1793 /**
1794 * @brief Sort the elements.
1795 *
1796 * Sorts the elements of this list in NlogN time. Equivalent
1797 * elements remain in list order.
1798 */
1799 void
1800 sort();
1801
1802 /**
1803 * @brief Sort the elements according to comparison function.
1804 *
1805 * Sorts the elements of this list in NlogN time. Equivalent
1806 * elements remain in list order.
1807 */
1808 template<typename _StrictWeakOrdering>
1809 void
1810 sort(_StrictWeakOrdering);
1811
1812 protected:
1813 // Internal constructor functions follow.
1814
1815 // Called by the range constructor to implement [23.1.1]/9
1816
1817 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1818 // 438. Ambiguity in the "do the right thing" clause
1819 template<typename _Integer>
1820 void
1821 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1822 { _M_fill_initialize(static_cast<size_type>(__n), __x); }
1823
1824 // Called by the range constructor to implement [23.1.1]/9
1825 template<typename _InputIterator>
1826 void
1827 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1828 __false_type)
1829 {
1830 for (; __first != __last; ++__first)
1831#if __cplusplus >= 201103L
1832 emplace_back(*__first);
1833#else
1834 push_back(*__first);
1835#endif
1836 }
1837
1838 // Called by list(n,v,a), and the range constructor when it turns out
1839 // to be the same thing.
1840 void
1841 _M_fill_initialize(size_type __n, const value_type& __x)
1842 {
1843 for (; __n; --__n)
1844 push_back(__x);
1845 }
1846
1847#if __cplusplus >= 201103L
1848 // Called by list(n).
1849 void
1850 _M_default_initialize(size_type __n)
1851 {
1852 for (; __n; --__n)
1853 emplace_back();
1854 }
1855
1856 // Called by resize(sz).
1857 void
1858 _M_default_append(size_type __n);
1859#endif
1860
1861 // Internal assign functions follow.
1862
1863 // Called by the range assign to implement [23.1.1]/9
1864
1865 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1866 // 438. Ambiguity in the "do the right thing" clause
1867 template<typename _Integer>
1868 void
1869 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1870 { _M_fill_assign(__n, __val); }
1871
1872 // Called by the range assign to implement [23.1.1]/9
1873 template<typename _InputIterator>
1874 void
1875 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1876 __false_type);
1877
1878 // Called by assign(n,t), and the range assign when it turns out
1879 // to be the same thing.
1880 void
1881 _M_fill_assign(size_type __n, const value_type& __val);
1882
1883
1884 // Moves the elements from [first,last) before position.
1885 void
1886 _M_transfer(iterator __position, iterator __first, iterator __last)
1887 { __position._M_node->_M_transfer(__first._M_node, __last._M_node); }
1888
1889 // Inserts new element at position given and with value given.
1890#if __cplusplus < 201103L
1891 void
1892 _M_insert(iterator __position, const value_type& __x)
1893 {
1894 _Node* __tmp = _M_create_node(__x);
1895 __tmp->_M_hook(__position._M_node);
1896 this->_M_inc_size(1);
1897 }
1898#else
1899 template<typename... _Args>
1900 void
1901 _M_insert(iterator __position, _Args&&... __args)
1902 {
1903 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
1904 __tmp->_M_hook(__position._M_node);
1905 this->_M_inc_size(1);
1906 }
1907#endif
1908
1909 // Erases element at position given.
1910 void
1911 _M_erase(iterator __position) _GLIBCXX_NOEXCEPT
1912 {
1913 this->_M_dec_size(1);
1914 __position._M_node->_M_unhook();
1915 _Node* __n = static_cast<_Node*>(__position._M_node);
1916#if __cplusplus >= 201103L
1917 _Node_alloc_traits::destroy(_M_get_Node_allocator(), __n->_M_valptr());
1918#else
1919 _Tp_alloc_type(_M_get_Node_allocator()).destroy(__n->_M_valptr());
1920#endif
1921
1922 _M_put_node(__n);
1923 }
1924
1925 // To implement the splice (and merge) bits of N1599.
1926 void
1927 _M_check_equal_allocators(list& __x) _GLIBCXX_NOEXCEPT
1928 {
1929 if (std::__alloc_neq<typename _Base::_Node_alloc_type>::
1930 _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()))
1931 __builtin_abort();
1932 }
1933
1934 // Used to implement resize.
1935 const_iterator
1936 _M_resize_pos(size_type& __new_size) const;
1937
1938#if __cplusplus >= 201103L
1939 void
1940 _M_move_assign(list&& __x, true_type) noexcept
1941 {
1942 this->_M_clear();
1943 this->_M_move_nodes(std::move(__x));
1944 std::__alloc_on_move(this->_M_get_Node_allocator(),
1945 __x._M_get_Node_allocator());
1946 }
1947
1948 void
1949 _M_move_assign(list&& __x, false_type)
1950 {
1951 if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator())
1952 _M_move_assign(std::move(__x), true_type{});
1953 else
1954 // The rvalue's allocator cannot be moved, or is not equal,
1955 // so we need to individually move each element.
1956 _M_assign_dispatch(std::__make_move_if_noexcept_iterator(__x.begin()),
1957 std::__make_move_if_noexcept_iterator(__x.end()),
1958 __false_type{});
1959 }
1960#endif
1961 };
1962
1963#if __cpp_deduction_guides >= 201606
1964 template<typename _InputIterator, typename _ValT
1965 = typename iterator_traits<_InputIterator>::value_type,
1966 typename _Allocator = allocator<_ValT>,
1967 typename = _RequireInputIter<_InputIterator>,
1968 typename = _RequireAllocator<_Allocator>>
1969 list(_InputIterator, _InputIterator, _Allocator = _Allocator())
1970 -> list<_ValT, _Allocator>;
1971#endif
1972
1973_GLIBCXX_END_NAMESPACE_CXX11
1974
1975 /**
1976 * @brief List equality comparison.
1977 * @param __x A %list.
1978 * @param __y A %list of the same type as @a __x.
1979 * @return True iff the size and elements of the lists are equal.
1980 *
1981 * This is an equivalence relation. It is linear in the size of
1982 * the lists. Lists are considered equivalent if their sizes are
1983 * equal, and if corresponding elements compare equal.
1984 */
1985 template<typename _Tp, typename _Alloc>
1986 inline bool
1987 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
1988 {
1989#if _GLIBCXX_USE_CXX11_ABI
1990 if (__x.size() != __y.size())
1991 return false;
1992#endif
1993
1994 typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
1995 const_iterator __end1 = __x.end();
1996 const_iterator __end2 = __y.end();
1997
1998 const_iterator __i1 = __x.begin();
1999 const_iterator __i2 = __y.begin();
2000 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
2001 {
2002 ++__i1;
2003 ++__i2;
2004 }
2005 return __i1 == __end1 && __i2 == __end2;
2006 }
2007
2008 /**
2009 * @brief List ordering relation.
2010 * @param __x A %list.
2011 * @param __y A %list of the same type as @a __x.
2012 * @return True iff @a __x is lexicographically less than @a __y.
2013 *
2014 * This is a total ordering relation. It is linear in the size of the
2015 * lists. The elements must be comparable with @c <.
2016 *
2017 * See std::lexicographical_compare() for how the determination is made.
2018 */
2019 template<typename _Tp, typename _Alloc>
2020 inline bool
2021 operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2022 { return std::lexicographical_compare(__x.begin(), __x.end(),
2023 __y.begin(), __y.end()); }
2024
2025 /// Based on operator==
2026 template<typename _Tp, typename _Alloc>
2027 inline bool
2028 operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2029 { return !(__x == __y); }
2030
2031 /// Based on operator<
2032 template<typename _Tp, typename _Alloc>
2033 inline bool
2034 operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2035 { return __y < __x; }
2036
2037 /// Based on operator<
2038 template<typename _Tp, typename _Alloc>
2039 inline bool
2040 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2041 { return !(__y < __x); }
2042
2043 /// Based on operator<
2044 template<typename _Tp, typename _Alloc>
2045 inline bool
2046 operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2047 { return !(__x < __y); }
2048
2049 /// See std::list::swap().
2050 template<typename _Tp, typename _Alloc>
2051 inline void
2052 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
2053 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
2054 { __x.swap(__y); }
2055
2056_GLIBCXX_END_NAMESPACE_CONTAINER
2057
2058#if _GLIBCXX_USE_CXX11_ABI
2059
2060 // Detect when distance is used to compute the size of the whole list.
2061 template<typename _Tp>
2062 inline ptrdiff_t
2063 __distance(_GLIBCXX_STD_C::_List_iterator<_Tp> __first,
2064 _GLIBCXX_STD_C::_List_iterator<_Tp> __last,
2065 input_iterator_tag __tag)
2066 {
2067 typedef _GLIBCXX_STD_C::_List_const_iterator<_Tp> _CIter;
2068 return std::__distance(_CIter(__first), _CIter(__last), __tag);
2069 }
2070
2071 template<typename _Tp>
2072 inline ptrdiff_t
2073 __distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp> __first,
2074 _GLIBCXX_STD_C::_List_const_iterator<_Tp> __last,
2075 input_iterator_tag)
2076 {
2077 typedef __detail::_List_node_header _Sentinel;
2078 _GLIBCXX_STD_C::_List_const_iterator<_Tp> __beyond = __last;
2079 ++__beyond;
2080 const bool __whole = __first == __beyond;
2081 if (__builtin_constant_p (__whole) && __whole)
2082 return static_cast<const _Sentinel*>(__last._M_node)->_M_size;
2083
2084 ptrdiff_t __n = 0;
2085 while (__first != __last)
2086 {
2087 ++__first;
2088 ++__n;
2089 }
2090 return __n;
2091 }
2092#endif
2093
2094_GLIBCXX_END_NAMESPACE_VERSION
2095} // namespace std
2096
2097#endif /* _STL_LIST_H */
2098