目錄
????????1.前言
????????2.list的節點定義和結構
????????3.list的迭代器定義和結構
????????4.list的定義和結構
????????5.list的內存管理????????
????????6.list的元素操作
? ? ? ? 前言
? ? ? ? 在刨析了vector容器的源碼后，list容器相比與vector容器，其元素的插入和刪除較快，不需要對原本容器中的元素進行排序，因此針對list容器的每一次插入和刪除都是常數級。而且list對于內存的申請屬于是需要幾個內存就申請幾個內容，而vector申請的內存通常為當前內存的兩倍。本章將對list進行講解，至于何時使用vector，何時使用list更是要區別于元素的多少，具體的業務場景。
list的節點定義和結構
? ? ? ? list的結構屬于環狀雙向鏈表的結構(PS：環狀雙向鏈表，指的是鏈表的頭指針指向尾節點，鏈表的尾指針指向頭節點，故稱環狀雙向鏈表)，應此在實現list時，我們還需要針對其list中的每一個節點進行設計。在設計list節點時，要實現list雙向鏈表的特性，我們還需要兩個指針，一個頭指針一個尾指針，且每一個節點需要存儲值，故list節點設計代碼如下：
//list節點設計代碼
template <class T>
struct _list_node{typedef void* void_pointer;//設計為空指針方便類型轉換，也可以設計為_list_node<T>*void_pointer prev;//頭指針void_pointer next;//尾指針T data; //存儲值
}list的迭代器定義和結構
????????相比于vector的隨機迭代器，list提供的迭代器為雙向迭代器，因為list不支持下標操作。而且vector在擴充元素時，若內存空間不足則需要向系統申請新的空間，并把舊元素復制到新的空間上，這會導致迭代器生效(類似于虛吊指針，也可以叫懸空指針)。但是list的插入操作都只是修改節點的頭指針和尾指針的指向空間，應此不會導致迭代器生效。在了解list迭代器類型后，其設計的源碼如下：
//list的迭代器設計源碼
template<class T, class Ref, class Ptr> //Ref代表解引用時返回引用類型，Ptr則是指針類型
struct _list_iterator{typedef _list_node<T>* link_type; /list節點指針link_type node; //變量node指向list節點typedef _List_iterator<T, Ref, Ptr> self; //當前實例對象的別名typedef _list_iterator<T, T&，T*> iterator; //當前實例對象的迭代器typedef bidirectional_iterator_tag iterator_category; //封裝雙向迭代器//以下為迭代器常用封裝，Traits編程方法typedef T value_tyoe;typedef Ptr pointer;typedef Ref reference;typedef size_t size_type;typedef ptrdiff_t difference_type;
}? ? ? ? 在知道list迭代器為雙向迭代器后，我們知道雙向迭代器的特點，即不支持下標操作，僅支持迭代器的累加，遞減，解引用和判斷節點值是否相等的特性，為了實現這些特性，其迭代器還需要實現以下功能：
//list迭代器支持的操作的實現
_list_iterator(){}
_list_iterator(link_type x) : node(x){}
_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;
}pointer operator->() const { return &(operator*()); } //取值(左值)reference operator*() const { return (*node).data; } //取值(右值)//以下為累加的實現
self& operator++(){node = (link_type)((*node).next);return *this;
}self& operator++(int){self temp =*this;++(*this);return tem;
}//以下為遞減的實現
self& operator--(){node = (link_type)((*node).prev);return *this;
}self& operator--(int){self tmp = *this;--(*this);return tmp;
}list的定義和結構
? ? ? ? 在了解list節點和迭代器的定義和結構后，我們還提到list是一種環狀的雙向鏈表，而由于獨特的環狀結構，我們在設計該雙鏈表時需要插入一個空的節點(PS：是為了滿足STL的前閉后開的要求，但是我覺得更多的是為了方便判斷是否遍歷完整個鏈表而設計的節點)。在滿足設計的結構的基礎上，我們在實現list的結構時，還需要定義形如begin()，end()，empty()，size()，font()和back()等操作函數，故list結構大致如下：
//list的結構實現
template<class T, class Alloc = alloc>
class list{
protected:typedef _list_node<T> list_node;typedef simple_alloca<list_node,Alloc> list_node_allocator;//封裝迭代器，內存管理中使用
public:typedef list_node* link_type;
protected:link_type node; //節點指針，指向鏈表的頭節點便可表示整個鏈表
}iterator begin() { return (link_type)((*node).next); } //獲取頭節點iterator end() { return node; } //獲取尾節點bool empty() const { return node->next == node; } //判斷是否為空節點size_type size() const{ //計算容器中元素的個數size_type result = 0; distance(begin(), end(), result);//遍歷容器return result;
}reference front() { return *begin(); } //取頭節點的值rederence back() { return *(--end()); } //取尾節點的值? ? ? ? 針對list的環狀雙向鏈表，可以參考下圖：
圖1.listD的環狀雙向鏈表結構圖
list的內存管理????????
? ? ? ? 參考vector容器的講解，其list內部也存在應該迭代器，為了實現內存的精準控制，其迭代器也是專門定義了一個(參考小節：list的迭代器定義和結構)，為了實現內存的管理，我們需要滿足內存的分配，釋放等操作，在這些操作基礎上還需要滿足帶值的節點的內存申請，對此list于內存相關的代碼如下：
//list內存管理源碼實現
link_type get_node(){ return list_node_allocator::allocate(); } //申請一個節點link_type put_node(link_type p){ return list_node_allocator::deallocate(p); }//釋放一個節點link_type create_node(const T& x){ //申請一個帶值的節點link_type p = get_node();construct(&p->data,x); //構造函數return p;
}link_type destroy_node(link_type p){ //銷毀一個帶值的節點destroy(&p->data);put_node(p);
}list() { empty_initialize(); } //list構造函數，用于產生一個空鏈表void empty_initialize(){ //產生一個空節點node = get_node();node->next = node;noed->prev = node;
}list的元素操作
? ? ? ? 形如vector，list也提供了許多元素操作的函數，如insert()，push_back()，erase()和uniques()函數等操作，本小節將對這些元素操作進行源碼的講解，如下：
? ? ? ? 1.insert()函數實現源碼：
//inser()用于在指定位置前插入元素
iterator inser(iterator position, const T& x){link_type tmp = create_node(x); //初始化帶值節點//調整當前插入節點的指針指向tmp->next = position.node;tmp->prev = position.node->prev;//調整迭代器指向節點的指針指向(link_type(position.node->prev))->next = tmp;position.node->prev = tmp;return tmp;
}? ? ? ? 2.push_front()函數實現源碼：
//push_front()用于插入一個節點作為頭節點
void push_front(const T& x){insert(begin(),x);
}? ? ? ? 3.push_back()函數實現源碼：
//push_back()函數用于插入一個節點作為尾節點
void push_back(const T& x){insert(end(),x);
}? ? ? ? 4.erase()函數實現源碼：
//erase()函數用于移除指定節點
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;destory_node(position.node); //釋放當前節點return iterator(next_node); //返回移除節點的上一個節點指針
}? ? ? ? 5.pop_front()函數實現源碼：
//pop_front()函數用于移除頭節點
void pop_front(){rease(begin());
}? ? ? ? 6.pop_back()函數實現源碼：
//pop_back()函數用于移除尾節點
void pop_back(){iterator tmp = end();rease(--tmp);
}//因為真實的尾節點其值為空，參考環狀雙向鏈表結構體
//所以先獲取尾節點后，再移動指針指向帶有值的最后一個節點，最后釋放該節點? ? ? ? 7.clear()函數實現源碼：
//clear()函數用于清除所有節點
template<class T , class Alloc>
void list<T,Alloc>::clear(){link_type cur = (link_type) node->next; //獲取鏈表頭節點while(cur != node){ //遍歷鏈表中的節點link_type tmp = cur; cur = (link_type) cur->next;//更新為下一個節點destroy_node(tmp);}//恢復node狀態node->next = node;node->prev = node;
}? ? ? ? 8.remove()函數實現源碼：
//remove()函數用于移除指定值的所有節點
template<class T, class Alloc>
void list<T,Alloc>::remove(const T& value){iterator first = begin(); //獲取頭節點iterator lase = end(); //獲取尾節點while(first != lase){ //遍歷所有節點iterator next = first;++next; //獲取下一個節點if(*first == value) erase(first);first = next;}
}? ? ? ? 9.unique()函數實現源碼：
//unique()函數用于移除數值相同的連續元素(最后剩余一個)
template<class T, class Alloc>
void list<T,Alloc>::unique(){iterator first = begin();iterator lase = end();if(first == last) teturn; //空鏈表則退出iterator next = first;while(++next != last){ //遍歷所有節點if(*first == *next) erase(next);elsefirst = next;next = first;}
}? ? ? ? 10.transfer()函數實現源碼：
//transfer()函數用于將指定范圍內的節點移動到指定節點的前面
void transfer(iterator position, iterator first, iterator last){//position：指定節點 first：范圍的頭節點 last：范圍的尾節點(不包含至移動的范圍中)if(position != last){(*(link_type((*last.node).prev))).next = position.node;(*(link_type((*first.node).prev))).next = last.node;(*(link_type((*position.node).prev))).next = first.node;link_type tmp = link_type((*position.node).prev);(*position.node).prev = (*last.node).prev;(*last.node).prev = (*first.node).prev;(*first.node).prev = tmp;}
}????????11.splice()函數實現源碼：
//splice()函數用于將指定的兩個鏈表結合
void splice(iterator position, list& x){if(!x.empty()){ //判斷鏈表是否為空transfer(position,x.begin(),x.end());}
}void splice(iterator position, list& x, iterator i){iterator j = i;++j;if(position == i || position == j) return; //當前鏈表只存在一個節點transfer(position,i,j);
}void splice(terator position, list& x, iterator first, iterator last){if(first != last) transfer(position,first,last)
}? ? ? ? 11.merge()函數實現源碼：
//merge()函數用于合并兩個遞增的鏈表，最后鏈表元素排序也為遞增
template<class T, class Alloc>
void list<T,Alloc>::merge(list<T,Alloc>& x){iterator first1 = begin();iterator last1 = end();iterator first2 = x.begin();iterator last2 = x.end();while(first1 != last1 && first2 != last2){ //遍歷次數為最短的鏈表元素個數if(*first2 < *first1){ //當鏈表1的值大于鏈表2iterator next = first2;transfer(first1,first2,++next);first2 = next;}else{++first1;}if(first2 != last2) { transfer(last,first1,first2); } //如果鏈表沒有插入完，則合并}
}? ? ? ? 12.reverse()函數實現源碼：
//reverse()函數用于見元素逆向排序
template<class T, class Alloc>
void list<T,Alloc>::reversr(){if(node->next == node || link_type(node->next)->next == node) return; //鏈表節點為1或0iterator first = begin();++first;while(first != end()){ 遍歷整個鏈表iterator old = first;++first;transfer(begin(),old,first); //把頭節點到old節點轉移到鏈表前}
}? ? ? ? 13.sort()函數實現源碼：
//sort()函數用于對鏈表進行排序
template <class T, class Alloc>
void list<T, Alloc>::sort() {if(node->next == node || link_type(node->next)->next == node) return;//鏈表節點個數為0或1list<T, Alloc> carry; //臨時存儲鏈表節點list<T, 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);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]);swap(counter[fill-1]);
}
![[9] CUDA性能測量與錯誤處理](http://pic.xiahunao.cn/[9] CUDA性能測量與錯誤處理)
