list的介紹及使用(了解,后邊細講)
1.1 list的介紹(雙向循環鏈表)
https://cplusplus.com/reference/list/list/?kw=list(list文檔介紹)
1. list是可以在常數范圍內在任意位置進行插入和刪除的序列式容器,并且該容器可以前后雙向迭代。
2. list的底層是雙向鏈表結構,雙向鏈表中每個元素存儲在互不相關的獨立節點中,在節點中通過指針指向其前一個元素和后一個元素。
3. list與forward_list非常相似:最主要的不同在于forward_list是單鏈表,只能朝前迭代,已讓其更簡單高效。
4. 與其他的序列式容器相比(array,vector,deque),list通常在任意位置進行插入、移除元素的執行效率更好。
1.2 list的使用(可以對照模擬實現看,重要的都有,后邊模擬實現都會講)
list中的接口比較多,此處類似,只需要掌握如何正確的使用,然后再去深入研究背后的原理,已達到可擴展的能力。以下為list中一些常見的重要接口。
1.2.1 list的構造
1.2.2 list iterator的使用
此處,大家可暫時將迭代器理解成一個指針,該指針指向list中的某個節點。
【注意】
1. begin與end為正向迭代器,對迭代器執行++操作,迭代器向后移動
2. rbegin(end)與rend(begin)為反向迭代器,對迭代器執行++操作,迭代器向前移動
1.2.3 list capacity
1.2.4 list element access
1.2.5 list modifiers
list中還有一些操作,需要用到時大家可參閱list的文檔說明。
?list的迭代器失效
? ? ? ? 注意,insert不會失效,迭代器依舊指向原來位置,erase會失效(刪除后返回下一個地址),跟vector的迭代器失效類比,都是因為沒有接收刪除后的迭代器。insert不會失效,因為插入后返回新的節點地址,本身就指向新節點,不會失效
錯誤代碼:
void TestListIterator1() {int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函數執行后,it所指向的節點已被刪除,因此it無效,在下一次使用it時,必須先給 其賦值l.erase(it); ++it;} }
改正后:
// 改正 void TestListIterator() {int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);兩種寫法都對} }
?list的反向迭代器
? ReverseIterator.h
template<class Iterator,class Ref,class Ptr> struct ReverseIterator {typedef ReverseIterator<Iterator, Ref, Ptr> Self;Iterator cur;ReverseIterator(Iterator it):cur(it){ }Self& operator++(){--cur;return *this;}Ref operator*(){Iterator tmp = cur;--tmp;return *tmp;}Ptr operator->(){return &(operator*());}bool operator!=(const Self& s){return cur != s.cur;} };
List.h
在list類內部多了一些改動,將反向迭代器的類重命名,并且新加兩個成員函數
test.cpp
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream> #include<list>using namespace std;#include"List.h"int main() {jzy::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);jzy::list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}cout << endl;return 0; }
可以看到反向迭代器起了作用,下面我來講解反向迭代器的原理
反向迭代器可以理解成封裝了正向迭代器,正向迭代器又封裝了原生指針,反向迭代器++等價于正向迭代器--,反向迭代器解引用相當于正向迭代器--再解引用
因為反向迭代器的開始是正向迭代器結束位置,結束是正向的開始,所以反向迭代器要先--在解引用才是正確的值
反向迭代器的->也就是*拿到存放的值再取地址,和之前講的是一個道理
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;//typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}
反向迭代器在list類那里要多加一些東西,重命名反向迭代器這個類,當是普通反向迭代器的時候實例化iterator,T&,T*,當是const反向迭代器的時候,實例化參數是const_iterator,const T&,const T*
總體來講,可以把反向迭代器看成適配器,當實例化參數是普通迭代器,會按照普通迭代器的行為進行操作,當參數是const時,會調用const的操作
list與vector的對比
vector與list都是STL中非常重要的序列式容器,由于兩個容器的底層結構不同,導致其特性以及應用場景不同,其主要不同如下:
list模擬實現講解(超詳細)
定義結點結構體,結構體成員是前仆后繼指針和元素data,還要寫一個構造函數用來初始化結點
迭代器封裝為一個類,類定義的對象存放每個節點的地址,也就是_node,相當于迭代器指針被封裝成了一個類里存放,typedef是將類型重命名,將長的類型重命名為短的,記住類名不是類型,類名<類型>才是類型
這里模版有三個參數,第一個T是實例化類型,第二個和第三個參數是為了*和->,const類型會匹配T,constT& ,constT* ,正常類型會匹配T,T&,T*
這里將原生指針封裝了一層包裝在一個類里邊,類定義的對象會通過操作指針前后移動來操作結點,解引用拿到對應結點的值,或者->拿到對應的地址
迭代器構造函數,當返回值是iterator類型時,會構造一個臨時對象來操作
迭代器++,--,和日期類的原理類似,++it是當前指針往后走一步,this是it的地址,然后返回++之后的值,后置++,參數多傳一個int就行,構造一個局部對象,指針向后走一步,返回走之前的值,迭代器--和++同理,無非是向前走
operator*是(*it)相當于拿到對應的值,我們就把it當成指針,*it當成解引用地址即可,這里是把指針封裝到類里邊,和前邊string和vector的指針有所區分;->箭頭相當于拿到存放對象的地址,當在list內部存放結構體時會用到
最簡單的兩個運算符重載,當判斷不等于的時候會用到
list類要把上邊兩個類typedef后的類型寫上去,方便等會用
迭代器的重載,當我們用begin()或者end()的時候,會調用這四個重載,普通對象調用普通迭代器,返回普通可修改指向對象的迭代器(這個對象可以用類名(),也可以直接返回Node*的結點指針(單參數的構造函數支持隱式類型轉換),這兩個寫法都會生成一個臨時對象,然后進行使用),const類型調用const迭代器,返回const不可修改指向對象的迭代器(慢慢理解這部分,其實沒有想象的那么難)
list類的私有成員是_head,充當一個指針用來聲明第一個哨兵位頭結點
默認構造是初始化一個哨兵位頭結點,結點內部存放前仆后繼指針和data值(是某個類型的默認構造),然后讓_head指向第一個哨兵位結點,并且_next和_prev都指向自己,完成哨兵位結點的初始化
析構函數先用clear清理,刪除除了哨兵位結點的剩余存放有效數據的結點(釋放了空間),最后釋放哨兵位結點空間,_head置空就OK
拷貝構造,先初始化一個哨兵位結點,然后將要構造的對象內容依次給給e,尾插到新對象后邊
賦值拷貝,先拷貝構造一個lt,將lt和新對象交換,lt是局部對象,出作用域會調用析構函數,新對象引用返回,完成賦值拷貝
insert插入,參數是迭代器指針(生成臨時對象+2次拷貝構造)和要插入的值,cur指向要插入位置,prev存放要插入位置前邊的指針,new一個新節點是要插入的新結點
三個指針相對位置是這樣的,一般都是在某個位置之前插入,所以是這樣的關系,然后按順序鏈接這三個位置,前一個位置的后繼指針和后一個位置的前驅指針都指向中間位置,最后返回插入節點的迭代器(單參數構造函數支持隱式類型轉換)
刪除很簡單,不能刪除哨兵位結點,找到要刪除節點,記錄要刪除結點的前一個和后一個,鏈接兩邊的節點,最后釋放要刪除節點的空間,返回下一個節點的迭代器(會隱式類型轉換成iterator類型的對象)
尾插,可以自己重新寫邏輯,也可以復用insert邏輯,將第一個參數換成最后一個位置的迭代器,相當于在哨兵位節點之前插入,效果是一樣的
頭插,尾插,尾刪是一樣的,復用insert,erase邏輯就行
這部分在c語言實現數據結構鏈表那里講的很詳細了,想看的可以看看
代碼樣例講解
這是一個很基礎的尾插和打印對象邏輯,可以用第一個迭代器打印,也可以用第二個,范圍for打印(范圍for底層就是迭代器,無腦替換成迭代器進行打印),可以看到*it和it++,都是我們封裝成類的功勞,原理很簡單前面講過
測試插入刪除邏輯,可以看到不管是頭插,頭刪,尾插,尾刪都很清晰明了,clear是直接刪除有效結點只剩哨兵位,所以打印不出來
可以看到,拷貝構造和賦值拷貝都完成了使命,前邊講的很詳細,這里不再贅述
這里主要測試普通迭代器和const迭代器,各自調用各自,const迭代器不可修改對象,普通迭代器可以修改對象
最后一個樣例,插入AA類對象,*it是拿到存放的結構體變量,.操作符訪問結構體成員,拿到1:1,打印第二行是編譯器會將*it轉換成it.operator*(),效果是一樣的
->箭頭訪問操作符會特殊處理一個箭頭可以當做兩個->->,并且編譯器會轉換成it.operator->()->_a1去訪問,會特殊處理,這里當成特殊處理就好
list的模擬實現(代碼)
? ? ? ?要模擬實現list,必須要熟悉list的底層結構以及其接口的含義,通過上面的學習,這些內容已基本掌握,現在我們來模擬實現list。
test.cpp
#include<iostream> #include<list> #include<vector> #include<algorithm> using namespace std;#include"List.h"namespace jzy {void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){//*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void test_list2(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;lt.push_back(5);lt.push_front(0);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;lt.clear();for (auto e : lt){cout << e << " ";}cout << endl;lt.push_back(10);lt.push_back(20);for (auto e : lt){cout << e << " ";}cout << endl;}void test_list3(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;list<int> copy(lt);for (auto e : copy){cout << e << " ";}cout << endl;list<int> lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);lt1.push_back(40);lt = lt1;for (auto e : copy){cout << e << " ";}cout << endl;}void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){//*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void test_list4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);print_list(lt);list<int>::iterator it = lt.begin();while (it != lt.end()){*it += 10;cout << *it << " ";++it;}cout << endl;}struct AA{int _a1;int _a2;AA(int a1 = 1, int a2 = 1):_a1(a1), _a2(a2){}};void test_list5(){list<AA> lt;AA aa1;lt.push_back(aa1);lt.push_back(AA());AA aa2(2, 2);lt.push_back(aa2);lt.push_back(AA(2, 2));list<AA>::iterator it = lt.begin();cout << (*it)._a1 << ":" << (*it)._a2 << endl;cout << it.operator*()._a1 << ":" << it.operator*()._a2 << endl;cout << it->_a1 << ":" << it->_a2 << endl;cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;cout << endl;}}int main(){jzy::test_list1();return 0;}
list.h
#pragma once #include<assert.h>namespace jzy {template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};template<class T, class Ref, class Ptr>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T, Ref, Ptr> self;Node* _node;__list_iterator(Node* x):_node(x){}// ++itself& operator++(){_node = _node->_next;return *this;}// it++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};//template<class T>//struct __list_const_iterator//{// typedef ListNode<T> Node;// typedef __list_const_iterator<T> self;// Node* _node;// __list_const_iterator(Node* x)// :_node(x)// {}// // ++it// self& operator++()// {// _node = _node->_next;// return *this;// }// // it++// self operator++(int)// {// self tmp(*this);// _node = _node->_next;// return tmp;// }// self& operator--()// {// _node = _node->_prev;// return *this;// }// self operator--(int)// {// self tmp(*this);// _node = _node->_prev;// return tmp;// }// const T& operator*()// {// return _node->_data;// }// bool operator!=(const self& s)// {// return _node != s._node;// }// bool operator==(const self& s)// {// return _node == s._node;// }//};template<class T>class list{typedef ListNode<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){//return iterator(_head->_next);return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}list(const list<T>& lt){empty_init();for (const auto& e : lt){push_back(e);}}// lt1 = lt2;// list<T>& operator=(const list<T>& lt)/*list<T>& operator=(list<T>& lt){if (this != <){clear();for (const auto& e : lt){push_back(e);}}return *this;}*/void swap(list<T>& tmp){std::swap(_head, tmp._head);}//list& operator=(list lt)list<T>& operator=(list<T> lt){swap(lt);return *this;}void push_back(const T& x){/*Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}// vector insert會導致迭代器失效// list會不會?不會iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);// prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;//return iterator(newnode);return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return next;}private:Node* _head;}; }
注意list的const迭代器可以實現為一個類,也可以實現為模版參數實例化后的結果,一般實現為后者,會少寫很多冗余代碼
以上就是我對list容器內容的講解,很詳細,歡迎大神交流!!!