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