list

list概念

1. list是可以在常數(shù)范圍內(nèi)在任意位置進(jìn)行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
2. list的底層是雙向鏈表結(jié)構(gòu)，雙向鏈表中每個元素存儲在互不相關(guān)的獨(dú)立節(jié)點(diǎn)中，在節(jié)點(diǎn)中通過指針指向
   其前一個元素和后一個元素。
3. list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡單高
   效。
4. 與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進(jìn)行插入、移除元素的執(zhí)行效率
   更好。
5. 與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機(jī)訪問，比如：要訪問list
   的第6個元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時間
   開銷；list還需要一些額外的空間，以保存每個節(jié)點(diǎn)的相關(guān)聯(lián)信息(對于存儲類型較小元素的大list來說這
   可能是一個重要的因素)

list 中的迭代器

有興趣的可以直接跳轉(zhuǎn)附錄代碼中，里面幾乎涵蓋了所有的問題答案.

list迭代器知識

迭代器原理就是對原生指針的封裝，幫助我們更好的使用指針來對節(jié)點(diǎn)的內(nèi)容進(jìn)行訪問。

迭代器目前學(xué)習(xí)的進(jìn)度來看是分成普通迭代器和const迭代器。在對list的模擬實(shí)現(xiàn)過程中發(fā)現(xiàn)了許多新的迭代器知識點(diǎn)。

const迭代器寫法

由于對迭代器封裝后的代碼重命名為：typedef __list_iterator<T > iterator;
所以下意識會認(rèn)為const迭代器應(yīng)該是這個樣子的：//typedef __list_const_iterator<T> const_iterator;
實(shí)際上這是有問題的！

因?yàn)閏onst迭代器修飾的應(yīng)該節(jié)點(diǎn)內(nèi)部的數(shù)據(jù)不可以被修改，而迭代器本身是可以前后移動來遍歷鏈表。 而 const_iterator所表達(dá)的意思是T* const，但是我們想要的是const T*。 這兩者的區(qū)別便是前一個T* const可以修改節(jié)點(diǎn)內(nèi)部數(shù)據(jù)信息，但因?yàn)椴豢梢孕薷牡刂匪圆荒鼙闅v鏈表，，而后一個const T*不可以修改數(shù)據(jù)信息，但是可以遍歷鏈表。
要想辦法實(shí)現(xiàn)const T*！！！！

list中的const迭代器實(shí)際上是保證對信息不可修改，所以只需要對讀取信息的操作賦予控制是否為const屬性的操作，即為T* operator*()確保在某些時刻是const屬性。所以可以在模板上對其進(jìn)行特殊化操作： template<class T, class Ref>

	template<class T, class Ref>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T, Ref> self;node* _node;__list_iterator(node* n):_node(n){}Ref operator*()//T* operator(){return _node->_data;}};template<class T>class list{typedef list_node<T> node;public:typedef __list_iterator<T, T&> iterator;//使用普通迭代器就更改Ref就好了typedef __list_iterator<T, const T&> const_iterator;

在需要const迭代器時候，傳遞const T&，而需要普通迭代器就直接傳遞T&,這樣不僅解決的繁瑣的復(fù)用問題，還能夠滿足使用。

list訪問自定義類型

迭代器要么是原生指針，要么是自定義類型對原生指針的封裝，在模擬指針的行為。

而訪問自定義類型不能使用解引用操作，而是使用訪問操作符->,所以list庫對訪問自定義類型也做了對應(yīng)的設(shè)置，即重載operator->

但是因?yàn)橐L問自定義類型就一棒子大打死，就只能使用operator->來進(jìn)行訪問，內(nèi)部的函數(shù)大可以直接訪問，而復(fù)用又太過于繁瑣了，所以又新增了特殊的模板類，控制是訪問自定義類型還是訪問內(nèi)部函數(shù)！

	template<class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;node* _node;__list_iterator(node* n):_node(n){}Ptr operator->(){return &_node->_data;}template<class T>class list{typedef list_node<T> node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;}

	struct AA{int _a1;int _a2;AA(int a1 = 0, int a2 = 0)//全缺省的默認(rèn)構(gòu)造:_a1(a1), _a2(a2){}};void test_list2(){list<AA> lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));list<AA>::iterator it = lt.begin();while (it != lt.end()){cout << it->_a1 << "," << it->_a2 << " ";++it;}cout << endl;}

因此不僅僅可以訪問是否為const屬性的信息，還可以控制訪問是否為自定義類型的參數(shù)

附錄代碼

#pragma once#include<iostream>
#include<assert.h>
using namespace std;
namespace lby
{template<class T>struct list_node //節(jié)點(diǎn)的類//struct默認(rèn)為公有，不打算對內(nèi)容進(jìn)行限制就用struct{list_node<T>* _next;list_node<T>* _prev;T _data;list_node(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};//迭代器要么是原生指針，要么是自定義類型對原生指針的封裝，在模擬指針的行為template<class T, class Ref, class Ptr>//使用普通迭代器就更改Ref就好了struct __list_iterator//封裝的是迭代器，而迭代器的本質(zhì)是用一個類去封裝這個 node*,即指針指向這個鏈表的頭節(jié)點(diǎn){typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;node* _node;//注意節(jié)點(diǎn)的指針不屬于迭代器，只是讓迭代器封裝之后的一系列操作，不支持釋放，釋放是鏈表的事情，迭代器只能使用節(jié)點(diǎn)，不能釋放節(jié)點(diǎn)__list_iterator(node* n):_node(n){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++(){_node = _node->_next;return *this;}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;}bool operator!=(const self& x)//傳遞的是迭代器中的x{return _node != x._node;}bool operator==(const self& x){return _node == x._node;}};/*template<class T>struct __list_const_iterator//封裝的是迭代器，而迭代器的本質(zhì)是用一個類去封裝這個 node*,即指針指向這個鏈表的頭節(jié)點(diǎn){typedef list_node<T> node;typedef __list_const_iterator<T> self;node* _node;//注意節(jié)點(diǎn)的指針不屬于迭代器，只是讓迭代器封裝之后的一系列操作，不支持釋放，釋放是鏈表的事情，迭代器只能使用節(jié)點(diǎn)，不能釋放節(jié)點(diǎn)__list_const_iterator(node* n):_node(n){}const T& operator*()//控制整個返回值不可修改{return _node->_data;}self& operator++(){_node = _node->_next;return *this;}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;}bool operator!=(const self& x)//傳遞的是迭代器中的x{return _node != x._node;}bool operator==(const self& x){return _node == x._node;}};*/template<class T>class list{typedef list_node<T> node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;//typedef __list_const_iterator<T>  const_iterator;//typedef const iterator const_itrator;//絕對不可以，這種方式const修飾的是地址 --> T* const，而不是const T*；iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}//iterator begin() const//這里有個問題，既然是const指針，那就應(yīng)該是常量，但是為什么你還能改變指向的位置？//{//	return iterator(_head->_next);//因?yàn)閏onst指針修飾的是*this，即this指針指向的內(nèi)容，它指向的內(nèi)容是_head這個的指針，//								  //即為修飾的是_head這個指針本身！也就是說_head本身不能被改變，它指向的內(nèi)容是可以改變的//								  //但是與我們的預(yù)期不符，因?yàn)閏onst迭代器他是只讀操作，不允許改變內(nèi)容，如果他內(nèi)容是可以改變的，我為什么要使用const迭代器呢const迭代器與普通迭代器區(qū)別是：const迭代器本身是可以修改的(可以前后移動去訪問)，但是const迭代器指向的內(nèi)容是不可以修改的--> 要const T*，不要T* const ！//}//iterator end() const//{//	return iterator(_head); //}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}template<class Iterator>list(Iterator first, Iterator last){empty_init();//先構(gòu)造頭節(jié)點(diǎn)while (first != last){push_back(*first);//push_back 的前提是有哨兵位的頭節(jié)點(diǎn)，所以需要先構(gòu)造頭節(jié)點(diǎn)++first;}}void swap(list<T>& t){std::swap(_head, t._head);}list(const list<T>& lt)//lt2(lt1){/*empty_init();//正常寫法for (auto e : lt){push_back(e);}*/empty_init();list<T> tmp(lt.begin(), lt.end());//借助模板類進(jìn)行復(fù)制后交換swap(tmp);}//lt1 = lt3	list<T>& operator=(list<T> lt)//(list<T>& lt)不能引用傳引用，因?yàn)闀⒃瓉淼膌t進(jìn)行修改{swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);//erase(it++);//這個地方析構(gòu)的值是返回的迭代器對象，是it的拷貝，不是it}}void push_back(const T& x){//node* tail = _head->_prev;//node* new_node = new node(x);//需要node(list_node<T>)的構(gòu)造函數(shù)//tail->_next = new_node;//new_node->_prev = tail;//new_node->_next = _head;//_head->_prev = new_node;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void insert(iterator pos, const T& x)//鏈表的迭代器插入數(shù)據(jù)不會失效，因?yàn)閜os指針指向的位置是不變的{node* cur = pos._node;node* prev = cur->_prev;node* new_node = new node(x);prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator erase(iterator pos)//由于pos指針位置被析構(gòu)了，所以迭代器失效了{assert(pos != end());node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;return iterator(next);}private:node* _head;};void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){//(*it) *= 2;//const不可修改cout << *it << " ";++it;}cout << endl;}void test_list1(){const list<int> l;//const對象在定義時，最開始不會賦給常值，因?yàn)橐跏蓟?#xff0c;否則沒辦法進(jìn)行初始化，之后才會賦給const屬性//const對象在定義的一瞬間不會給const屬性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()){cout << *it << " ";++it;}cout << endl;for (auto p : lt){cout << p << " ";}cout << endl;print_list(lt);}struct AA{int _a1;int _a2;AA(int a1 = 0, int a2 = 0)//全缺省的默認(rèn)構(gòu)造:_a1(a1), _a2(a2){}};void test_list2(){list<AA> lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));list<AA>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << " " << (*it)._a2 << " ";cout << it->_a1 << "," << it->_a2 << " ";//由于函數(shù)重載了 -> ，所以本來應(yīng)該是it->->_a1,編譯器優(yōu)化了設(shè)置，變成了it->_a1;//it.operator->()->_a1,it.operator->()返回的是T*，T*->_a1就可以訪問++it;}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 p : lt){cout << p << " ";}cout << endl;auto pos = lt.begin();++pos;lt.insert(pos, 100);for (auto p : lt){cout << p << " ";}cout << endl;lt.push_front(200);lt.push_front(300);for (auto p : lt){cout << p << " ";}cout << endl;lt.push_back(400);lt.push_back(500);for (auto p : lt){cout << p << " ";}cout << endl;lt.pop_back();lt.pop_front();for (auto p : lt){cout << p << " ";}cout << endl;lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();for (auto p : lt){cout << p << " ";}cout << endl;}void test_list4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto p : lt){cout << p << " ";}cout << endl;lt.clear();for (auto p : lt){cout << p << " ";}cout << endl;lt.push_back(10);lt.push_back(2);lt.push_back(30);lt.push_back(1);for (auto p : lt){cout << p << " ";}cout << endl;}void test_list5(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto p : lt){cout << p << " ";}cout << endl;list<int> lt2(lt);for (auto e : lt2){cout << e << " ";}cout << endl;}
}