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:
- 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() );
dtor:
std::list< T,Allocator>::operator=
- list& operator=( const list& other );list& operator=( list&& other );list& operator=( list&& other ) noexceptlist& operator=( std::initializer_list ilist );
- void assign( size_type count, const T& value );template< class InputIt >void assign( InputIt first, InputIt last );void assign( std::initializer_list ilist );
- allocator_type get_allocator() const noexcept;
- reference front();const_reference front() const;
- reference back();const_reference back() const;
- iterator begin() noexcept;const_iterator begin() const noexcept;const_iterator cbegin() const noexcept;
- iterator end() noexcept;const_iterator end() const noexcept;const_iterator cend() const noexcept;
- reverse_iterator rbegin() noexcept;const_reverse_iterator rbegin() const noexcept;const_reverse_iterator crbegin() const noexcept;
- reverse_iterator rend() noexcept;const_reverse_iterator rend() const noexcept;const_reverse_iterator crend() const noexcept;
- bool empty() const noexcept;
- size_type size() const noexcept;
- size_type max_size() const noexcept;
std::list< T,Allocator>::insert
- 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 );
std::list< T,Allocator>::emplace
- template< class... Args >iterator emplace( const_iterator pos, Args&&... args );
std::list< T,Allocator>::erase
- iterator erase( const_iterator pos );iterator erase( const_iterator first, const_iterator last );
如果first == last，则first迭代器不需要解引用:清除空范围是一个空使用。
返回值：返回最后一个移除的元素的下一个位置的迭代器， 若pos指向list最后一个元素，则返回end()迭代器， 若删除之前last==end()，则返回删除更新之后的end(), 若[first, last) 范围为空， 返回last位置迭代器
std::list< T,Allocator>::push_back
- void push_back( const T& value );void push_back( T&& value );
- template< class... Args >void emplace_back( Args&&... args );
std::list< T,Allocator>::push_front
- void push_front( const T& value );void push_front( T&& value );
- template< class... Args >void emplace_front( Args&&... args );
std::list< T,Allocator>::resize
- void resize( size_type count );void resize( size_type count, const value_type& value );
- void merge( list& other );void merge( list&& other );template void merge( list& other, Compare comp );template void merge( list&& other, Compare comp );
- 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 );
std::list< T,Allocator>::remove, remove_if
- void remove( const T& value );template< class UnaryPredicate >void remove_if( UnaryPredicate p );
迭代器不会失效
std::list< T,Allocator>::unique
- void unique();template< class BinaryPredicate >void unique( BinaryPredicate p );
std::list< T,Allocator>::sort
- void sort();template< class Compare >void sort( Compare comp );
非成员函数
operator==,!=,=,
- 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的内容。比力由等效于字典序 (std::lexicographical_compare)。
std::swap(std::list)
- template< class T, class Alloc >void swap( std::list& lhs, std::list& rhs );
本文省略了版本判断#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 |
