### 前言 ? 在SGI STL中，list容器是一個循環的雙向鏈表，它的內存空間效率較前文介紹的vector容器高。因為vector容器的內存空間是連續存儲的，且在分配內存空間時，會分配額外的可用空間；而list容器的內存空間不一定是連續存儲，內存之間是采用迭代器或節點指針進行連接，并且在插入或刪除數據節點時，就配置或釋放一個數據節點，并不會分配額外的內存空間，這兩個操作過程都是常數時間。 ? 與vector容器不同的是，list容器在進行插入操作或拼接操作時，迭代器并不會失效；且不能以普通指針作為迭代器，因為普通指針的+或-操作只能指向連續空間的后移地址或前移個地址，不能保證指向list的下一個節點，迭代器必須是雙向迭代器，因為list容器具備有前移和后移的能力。 ? 注：本文所列的源碼出自SGI STL中的文件<stl_list.h>，對于list容器類的詳細信息也可以查看[《list容器庫》](http://zh.cppreference.com/w/cpp/container/list)和[《](http://msdn.microsoft.com/zh-cn/library/802d66bt.aspx)[MSDN](http://msdn.microsoft.com/zh-cn/library/802d66bt.aspx)[的](http://msdn.microsoft.com/zh-cn/library/802d66bt.aspx)[list](http://msdn.microsoft.com/zh-cn/library/802d66bt.aspx)[類》](http://msdn.microsoft.com/zh-cn/library/802d66bt.aspx) ### list容器 ### list節點和list數據結構 ? 在list容器中，list本身和list節點是分開設計的，list節點結構是存儲數據和指向相鄰節點的指針；如下源碼所示： ~~~ //以下是list鏈表節點的數據結構 struct _List_node_base { _List_node_base* _M_next;//指向直接后繼節點 _List_node_base* _M_prev;//指向直接前驅節點 }; template <class _Tp> struct _List_node : public _List_node_base { _Tp _M_data;//節點存儲的數據 }; ~~~ ? ? ?list本身的數據結構是只有一個指向鏈表節點的指針，因為list容器是循環雙向鏈表，則足夠遍歷整個鏈表；如下源碼所示： ~~~ //以下是雙向鏈表list類的定義，分配器_Alloc默認為第二級配置器 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > class list : protected _List_base<_Tp, _Alloc> { ... public: typedef _List_node<_Tp> _Node; protected: //定義指向鏈表節點指針 _List_node<_Tp>* _M_node; ... }; ~~~ ? 下面給出list節點和list本身的數據結構圖：  ### list容器的迭代器 ? ? ?list容器的內存空間存儲不一定是連續的，則不能用普通指針做為迭代器；list容器的迭代器是雙向迭代器，這也是導致list容器的排序成員函數sort()不能使用STL算法中的排序函數，因為STL中的排序算法接受的迭代器是隨機訪問迭代器；list容器在進行插入和拼接操作時迭代器不會失效；以下是源碼對迭代器的定義： ~~~ //以下是鏈表List_iterator_base的迭代器 struct _List_iterator_base { //數據類型 typedef size_t size_type; typedef ptrdiff_t difference_type; //list迭代器的類型是雙向迭代器bidirectional_iterator typedef bidirectional_iterator_tag iterator_category; //定義指向鏈表節點的指針 _List_node_base* _M_node; //構造函數 _List_iterator_base(_List_node_base* __x) : _M_node(__x) {} _List_iterator_base() {} //更新節點指針，指向直接前驅或直接后繼節點 void _M_incr() { _M_node = _M_node->_M_next; } void _M_decr() { _M_node = _M_node->_M_prev; } //操作符重載 bool operator==(const _List_iterator_base& __x) const { return _M_node == __x._M_node; } bool operator!=(const _List_iterator_base& __x) const { return _M_node != __x._M_node; } }; //以下是鏈表List_iterator的迭代器 template<class _Tp, class _Ref, class _Ptr> struct _List_iterator : public _List_iterator_base { typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; typedef _List_iterator<_Tp,_Ref,_Ptr> _Self; typedef _Tp value_type; typedef _Ptr pointer; typedef _Ref reference; typedef _List_node<_Tp> _Node; //構造函數 _List_iterator(_Node* __x) : _List_iterator_base(__x) {} _List_iterator() {} _List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {} //以下都是基本操作符的重載,取出節點數據 reference operator*() const { return ((_Node*) _M_node)->_M_data; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ _Self& operator++() { this->_M_incr(); return *this; } _Self operator++(int) { _Self __tmp = *this; this->_M_incr(); return __tmp; } _Self& operator--() { this->_M_decr(); return *this; } _Self operator--(int) { _Self __tmp = *this; this->_M_decr(); return __tmp; } }; #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION //返回迭代器的類型 inline bidirectional_iterator_tag iterator_category(const _List_iterator_base&) { return bidirectional_iterator_tag(); } template <class _Tp, class _Ref, class _Ptr> inline _Tp* value_type(const _List_iterator<_Tp, _Ref, _Ptr>&) { return 0; } inline ptrdiff_t* distance_type(const _List_iterator_base&) { return 0; } #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ ~~~ ### list容器的構造函數和析構函數 ? 這里把list容器的構造函數列出來講解，使我們對list容器的構造函數進行全面的了解，以便我們對其使用。在以下源碼的前面我會總結出list容器的構造函數及其使用方法。 ~~~ //以下是雙向鏈表list類的定義，分配器_Alloc默認為第二級配置器 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > class list : protected _List_base<_Tp, _Alloc> { ... public: //************************************ /*************以下是構造函數****************** //***********默認構造函數********************* explicit list( const Allocator& alloc = Allocator() ); //************具有初值和大小的構造函數************ 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 ); //******某個范圍的值為初始值的構造函數************** template< class InputIt > list( InputIt first, InputIt last, const Allocator& alloc = Allocator() ); //******拷貝構造函數************************* list( const list& other ); */ //************************************ //構造函數 //鏈表的默認構造函數 explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {} list(size_type __n, const _Tp& __value, const allocator_type& __a = allocator_type()) : _Base(__a) { insert(begin(), __n, __value); } explicit list(size_type __n) : _Base(allocator_type()) { insert(begin(), __n, _Tp()); } #ifdef __STL_MEMBER_TEMPLATES // We don't need any dispatching tricks here, because insert does all of // that anyway. template <class _InputIterator> list(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) { insert(begin(), __first, __last); } #else /* __STL_MEMBER_TEMPLATES */ list(const _Tp* __first, const _Tp* __last, const allocator_type& __a = allocator_type()) : _Base(__a) { this->insert(begin(), __first, __last); } list(const_iterator __first, const_iterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) { this->insert(begin(), __first, __last); } #endif /* __STL_MEMBER_TEMPLATES */ list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator()) { insert(begin(), __x.begin(), __x.end()); }//拷貝構造函數 ~list() { }//析構函數 //賦值操作 list<_Tp, _Alloc>& operator=(const list<_Tp, _Alloc>& __x); //構造函數，析構函數，賦值操作 定義到此結束 //*********************************** ... }; ~~~ ### list容器的成員函數 ? list容器的成員函數為我們使用該容器提供了很大的幫助，所以這里對其進行講解，首先先給出源碼的剖析，然后在對其中一些重點的成員函數進行圖文講解；具體源碼剖析如下所示： ~~~ //以下是雙向鏈表list類的定義，分配器_Alloc默認為第二級配置器 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > class list : protected _List_base<_Tp, _Alloc> { // requirements: ... protected: //創建值為x的節點，并返回該節點的地址 _Node* _M_create_node(const _Tp& __x) { _Node* __p = _M_get_node();//分配一個節點空間 __STL_TRY {//把x值賦予指定的地址，即是data值 _Construct(&__p->_M_data, __x); } __STL_UNWIND(_M_put_node(__p)); return __p;//返回節點地址 } //創建默認值的節點 _Node* _M_create_node() { _Node* __p = _M_get_node(); __STL_TRY { _Construct(&__p->_M_data); } __STL_UNWIND(_M_put_node(__p)); return __p; } public: //以下是迭代器的定義 iterator begin() { return (_Node*)(_M_node->_M_next); } const_iterator begin() const { return (_Node*)(_M_node->_M_next); } iterator end() { return _M_node; } const_iterator end() const { return _M_node; } reverse_iterator rbegin() { return reverse_iterator(end()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } //判斷鏈表是否為空鏈表 bool empty() const { return _M_node->_M_next == _M_node; } //返回鏈表的大小 size_type size() const { size_type __result = 0; //返回兩個迭代器之間的距離 distance(begin(), end(), __result); //返回鏈表的元素個數 return __result; } size_type max_size() const { return size_type(-1); } //返回第一個節點數據的引用，reference相當于value_type& reference front() { return *begin(); } const_reference front() const { return *begin(); } //返回最后一個節點數據的引用 reference back() { return *(--end()); } const_reference back() const { return *(--end()); } //交換鏈表容器的內容 void swap(list<_Tp, _Alloc>& __x) { __STD::swap(_M_node, __x._M_node); } //************************************ //***********插入節點********************* /**********以下是插入節點函數的原型，也是公共接口******** //在指定的位置pos之前插入值為value的數據節點 iterator insert( iterator pos, const T& value ); iterator insert( const_iterator pos, const T& value ); //在指定的位置pos之前插入n個值為value的數據節點 void insert( iterator pos, size_type count, const T& value ); iterator insert( const_iterator pos, size_type count, const T& value ); //在指定的位置pos之前插入[first,last)之間的數據節點 template< class InputIt > void insert( iterator pos, InputIt first, InputIt last); template< class InputIt > iterator insert( const_iterator pos, InputIt first, InputIt last ); *************************************/ /**在整個鏈表的操作中，插入操作是非常重要的，很多成員函數會調用該函數**/ //************************************* //在指定的位置插入初始值為x的節點 iterator insert(iterator __position, const _Tp& __x) { //首先創建一個初始值為x的節點，并返回該節點的地址 _Node* __tmp = _M_create_node(__x); //調整節點指針，把新節點插入到指定位置 __tmp->_M_next = __position._M_node; __tmp->_M_prev = __position._M_node->_M_prev; __position._M_node->_M_prev->_M_next = __tmp; __position._M_node->_M_prev = __tmp; //返回新節點地址 return __tmp; } //在指定的位置插入為默認值的節點 iterator insert(iterator __position) { return insert(__position, _Tp()); } //在指定位置插入n個初始值為x的節點 void insert(iterator __pos, size_type __n, const _Tp& __x) { _M_fill_insert(__pos, __n, __x); } void _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x); #ifdef __STL_MEMBER_TEMPLATES // Check whether it's an integral type. If so, it's not an iterator. //這里采用__type_traits技術 //在指定位置插入指定范圍內的數據 //首先判斷輸入迭代器類型_InputIterator是否為整數類型 template <class _InputIterator> void insert(iterator __pos, _InputIterator __first, _InputIterator __last) { typedef typename _Is_integer<_InputIterator>::_Integral _Integral; _M_insert_dispatch(__pos, __first, __last, _Integral()); } //若輸入迭代器類型_InputIterator是為整數類型，調用此函數 template<class _Integer> void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type) { _M_fill_insert(__pos, (size_type) __n, (_Tp) __x); } //若輸入迭代器類型_InputIterator是不為整數類型，調用此函數 template <class _InputIterator> void _M_insert_dispatch(iterator __pos, _InputIterator __first, _InputIterator __last, __false_type); #else /* __STL_MEMBER_TEMPLATES */ void insert(iterator __position, const _Tp* __first, const _Tp* __last); void insert(iterator __position, const_iterator __first, const_iterator __last); #endif /* __STL_MEMBER_TEMPLATES */ //在鏈表頭插入節點 void push_front(const _Tp& __x) { insert(begin(), __x); } void push_front() {insert(begin());} //在鏈表尾插入節點 void push_back(const _Tp& __x) { insert(end(), __x); } void push_back() {insert(end());} //******************************* //**********在指定位置刪除節點*********** //**********以下是刪除節點的公共接口********* /****************************** //刪除指定位置pos的節點 iterator erase( iterator pos ); iterator erase( const_iterator pos ); //刪除指定范圍[first,last)的數據節點 iterator erase( iterator first, iterator last ); iterator erase( const_iterator first, const_iterator last ); ******************************/ //******************************* //在指定位置position刪除節點，并返回直接后繼節點的地址 iterator erase(iterator __position) { //調整前驅和后繼節點的位置 _List_node_base* __next_node = __position._M_node->_M_next; _List_node_base* __prev_node = __position._M_node->_M_prev; _Node* __n = (_Node*) __position._M_node; __prev_node->_M_next = __next_node; __next_node->_M_prev = __prev_node; _Destroy(&__n->_M_data); _M_put_node(__n); return iterator((_Node*) __next_node); } //刪除兩個迭代器之間的節點 iterator erase(iterator __first, iterator __last); //清空鏈表，這里是調用父類的clear()函數 void clear() { _Base::clear(); } //調整鏈表的大小 void resize(size_type __new_size, const _Tp& __x); void resize(size_type __new_size) { this->resize(__new_size, _Tp()); } //取出第一個數據節點 void pop_front() { erase(begin()); } //取出最后一個數據節點 void pop_back() { iterator __tmp = end(); erase(--__tmp); } public: // assign(), a generalized assignment member function. Two // versions: one that takes a count, and one that takes a range. // The range version is a member template, so we dispatch on whether // or not the type is an integer. /*********************************** //assign()函數的兩個版本原型，功能是在已定義的list容器填充值 void assign( size_type count, const T& value ); template< class InputIt > void assign( InputIt first, InputIt last ); //*********************************** 例子： #include <list> #include <iostream> int main() { std::list<char> characters; //若定義characters時并初始化為字符b，下面的填充操作一樣有效 //std::list<char>characters(5,'b') characters.assign(5, 'a'); for (char c : characters) { std::cout << c << ' '; } return 0; } 輸出結果：a a a a a ***********************************/ //這里是第一個版本void assign( size_type count, const T& value ); void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); } //這里為什么要把_M_fill_assign這個函數放在public呢？？保護起來不是更好嗎？？ void _M_fill_assign(size_type __n, const _Tp& __val); #ifdef __STL_MEMBER_TEMPLATES //以下是針對assign()函數的第二個版本 /* template< class InputIt > void assign( InputIt first, InputIt last ); 這里有偏特化的現象，判斷輸入數據類型是否為整數型別 */ template <class _InputIterator> void assign(_InputIterator __first, _InputIterator __last) { typedef typename _Is_integer<_InputIterator>::_Integral _Integral; _M_assign_dispatch(__first, __last, _Integral()); } //若輸入數據類型為整數型別，則派送到此函數 template <class _Integer> void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) { _M_fill_assign((size_type) __n, (_Tp) __val); } //若輸入數據類型不是整數型別，則派送到此函數 template <class _InputIterator> void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type); #endif /* __STL_MEMBER_TEMPLATES */ //assign()函數定義結束 //********************************* protected: //把區間[first,last）的節點數據插入到指定節點position之前,position不能在區間內部 //這個函數是list類的protected屬性，不是公共接口，只為list類成員服務 //為下面拼接函數void splice()服務 void transfer(iterator __position, iterator __first, iterator __last) { if (__position != __last) { // Remove [first, last) from its old position. __last._M_node->_M_prev->_M_next = __position._M_node; __first._M_node->_M_prev->_M_next = __last._M_node; __position._M_node->_M_prev->_M_next = __first._M_node; // Splice [first, last) into its new position. _List_node_base* __tmp = __position._M_node->_M_prev; __position._M_node->_M_prev = __last._M_node->_M_prev; __last._M_node->_M_prev = __first._M_node->_M_prev; __first._M_node->_M_prev = __tmp; } } public: //****************************** //***********拼接操作對外接口************* //把鏈表拼接到當前鏈表指定位置position之前 /*void splice(const_iterator pos, list& other); //把it在鏈表other所指的位置拼接到當前鏈表pos之前，it和pos可指向同一鏈表 void splice(const_iterator pos, list& other, const_iterator it); //把鏈表other的節點范圍[first,last)拼接在當前鏈表所指定的位置pos之前 //[first,last)和pos可指向同一鏈表 void splice(const_iterator pos, list& other, const_iterator first, const_iterator last); *******************************/ //****************************** //將鏈表x拼接到當前鏈表的指定位置position之前 //這里x和*this必須不同，即是兩個不同的鏈表 void splice(iterator __position, list& __x) { if (!__x.empty()) this->transfer(__position, __x.begin(), __x.end()); } //將i所指向的節點拼接到position所指位置之前 //注意：i和position可以指向同一個鏈表 void splice(iterator __position, list&, iterator __i) { iterator __j = __i; ++__j; //若i和position指向同一個鏈表，且指向同一位置 //或者i和position指向同一個鏈表，且就在position的直接前驅位置 //針對以上這兩種情況，不做任何操作 if (__position == __i || __position == __j) return; //否則，進行拼接操作 this->transfer(__position, __i, __j); } //將范圍[first,last)內所有節點拼接到position所指位置之前 //注意：[first,last)和position可指向同一個鏈表， //但是position不能在[first,last)范圍之內 void splice(iterator __position, list&, iterator __first, iterator __last) { if (__first != __last) this->transfer(__position, __first, __last); } //以下是成員函數聲明，定義在list類外實現 //****************************** //刪除鏈表中值等于value的所有節點 void remove(const _Tp& __value); //刪除連續重復的元素節點，使之唯一 //注意：是連續的重復元素 void unique(); //合并兩個已排序的鏈表 void merge(list& __x); //反轉鏈表容器的內容 void reverse(); //按升序排序鏈表內容 void sort(); #ifdef __STL_MEMBER_TEMPLATES template <class _Predicate> void remove_if(_Predicate); template <class _BinaryPredicate> void unique(_BinaryPredicate); template <class _StrictWeakOrdering> void merge(list&, _StrictWeakOrdering); template <class _StrictWeakOrdering> void sort(_StrictWeakOrdering); #endif /* __STL_MEMBER_TEMPLATES */ }; ~~~ ? 在list容器的成員函數中最重要的幾個成員函數是插入insert()、擦除erase()、拼接splice()和排序sort()函數；以下利用圖文的形式對其進行講解；首先對插入節點函數進行insert()分析： ? 下面的插入函數是在指定的位置插入初始值為value的節點，具體實現見下面源碼剖析： ~~~ //***********插入節點********************* /**********以下是插入節點函數的原型，也是公共接口******** //在指定的位置pos之前插入值為value的數據節點 iterator insert( iterator pos, const T& value ); iterator insert( const_iterator pos, const T& value ); //在指定的位置pos之前插入n個值為value的數據節點 void insert( iterator pos, size_type count, const T& value ); iterator insert( const_iterator pos, size_type count, const T& value ); //在指定的位置pos之前插入[first,last)之間的數據節點 template< class InputIt > void insert( iterator pos, InputIt first, InputIt last); template< class InputIt > iterator insert( const_iterator pos, InputIt first, InputIt last ); *************************************/ /**在整個鏈表的操作中，插入操作是非常重要的，很多成員函數會調用該函數**/ //************************************* //在指定的位置插入初始值為x的節點 iterator insert(iterator __position, const _Tp& __x) { //首先創建一個初始值為x的節點，并返回該節點的地址 _Node* __tmp = _M_create_node(__x); //調整節點指針，把新節點插入到指定位置 __tmp->_M_next = __position._M_node; __tmp->_M_prev = __position._M_node->_M_prev; __position._M_node->_M_prev->_M_next = __tmp; __position._M_node->_M_prev = __tmp; //返回新節點地址 return __tmp; } ~~~ ? ? ? ? ?下面舉一個例子對插入函數insert()進行圖文分析：假設在以下list鏈表中節點5之前插入節點9，具體實現見下圖步驟：注：圖中的箭頭旁邊的數字表示語句的執行步驟 ? 第一步：首先初始化節點9，并為其分配節點空間； ? 第二步：調整節點5指針方向，使其與節點9連接； ? 第三步：調整節點5的前驅結點7指針的方向，使其與節點9連接；  ? 以下分析的是擦除指定位置的節點，詳細見源碼剖析： ~~~ //******************************* //**********在指定位置刪除節點*********** //**********以下是刪除節點的公共接口********* /****************************** //刪除指定位置pos的節點 iterator erase( iterator pos ); iterator erase( const_iterator pos ); //刪除指定范圍[first,last)的數據節點 iterator erase( iterator first, iterator last ); iterator erase( const_iterator first, const_iterator last ); ******************************/ //******************************* //在指定位置position刪除節點，并返回直接后繼節點的地址 iterator erase(iterator __position) { //調整前驅和后繼節點的位置 _List_node_base* __next_node = __position._M_node->_M_next; _List_node_base* __prev_node = __position._M_node->_M_prev; _Node* __n = (_Node*) __position._M_node; __prev_node->_M_next = __next_node; __next_node->_M_prev = __prev_node; _Destroy(&__n->_M_data); _M_put_node(__n); return iterator((_Node*) __next_node); } ~~~ ? 下面舉一個例子對擦除函數erase()進行圖文分析：假設在以下list鏈表中刪除節點5，具體實現見下圖步驟：圖中的箭頭旁邊的數字表示語句的執行步驟 ? 第一步：首先調整待刪除節點直接前驅指針，使其指向待刪除節點的直接后繼節點； ? 第二步：調整待刪除節點直接后繼指針方向，使其指向待刪除節點的直接前驅節點； ? 第三步：釋放待刪除節點對象，回收待刪除節點內存空；  ? 以下對遷移操作transfer()進行分析，該函數不是公共接口，屬于list容器的保護成員函數，但是它為拼接函數服務，拼接函數的核心就是遷移函數;transfer()和splice()函數源代碼剖析如下： ~~~ protected: //把區間[first,last）的節點數據插入到指定節點position之前,position不能在區間內部 //這個函數是list類的protected屬性，不是公共接口，只為list類成員服務 //為下面拼接函數void splice()服務 void transfer(iterator __position, iterator __first, iterator __last) { if (__position != __last) { // Remove [first, last) from its old position. __last._M_node->_M_prev->_M_next = __position._M_node; __first._M_node->_M_prev->_M_next = __last._M_node; __position._M_node->_M_prev->_M_next = __first._M_node; // Splice [first, last) into its new position. _List_node_base* __tmp = __position._M_node->_M_prev; __position._M_node->_M_prev = __last._M_node->_M_prev; __last._M_node->_M_prev = __first._M_node->_M_prev; __first._M_node->_M_prev = __tmp; } } public: //****************************** //***********拼接操作對外接口************* //把鏈表拼接到當前鏈表指定位置position之前 /*void splice(const_iterator pos, list& other); //把it在鏈表other所指的位置拼接到當前鏈表pos之前，it和pos可指向同一鏈表 void splice(const_iterator pos, list& other, const_iterator it); //把鏈表other的節點范圍[first,last)拼接在當前鏈表所指定的位置pos之前 //[first,last)和pos可指向同一鏈表 void splice(const_iterator pos, list& other, const_iterator first, const_iterator last); *******************************/ //****************************** //將鏈表x拼接到當前鏈表的指定位置position之前 //這里x和*this必須不同，即是兩個不同的鏈表 void splice(iterator __position, list& __x) { if (!__x.empty()) this->transfer(__position, __x.begin(), __x.end()); } //將i所指向的節點拼接到position所指位置之前 //注意：i和position可以指向同一個鏈表 void splice(iterator __position, list&, iterator __i) { iterator __j = __i; ++__j; //若i和position指向同一個鏈表，且指向同一位置 //或者i和position指向同一個鏈表，且就在position的直接前驅位置 //針對以上這兩種情況，不做任何操作 if (__position == __i || __position == __j) return; //否則，進行拼接操作 this->transfer(__position, __i, __j); } //將范圍[first,last)內所有節點拼接到position所指位置之前 //注意：[first,last)和position可指向同一個鏈表， //但是position不能在[first,last)范圍之內 void splice(iterator __position, list&, iterator __first, iterator __last) { if (__first != __last) this->transfer(__position, __first, __last); } ~~~ ? 下面用圖文對該函數進行分析：注：transfer函數中的每一條語句按順序對應圖中執行步驟； ? 下圖是執行第一過程Remove[first, last) from its old position流圖：  ? 下圖是執行第二過程Splice [first, last) into its new position流圖：  ?關于list容器的排序算法sort前面博文已經單獨對其進行講解，需要了解的請往前面博文[《STL源碼剖析——list容器的排序算法sort()》](http://blog.csdn.net/chenhanzhun/article/details/39337331)了解； ### list容器的操作符重載 ? 關于操作符重載具體看源碼剖析： ~~~ //******************************** //*********以下是比較運算符操作符重載*********** //******************************** template <class _Tp, class _Alloc> inline bool operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) { typedef typename list<_Tp,_Alloc>::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 <class _Tp, class _Alloc> inline bool operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) { return lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); } #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER template <class _Tp, class _Alloc> inline bool operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) { return !(__x == __y); } template <class _Tp, class _Alloc> inline bool operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) { return __y < __x; } template <class _Tp, class _Alloc> inline bool operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) { return !(__y < __x); } template <class _Tp, class _Alloc> inline bool operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) { return !(__x < __y); } //交換兩個鏈表內容 template <class _Tp, class _Alloc> inline void swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) { __x.swap(__y); } #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ //操作符重載結束 //******************************** ~~~ ### list容器完整源碼剖析 ? ? ?list容器完成源碼剖析： ~~~ //以下是list鏈表節點的數據結構 struct _List_node_base { _List_node_base* _M_next;//指向直接后繼節點 _List_node_base* _M_prev;//指向直接前驅節點 }; template <class _Tp> struct _List_node : public _List_node_base { _Tp _M_data;//節點存儲的數據 }; //以下是鏈表List_iterator_base的迭代器 struct _List_iterator_base { //數據類型 typedef size_t size_type; typedef ptrdiff_t difference_type; //list迭代器的類型是雙向迭代器bidirectional_iterator typedef bidirectional_iterator_tag iterator_category; //定義指向鏈表節點的指針 _List_node_base* _M_node; //構造函數 _List_iterator_base(_List_node_base* __x) : _M_node(__x) {} _List_iterator_base() {} //更新節點指針，指向直接前驅或直接后繼節點 void _M_incr() { _M_node = _M_node->_M_next; } void _M_decr() { _M_node = _M_node->_M_prev; } //操作符重載 bool operator==(const _List_iterator_base& __x) const { return _M_node == __x._M_node; } bool operator!=(const _List_iterator_base& __x) const { return _M_node != __x._M_node; } }; //以下是鏈表List_iterator的迭代器 template<class _Tp, class _Ref, class _Ptr> struct _List_iterator : public _List_iterator_base { typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; typedef _List_iterator<_Tp,_Ref,_Ptr> _Self; typedef _Tp value_type; typedef _Ptr pointer; typedef _Ref reference; typedef _List_node<_Tp> _Node; //構造函數 _List_iterator(_Node* __x) : _List_iterator_base(__x) {} _List_iterator() {} _List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {} //以下都是基本操作符的重載,取出節點數據 reference operator*() const { return ((_Node*) _M_node)->_M_data; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ _Self& operator++() { this->_M_incr(); return *this; } _Self operator++(int) { _Self __tmp = *this; this->_M_incr(); return __tmp; } _Self& operator--() { this->_M_decr(); return *this; } _Self operator--(int) { _Self __tmp = *this; this->_M_decr(); return __tmp; } }; #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION //返回迭代器的類型 inline bidirectional_iterator_tag iterator_category(const _List_iterator_base&) { return bidirectional_iterator_tag(); } template <class _Tp, class _Ref, class _Ptr> inline _Tp* value_type(const _List_iterator<_Tp, _Ref, _Ptr>&) { return 0; } inline ptrdiff_t* distance_type(const _List_iterator_base&) { return 0; } #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ // Base class that encapsulates details of allocators. Three cases: // an ordinary standard-conforming allocator, a standard-conforming // allocator with no non-static data, and an SGI-style allocator. // This complexity is necessary only because we're worrying about backward // compatibility and because we want to avoid wasting storage on an // allocator instance if it isn't necessary. #ifdef __STL_USE_STD_ALLOCATORS // Base for general standard-conforming allocators. template <class _Tp, class _Allocator, bool _IsStatic> class _List_alloc_base { public: typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type allocator_type;//返回節點配置器 allocator_type get_allocator() const { return _Node_allocator; } _List_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {} protected: _List_node<_Tp>* _M_get_node() { return _Node_allocator.allocate(1); } void _M_put_node(_List_node<_Tp>* __p) { _Node_allocator.deallocate(__p, 1); } protected: typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type _Node_allocator; _List_node<_Tp>* _M_node; }; // Specialization for instanceless allocators. //instanceless分配器偏特化版 template <class _Tp, class _Allocator> class _List_alloc_base<_Tp, _Allocator, true> { public: //定義分配器類型 typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type allocator_type; //返回節點配置器 allocator_type get_allocator() const { return allocator_type(); } //構造函數 _List_alloc_base(const allocator_type&) {} protected: typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type _Alloc_type; //分配一個節點空間 _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); } //回收一個節點空間 void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } protected: //定義節點指針 _List_node<_Tp>* _M_node; }; template <class _Tp, class _Alloc> class _List_base : public _List_alloc_base<_Tp, _Alloc, _Alloc_traits<_Tp, _Alloc>::_S_instanceless> { public: typedef _List_alloc_base<_Tp, _Alloc, _Alloc_traits<_Tp, _Alloc>::_S_instanceless> _Base; //allocator_type迭代器類型 typedef typename _Base::allocator_type allocator_type; //構造函數 _List_base(const allocator_type& __a) : _Base(__a) { _M_node = _M_get_node();//分配一個節點空間 _M_node->_M_next = _M_node;// _M_node->_M_prev = _M_node; } //析構函數 ~_List_base() { clear();//清空鏈表 _M_put_node(_M_node);//回收一個節點內存空間 } void clear();//清空鏈表 }; #else /* __STL_USE_STD_ALLOCATORS */ template <class _Tp, class _Alloc> class _List_base { public: typedef _Alloc allocator_type;//獲得分配器類型 allocator_type get_allocator() const { return allocator_type(); } //構造函數 _List_base(const allocator_type&) { _M_node = _M_get_node();//分配一個節點空間 //節點前驅和后繼指針指向自己，表示是一個空鏈表 _M_node->_M_next = _M_node; _M_node->_M_prev = _M_node; } //析構函數 ~_List_base() { clear();//清空鏈表 _M_put_node(_M_node);//回收一個節點內存空間 } void clear();//清空鏈表 protected: //迭代器類型 typedef simple_alloc<_List_node<_Tp>, _Alloc> _Alloc_type; //分配一個節點內存空間 _List_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); } //回收一個節點內存空間 void _M_put_node(_List_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } protected: _List_node<_Tp>* _M_node;//鏈表的節點指針 }; #endif /* __STL_USE_STD_ALLOCATORS */ //clear()函數的實現，即清空鏈表 template <class _Tp, class _Alloc> void _List_base<_Tp,_Alloc>::clear() { //選取_M_node->_M_next作為當前節點 _List_node<_Tp>* __cur = (_List_node<_Tp>*) _M_node->_M_next; while (__cur != _M_node) {//遍歷每一個節點 _List_node<_Tp>* __tmp = __cur;//設置一個節點臨時別名 __cur = (_List_node<_Tp>*) __cur->_M_next;//指向下一個節點 _Destroy(&__tmp->_M_data);//析構數據對象 _M_put_node(__tmp);//回收節點tmp指向的內存空間 } //空鏈表,即前驅和后繼指針都指向自己 _M_node->_M_next = _M_node; _M_node->_M_prev = _M_node; } //以下是雙向鏈表list類的定義，分配器_Alloc默認為第二級配置器 template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > class list : protected _List_base<_Tp, _Alloc> { // requirements: __STL_CLASS_REQUIRES(_Tp, _Assignable); typedef _List_base<_Tp, _Alloc> _Base; protected: typedef void* _Void_pointer;//定義指針類型 public: //以下是內嵌型別 typedef _Tp value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef _List_node<_Tp> _Node; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef typename _Base::allocator_type allocator_type;//分配器類型 allocator_type get_allocator() const { return _Base::get_allocator(); } public: //迭代器的類型 typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION typedef reverse_iterator<const_iterator> const_reverse_iterator; typedef reverse_iterator<iterator> reverse_iterator; #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ typedef reverse_bidirectional_iterator<const_iterator,value_type, const_reference,difference_type> const_reverse_iterator; typedef reverse_bidirectional_iterator<iterator,value_type,reference, difference_type> reverse_iterator; #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ protected: #ifdef __STL_HAS_NAMESPACES using _Base::_M_node; using _Base::_M_put_node; using _Base::_M_get_node; #endif /* __STL_HAS_NAMESPACES */ protected: //創建值為x的節點，并返回該節點的地址 _Node* _M_create_node(const _Tp& __x) { _Node* __p = _M_get_node();//分配一個節點空間 __STL_TRY {//把x值賦予指定的地址，即是data值 _Construct(&__p->_M_data, __x); } __STL_UNWIND(_M_put_node(__p)); return __p;//返回節點地址 } //創建默認值的節點 _Node* _M_create_node() { _Node* __p = _M_get_node(); __STL_TRY { _Construct(&__p->_M_data); } __STL_UNWIND(_M_put_node(__p)); return __p; } public: //以下是迭代器的定義 iterator begin() { return (_Node*)(_M_node->_M_next); } const_iterator begin() const { return (_Node*)(_M_node->_M_next); } iterator end() { return _M_node; } const_iterator end() const { return _M_node; } reverse_iterator rbegin() { return reverse_iterator(end()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } //判斷鏈表是否為空鏈表 bool empty() const { return _M_node->_M_next == _M_node; } //返回鏈表的大小 size_type size() const { size_type __result = 0; //返回兩個迭代器之間的距離 distance(begin(), end(), __result); //返回鏈表的元素個數 return __result; } size_type max_size() const { return size_type(-1); } //返回第一個節點數據的引用，reference相當于value_type& reference front() { return *begin(); } const_reference front() const { return *begin(); } //返回最后一個節點數據的引用 reference back() { return *(--end()); } const_reference back() const { return *(--end()); } //交換鏈表容器的內容 void swap(list<_Tp, _Alloc>& __x) { __STD::swap(_M_node, __x._M_node); } //************************************ //***********插入節點********************* /**********以下是插入節點函數的原型，也是公共接口******** //在指定的位置pos之前插入值為value的數據節點 iterator insert( iterator pos, const T& value ); iterator insert( const_iterator pos, const T& value ); //在指定的位置pos之前插入n個值為value的數據節點 void insert( iterator pos, size_type count, const T& value ); iterator insert( const_iterator pos, size_type count, const T& value ); //在指定的位置pos之前插入[first,last)之間的數據節點 template< class InputIt > void insert( iterator pos, InputIt first, InputIt last); template< class InputIt > iterator insert( const_iterator pos, InputIt first, InputIt last ); *************************************/ /**在整個鏈表的操作中，插入操作是非常重要的，很多成員函數會調用該函數**/ //************************************* //在指定的位置插入初始值為x的節點 iterator insert(iterator __position, const _Tp& __x) { //首先創建一個初始值為x的節點，并返回該節點的地址 _Node* __tmp = _M_create_node(__x); //調整節點指針，把新節點插入到指定位置 __tmp->_M_next = __position._M_node; __tmp->_M_prev = __position._M_node->_M_prev; __position._M_node->_M_prev->_M_next = __tmp; __position._M_node->_M_prev = __tmp; //返回新節點地址 return __tmp; } //在指定的位置插入為默認值的節點 iterator insert(iterator __position) { return insert(__position, _Tp()); } //在指定位置插入n個初始值為x的節點 void insert(iterator __pos, size_type __n, const _Tp& __x) { _M_fill_insert(__pos, __n, __x); } void _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x); #ifdef __STL_MEMBER_TEMPLATES // Check whether it's an integral type. If so, it's not an iterator. //這里采用__type_traits技術 //在指定位置插入指定范圍內的數據 //首先判斷輸入迭代器類型_InputIterator是否為整數類型 template <class _InputIterator> void insert(iterator __pos, _InputIterator __first, _InputIterator __last) { typedef typename _Is_integer<_InputIterator>::_Integral _Integral; _M_insert_dispatch(__pos, __first, __last, _Integral()); } //若輸入迭代器類型_InputIterator是為整數類型，調用此函數 template<class _Integer> void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type) { _M_fill_insert(__pos, (size_type) __n, (_Tp) __x); } //若輸入迭代器類型_InputIterator是不為整數類型，調用此函數 template <class _InputIterator> void _M_insert_dispatch(iterator __pos, _InputIterator __first, _InputIterator __last, __false_type); #else /* __STL_MEMBER_TEMPLATES */ void insert(iterator __position, const _Tp* __first, const _Tp* __last); void insert(iterator __position, const_iterator __first, const_iterator __last); #endif /* __STL_MEMBER_TEMPLATES */ //在鏈表頭插入節點 void push_front(const _Tp& __x) { insert(begin(), __x); } void push_front() {insert(begin());} //在鏈表尾插入節點 void push_back(const _Tp& __x) { insert(end(), __x); } void push_back() {insert(end());} //******************************* //**********在指定位置刪除節點*********** //**********以下是刪除節點的公共接口********* /****************************** //刪除指定位置pos的節點 iterator erase( iterator pos ); iterator erase( const_iterator pos ); //刪除指定范圍[first,last)的數據節點 iterator erase( iterator first, iterator last ); iterator erase( const_iterator first, const_iterator last ); ******************************/ //******************************* //在指定位置position刪除節點，并返回直接后繼節點的地址 iterator erase(iterator __position) { //調整前驅和后繼節點的位置 _List_node_base* __next_node = __position._M_node->_M_next; _List_node_base* __prev_node = __position._M_node->_M_prev; _Node* __n = (_Node*) __position._M_node; __prev_node->_M_next = __next_node; __next_node->_M_prev = __prev_node; _Destroy(&__n->_M_data); _M_put_node(__n); return iterator((_Node*) __next_node); } //刪除兩個迭代器之間的節點 iterator erase(iterator __first, iterator __last); //清空鏈表，這里是調用父類的clear()函數 void clear() { _Base::clear(); } //調整鏈表的大小 void resize(size_type __new_size, const _Tp& __x); void resize(size_type __new_size) { this->resize(__new_size, _Tp()); } //取出第一個數據節點 void pop_front() { erase(begin()); } //取出最后一個數據節點 void pop_back() { iterator __tmp = end(); erase(--__tmp); } //************************************ /*************以下是構造函數****************** //***********默認構造函數********************* explicit list( const Allocator& alloc = Allocator() ); //************具有初值和大小的構造函數************ 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 ); //******某個范圍的值為初始值的構造函數************** template< class InputIt > list( InputIt first, InputIt last, const Allocator& alloc = Allocator() ); //******拷貝構造函數************************* list( const list& other ); */ //************************************ //構造函數 //鏈表的默認構造函數 explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {} list(size_type __n, const _Tp& __value, const allocator_type& __a = allocator_type()) : _Base(__a) { insert(begin(), __n, __value); } explicit list(size_type __n) : _Base(allocator_type()) { insert(begin(), __n, _Tp()); } #ifdef __STL_MEMBER_TEMPLATES // We don't need any dispatching tricks here, because insert does all of // that anyway. template <class _InputIterator> list(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) { insert(begin(), __first, __last); } #else /* __STL_MEMBER_TEMPLATES */ list(const _Tp* __first, const _Tp* __last, const allocator_type& __a = allocator_type()) : _Base(__a) { this->insert(begin(), __first, __last); } list(const_iterator __first, const_iterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) { this->insert(begin(), __first, __last); } #endif /* __STL_MEMBER_TEMPLATES */ list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator()) { insert(begin(), __x.begin(), __x.end()); }//拷貝構造函數 ~list() { }//析構函數 //賦值操作 list<_Tp, _Alloc>& operator=(const list<_Tp, _Alloc>& __x); //構造函數，析構函數，賦值操作 定義到此結束 //*********************************** public: // assign(), a generalized assignment member function. Two // versions: one that takes a count, and one that takes a range. // The range version is a member template, so we dispatch on whether // or not the type is an integer. /*********************************** //assign()函數的兩個版本原型，功能是在已定義的list容器填充值 void assign( size_type count, const T& value ); template< class InputIt > void assign( InputIt first, InputIt last ); //*********************************** 例子： #include <list> #include <iostream> int main() { std::list<char> characters; //若定義characters時并初始化為字符b，下面的填充操作一樣有效 //std::list<char>characters(5,'b') characters.assign(5, 'a'); for (char c : characters) { std::cout << c << ' '; } return 0; } 輸出結果：a a a a a ***********************************/ //這里是第一個版本void assign( size_type count, const T& value ); void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); } //這里為什么要把_M_fill_assign這個函數放在public呢？？保護起來不是更好嗎？？ void _M_fill_assign(size_type __n, const _Tp& __val); #ifdef __STL_MEMBER_TEMPLATES //以下是針對assign()函數的第二個版本 /* template< class InputIt > void assign( InputIt first, InputIt last ); 這里有偏特化的現象，判斷輸入數據類型是否為整數型別 */ template <class _InputIterator> void assign(_InputIterator __first, _InputIterator __last) { typedef typename _Is_integer<_InputIterator>::_Integral _Integral; _M_assign_dispatch(__first, __last, _Integral()); } //若輸入數據類型為整數型別，則派送到此函數 template <class _Integer> void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) { _M_fill_assign((size_type) __n, (_Tp) __val); } //若輸入數據類型不是整數型別，則派送到此函數 template <class _InputIterator> void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type); #endif /* __STL_MEMBER_TEMPLATES */ //assign()函數定義結束 //********************************* protected: //把區間[first,last）的節點數據插入到指定節點position之前,position不能在區間內部 //這個函數是list類的protected屬性，不是公共接口，只為list類成員服務 //為下面拼接函數void splice()服務 void transfer(iterator __position, iterator __first, iterator __last) { if (__position != __last) { // Remove [first, last) from its old position. __last._M_node->_M_prev->_M_next = __position._M_node; __first._M_node->_M_prev->_M_next = __last._M_node; __position._M_node->_M_prev->_M_next = __first._M_node; // Splice [first, last) into its new position. _List_node_base* __tmp = __position._M_node->_M_prev; __position._M_node->_M_prev = __last._M_node->_M_prev; __last._M_node->_M_prev = __first._M_node->_M_prev; __first._M_node->_M_prev = __tmp; } } public: //****************************** //***********拼接操作對外接口************* //把鏈表拼接到當前鏈表指定位置position之前 /*void splice(const_iterator pos, list& other); //把it在鏈表other所指的位置拼接到當前鏈表pos之前，it和pos可指向同一鏈表 void splice(const_iterator pos, list& other, const_iterator it); //把鏈表other的節點范圍[first,last)拼接在當前鏈表所指定的位置pos之前 //[first,last)和pos可指向同一鏈表 void splice(const_iterator pos, list& other, const_iterator first, const_iterator last); *******************************/ //****************************** //將鏈表x拼接到當前鏈表的指定位置position之前 //這里x和*this必須不同，即是兩個不同的鏈表 void splice(iterator __position, list& __x) { if (!__x.empty()) this->transfer(__position, __x.begin(), __x.end()); } //將i所指向的節點拼接到position所指位置之前 //注意：i和position可以指向同一個鏈表 void splice(iterator __position, list&, iterator __i) { iterator __j = __i; ++__j; //若i和position指向同一個鏈表，且指向同一位置 //或者i和position指向同一個鏈表，且就在position的直接前驅位置 //針對以上這兩種情況，不做任何操作 if (__position == __i || __position == __j) return; //否則，進行拼接操作 this->transfer(__position, __i, __j); } //將范圍[first,last)內所有節點拼接到position所指位置之前 //注意：[first,last)和position可指向同一個鏈表， //但是position不能在[first,last)范圍之內 void splice(iterator __position, list&, iterator __first, iterator __last) { if (__first != __last) this->transfer(__position, __first, __last); } //以下是成員函數聲明，定義在list類外實現 //****************************** //刪除鏈表中值等于value的所有節點 void remove(const _Tp& __value); //刪除連續重復的元素節點，使之唯一 //注意：是連續的重復元素 void unique(); //合并兩個已排序的鏈表 void merge(list& __x); //反轉鏈表容器的內容 void reverse(); //按升序排序鏈表內容 void sort(); #ifdef __STL_MEMBER_TEMPLATES template <class _Predicate> void remove_if(_Predicate); template <class _BinaryPredicate> void unique(_BinaryPredicate); template <class _StrictWeakOrdering> void merge(list&, _StrictWeakOrdering); template <class _StrictWeakOrdering> void sort(_StrictWeakOrdering); #endif /* __STL_MEMBER_TEMPLATES */ }; //list定義結束 //******************************** //******************************** //*********以下是比較運算符操作符重載*********** //******************************** template <class _Tp, class _Alloc> inline bool operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) { typedef typename list<_Tp,_Alloc>::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 <class _Tp, class _Alloc> inline bool operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) { return lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); } #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER template <class _Tp, class _Alloc> inline bool operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) { return !(__x == __y); } template <class _Tp, class _Alloc> inline bool operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) { return __y < __x; } template <class _Tp, class _Alloc> inline bool operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) { return !(__y < __x); } template <class _Tp, class _Alloc> inline bool operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) { return !(__x < __y); } //交換兩個鏈表內容 template <class _Tp, class _Alloc> inline void swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) { __x.swap(__y); } #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ //操作符重載結束 //******************************** //以下是list類成員函數的具體定義 //******************************** #ifdef __STL_MEMBER_TEMPLATES template <class _Tp, class _Alloc> template <class _InputIter> void list<_Tp, _Alloc>::_M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last, __false_type) { for ( ; __first != __last; ++__first)//遍歷范圍[first,last) insert(__position, *__first);//一個一個節點插入 } #else /* __STL_MEMBER_TEMPLATES */ template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::insert(iterator __position, const _Tp* __first, const _Tp* __last) { for ( ; __first != __last; ++__first)//遍歷范圍[first,last) insert(__position, *__first);//一個一個節點插入 } template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::insert(iterator __position, const_iterator __first, const_iterator __last) { for ( ; __first != __last; ++__first)//遍歷范圍[first,last) insert(__position, *__first);//一個一個節點插入 } #endif /* __STL_MEMBER_TEMPLATES */ template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n, const _Tp& __x) { for ( ; __n > 0; --__n)//插入n個節點 insert(__position, __x);//在position之前插入x節點 } template <class _Tp, class _Alloc> typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first, iterator __last) { while (__first != __last)//遍歷范圍[first,last) erase(__first++);//一個一個節點刪除 return __last; } //重新調整容器的大小 template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x) { iterator __i = begin(); size_type __len = 0;//表示容器的原始大小 for ( ; __i != end() && __len < __new_size; ++__i, ++__len) ; if (__len == __new_size)//若容器新的長度比原來的小，則擦除多余的元素 erase(__i, end()); else//若容器新的長度比原來的大，則把其初始化為x值 // __i == end() insert(end(), __new_size - __len, __x); } //賦值操作 template <class _Tp, class _Alloc> list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x) { if (this != &__x) { iterator __first1 = begin(); iterator __last1 = end(); const_iterator __first2 = __x.begin(); const_iterator __last2 = __x.end(); while (__first1 != __last1 && __first2 != __last2) *__first1++ = *__first2++; if (__first2 == __last2)//若當前容器的大小大于x容器大小 erase(__first1, __last1);//則擦除多余部分 else//若當前容器大小小于x容器大小，則把x容器剩下的數據插入到當前容器尾 insert(__last1, __first2, __last2); //上面if語句里面的語句可以用下面代替 /* clear(); this->assign(__x.begin(),__x.end()); */ } return *this; } //在已定義list容器中填充n個初始值為val的節點 template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) { iterator __i = begin(); for ( ; __i != end() && __n > 0; ++__i, --__n) *__i = __val; if (__n > 0)//若容器大小不夠存儲n個節點，則使用插入函數 insert(end(), __n, __val); else//若容器原來的數據大小比n大，則擦除多余的數據 erase(__i, end()); //注：個人認為該函數也可以這樣實現： //首先清空容器原來的內容 //然后在容器插入n個值為val的數據節點 /* _Tp tmp = __val; clear(); insert(begin(),__n,__val); */ } #ifdef __STL_MEMBER_TEMPLATES //若輸入數據類型不是整數型別時，assign(_InputIter __first, _InputIter __last)調用該函數 //在[first,last)實現填充數值操作 template <class _Tp, class _Alloc> template <class _InputIter> void list<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type) { //獲取原始容器的大小 iterator __first1 = begin(); iterator __last1 = end(); //若原始容器和[first2,last2)大小不為0或1，則進行賦值操作 for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) *__first1 = *__first2; if (__first2 == __last2)//若原始容器的大小比[first2,last2)大 erase(__first1, __last1); else //若原始容器的大小比[first2,last2)小 insert(__last1, __first2, __last2); } #endif /* __STL_MEMBER_TEMPLATES */ //刪除容器中值為value的所有數據節點 template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::remove(const _Tp& __value) { iterator __first = begin(); iterator __last = end(); while (__first != __last) {//遍歷整個容器 iterator __next = __first; ++__next; if (*__first == __value) erase(__first);//若存在該值，則擦除 __first = __next;//繼續查找，直到first == last } } // template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::unique() { iterator __first = begin(); iterator __last = end(); if (__first == __last) return;//若為空容器，則退出 iterator __next = __first; while (++__next != __last) {//若容器大小大于1，進入while循環 if (*__first == *__next)//若相鄰元素相同 erase(__next);//則擦除 else//否則，查找下一節點 __first = __next; __next = __first; } } //合并兩個已排序的鏈表,合并后的鏈表仍然是有序的 template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x) { iterator __first1 = begin(); iterator __last1 = end(); iterator __first2 = __x.begin(); iterator __last2 = __x.end(); while (__first1 != __last1 && __first2 != __last2) if (*__first2 < *__first1) { iterator __next = __first2; transfer(__first1, __first2, ++__next);//把first2拼接在first1之前 __first2 = __next; } else ++__first1; //若鏈表x比當前鏈表長，則把剩余的數據節點拼接到當前鏈表的尾端 if (__first2 != __last2) transfer(__last1, __first2, __last2); } inline void __List_base_reverse(_List_node_base* __p) { _List_node_base* __tmp = __p; do { __STD::swap(__tmp->_M_next, __tmp->_M_prev);//交換指針所指的節點地址 __tmp = __tmp->_M_prev; // Old next node is now prev. } while (__tmp != __p); } //把當前鏈表逆序 template <class _Tp, class _Alloc> inline void list<_Tp, _Alloc>::reverse() { __List_base_reverse(this->_M_node); } //按升序進行排序，list鏈表的迭代器訪問時雙向迭代器 //因為STL的排序算法函數sort()是接受隨機訪問迭代器，在這里并不適合 template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::sort() { // Do nothing if the list has length 0 or 1. if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) { list<_Tp, _Alloc> __carry;//carry鏈表起到搬運的作用 //counter鏈表是中間存儲作用 /* *其中對于counter[i]里面最多的存儲數據為2^(i+1)個節點 *若超出則向高位進位即counter[i+1] */ list<_Tp, _Alloc> __counter[64]; int __fill = 0; while (!empty()) {//若不是空鏈表 //第一步： __carry.splice(__carry.begin(), *this, begin());//把當前鏈表的第一個節點放在carry鏈表頭 int __i = 0; while(__i < __fill && !__counter[__i].empty()) { //第二步： __counter[__i].merge(__carry);//把鏈表carry合并到counter[i] //第三步： __carry.swap(__counter[__i++]);//交換鏈表carry和counter[i]內容 } //第四步： __carry.swap(__counter[__i]);//交換鏈表carry和counter[i]內容 //第五步： if (__i == __fill) ++__fill; } for (int __i = 1; __i < __fill; ++__i) //第六步： __counter[__i].merge(__counter[__i-1]);//把低位不滿足進位的剩余數據全部有序的合并到上一位 //第七步： swap(__counter[__fill-1]);//最后把已排序好的鏈表內容交換到當前鏈表 } } #ifdef __STL_MEMBER_TEMPLATES template <class _Tp, class _Alloc> template <class _Predicate> void list<_Tp, _Alloc>::remove_if(_Predicate __pred) { iterator __first = begin(); iterator __last = end(); while (__first != __last) { iterator __next = __first; ++__next; if (__pred(*__first)) erase(__first); __first = __next; } } template <class _Tp, class _Alloc> template <class _BinaryPredicate> void list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) { iterator __first = begin(); iterator __last = end(); if (__first == __last) return; iterator __next = __first; while (++__next != __last) { if (__binary_pred(*__first, *__next)) erase(__next); else __first = __next; __next = __first; } } template <class _Tp, class _Alloc> template <class _StrictWeakOrdering> void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x, _StrictWeakOrdering __comp) { iterator __first1 = begin(); iterator __last1 = end(); iterator __first2 = __x.begin(); iterator __last2 = __x.end(); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first2, *__first1)) { iterator __next = __first2; transfer(__first1, __first2, ++__next); __first2 = __next; } else ++__first1; if (__first2 != __last2) transfer(__last1, __first2, __last2); } template <class _Tp, class _Alloc> template <class _StrictWeakOrdering> void list<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp) { // Do nothing if the list has length 0 or 1. if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) { list<_Tp, _Alloc> __carry; list<_Tp, _Alloc> __counter[64]; int __fill = 0; while (!empty()) { __carry.splice(__carry.begin(), *this, begin()); int __i = 0; while(__i < __fill && !__counter[__i].empty()) { __counter[__i].merge(__carry, __comp); __carry.swap(__counter[__i++]); } __carry.swap(__counter[__i]); if (__i == __fill) ++__fill; } for (int __i = 1; __i < __fill; ++__i) __counter[__i].merge(__counter[__i-1], __comp); swap(__counter[__fill-1]); } } #endif /* __STL_MEMBER_TEMPLATES */ #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) #pragma reset woff 1174 #pragma reset woff 1375 #endif __STL_END_NAMESPACE #endif /* __SGI_STL_INTERNAL_LIST_H */ // Local Variables: // mode:C++ // End: ~~~ ? 參考資料： ? ? 《STL源碼剖析》侯捷 ? ? [《](http://www.programlife.net/stl-list.html)[STL筆記之list](http://www.programlife.net/stl-list.html)[》](http://www.programlife.net/stl-list.html) ? ? [《](http://blog.csdn.net/mdl13412/article/details/6645244)[STL源碼剖析--stl_list.h》](http://blog.csdn.net/mdl13412/article/details/6645244) ? ??[《STL源碼剖析 容器 stl_list.h》](http://blog.csdn.net/zhengsenlie/article/details/38011161)