请选择 进入手机版 | 继续访问电脑版
二次方先生 发表于 2021-1-1 10:33:09 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
list

list作为一个序列式容器,支持在常量时间内插入和删除容器内任何位置的元素。它的实现为一个双链表,提供了bidirectional iterator,不支持快速随机访问。与std::forward_list相比,这个容器提供了双向迭代本事,但空间效率较低。
在列表内或多个列表中添加、删除和移动元素不会使迭代器或引用失效。只有当相应的元素被删除时,迭代器才会失效。
本文首先列出了list成员函数及相关非成员函数签名,之后对SGI STL std::list重点源码以注释的方式举行分析。
由于常用的GCC6.4.1支持 c++11 且代表了当前大多数编译器对 c++的支持情况,故仅列出了c++11支持的相关成员函数及非成员函数,暂未列出c++17及c++20支持的新方法。
整理自个人条记,水平所限不免存在遗漏与错误,任何问题可以与我互换~本篇也会保持增补更新
成员函数

ctor:
  1. std::list::listlist();explicit list( const Allocator& alloc );explicit list( size_type count, const T& value = T(), const Allocator& alloc = Allocator());list( size_type count, const T& value, const Allocator& alloc = Allocator());explicit list( size_type count );explicit list( size_type count, const Allocator& alloc = Allocator() );template< class InputIt >list( InputIt first, InputIt last, const Allocator& alloc = Allocator() );      list( const list& other );list( const list& other, const Allocator& alloc );list( list&& other );list( list&& other, const Allocator& alloc );list( std::initializer_list init, const Allocator& alloc = Allocator() );      
复制代码
在list容器移动构造之后,指向other的引用、指针和迭代器仍然有效,但指向的是*this中的元素
dtor:
  1. ~list();
复制代码
std::list< T,Allocator>::operator=
  1. list& operator=( const list& other );list& operator=( list&& other );list& operator=( list&& other ) noexceptlist& operator=( std::initializer_list ilist );
复制代码
std::list< T,Allocator>::assign
  1. void assign( size_type count, const T& value );template< class InputIt >void assign( InputIt first, InputIt last );void assign( std::initializer_list ilist );
复制代码
std::list< T,Allocator>::get_allocator
  1. allocator_type get_allocator() const noexcept;
复制代码
std::list< T,Allocator>::front
  1. reference front();const_reference front() const;
复制代码
std::list< T,Allocator>::back
  1. reference back();const_reference back() const;
复制代码
std::list< T,Allocator>::begin, std::list::cbegin
  1. iterator begin() noexcept;const_iterator begin() const noexcept;const_iterator cbegin() const noexcept;
复制代码
std::list< T,Allocator>::end, std::list::cend
  1. iterator end() noexcept;const_iterator end() const noexcept;const_iterator cend() const noexcept;
复制代码
std::list< T,Allocator>::rbegin, std::list::crbegin
  1. reverse_iterator rbegin() noexcept;const_reverse_iterator rbegin() const noexcept;const_reverse_iterator crbegin() const noexcept;
复制代码
std::list< T,Allocator>::rend, std::list::crend
  1. reverse_iterator rend() noexcept;const_reverse_iterator rend() const noexcept;const_reverse_iterator crend() const noexcept;
复制代码
std::list< T,Allocator>::empty
  1. bool empty() const noexcept;
复制代码
std::list::size
  1. size_type size() const noexcept;
复制代码
std::list< T,Allocator>::max_size
  1. size_type max_size() const noexcept;
复制代码
std::list< T,Allocator>::clear
  1. void clear() noexcept;
复制代码
std::list< T,Allocator>::insert
  1. iterator insert( const_iterator pos, const T& value );iterator insert( const_iterator pos, T&& value );iterator insert( const_iterator pos, size_type count, const T& value );template< class InputIt >iterator insert( const_iterator pos, InputIt first, InputIt last );iterator insert( const_iterator pos, std::initializer_list ilist );
复制代码
insert()后迭代器或引用都不会失效
std::list< T,Allocator>::emplace
  1. template< class... Args >iterator emplace( const_iterator pos, Args&&... args );
复制代码
emplace()后迭代器或引用都不会失效, 参数args… 会由std::forward(args)…转换至ctor
std::list< T,Allocator>::erase
  1. iterator erase( const_iterator pos );iterator erase( const_iterator first, const_iterator last );
复制代码
对已删除元素的引用和迭代器无效。其他引用和迭代器不受影响。迭代器pos必须是有效的,而且是可解引用的。因此,end()迭代器(有效的,但不能解引用)不能用作pos的值。
如果first == last,则first迭代器不需要解引用:清除空范围是一个空使用。
返回值:返回最后一个移除的元素的下一个位置的迭代器, 若pos指向list最后一个元素,则返回end()迭代器, 若删除之前last==end(),则返回删除更新之后的end(), 若[first, last) 范围为空, 返回last位置迭代器
std::list< T,Allocator>::push_back
  1. void push_back( const T& value );void push_back( T&& value );
复制代码
std::list< T,Allocator>::emplace_back
  1. template< class... Args >void emplace_back( Args&&... args );
复制代码
std::list< T,Allocator>::pop_back
  1. void pop_back();
复制代码
std::list< T,Allocator>::push_front
  1. void push_front( const T& value );void push_front( T&& value );
复制代码
std::list< T,Allocator>::emplace_front
  1. template< class... Args >void emplace_front( Args&&... args );
复制代码
std::list< T,Allocator>::pop_front
  1. void pop_front();
复制代码
std::list< T,Allocator>::resize
  1. void resize( size_type count );void resize( size_type count, const value_type& value );
复制代码
std::list< T,Allocator>::merge
  1. void merge( list& other );void merge( list&& other );template void merge( list& other, Compare comp );template void merge( list&& other, Compare comp );
复制代码
std::list< T,Allocator>::splice
  1. void splice( const_iterator pos, list& other );void splice( const_iterator pos, list&& other );void splice( const_iterator pos, list& other, const_iterator it );void splice( const_iterator pos, list&& other, const_iterator it );void splice( const_iterator pos, list& other, const_iterator first, const_iterator last);void splice( const_iterator pos, list&& other, const_iterator first, const_iterator last );
复制代码
将list中的元素转移至另一个list,不拷贝或移动元素,仅仅list节点中的内部指针改变了指向。没有任何迭代器或引用失效,移动元素的迭代器仍然有效,但现在指向*this,而不是other。
std::list< T,Allocator>::remove, remove_if
  1. void remove( const T& value );template< class UnaryPredicate >void remove_if( UnaryPredicate p );
复制代码
std::list< T,Allocator>::reverse
  1. void reverse() noexcept;
复制代码
迭代器不会失效
std::list< T,Allocator>::unique
  1. void unique();template< class BinaryPredicate >void unique( BinaryPredicate p );
复制代码
第一个版本使用operator= 比力,第二个版本使用BinaryPredicate 比力元素
std::list< T,Allocator>::sort
  1. void sort();template< class Compare >void sort( Compare comp );
复制代码
第一个版本使用operator< 比力,第二个版本使用Compare 比力元素
非成员函数

operator==,!=,=,
  1. template< class T, class Alloc >bool operator==( const std::list& lhs,                 const std::list& rhs );template< class T, class Alloc >bool operator!=( const std::list& lhs,                 const std::list& rhs );template< class T, class Alloc >bool operatorbool operatorbool operator>( const std::list& lhs,                const std::list& rhs );template< class T, class Alloc >bool operator>=( const std::list& lhs,                 const std::list& rhs );
复制代码
==/!=查抄lhs和rhs的含量是否相等,即它们的元素个数相同,lhs中的每个元素与rhs中相同位置的元素比力相等。
= 比力lhs和rhs的内容。比力由等效于字典序 (std::lexicographical_compare)。
std::swap(std::list)
  1. template< class T, class Alloc >void swap( std::list& lhs,           std::list& rhs );
复制代码
list的主要实现在文件stl_list.h中。
本文省略了版本判断#if __cplusplus >= 201103L,采用GCC6.4.1
stl_list.h:
头文件中对于cpp11特性主要使用了initializer_list、allocated_ptr.h、aligned_buffer.h
[code]#include #include #include #endif//链表节点基类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;};//真正的链表节点类,继承于_List_node_base  template    struct _List_node : public __detail::_List_node_base    {        //__aligned_membuf可以生存通过placement new或allocator_traits::construct初始化的_Tp类型的对象。        //要用作数据成员子对象,对完整对象使用__aligned_membuf。      __gnu_cxx::__aligned_membuf _M_storage;      _Tp*       _M_valptr()       { return _M_storage._M_ptr(); }      _Tp const* _M_valptr() const { return _M_storage._M_ptr(); }    };//list 迭代器类  template    struct _List_iterator    {      typedef _List_iterator                _Self;      typedef _List_node                        _Node;      typedef ptrdiff_t                                difference_type;      //list为一个双向链表,迭代器必须具备前移、后移的本事,所以提供了bidirectional iterator      typedef std::bidirectional_iterator_tag        iterator_category;      typedef _Tp                                value_type;      typedef _Tp*                                pointer;      typedef _Tp&                                reference;      _List_iterator() _GLIBCXX_NOEXCEPT      : _M_node() { }      explicit      _List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT      : _M_node(__x) { }      _Self      _M_const_cast() const _GLIBCXX_NOEXCEPT      { return *this; }      //必须向下转换(从_List_node_base到_List_node)解引用取值      reference      operator*() const _GLIBCXX_NOEXCEPT      { return *static_cast(_M_node)->_M_valptr(); }      pointer      operator->() const _GLIBCXX_NOEXCEPT      { return static_cast(_M_node)->_M_valptr(); }      //前缀++前向移动,调用_M_next      _Self&      operator++() _GLIBCXX_NOEXCEPT      {        _M_node = _M_node->_M_next;        return *this;      }      //后缀++前向移动,调用_M_next      _Self      operator++(int) _GLIBCXX_NOEXCEPT      {        _Self __tmp = *this;        _M_node = _M_node->_M_next;        return __tmp;      }      //前缀--后向移动,调用_M_prev      _Self&      operator--() _GLIBCXX_NOEXCEPT      {        _M_node = _M_node->_M_prev;        return *this;      }      //后缀--后向移动,调用_M_prev      _Self      operator--(int) _GLIBCXX_NOEXCEPT      {        _Self __tmp = *this;        _M_node = _M_node->_M_prev;        return __tmp;      }      bool      operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT      { return _M_node == __x._M_node; }      bool      operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT      { return _M_node != __x._M_node; }      //list 唯一成员指针      __detail::_List_node_base* _M_node;    };                //list 基类          template    class _List_base    {    protected:      typedef typename __gnu_cxx::__alloc_traits::template        rebind::other                                _Tp_alloc_type;      typedef __gnu_cxx::__alloc_traits        _Tp_alloc_traits;      typedef typename _Tp_alloc_traits::template        rebind::other _Node_alloc_type;      typedef __gnu_cxx::__alloc_traits _Node_alloc_traits;      //_S_distance:获得两个节点之间的隔断      static size_t      _S_distance(const __detail::_List_node_base* __first,                  const __detail::_List_node_base* __last)      {        size_t __n = 0;        while (__first != __last)          {            __first = __first->_M_next;            ++__n;          }        return __n;      }      //      struct _List_impl      : public _Node_alloc_type      {#if _GLIBCXX_USE_CXX11_ABI        _List_node _M_node;#else        __detail::_List_node_base _M_node;#endif        _List_impl() _GLIBCXX_NOEXCEPT        : _Node_alloc_type(), _M_node()        { }        _List_impl(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT        : _Node_alloc_type(__a), _M_node()        { }        _List_impl(_Node_alloc_type&& __a) noexcept        : _Node_alloc_type(std::move(__a)), _M_node()        { }      };      _List_impl _M_impl;#if _GLIBCXX_USE_CXX11_ABI      size_t _M_get_size() const { return *_M_impl._M_node._M_valptr(); }      void _M_set_size(size_t __n) { *_M_impl._M_node._M_valptr() = __n; }      void _M_inc_size(size_t __n) { *_M_impl._M_node._M_valptr() += __n; }      void _M_dec_size(size_t __n) { *_M_impl._M_node._M_valptr() -= __n; }      size_t      _M_distance(const __detail::_List_node_base* __first,                  const __detail::_List_node_base* __last) const      { return _S_distance(__first, __last); }      // return the stored size      size_t _M_node_count() const { return *_M_impl._M_node._M_valptr(); }#else      // dummy implementations used when the size is not stored      size_t _M_get_size() const { return 0; }      void _M_set_size(size_t) { }      void _M_inc_size(size_t) { }      void _M_dec_size(size_t) { }      size_t _M_distance(const void*, const void*) const { return 0; }      // count the number of nodes      size_t _M_node_count() const      {        return _S_distance(_M_impl._M_node._M_next,                           std::__addressof(_M_impl._M_node));      }#endif      typename _Node_alloc_traits::pointer      _M_get_node()      { return _Node_alloc_traits::allocate(_M_impl, 1); }      void      _M_put_node(typename _Node_alloc_traits::pointer __p) _GLIBCXX_NOEXCEPT      { _Node_alloc_traits::deallocate(_M_impl, __p, 1); }  public:      typedef _Alloc allocator_type;      _Node_alloc_type&      _M_get_Node_allocator() _GLIBCXX_NOEXCEPT      { return _M_impl; }      const _Node_alloc_type&      _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT      { return _M_impl; }      _List_base()      : _M_impl()      { _M_init(); }      _List_base(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT      : _M_impl(__a)      { _M_init(); }      _List_base(_List_base&& __x) noexcept      : _M_impl(std::move(__x._M_get_Node_allocator()))      { _M_move_nodes(std::move(__x)); }      _List_base(_List_base&& __x, _Node_alloc_type&& __a)      : _M_impl(std::move(__a))      {        if (__x._M_get_Node_allocator() == _M_get_Node_allocator())          _M_move_nodes(std::move(__x));        else          _M_init(); // Caller must move individual elements.      }      void      _M_move_nodes(_List_base&& __x)      {        auto* const __xnode = std::__addressof(__x._M_impl._M_node);        if (__xnode->_M_next == __xnode)          _M_init();        else          {            auto* const __node = std::__addressof(_M_impl._M_node);            __node->_M_next = __xnode->_M_next;            __node->_M_prev = __xnode->_M_prev;            __node->_M_next->_M_prev = __node->_M_prev->_M_next = __node;            _M_set_size(__x._M_get_size());            __x._M_init();          }      }      // This is what actually destroys the list.      ~_List_base() _GLIBCXX_NOEXCEPT      { _M_clear(); }      void      _M_clear() _GLIBCXX_NOEXCEPT;      void      _M_init() _GLIBCXX_NOEXCEPT      {        this->_M_impl._M_node._M_next = &this->_M_impl._M_node;        this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;        _M_set_size(0);      }    };        /*list类:    * 双向循环链表    * 标准容器类,查找元素时间o(n),插入、删除一个节点的时间固定    * 与vector和deque差别,list不能提供random access iterator(其节点不包管在储存空间中一连存在),由于双向链表的构成,提供的是    * Bidirectional iterator,对于算法(algorithm)来说,只需要序列式存储,所以不受影响    * 链表体现为   A  B  C  D时,    * D中会存储一个private 迭代器,作为其仅有的数据成员,由于环形链表的特性,从尾部向后移动一位即可到达链表头部    * 链表为空的鉴别方法:前向/后向迭代器均指向自己    * _Tp  元素类型 _Tp必须满意CopyAssignable和CopyConstructible的要求    * _Alloc  Allocator类型,默认值为allocator    *     */  template    class list : protected _List_base    {      typedef _List_base                        _Base;      typedef typename _Base::_Tp_alloc_type                _Tp_alloc_type;      typedef typename _Base::_Tp_alloc_traits                _Tp_alloc_traits;      typedef typename _Base::_Node_alloc_type                _Node_alloc_type;      typedef typename _Base::_Node_alloc_traits        _Node_alloc_traits;    public:      typedef _Tp                                         value_type;      typedef typename _Tp_alloc_traits::pointer         pointer;      typedef typename _Tp_alloc_traits::const_pointer         const_pointer;      typedef typename _Tp_alloc_traits::reference         reference;      typedef typename _Tp_alloc_traits::const_reference const_reference;      typedef _List_iterator                         iterator;      typedef _List_const_iterator                         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:      // 指针可以转换为迭代器,只要一个指针便可体现整个环形链表      typedef _List_node                                 _Node;      using _Base::_M_impl;      using _Base::_M_put_node;      using _Base::_M_get_node;      using _Base::_M_get_Node_allocator;              //为新节点分配空间而且构造一个变参拷贝      template        _Node*        _M_create_node(_Args&&... __args)        {          auto __p = this->_M_get_node();          auto& __alloc = _M_get_Node_allocator();          __allocated_ptr __guard{__alloc, __p};          _Node_alloc_traits::construct(__alloc, __p->_M_valptr(),                                        std::forward(__args)...);          __guard = nullptr;          return __p;        }                      /**       *  使用默认元素创建List       *  __n:  The number of elements to initially create.       *  __a:  An allocator object.       */      explicit      list(size_type __n, const allocator_type& __a = allocator_type())      : _Base(_Node_alloc_type(__a))      { _M_default_initialize(__n); }      /**       *  __n      The number of elements to initially create.       *  __value  An element to copy.       *  __a      An allocator object.       *       *  以n个value值构造List       */      list(size_type __n, const value_type& __value,           const allocator_type& __a = allocator_type())      : _Base(_Node_alloc_type(__a))      { _M_fill_initialize(__n, __value); }      /**       *  List ctor       *  __x  A %list of identical element and allocator types.       *       */      list(const list& __x)      : _Base(_Node_alloc_traits::              _S_select_on_copy(__x._M_get_Node_allocator()))      { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }      /**       *  List move constructor.       *  __x  A %list of identical element and allocator types.       */      list(list&& __x) noexcept      : _Base(std::move(__x)) { }      /**       *  以initializer_list构造list       *  __l  An initializer_list of value_type.       *  __a  An allocator object.       */      list(initializer_list __l,           const allocator_type& __a = allocator_type())      : _Base(_Node_alloc_type(__a))      { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); }      /**       *  范围构造list       *  __first  输入迭代器       *  __last   输入迭代器       *  __a      分配对象       */      template        list(_InputIterator __first, _InputIterator __last,             const allocator_type& __a = allocator_type())        : _Base(_Node_alloc_type(__a))        { _M_initialize_dispatch(__first, __last, __false_type()); }      /**       *  由于Base中的dtor已经做了析构的工作,所以不需要显示的dtor       *  _Base中的dtor仅仅清除了元素,若元素为指针类型,所指向的内存无法被使用       */      ~list() = default;      /**       *  List operator=.       */      list&      operator=(const list& __x);      /**       *  %List move assignment operator.       *  __x  相同元素和分配器类型的列表       */      list&      operator=(list&& __x)      noexcept(_Node_alloc_traits::_S_nothrow_move())      {        constexpr bool __move_storage =          _Node_alloc_traits::_S_propagate_on_move_assign()          || _Node_alloc_traits::_S_always_equal();        _M_move_assign(std::move(__x), __bool_constant());        return *this;      }      /**       *  List initializer list assignment operator.       *  __l  value_type类型的 initializer_list.       */      list&      operator=(initializer_list __l)      {        this->assign(__l.begin(), __l.end());        return *this;      }      /**       *  将给定值赋值给list.       *       *  此函数用给定值的n个副本填充列表。赋值会完全更改list,而且得到的list的巨细与分配的元素数相同。       */      void      assign(size_type __n, const value_type& __val)      { _M_fill_assign(__n, __val); }      /**       *  将范围值赋值给list.       *  __first  输入迭代器.       *  __last   输入迭代器.       *       *  赋值会完全更改list,而且得到的list的巨细与分配的元素数相同       */      template        void        assign(_InputIterator __first, _InputIterator __last)        { _M_assign_dispatch(__first, __last, __false_type()); }      /**       *  将 initializer_list 赋值给list.       */      void      assign(initializer_list __l)      { this->_M_assign_dispatch(__l.begin(), __l.end(), __false_type()); }      /**       *  返转头结点读写迭代器的方法,使用_M_node._M_next       */      iterator      begin() _GLIBCXX_NOEXCEPT      { return iterator(this->_M_impl._M_node._M_next); }      /**       *  返回只读的指向头结点的迭代器的方法       */      const_iterator      begin() const _GLIBCXX_NOEXCEPT      { return const_iterator(this->_M_impl._M_node._M_next); }      /**       *  返转头结点读写迭代器的方法,直接指向_M_node       */      iterator      end() _GLIBCXX_NOEXCEPT      { return iterator(&this->_M_impl._M_node); }      /**       *  返回只读的指向尾结点的迭代器的方法       */      const_iterator      end() const _GLIBCXX_NOEXCEPT      { return const_iterator(&this->_M_impl._M_node); }      /**       *  返回尾结点读写反向迭代器的方法,使用end()       */      reverse_iterator      rbegin() _GLIBCXX_NOEXCEPT      { return reverse_iterator(end()); }      /**       *  返回尾结点只读反向迭代器的方法,使用end()       */      const_reverse_iterator      rbegin() const _GLIBCXX_NOEXCEPT      { return const_reverse_iterator(end()); }      reverse_iterator      rend() _GLIBCXX_NOEXCEPT      { return reverse_iterator(begin()); }      const_reverse_iterator      rend() const _GLIBCXX_NOEXCEPT      { return const_reverse_iterator(begin()); }      const_iterator      cbegin() const noexcept      { return const_iterator(this->_M_impl._M_node._M_next); }      const_iterator      cend() const noexcept      { return const_iterator(&this->_M_impl._M_node); }      const_reverse_iterator      crbegin() const noexcept      { return const_reverse_iterator(end()); }      const_reverse_iterator      crend() const noexcept      { return const_reverse_iterator(begin()); }      /**       *  list判空.  (begin()==end())       */      bool      empty() const _GLIBCXX_NOEXCEPT      { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }            size_type      size() const _GLIBCXX_NOEXCEPT      { return this->_M_node_count(); }#if __cplusplus >= 201103L      /**       *  resize list 多裁少补       */      void      resize(size_type __new_size);      /**       *  resize list 多裁少补(__x为填充默认值)       */      void      resize(size_type __new_size, const value_type& __x);            // 元素存取方法      /**       *  返回List首元素的读写引用       */      reference      front() _GLIBCXX_NOEXCEPT      { return *begin(); }      const_reference      front() const _GLIBCXX_NOEXCEPT      { return *begin(); }      /**       *  返回List尾元素的读写引用       */      reference      back() _GLIBCXX_NOEXCEPT      {        iterator __tmp = end();        --__tmp;        return *__tmp;      }       const_reference      back() const _GLIBCXX_NOEXCEPT      {        const_iterator __tmp = end();        --__tmp;        return *__tmp;      }      // [23.2.2.3] modifiers      /**       *  list首部添加元素       */      void      push_front(const value_type& __x)      { this->_M_insert(begin(), __x); }      void      push_front(value_type&& __x)      { this->_M_insert(begin(), std::move(__x)); }      template        reference        emplace_front(_Args&&... __args)        {          this->_M_insert(begin(), std::forward(__args)...);          return front();        }      /**       *  移除首部元素.       */      void      pop_front() _GLIBCXX_NOEXCEPT      { this->_M_erase(begin()); }      void      push_back(const value_type& __x)      { this->_M_insert(end(), __x); }      void      push_back(value_type&& __x)      { this->_M_insert(end(), std::move(__x)); }          //移动语义尾部插入元素      template        reference        emplace_back(_Args&&... __args)        {          this->_M_insert(end(), std::forward(__args)...);        return back();        }      /**       *  移除尾部一个元素.       */      void      pop_back() _GLIBCXX_NOEXCEPT      { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); }      /**       *  在list某个迭代器之前构造一个对象       */      template        iterator        emplace(const_iterator __position, _Args&&... __args);      iterator      insert(const_iterator __position, const value_type& __x);      /**       *  由给定的右值在某个迭代器前插入        */      iterator      insert(const_iterator __position, value_type&& __x)      { return emplace(__position, std::move(__x)); }      /**       *  由给定的初始化列表在某个迭代器前插入       */      iterator      insert(const_iterator __p, initializer_list __l)      { return this->insert(__p, __l.begin(), __l.end()); }      iterator      insert(const_iterator __position, size_type __n, const value_type& __x);      /**       *  将某个区间内值插入List,返回值为指向__position前的一个迭代器        */      template        iterator        insert(const_iterator __position, _InputIterator __first,               _InputIterator __last);      /**       *  在给定位置删除元素,返回值为指向下一个元素的迭代器       *  仅指向被指向元素的迭代器失效,使用者必须注意仅仅清除了元素,若元素为指针类型,所指向的内存无法被使用       */      iterator      erase(const_iterator __position) noexcept;      /**       *  移除区间内的元素,返回区间后节点(__last)删除后的下一个位置的迭代器       */      iterator      erase(const_iterator __first, const_iterator __last) noexcept      {        while (__first != __last)          __first = erase(__first);        return __last._M_const_cast();      }      /**       *  互换所有数据       *  全局的std::swap() 方法有大概覆盖该方法       */      void      swap(list& __x) _GLIBCXX_NOEXCEPT      {        __detail::_List_node_base::swap(this->_M_impl._M_node,                                        __x._M_impl._M_node);        size_t __xsize = __x._M_get_size();        __x._M_set_size(this->_M_get_size());        this->_M_set_size(__xsize);        _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(),                                       __x._M_get_Node_allocator());      }      void      clear() _GLIBCXX_NOEXCEPT      {        _Base::_M_clear();        _Base::_M_init();      }      // [23.2.2.4] list operations      /**       *  在__position前插入list __x的内容,要求this != __x       *  由移动语义,方法使用后list __x会清空       */      void      splice(const_iterator __position, list&& __x) noexcept      {        if (!__x.empty())          {            _M_check_equal_allocators(__x);            this->_M_transfer(__position._M_const_cast(),                              __x.begin(), __x.end());            this->_M_inc_size(__x._M_get_size());            __x._M_set_size(0);          }      }      void      splice(const_iterator __position, list& __x) noexcept      { splice(__position, std::move(__x)); }     /**       *  将List__x中__i指向的元素删除并将该元素插入当前list __position之前       */      void      splice(const_iterator __position, list&& __x, const_iterator __i) noexcept      {        iterator __j = __i._M_const_cast();        ++__j;        if (__position == __i || __position == __j)          return;        if (this != std::__addressof(__x))          _M_check_equal_allocators(__x);        this->_M_transfer(__position._M_const_cast(),                          __i._M_const_cast(), __j);        this->_M_inc_size(1);        __x._M_dec_size(1);      }      void      splice(const_iterator __position, list& __x, const_iterator __i) noexcept      { splice(__position, std::move(__x), __i); }      /**       *  将List__x中[__first,__last)范围内的元素删除并将该元素插入当前list __position之前       *  若__position不在[__first,__last)内会产生未界说行为       */      void      splice(const_iterator __position, list&& __x, const_iterator __first,             const_iterator __last) noexcept      {        if (__first != __last)          {            if (this != std::__addressof(__x))              _M_check_equal_allocators(__x);            size_t __n = this->_M_distance(__first._M_node, __last._M_node);            this->_M_inc_size(__n);            __x._M_dec_size(__n);            this->_M_transfer(__position._M_const_cast(),                              __first._M_const_cast(),                              __last._M_const_cast());          }      }      /**       *  同上,左值版本       */      void      splice(const_iterator __position, list& __x, const_iterator __first,             const_iterator __last) noexcept      { splice(__position, std::move(__x), __first, __last); }      /**       *  移除list中与__value相等的所有元素       */      void      remove(const _Tp& __value);      /**       *  移除所有满意条件 _Predicate 的元素        */      template        void        remove_if(_Predicate);      /**       *  移除一连的除了第一个以外的重复的元素        */      void      unique();      /**       *  移除所有满意条件 _Predicate 的一连的除了第一个以外的元素        */      template        void        unique(_BinaryPredicate);      /**       *  合并排序的两个list,若存在相等的元素,__x中的元素会排在反面        *  假定两个list都通过operator_M_impl._M_node._M_reverse(); }      /**       *  sort所有元素       */      void      sort();      /**       *  根据比力方法排序       */      template        void        sort(_StrictWeakOrdering);  template    inline bool    operator==(const list& __x, const list& __y)    {#if _GLIBCXX_USE_CXX11_ABI      if (__x.size() != __y.size())        return false;#endif      typedef typename list::const_iterator const_iterator;      const_iterator __end1 = __x.end();      const_iterator __end2 = __y.end();      const_iterator __i1 = __x.begin();      const_iterator __i2 = __y.begin();      while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)        {          ++__i1;          ++__i2;        }      return __i1 == __end1 && __i2 == __end2;    }  template    inline bool    operator(const list& __x, const list& __y)    { return __y < __x; }  /// Based on operator<  template    inline bool    operator
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )