一? std::list 介紹

? ? ? ?list 是 c++ 中的序列式容器，其實現(xiàn)是雙向鏈表，每個元素都有兩個指針，分別指向前一個節(jié)點與后一個節(jié)點

? ? ? 鏈表與數(shù)組都是計算機常用的內(nèi)存數(shù)據(jù)結(jié)構(gòu)，與數(shù)組連續(xù)內(nèi)存空間不一樣的地方在于，鏈表的空間是不連續(xù)的，鏈表是將一塊塊不連續(xù)的內(nèi)存串聯(lián)起來使用。

? ? 正是由于鏈表的內(nèi)存不連續(xù)這一特點，所以不能像數(shù)組一樣，可以根據(jù)位置隨機的訪問每個元素，而鏈表我們壓根不知道每個元素的實際位置到底在哪塊內(nèi)存區(qū)域。

? ? ?查找某個元素需要遍歷整個鏈表，直到找到目標元素位置，時間復(fù)雜度是 O(n)；

? ? 在鏈表中插入一個元素與刪除一個元素的時間復(fù)雜度是 O(1)；

二? ?c++ 中 stl 鏈表結(jié)構(gòu)

1. list 結(jié)構(gòu)

? ?list? 結(jié)構(gòu)?（借用侯捷老師的一張圖片來）：

??

? 由上面的結(jié)構(gòu)上可以看出，list 是一個循環(huán)鏈表，鏈表的尾端是一個空節(jié)點，不存儲任何數(shù)據(jù)。

三? ?c++ 中 stl 鏈表使用

?1? 構(gòu)造函數(shù)

構(gòu)造函數(shù)	說明
list()	空構(gòu)造函數(shù)
list(?size_type count, const?T&?value）	初始化一個元素數(shù)量為 count 個的 value 元素
list(?std::initializer_list<T>?init)	利用列表初始化 list
list(?InputIt first, InputIt last)	利用迭代器的起始于終止位置初始化 list

?2? ?容器修改

函數(shù)	說明
clear()	?清空所有元素
insert	在指定位置插入元素
emplace	在指定位置插入元素, 可以通過直接傳入元素類的構(gòu)造參數(shù)實現(xiàn)原地構(gòu)造
erase	移除指定元素
push_back	append 元素到鏈表的尾部
pop_back	將鏈表尾部元素彈出
push_front	append 元素到鏈表的頭部
pop_front	將鏈表頭部元素彈出
emplace_back	append 元素到鏈表的尾部, 可以通過直接傳入元素類的構(gòu)造參數(shù)實現(xiàn)原地構(gòu)造
emplace_front	append 元素到鏈表的頭部, 可以通過直接傳入元素類的構(gòu)造參數(shù)實現(xiàn)原地構(gòu)造

?3? 容器訪問

函數(shù)	說明
begin	返回頭部元素的迭代器
end	返回尾部元素的迭代器
rbegin	返回尾部元素的迭代器
rend	返回頭部元素的迭代器
front	返回頭部元素的引用
back	返回尾部元素的引用

4? 容器容量

函數(shù)	說明
empty	判斷 list是否為空
size	返回 list 存儲元素的個數(shù)

#include<iostream>
#include<list>int main()
{// 1. 構(gòu)造函數(shù)std::list<int> list;auto iter = list.begin();std::cout << *iter << "--- " << std::endl;;// 2. 容器修改list.push_back(1);list.push_back(2);list.push_back(3);list.push_back(4);list.push_back(5);list.push_front(11);list.push_front(22);list.pop_back();list.pop_front();list.insert(list.begin(), 666);// 3. 容器訪問for(auto iter = list.begin(); iter != list.end();iter++){std::cout << *iter << " "; // 666 11 1 2 3 4}std::cout << "" << std::endl;for(auto iter = list.rbegin(); iter != list.rend();iter++){std::cout << *iter << " "; // 4 3 2 1 11 666}std::cout << "" << std::endl;std::cout << "first: " << list.front() << ", finish: " << list.back() << std::endl; // first: 666, finish: 4// 4. 容器容量std::cout << "empyt: " << list.empty() << std::endl; // 0std::cout << "size: "<< list.size() << std::endl; // 6list.clear();std::cout << "empyt: " << list.empty() << std::endl; // 1std::cout << "size: "<< list.size() << std::endl; // 0return 0;
}

四? 簡單實現(xiàn)

??

// my_list.h#include<memory>
#include<iostream>template<typename T>
struct _List_Node
{typedef _List_Node node;_List_Node(){prev = nullptr;next = nullptr;}_List_Node(T& da):data(da){prev = nullptr;next = nullptr;}_List_Node(T&& da):data(da){prev = nullptr;next = nullptr;}~_List_Node(){prev = nullptr;next = nullptr;}node* prev;node* next;T data;
};template<typename T>
struct _List_Iterator
{typedef T valueType;typedef T& refrence;typedef T* pointer;typedef  _List_Node<T> node;_List_Iterator(node* val):data(val){}_List_Iterator& operator++(){this->data = this->data->next;return *this;}_List_Iterator operator++(int){_List_Iterator tmp = *this;++(*this);return tmp;}_List_Iterator& operator--(){this->data = this->data->prev;return *this;}_List_Iterator operator--(int){_List_Iterator tmp = *this;--(*this);return tmp;}T& operator*(){return this->data->data;}bool operator != (_List_Iterator& other){return this->data != other->data;}bool operator == (_List_Iterator& other){return this->data == other.data;}bool operator != (_List_Iterator&& other){return this->data != other.data;}bool operator == (_List_Iterator&& other){return this->data == other.data;}node*  data;
};template<typename T>
class my_list
{typedef  _List_Node<T>  node;typedef  _List_Iterator<T> iterator;
public:my_list():count(0){next_curr = new node;pre_curr = next_curr;finish = new node;next_curr->next = finish;finish->next = next_curr;pre_curr->prev = finish;finish->prev = pre_curr;}~my_list(){node* tmp = pre_curr;while (tmp != nullptr) {node* tt = tmp->next;delete tmp;tmp = tt;}}void push_back(T& val){std::cout << "count: " << count << std::endl;if(count == 0)next_curr->data = val;else {node* tmp = new node(val);tmp->next = next_curr->next;tmp->next->prev = tmp;next_curr->next = tmp;tmp->prev = next_curr;next_curr = next_curr->next;}count++;}void push_back(T&& val){push_back(val);}void push_front(T& val){if(count == 0)pre_curr->data = val;else {node* tmp = new node(val);tmp->prev = pre_curr->prev;pre_curr->prev->next = tmp;tmp->next = pre_curr;pre_curr->prev = tmp;pre_curr = pre_curr->prev;}count++;}void push_front(T&& val){push_front(val);}void pop_back(){if(count == 0){return;} else{node* tmp = next_curr;next_curr->prev->next = next_curr->next;next_curr->next->prev = next_curr->prev;next_curr = next_curr->prev;delete tmp;count--;}}void pop_front(){if(count == 0){return;} else{node* tmp = pre_curr;finish->next = pre_curr->next;pre_curr->next->prev = finish;pre_curr = pre_curr->next;delete tmp;count--;}}int size(){return count;}iterator begin(){return iterator(pre_curr);}iterator end(){return iterator(finish);}iterator rbegin(){return iterator(finish->prev);}iterator rend(){return iterator(pre_curr->prev);}void insert(iterator pos, T& val){node* tmp = new node(val);pos.data->prev->next = tmp;tmp->prev = pos.data->prev;tmp->next = pos.data;pos.data->prev = tmp;if(pos.data == pre_curr){pre_curr = pre_curr->prev;}else if(pos.data == next_curr){next_curr = next_curr->next;}count++;}void insert(iterator pos, T&& val){insert(pos, val);}template<typename ... Args>void emplace(iterator pos, Args... args){node* tmp = new node(std::forward<Args>(args)...);pos.data->prev->next = tmp;tmp->prev = pos.data->prev->next;tmp->next = pos.data;pos.data->prev = tmp;count++;}void erase(iterator pos){node* tmp = pos.data;tmp->prev = tmp->next;delete tmp;count--;}void clear(){while (pre_curr->next != finish) {pop_back();}count = 0;}T& front(){return pre_curr->data;}T& back(){return next_curr->data;}bool empty(){return count == 0;}public:node* next_curr = nullptr;node* pre_curr = nullptr;node* finish = nullptr;int count;
};// main.cpp
#include<iostream>
#include<my_list.h>int main()
{// 1. 構(gòu)造函數(shù)my_list<int> list;// 2. 容器修改list.push_back(1);list.push_back(2);list.push_back(3);list.push_back(4);list.push_back(5);list.push_front(11);list.push_front(22);// 22 11 1 2 3 4 5list.pop_back();list.pop_front();list.insert(list.begin(), 666);// 3. 容器訪問for(auto iter = list.begin(); iter != list.end();iter++){std::cout << *iter << " "; // 666 11 1 2 3 4}std::cout << "" << std::endl;for(auto iter = list.rbegin(); iter != list.rend();iter--){std::cout << *iter << " "; // 4 3 2 1 11 666}std::cout << "" << std::endl;std::cout << "first: " << list.front() << ", finish: " << list.back() << std::endl; // first: 666, finish: 4// 3. 容器容量std::cout << "empty: " << list.empty() << std::endl; // 0std::cout << "size: "<< list.size() << std::endl; // 6list.clear();std::cout << "empyt: " << list.empty() << std::endl; // 1std::cout << "size: "<< list.size() << std::endl; // 0return 0;
}