一 List 核心字段和接口

1. 節點字段

template<class T>
struct __list_node
{typedef void* void_pointer;void_pointer prev;void_pointer next;T data;
}

由于 鏈表?不是連續的內存塊，所以對每一個申請到的內存塊要進行統一組織，也就是封裝成一個類，添加前后指針來關聯申請到的內存塊，在由?List 統一管理起來。

2. List本身字段

template<class T.class Alloc=alloc>
class list
{protecred:// node 節點typedef __list_node<T> list_node;public:typedef list_node* link_type;ptotected:link_type node;// 這里沒有按 T 來開辟空間，是按節點來開辟空間typedef simple_alloc<list_node,Alloc> list_node_allocator;    // 申請一個節點link_type get_node(){ return list_node_allocator::allocate(); }// 釋放一個節點void put_node(link_type p){ list_node_allocator::deallocate(p); }// 申請并構造這個節點link_type create_node(const T& x){link_type p = get_node();construct(&p->data,x);        // 全局函數return p;    }// 析構并銷毀這個節點void destroy_node(link_type p){destroy(&p->data);            // 全局函數put_node(p);}public:// 無參構造，初始化哨兵節點list(){ empty_initialize(); }protected:void empty_initialize(){node = get_node();node->next = node;node->prev = node;}
}    

list的無參構造表示沒有節點，但要有個哨兵節點，因為list是雙向帶頭循環鏈表，為了處理邊界情況，所以有一個領頭羊。

那么怎么訪問/遍歷/修改 List 中的節點，一個個的訪問嗎？下面來看看 List 的迭代器。

由于 List 不像vector那樣有一段連續的空間，所以不能直接用裸指針作為 List 的迭代器，但可以為這個指針封裝一層，讓他模擬指針的行為即可。

template <class T,class Ref,class Ptr>
struct __list_iterator
{// 非 const 迭代器，list操作時使用typedef __list_iterator<T,T&,T*> iterator;// const/非 const迭代器，迭代器內部使用typedef __list_iterator<T,Ref,Ptr> self;// 表示該迭代器是雙向迭代器，前章vector的迭代器是隨機訪問迭代器typedef bidirectional_iterator_tag iterator_category;// 迭代器管理的節點內部 T 對象typedef T value_type;// 迭代器管理的節點內部 T 指針typedef Ptr pointer;// 迭代器管理的節點內部 T 引用typedef Ref reference;// 迭代器管理的節點指針typedef __list_node<T>* link_type;// 無符號整型typedef size_t size_type;// 有符號整型typedef ptrdiff_t difference_type;// node 指針link_type node;// 指針構造__list_iterator(link_type x):node(x){}// 無參構造__list_iterator(){}// 迭代器的拷貝構造，這里是淺拷貝__list_iterator(const iterator& x):node(x.node){}// 迭代器判相等bool operator==(const self& x)const {return node == x.node;}// 迭代器判不相等bool operator!=(const self& x)const {return node != x.node;}// 迭代器模擬指針訪問 node 內部的 Treference operator*()const {return (*node).data;}    // 迭代器模擬指針訪問 node 內部的 T 的地址reference operator->()const {return &(operator*());}// 前置++ ，返回下一個迭代器的引用self& operator++(){// 先訪問 node 內部的 next，在把 next 強轉成 node*，next 是 void* 類型node = (link_type)(*node).next;return *this;}//后置++，返回當前迭代器的拷貝self operator++(int){// 當前迭代器拷貝給臨時對象self tmp = *this;// this 是指針，解引用成迭代器對象，然后進行 ++++*this;// 返回臨時對象，值返回有拷貝return tmp;}// 下面2個--，和上面2個++一樣 Self& operator--(){self tmp = *this;return *this}self operator--(int){self tmp = *this;--*this;return tmp;}};

list 內部對管理的 node 進行操作的函數：

template <class T,class Alloc = alloc>
class list
{public:// 返回第一個節點，并用這個節點構造一個迭代器iterator begin() { return (link_type)((*node).next); }// 返回最后一個節點，原理同上iterator end() { return node; }// 判空，和哨兵節點比較bool empty() const { return node->next == node; }// 這里調用了distance，針對迭代器類型進行計數，比如vector(end() - begin())，List就逐個遍歷了size_type size() const{size_type result = 0;distance(begin(),end(),result);return result;}// 返回第一個迭代器內部的 T 對象的引用reference front() { return *begin(); }// 返回最后一個迭代器內部 T 對象的引用reference back() { return *(--end()); }// 頭插void push_front(const T& x) { insert(begin(),x); }// 尾插void push_back(const T& x) { insert(end(),x); }// 頭刪void pop_front() { erase(begin()); }// 尾刪，這里 end() 是哨兵節點，所以要--到前一個節點，也就是實際的最后一個節點// tmp 是淺拷貝的 end()void pop_back() {iterator tmp = end();erase(--tmp);}// 在 pos 位置前面插入 Tvoid insert(iterator position,const T& x){// 構造 node 節點link_type tmp = create_node(x);// 讓這個新節點 next 指向 pos// 下面2個操作不需要強轉，因為只需要改變指針的指向，并不訪問指針內容tmp->next = position.node;// 讓這個新節點 prev 指向 pos 的上一個節點(prev)tmp->prev = position.node->prev;// 這里需要訪問指針的內容，讓這樣內容的 next 指向 tmp，所以要強轉// 讓 pos 的 prev 的 next 指向 tmp(link_type(position.node->prev))->next = tmp;// 讓 pos 的 prev 指向 tmp，這里也不需要強轉，不訪問 prev，只是改變指向position.node->prev = tmp;return tmp;}// 刪除指定迭代器，并返回迭代器的下一個迭代器iterator erase(iterator position){// 該迭代器的下一個迭代器link_type next_node = link_type(position.node->next);// 該迭代器的上一個迭代器link_type prev_node = link_type(position.node->prev);// 讓該迭代器的上一個迭代器指向該迭代器的下一個迭代器prev_node->next = next_node;// 讓該迭代器的下一個迭代器指向該迭代器的上一個迭代器next_node->prev = prev_node;// 釋放該迭代器destroy_node(position.node);// 返回該迭代器的下一個迭代器return iterator(next_node);}// 清空節點，保留哨兵節點template<class T,class Alloc>void list<T,Alloc>::clear(){// cur = 哨兵節點的下一個link_type cur = (link_type)node->next;while(cur != node){// tmp 指向 cur 的 nodelink_type tmp = cur;// cur 訪問 node 的 next，在強轉 next 為 node*，這里 next 是 void* 類型cur = (link_type)cur->next;// 析構并釋放destroy_node(tmp);}// 這里刪除全部節點，沒刪除一個沒有處理相互之間的鏈接關系，哨兵節點的指針是不可預期的// 所以要重置成初始狀態node->next = node;node->prev = node;}// 刪除所有的 T 對象template<class T,class Alloc>void list<T,Alloc>::remove(const T& value){// 取 List 的頭iterator first = begin();// 取哨兵節點iterator last = end();while(first != last){// 這個地方刪除用到了迭代器，不像 clear 直接操作 node iterator next = first;++next;相等就刪除，并調整鏈接前后關系if(*first == value)erase(first);first = next;}}// 刪除連續且相同的 T，不連續相同不刪除template<class T,class Alloc>void list<T,Alloc>::unique(){// 和 remove 一樣iterator first = begin();iterator last = end();// 空鏈表直接返回if(first == last) return;iterator next = first;while(++next != last){// 這里刪除的是后一個 Tif(*first == *next) erase(next);// 不相等讓前一個 T first 等于 后一個不相等的 T nextelse first = next;// 刪完了，讓后一個 T 也就是 next，等于前一個 T 也就是 firstnext = first;}}// 將 first ~ last 這個區間的迭代器移動到 pos 的前面，不包含 last// 該函數只能用于同一個 list 內部的迭代器進行操作，不同的list不行，即使模板參數一樣void transfer(iterator position,iterator first,iterator last){// 尾和 pos 先等不需要移動，因為 first ~ last 已經在 pos 的前面了if(position != last){// 讓 last 的上一個 node 的 next 指向 pos(*(link_type((*last.node).prev))).next = position.node;// 讓 first 的上一個 node 的 next 指向 last(*(link_type((*first.node).prev))).next = last.node;// 讓 pos 的上一個的 next 指向 first(*(link_type((*position.node).prev))).next = first.node;// tmp 指向 pos 的上一個 nodelink_type tmp = link_type((*position.node).prev);// 讓 pos 的 prev 等于 last 的上一個 node(*position.node).prev = (*last.node).prev;// 讓 last 的上prev 等于 first 的上一個 node(*last.node).prev = (*first.node).prev;// 讓 first 的 prev 指向 tmp(*first.node).prev = tmp;// 讓 5,6,7 插入到4的前面pos = 4,first = 5,last = 8[1,2,3,4,5,6,7,8] -> [1,2,3,5,6,7,4,8]第一步：讓 last  的上一個 node      即7,指向4第二步：讓 first 的上一個 node      即4，指向8第三步：讓 pos   的上一個 node      即3，指向5第四步：讓 tmp = pos 的上一個       即3第五步：讓 pos   的 prev           即3，指向7第六步：讓 last  的 prev           即7，指向3第七步：讓 first 的 prev           即3，指向 tmp 4}}// STL源碼刨析這本書里的 splice 都只能作用與同一個 list，不能跨 list// 主要是因為都調用了 transfer 接口，這個接口只是針對單個 list// 把一個 list 的所有節點挪到 該迭代器的前面void splice(iterator position,list&,iterator i){// 不為空直接調用if(!x.empty()) transfer(position,x.begin(),x.end());}// 把一個迭代器挪到 pos 前面void splice(iterator position,list&,iterator i){iterator j = i;++j;if(position ==i || position == j) return;transfer(position,i,j);}// 把一個迭代器區間挪到 pos 前面void splice(iterator position,list&,iterator first,iterator last){if(first != last) transfer(position,first,last);}// 合并2個有序的 listtemplate<class T,class Alloc>void merage(list<T,ALloc>& x){// 標記2個list的頭和尾iterator first1 = begin();iterator last1 = end();iterator first2 = x.begin();iterator last2 = x.end();// 有一個為空則結束循環while(first1 != last1 && first2 != last2){// 如果第二個list的當前迭代器小于第一個list的當前迭代器if(*first2 < *first1){// 標記 first2iterator next = first2;// 把單個 first2 放到 first1 的前面transfer(first1,first2,++next);// 更新 first2first2 = next;}else ++first1;}// 如果 first2 的迭代器沒有到結尾，則把剩余的元素挪到 first1 的前面// list1：1，2，3，4 list2：0，5，6，7，8// 上面的 while 循環把 0 挪到 1 的前面：list1 0，1，2，3，4// 然后 list1 的迭代器到結尾，4的后面// 此時 list2 的迭代器指向 5，在把 5 到 last2，也就是 list2 的結尾，5，6，7，8 挪到// last1(4 的后面),在用 transfer 函數把 5，6，7，8 挪到 last的前面，即 4 的后面if(first2 != last2) transfer(last1,first2,last2);}// 反轉 list 所有節點void reverse(){// 如果為空或者只有一個節點，直接返回if(node->next == node || (link_type)(node->next)->next == node) return;// 保存下一個節點iterator first = begin();++first;// 下一個節點不等于 end()while(first != end()){// 保存下一個節點iterator old = frist;// 讓 first + 到后面一個節點++first;// 在讓 old ~ first 這個區間的節點移到 begin() 的前面// 其實只是移動一個節點,這里 first 是 old 的后面的節點，是開區間，不包括 first// 只是單純的把 old 移到 begin() 前面transfer(begin(),old,first);}}void sort(){// 如果為空或者只有一個節點，直接返回if(node->next == node || (link_type)(node->next)->next == node) return;// 這個對象為后面交換合并做鋪墊list<T,Alloc> carry;// 定義 64 個桶，每個桶是 2^n 次方個元素list<T,Alloc> counter[64];// 桶的最高層數int fill = 0;// 4 3 2 1while(!empty()){// 先取當前要排序對象的 第一個節點carry.splice(carry.begin(),*this,begin());// 該變量表示要合并的層數int i = 0;// 循環和合并while(i < fill && !counter[i].empty()){counter[i].merage(carry);carry.swap(counter[i++]);}// 合并之后的結果放到對應的桶里carry.swap(count[i]);// 如果合并的層數達到最高的層數,則讓最高的層數++if(i == fill) ++fill;}// 從 1 開始 合并前面的 桶for(int i = i;i < fill;++i){counter[i].merge(counter[i-1]);}// 最后在交換回去swap(counter[fill - 1]);}
}

transfer：