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