Subversion Repositories Kolibri OS

// List implementation -*- C++ -*-

// Copyright (C) 2001-2013 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 3, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// .

/*

 *

 * Copyright (c) 1994

 * Hewlett-Packard Company

 *

 * Permission to use, copy, modify, distribute and sell this software

 * and its documentation for any purpose is hereby granted without fee,

 * provided that the above copyright notice appear in all copies and

 * that both that copyright notice and this permission notice appear

 * in supporting documentation.  Hewlett-Packard Company makes no

 * representations about the suitability of this software for any

 * purpose.  It is provided "as is" without express or implied warranty.

 *

 *

 * Copyright (c) 1996,1997

 * Silicon Graphics Computer Systems, Inc.

 *

 * Permission to use, copy, modify, distribute and sell this software

 * and its documentation for any purpose is hereby granted without fee,

 * provided that the above copyright notice appear in all copies and

 * that both that copyright notice and this permission notice appear

 * in supporting documentation.  Silicon Graphics makes no

 * representations about the suitability of this software for any

 * purpose.  It is provided "as is" without express or implied warranty.

 */

/** @file bits/stl_list.h

 *  This is an internal header file, included by other library headers.

 *  Do not attempt to use it directly. @headername{list}

 */

#ifndef _STL_LIST_H

#define _STL_LIST_H 1

#include 

#if __cplusplus >= 201103L

#include 

#endif

namespace std _GLIBCXX_VISIBILITY(default)

{

  namespace __detail

  {

  _GLIBCXX_BEGIN_NAMESPACE_VERSION

    // Supporting structures are split into common and templated

    // types; the latter publicly inherits from the former in an

    // effort to reduce code duplication.  This results in some

    // "needless" static_cast'ing later on, but it's all safe

    // downcasting.

    /// Common part of a node in the %list.

    struct _List_node_base

    {

      _List_node_base* _M_next;

      _List_node_base* _M_prev;

      static void

      swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT;

      void

      _M_transfer(_List_node_base* const __first,

		  _List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT;

      void

      _M_reverse() _GLIBCXX_USE_NOEXCEPT;

      void

      _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;

      void

      _M_unhook() _GLIBCXX_USE_NOEXCEPT;

    };

  _GLIBCXX_END_NAMESPACE_VERSION

  } // namespace detail

_GLIBCXX_BEGIN_NAMESPACE_CONTAINER

  /// An actual node in the %list.

  template

    struct _List_node : public __detail::_List_node_base

    {

      ///< User's data.

      _Tp _M_data;

#if __cplusplus >= 201103L

      template

        _List_node(_Args&&... __args)

	: __detail::_List_node_base(), _M_data(std::forward<_Args>(__args)...)

        { }

#endif

    };

  /**

   *  @brief A list::iterator.

   *

   *  All the functions are op overloads.

  */

  template

    struct _List_iterator

    {

      typedef _List_iterator<_Tp>                _Self;

      typedef _List_node<_Tp>                    _Node;

      typedef ptrdiff_t                          difference_type;

      typedef std::bidirectional_iterator_tag    iterator_category;

      typedef _Tp                                value_type;

      typedef _Tp*                               pointer;

      typedef _Tp&                               reference;

      _List_iterator()

      : _M_node() { }

      explicit

      _List_iterator(__detail::_List_node_base* __x)

      : _M_node(__x) { }

      // Must downcast from _List_node_base to _List_node to get to _M_data.

      reference

      operator*() const

      { return static_cast<_Node*>(_M_node)->_M_data; }

      pointer

      operator->() const

      { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); }

      _Self&

      operator++()

      {

	_M_node = _M_node->_M_next;

	return *this;

      }

      _Self

      operator++(int)

      {

	_Self __tmp = *this;

	_M_node = _M_node->_M_next;

	return __tmp;

      }

      _Self&

      operator--()

      {

	_M_node = _M_node->_M_prev;

	return *this;

      }

      _Self

      operator--(int)

      {

	_Self __tmp = *this;

	_M_node = _M_node->_M_prev;

	return __tmp;

      }

      bool

      operator==(const _Self& __x) const

      { return _M_node == __x._M_node; }

      bool

      operator!=(const _Self& __x) const

      { return _M_node != __x._M_node; }

      // The only member points to the %list element.

      __detail::_List_node_base* _M_node;

    };

  /**

   *  @brief A list::const_iterator.

   *

   *  All the functions are op overloads.

  */

  template

    struct _List_const_iterator

    {

      typedef _List_const_iterator<_Tp>          _Self;

      typedef const _List_node<_Tp>              _Node;

      typedef _List_iterator<_Tp>                iterator;

      typedef ptrdiff_t                          difference_type;

      typedef std::bidirectional_iterator_tag    iterator_category;

      typedef _Tp                                value_type;

      typedef const _Tp*                         pointer;

      typedef const _Tp&                         reference;

      _List_const_iterator()

      : _M_node() { }

      explicit

      _List_const_iterator(const __detail::_List_node_base* __x)

      : _M_node(__x) { }

      _List_const_iterator(const iterator& __x)

      : _M_node(__x._M_node) { }

      // Must downcast from List_node_base to _List_node to get to

      // _M_data.

      reference

      operator*() const

      { return static_cast<_Node*>(_M_node)->_M_data; }

      pointer

      operator->() const

      { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); }

      _Self&

      operator++()

      {

	_M_node = _M_node->_M_next;

	return *this;

      }

      _Self

      operator++(int)

      {

	_Self __tmp = *this;

	_M_node = _M_node->_M_next;

	return __tmp;

      }

      _Self&

      operator--()

      {

	_M_node = _M_node->_M_prev;

	return *this;

      }

      _Self

      operator--(int)

      {

	_Self __tmp = *this;

	_M_node = _M_node->_M_prev;

	return __tmp;

      }

      bool

      operator==(const _Self& __x) const

      { return _M_node == __x._M_node; }

      bool

      operator!=(const _Self& __x) const

      { return _M_node != __x._M_node; }

      // The only member points to the %list element.

      const __detail::_List_node_base* _M_node;

    };

  template

    inline bool

    operator==(const _List_iterator<_Val>& __x,

	       const _List_const_iterator<_Val>& __y)

    { return __x._M_node == __y._M_node; }

  template

    inline bool

    operator!=(const _List_iterator<_Val>& __x,

               const _List_const_iterator<_Val>& __y)

    { return __x._M_node != __y._M_node; }

  /// See bits/stl_deque.h's _Deque_base for an explanation.

  template

    class _List_base

    {

    protected:

      // NOTA BENE

      // The stored instance is not actually of "allocator_type"'s

      // type.  Instead we rebind the type to

      // Allocator>, which according to [20.1.5]/4

      // should probably be the same.  List_node is not the same

      // size as Tp (it's two pointers larger), and specializations on

      // Tp may go unused because List_node is being bound

      // instead.

      //

      // We put this to the test in the constructors and in

      // get_allocator, where we use conversions between

      // allocator_type and _Node_alloc_type. The conversion is

      // required by table 32 in [20.1.5].

      typedef typename _Alloc::template rebind<_List_node<_Tp> >::other

        _Node_alloc_type;

      typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;

      struct _List_impl

      : public _Node_alloc_type

      {

	__detail::_List_node_base _M_node;

	_List_impl()

	: _Node_alloc_type(), _M_node()

	{ }

	_List_impl(const _Node_alloc_type& __a)

	: _Node_alloc_type(__a), _M_node()

	{ }

#if __cplusplus >= 201103L

	_List_impl(_Node_alloc_type&& __a)

	: _Node_alloc_type(std::move(__a)), _M_node()

	{ }

#endif

      };

      _List_impl _M_impl;

      _List_node<_Tp>*

      _M_get_node()

      { return _M_impl._Node_alloc_type::allocate(1); }

      void

      _M_put_node(_List_node<_Tp>* __p)

      { _M_impl._Node_alloc_type::deallocate(__p, 1); }

  public:

      typedef _Alloc allocator_type;

      _Node_alloc_type&

      _M_get_Node_allocator() _GLIBCXX_NOEXCEPT

      { return *static_cast<_Node_alloc_type*>(&_M_impl); }

      const _Node_alloc_type&

      _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT

      { return *static_cast(&_M_impl); }

      _Tp_alloc_type

      _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT

      { return _Tp_alloc_type(_M_get_Node_allocator()); }

      allocator_type

      get_allocator() const _GLIBCXX_NOEXCEPT

      { return allocator_type(_M_get_Node_allocator()); }

      _List_base()

      : _M_impl()

      { _M_init(); }

      _List_base(const _Node_alloc_type& __a)

      : _M_impl(__a)

      { _M_init(); }

#if __cplusplus >= 201103L

      _List_base(_List_base&& __x)

      : _M_impl(std::move(__x._M_get_Node_allocator()))

      {

	_M_init();

	__detail::_List_node_base::swap(_M_impl._M_node, __x._M_impl._M_node);

      }

#endif

      // This is what actually destroys the list.

      ~_List_base() _GLIBCXX_NOEXCEPT

      { _M_clear(); }

      void

      _M_clear();

      void

      _M_init()

      {

        this->_M_impl._M_node._M_next = &this->_M_impl._M_node;

        this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;

      }

    };

  /**

   *  @brief A standard container with linear time access to elements,

   *  and fixed time insertion/deletion at any point in the sequence.

   *

   *  @ingroup sequences

   *

   *  @tparam _Tp  Type of element.

   *  @tparam _Alloc  Allocator type, defaults to allocator<_Tp>.

   *

   *  Meets the requirements of a container, a

   *  reversible container, and a

   *  sequence, including the

   *  optional sequence requirements with the

   *  %exception of @c at and @c operator[].

   *

   *  This is a @e doubly @e linked %list.  Traversal up and down the

   *  %list requires linear time, but adding and removing elements (or

   *  @e nodes) is done in constant time, regardless of where the

   *  change takes place.  Unlike std::vector and std::deque,

   *  random-access iterators are not provided, so subscripting ( @c

   *  [] ) access is not allowed.  For algorithms which only need

   *  sequential access, this lack makes no difference.

   *

   *  Also unlike the other standard containers, std::list provides

   *  specialized algorithms %unique to linked lists, such as

   *  splicing, sorting, and in-place reversal.

   *

   *  A couple points on memory allocation for list:

   *

   *  First, we never actually allocate a Tp, we allocate

   *  List_node's and trust [20.1.5]/4 to DTRT.  This is to ensure

   *  that after elements from %list are spliced into

   *  %list, destroying the memory of the second %list is a

   *  valid operation, i.e., Alloc1 giveth and Alloc2 taketh away.

   *

   *  Second, a %list conceptually represented as

   *  @code

   *    A <---> B <---> C <---> D

   *  @endcode

   *  is actually circular; a link exists between A and D.  The %list

   *  class holds (as its only data member) a private list::iterator

   *  pointing to @e D, not to @e A!  To get to the head of the %list,

   *  we start at the tail and move forward by one.  When this member

   *  iterator's next/previous pointers refer to itself, the %list is

   *  %empty.

  */

  template >

    class list : protected _List_base<_Tp, _Alloc>

    {

      // concept requirements

      typedef typename _Alloc::value_type                _Alloc_value_type;

      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)

      __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)

      typedef _List_base<_Tp, _Alloc>                    _Base;

      typedef typename _Base::_Tp_alloc_type		 _Tp_alloc_type;

      typedef typename _Base::_Node_alloc_type		 _Node_alloc_type;

    public:

      typedef _Tp                                        value_type;

      typedef typename _Tp_alloc_type::pointer           pointer;

      typedef typename _Tp_alloc_type::const_pointer     const_pointer;

      typedef typename _Tp_alloc_type::reference         reference;

      typedef typename _Tp_alloc_type::const_reference   const_reference;

      typedef _List_iterator<_Tp>                        iterator;

      typedef _List_const_iterator<_Tp>                  const_iterator;

      typedef std::reverse_iterator      const_reverse_iterator;

      typedef std::reverse_iterator            reverse_iterator;

      typedef size_t                                     size_type;

      typedef ptrdiff_t                                  difference_type;

      typedef _Alloc                                     allocator_type;

    protected:

      // Note that pointers-to-_Node's can be ctor-converted to

      // iterator types.

      typedef _List_node<_Tp>				 _Node;

      using _Base::_M_impl;

      using _Base::_M_put_node;

      using _Base::_M_get_node;

      using _Base::_M_get_Tp_allocator;

      using _Base::_M_get_Node_allocator;

      /**

       *  @param  __args  An instance of user data.

       *

       *  Allocates space for a new node and constructs a copy of

       *  @a __args in it.

       */

#if __cplusplus < 201103L

      _Node*

      _M_create_node(const value_type& __x)

      {

	_Node* __p = this->_M_get_node();

	__try

	  {

	    _M_get_Tp_allocator().construct

	      (std::__addressof(__p->_M_data), __x);

	  }

	__catch(...)

	  {

	    _M_put_node(__p);

	    __throw_exception_again;

	  }

	return __p;

      }

#else

      template

        _Node*

        _M_create_node(_Args&&... __args)

	{

	  _Node* __p = this->_M_get_node();

	  __try

	    {

	      _M_get_Node_allocator().construct(__p,

						std::forward<_Args>(__args)...);

	    }

	  __catch(...)

	    {

	      _M_put_node(__p);

	      __throw_exception_again;

	    }

	  return __p;

	}

#endif

    public:

      // [23.2.2.1] construct/copy/destroy

      // (assign() and get_allocator() are also listed in this section)

      /**

       *  @brief  Default constructor creates no elements.

       */

      list()

      : _Base() { }

      /**

       *  @brief  Creates a %list with no elements.

       *  @param  __a  An allocator object.

       */

      explicit

      list(const allocator_type& __a)

      : _Base(_Node_alloc_type(__a)) { }

#if __cplusplus >= 201103L

      /**

       *  @brief  Creates a %list with default constructed elements.

       *  @param  __n  The number of elements to initially create.

       *

       *  This constructor fills the %list with @a __n default

       *  constructed elements.

       */

      explicit

      list(size_type __n)

      : _Base()

      { _M_default_initialize(__n); }

      /**

       *  @brief  Creates a %list with copies of an exemplar element.

       *  @param  __n  The number of elements to initially create.

       *  @param  __value  An element to copy.

       *  @param  __a  An allocator object.

       *

       *  This constructor fills the %list with @a __n copies of @a __value.

       */

      list(size_type __n, const value_type& __value,

	   const allocator_type& __a = allocator_type())

      : _Base(_Node_alloc_type(__a))

      { _M_fill_initialize(__n, __value); }

#else

      /**

       *  @brief  Creates a %list with copies of an exemplar element.

       *  @param  __n  The number of elements to initially create.

       *  @param  __value  An element to copy.

       *  @param  __a  An allocator object.

       *

       *  This constructor fills the %list with @a __n copies of @a __value.

       */

      explicit

      list(size_type __n, const value_type& __value = value_type(),

	   const allocator_type& __a = allocator_type())

      : _Base(_Node_alloc_type(__a))

      { _M_fill_initialize(__n, __value); }

#endif

      /**

       *  @brief  %List copy constructor.

       *  @param  __x  A %list of identical element and allocator types.

       *

       *  The newly-created %list uses a copy of the allocation object used

       *  by @a __x.

       */

      list(const list& __x)

      : _Base(__x._M_get_Node_allocator())

      { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }

#if __cplusplus >= 201103L

      /**

       *  @brief  %List move constructor.

       *  @param  __x  A %list of identical element and allocator types.

       *

       *  The newly-created %list contains the exact contents of @a __x.

       *  The contents of @a __x are a valid, but unspecified %list.

       */

      list(list&& __x) noexcept

      : _Base(std::move(__x)) { }

      /**

       *  @brief  Builds a %list from an initializer_list

       *  @param  __l  An initializer_list of value_type.

       *  @param  __a  An allocator object.

       *

       *  Create a %list consisting of copies of the elements in the

       *  initializer_list @a __l.  This is linear in __l.size().

       */

      list(initializer_list __l,

           const allocator_type& __a = allocator_type())

      : _Base(_Node_alloc_type(__a))

      { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); }

#endif

      /**

       *  @brief  Builds a %list from a range.

       *  @param  __first  An input iterator.

       *  @param  __last  An input iterator.

       *  @param  __a  An allocator object.

       *

       *  Create a %list consisting of copies of the elements from

       *  [@a __first,@a __last).  This is linear in N (where N is

       *  distance(@a __first,@a __last)).

       */

#if __cplusplus >= 201103L

      template

	       typename = std::_RequireInputIter<_InputIterator>>

        list(_InputIterator __first, _InputIterator __last,

	     const allocator_type& __a = allocator_type())

	: _Base(_Node_alloc_type(__a))

        { _M_initialize_dispatch(__first, __last, __false_type()); }

#else

      template

        list(_InputIterator __first, _InputIterator __last,

	     const allocator_type& __a = allocator_type())

	: _Base(_Node_alloc_type(__a))

        {

	  // Check whether it's an integral type.  If so, it's not an iterator.

	  typedef typename std::__is_integer<_InputIterator>::__type _Integral;

	  _M_initialize_dispatch(__first, __last, _Integral());

	}

#endif

      /**

       *  No explicit dtor needed as the _Base dtor takes care of

       *  things.  The _Base dtor only erases the elements, and note

       *  that if the elements themselves are pointers, the pointed-to

       *  memory is not touched in any way.  Managing the pointer is

       *  the user's responsibility.

       */

      /**

       *  @brief  %List assignment operator.

       *  @param  __x  A %list of identical element and allocator types.

       *

       *  All the elements of @a __x are copied, but unlike the copy

       *  constructor, the allocator object is not copied.

       */

      list&

      operator=(const list& __x);

#if __cplusplus >= 201103L

      /**

       *  @brief  %List move assignment operator.

       *  @param  __x  A %list of identical element and allocator types.

       *

       *  The contents of @a __x are moved into this %list (without copying).

       *  @a __x is a valid, but unspecified %list

       */

      list&

      operator=(list&& __x)

      {

	// NB: DR 1204.

	// NB: DR 675.

	this->clear();

	this->swap(__x);

	return *this;

      }

      /**

       *  @brief  %List initializer list assignment operator.

       *  @param  __l  An initializer_list of value_type.

       *

       *  Replace the contents of the %list with copies of the elements

       *  in the initializer_list @a __l.  This is linear in l.size().

       */

      list&

      operator=(initializer_list __l)

      {

	this->assign(__l.begin(), __l.end());

	return *this;

      }

#endif

      /**

       *  @brief  Assigns a given value to a %list.

       *  @param  __n  Number of elements to be assigned.

       *  @param  __val  Value to be assigned.

       *

       *  This function fills a %list with @a __n copies of the given

       *  value.  Note that the assignment completely changes the %list

       *  and that the resulting %list's size is the same as the number

       *  of elements assigned.  Old data may be lost.

       */

      void

      assign(size_type __n, const value_type& __val)

      { _M_fill_assign(__n, __val); }

      /**

       *  @brief  Assigns a range to a %list.

       *  @param  __first  An input iterator.

       *  @param  __last   An input iterator.

       *

       *  This function fills a %list with copies of the elements in the

       *  range [@a __first,@a __last).

       *

       *  Note that the assignment completely changes the %list and

       *  that the resulting %list's size is the same as the number of

       *  elements assigned.  Old data may be lost.

       */

#if __cplusplus >= 201103L

      template

	       typename = std::_RequireInputIter<_InputIterator>>

        void

        assign(_InputIterator __first, _InputIterator __last)

        { _M_assign_dispatch(__first, __last, __false_type()); }

#else

      template

        void

        assign(_InputIterator __first, _InputIterator __last)

        {

	  // Check whether it's an integral type.  If so, it's not an iterator.

	  typedef typename std::__is_integer<_InputIterator>::__type _Integral;

	  _M_assign_dispatch(__first, __last, _Integral());

	}

#endif

#if __cplusplus >= 201103L

      /**

       *  @brief  Assigns an initializer_list to a %list.

       *  @param  __l  An initializer_list of value_type.

       *

       *  Replace the contents of the %list with copies of the elements

       *  in the initializer_list @a __l.  This is linear in __l.size().

       */

      void

      assign(initializer_list __l)

      { this->assign(__l.begin(), __l.end()); }

#endif

      /// Get a copy of the memory allocation object.

      allocator_type

      get_allocator() const _GLIBCXX_NOEXCEPT

      { return _Base::get_allocator(); }

      // iterators

      /**

       *  Returns a read/write iterator that points to the first element in the

       *  %list.  Iteration is done in ordinary element order.

       */

      iterator

      begin() _GLIBCXX_NOEXCEPT

      { return iterator(this->_M_impl._M_node._M_next); }

      /**

       *  Returns a read-only (constant) iterator that points to the

       *  first element in the %list.  Iteration is done in ordinary

       *  element order.

       */

      const_iterator

      begin() const _GLIBCXX_NOEXCEPT

      { return const_iterator(this->_M_impl._M_node._M_next); }

      /**

       *  Returns a read/write iterator that points one past the last

       *  element in the %list.  Iteration is done in ordinary element

       *  order.

       */

      iterator

      end() _GLIBCXX_NOEXCEPT

      { return iterator(&this->_M_impl._M_node); }

      /**

       *  Returns a read-only (constant) iterator that points one past

       *  the last element in the %list.  Iteration is done in ordinary

       *  element order.

       */

      const_iterator

      end() const _GLIBCXX_NOEXCEPT

      { return const_iterator(&this->_M_impl._M_node); }

      /**

       *  Returns a read/write reverse iterator that points to the last

       *  element in the %list.  Iteration is done in reverse element

       *  order.

       */

      reverse_iterator

      rbegin() _GLIBCXX_NOEXCEPT

      { return reverse_iterator(end()); }

      /**

       *  Returns a read-only (constant) reverse iterator that points to

       *  the last element in the %list.  Iteration is done in reverse

       *  element order.

       */

      const_reverse_iterator

      rbegin() const _GLIBCXX_NOEXCEPT

      { return const_reverse_iterator(end()); }

      /**

       *  Returns a read/write reverse iterator that points to one

       *  before the first element in the %list.  Iteration is done in

       *  reverse element order.

       */

      reverse_iterator

      rend() _GLIBCXX_NOEXCEPT

      { return reverse_iterator(begin()); }

      /**

       *  Returns a read-only (constant) reverse iterator that points to one

       *  before the first element in the %list.  Iteration is done in reverse

       *  element order.

       */

      const_reverse_iterator

      rend() const _GLIBCXX_NOEXCEPT

      { return const_reverse_iterator(begin()); }

#if __cplusplus >= 201103L

      /**

       *  Returns a read-only (constant) iterator that points to the

       *  first element in the %list.  Iteration is done in ordinary

       *  element order.

       */

      const_iterator

      cbegin() const noexcept

      { return const_iterator(this->_M_impl._M_node._M_next); }

      /**

       *  Returns a read-only (constant) iterator that points one past

       *  the last element in the %list.  Iteration is done in ordinary

       *  element order.

       */

      const_iterator

      cend() const noexcept

      { return const_iterator(&this->_M_impl._M_node); }

      /**

       *  Returns a read-only (constant) reverse iterator that points to

       *  the last element in the %list.  Iteration is done in reverse

       *  element order.

       */

      const_reverse_iterator

      crbegin() const noexcept

      { return const_reverse_iterator(end()); }

      /**

       *  Returns a read-only (constant) reverse iterator that points to one

       *  before the first element in the %list.  Iteration is done in reverse

       *  element order.

       */

      const_reverse_iterator

      crend() const noexcept

      { return const_reverse_iterator(begin()); }

#endif

      // [23.2.2.2] capacity

      /**

       *  Returns true if the %list is empty.  (Thus begin() would equal

       *  end().)

       */

      bool

      empty() const _GLIBCXX_NOEXCEPT

      { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }

      /**  Returns the number of elements in the %list.  */

      size_type

      size() const _GLIBCXX_NOEXCEPT

      { return std::distance(begin(), end()); }

      /**  Returns the size() of the largest possible %list.  */

      size_type

      max_size() const _GLIBCXX_NOEXCEPT

      { return _M_get_Node_allocator().max_size(); }

#if __cplusplus >= 201103L

      /**

       *  @brief Resizes the %list to the specified number of elements.

       *  @param __new_size Number of elements the %list should contain.

       *

       *  This function will %resize the %list to the specified number

       *  of elements.  If the number is smaller than the %list's

       *  current size the %list is truncated, otherwise default

       *  constructed elements are appended.

       */

      void

      resize(size_type __new_size);

      /**

       *  @brief Resizes the %list to the specified number of elements.

       *  @param __new_size Number of elements the %list should contain.

       *  @param __x Data with which new elements should be populated.

       *

       *  This function will %resize the %list to the specified number

       *  of elements.  If the number is smaller than the %list's

       *  current size the %list is truncated, otherwise the %list is

       *  extended and new elements are populated with given data.

       */

      void

      resize(size_type __new_size, const value_type& __x);

#else

      /**

       *  @brief Resizes the %list to the specified number of elements.

       *  @param __new_size Number of elements the %list should contain.

       *  @param __x Data with which new elements should be populated.

       *

       *  This function will %resize the %list to the specified number

       *  of elements.  If the number is smaller than the %list's

       *  current size the %list is truncated, otherwise the %list is

       *  extended and new elements are populated with given data.

       */

      void

      resize(size_type __new_size, value_type __x = value_type());

#endif

      // element access

      /**

       *  Returns a read/write reference to the data at the first

       *  element of the %list.

       */

      reference

      front()

      { return *begin(); }

      /**

       *  Returns a read-only (constant) reference to the data at the first

       *  element of the %list.

       */

      const_reference

      front() const

      { return *begin(); }

      /**

       *  Returns a read/write reference to the data at the last element

       *  of the %list.

       */

      reference

      back()

      {

	iterator __tmp = end();

	--__tmp;

	return *__tmp;

      }

      /**

       *  Returns a read-only (constant) reference to the data at the last

       *  element of the %list.

       */

      const_reference

      back() const

      {

	const_iterator __tmp = end();

	--__tmp;

	return *__tmp;

      }

      // [23.2.2.3] modifiers

      /**

       *  @brief  Add data to the front of the %list.

       *  @param  __x  Data to be added.

       *

       *  This is a typical stack operation.  The function creates an

       *  element at the front of the %list and assigns the given data

       *  to it.  Due to the nature of a %list this operation can be

       *  done in constant time, and does not invalidate iterators and

       *  references.

       */

      void

      push_front(const value_type& __x)

      { this->_M_insert(begin(), __x); }

#if __cplusplus >= 201103L

      void

      push_front(value_type&& __x)

      { this->_M_insert(begin(), std::move(__x)); }

      template

        void

        emplace_front(_Args&&... __args)

        { this->_M_insert(begin(), std::forward<_Args>(__args)...); }

#endif

      /**

       *  @brief  Removes first element.

       *

       *  This is a typical stack operation.  It shrinks the %list by

       *  one.  Due to the nature of a %list this operation can be done

       *  in constant time, and only invalidates iterators/references to

       *  the element being removed.

       *

       *  Note that no data is returned, and if the first element's data

       *  is needed, it should be retrieved before pop_front() is

       *  called.

       */

      void

      pop_front()

      { this->_M_erase(begin()); }

      /**

       *  @brief  Add data to the end of the %list.

       *  @param  __x  Data to be added.

       *

       *  This is a typical stack operation.  The function creates an

       *  element at the end of the %list and assigns the given data to

       *  it.  Due to the nature of a %list this operation can be done

       *  in constant time, and does not invalidate iterators and

       *  references.

       */

      void

      push_back(const value_type& __x)

      { this->_M_insert(end(), __x); }

#if __cplusplus >= 201103L

      void

      push_back(value_type&& __x)

      { this->_M_insert(end(), std::move(__x)); }

      template

        void

        emplace_back(_Args&&... __args)

        { this->_M_insert(end(), std::forward<_Args>(__args)...); }

#endif

      /**

       *  @brief  Removes last element.

       *

       *  This is a typical stack operation.  It shrinks the %list by

       *  one.  Due to the nature of a %list this operation can be done

       *  in constant time, and only invalidates iterators/references to

       *  the element being removed.

       *

       *  Note that no data is returned, and if the last element's data

       *  is needed, it should be retrieved before pop_back() is called.

       */

      void

      pop_back()

      { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }

#if __cplusplus >= 201103L

      /**

       *  @brief  Constructs object in %list before specified iterator.

       *  @param  __position  A const_iterator into the %list.

       *  @param  __args  Arguments.

       *  @return  An iterator that points to the inserted data.

       *

       *  This function will insert an object of type T constructed

       *  with T(std::forward(args)...) before the specified

       *  location.  Due to the nature of a %list this operation can

       *  be done in constant time, and does not invalidate iterators

       *  and references.

       */

      template

        iterator

        emplace(iterator __position, _Args&&... __args);

#endif

      /**

       *  @brief  Inserts given value into %list before specified iterator.

       *  @param  __position  An iterator into the %list.

       *  @param  __x  Data to be inserted.

       *  @return  An iterator that points to the inserted data.

       *

       *  This function will insert a copy of the given value before

       *  the specified location.  Due to the nature of a %list this

       *  operation can be done in constant time, and does not

       *  invalidate iterators and references.

       */

      iterator

      insert(iterator __position, const value_type& __x);

#if __cplusplus >= 201103L

      /**

       *  @brief  Inserts given rvalue into %list before specified iterator.

       *  @param  __position  An iterator into the %list.

       *  @param  __x  Data to be inserted.

       *  @return  An iterator that points to the inserted data.

       *

       *  This function will insert a copy of the given rvalue before

       *  the specified location.  Due to the nature of a %list this

       *  operation can be done in constant time, and does not

       *  invalidate iterators and references.

        */

      iterator

      insert(iterator __position, value_type&& __x)

      { return emplace(__position, std::move(__x)); }

      /**

       *  @brief  Inserts the contents of an initializer_list into %list

       *          before specified iterator.

       *  @param  __p  An iterator into the %list.

       *  @param  __l  An initializer_list of value_type.

       *

       *  This function will insert copies of the data in the

       *  initializer_list @a l into the %list before the location

       *  specified by @a p.

       *

       *  This operation is linear in the number of elements inserted and

       *  does not invalidate iterators and references.

       */

      void

      insert(iterator __p, initializer_list __l)

      { this->insert(__p, __l.begin(), __l.end()); }

#endif

      /**

       *  @brief  Inserts a number of copies of given data into the %list.

       *  @param  __position  An iterator into the %list.

       *  @param  __n  Number of elements to be inserted.

       *  @param  __x  Data to be inserted.

       *

       *  This function will insert a specified number of copies of the

       *  given data before the location specified by @a position.

       *

       *  This operation is linear in the number of elements inserted and

       *  does not invalidate iterators and references.

       */

      void

      insert(iterator __position, size_type __n, const value_type& __x)

      {