怎樣做學(xué)校網(wǎng)站網(wǎng)站建設(shè)公司好
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 創(chuàng)作不易，感謝三連！！
一、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開始就不支持下標(biāo)訪問了，所以要訪問都要以迭代器為準(zhǔn)
void Print(const list<int>& l)
{//迭代去區(qū)間遍歷list<int>::const_iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;//范圍for遍歷for (auto e : l)cout << e << " ";cout << endl;
}二、List的使用注意事項(xiàng)?
博主覺得跟之前vector的基本上差不了多少，如果不會看文檔用庫里面的list的可以去看博主只管關(guān)于string和vector的使用。
C++：String類的使用-CSDN博客?
C++：Vector的使用-CSDN博客
下面直接介紹List使用中的易錯點(diǎn)
2.1 List的迭代器失效問題
? ? ? ? 我們之前學(xué)習(xí)vector的時候，知道了insert和erase都有可能存在迭代器失效的問題，那list會出現(xiàn)這種情況嗎？？下面來進(jìn)行分析
insert插入新節(jié)點(diǎn)的迭代器，因此insert不可能會出現(xiàn)失效的問題。
? ?而earse必然會失效，因?yàn)樵摰鲗?yīng)的節(jié)點(diǎn)被刪除了。如果我們想繼續(xù)用的話，就得利用返回值去更新迭代器，返回值是被刪除元素的下一個位置的迭代器。
2.2 List中sort的效率測試
我們用一段代碼來測試一下list中sort的性能
void test_op()
{srand((unsigned int)time(NULL));const int N = 1000000;vector<int> v;v.reserve(N);list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){int e = rand();lt1.push_back(e);lt2.push_back(e);}// 拷貝到vector排序，排完以后再拷貝回來int begin1 = clock();for (auto e : lt1){v.push_back(e);}sort(v.begin(), v.end());size_t i = 0;for (auto& e : lt1){e = v[i++];}int end1 = clock();//list調(diào)用自己的sortint begin2 = clock();lt2.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}
?會發(fā)現(xiàn)哪怕我先拷貝到vector排完再拷貝回去效率都比list的sort效率高，所以list的sort實(shí)際中意義不是很大！！
?三、模擬實(shí)現(xiàn)的注意事項(xiàng)
? ? ?還是跟之前模擬實(shí)現(xiàn)一樣，先看看SGI版本的源碼 ，list本質(zhì)上是帶頭雙向鏈表
第一部分? ? 鏈表節(jié)點(diǎn)
?
第二部分? ?迭代器
?
第三部分、鏈表
?
這里我們可以先實(shí)現(xiàn)鏈表節(jié)點(diǎn)結(jié)構(gòu)體 這里用sturct把權(quán)限放開。
//節(jié)點(diǎn)的封裝
template<class T>
struct list_node
{list_node<T>* _prev;list_node<T>* _next;T _data;//節(jié)點(diǎn)的構(gòu)造函數(shù)list_node(const T& val = T()):_prev(nullptr), _next(nullptr), _data(val){}
};然后封裝一個鏈表，將頭結(jié)點(diǎn)作為自己的成員變量封裝起來
template<class T>
class list
{typedef list_node<T> node;//typedef可以幫助我們簡潔代碼private:node* _head;};下面開始進(jìn)行我們的重中之重——迭代器?
四、正向迭代器的實(shí)現(xiàn)
2.1 正向迭代器的封裝
? ? ? 在學(xué)習(xí)Vector的時候，我們發(fā)現(xiàn)其實(shí)vector的迭代器就是一個原生指針，所以我們將他改了名字
?
? ? ? 這得益于vector空間連續(xù)的特點(diǎn)，所以對指針進(jìn)行加和減再進(jìn)行解引用可以訪問到我們想要的元素，但是鏈表可以嗎？
?
?
? ? ?雖然看似我們好像用箭頭連接起來了，但其實(shí)他們空間上是不連續(xù)的，那我們對一個節(jié)點(diǎn)指針進(jìn)行加減，就很難說能不能找到下一個節(jié)點(diǎn)，更多的是找不到的情況
? ? 那我們思考一樣，如果我們要搞一個迭代器，我們希望怎么去得到我們的數(shù)據(jù)呢？？我們希望我們解引用的時候，可以拿到他的data，希望++的時候，可以拿到他的next，--的時候，可以拿到他的prev。? 那我們怎么去改變原生操作符的行為呢？答案就是運(yùn)算符重載！所以我們可以將迭代器單獨(dú)封裝成一個類去管理節(jié)點(diǎn)，改變運(yùn)算符的行為！！
? ? ? ?我們先進(jìn)行實(shí)現(xiàn)，然后再慢慢分析
//封裝迭代器template<class T, class Ref, class Ptr>//Ref用于引用是否const，Ptr用于指針是否conststruct list_iterator{typedef list_node<T> node;typedef list_iterator<T, Ref, Ptr> self;node* _node;//迭代器的構(gòu)造函數(shù)list_iterator(node* n)//迭代器的構(gòu)造:_node(n){}//實(shí)現(xiàn)*Ref operator*() const{return _node->_data;}//實(shí)現(xiàn)->Ptr operator->() const{return &operator*(); //本來是兩個->,為了增強(qiáng)可讀性，我們封裝了這個函數(shù) 比如當(dāng)我們存儲的結(jié)構(gòu)體解引用后有多個成員，那么我們可以通過箭頭的直線去找到對應(yīng)我們想要的成員 }//前置++self& operator++(){_node = _node->_next;return *this;}//后置++self operator++(int){self temp(*this);++*this;return temp;}//前置--self& operator--(){_node = _node->_prev;return *this;}//后置--self operator--(int){self temp(*this);--*this;return temp;}//！=bool operator!=(const self& s) const{return _node != s._node;}//==bool operator==(const self& s) const{return _node == s._node;}};第一個模版參數(shù)是類型，第二個模版參數(shù)是引用，第三個模版參數(shù)是指針
? ? ? ?Ref和Ptr是用來區(qū)分正常的迭代器和const修飾的迭代器，Ref是T&或者是const T&,這樣可以在某些時候我們?nèi)ハ拗芼ata不能被修改。而Ptr是T*或者是const T*，重載箭頭的作用是如果我們data存儲的是一個自定義類型，這個時候如果直接解引用肯定是不行的，所以我們的箭頭可以在解引用的時候先返回data的地址，然后我們就可以通過箭頭去訪問他不同的成員變量。
下面舉個data存的是自定義類型的例子
?
2.2 迭代器的使用
template<class T>
class list
{typedef list_node<T> node;//typedef可以幫助我們簡潔代碼
public://正向迭代器typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;//可讀可寫正向迭代器iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}//可讀不可寫正向迭代器const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}private:node* _head;};這邊我們用到了匿名對象。
思考：這里的const迭代器為什么不能直接用const修飾普通迭代器？？
?
? ? ? ?因?yàn)閠ypedef碰到const的話，就不是簡單的字符串替換? 實(shí)際上你以為的const T*?，在這里變成了T*const ，因?yàn)榈魑覀兪窍Ｍ梢赃M(jìn)行++和--的，而我們只是不希望他指向的內(nèi)容給改變，所以我們的const要修飾的是指針的內(nèi)容，而不是修飾指針。
五、list相關(guān)的成員函數(shù)
3.1? 構(gòu)造函數(shù)
?
1、默認(rèn)構(gòu)造函數(shù)
?
因?yàn)闊o論如何都要有哨兵節(jié)點(diǎn)，所以我們直接封裝一個
void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}所以可以這么寫
//默認(rèn)構(gòu)造函數(shù)list(){empty_init();}2、有參構(gòu)造函數(shù)
//有參構(gòu)造函數(shù)
list(size_t n, const T& val = T())
{empty_init();for (size_t i = n; i > 0; --i)push_back(val);
}?3、迭代器區(qū)間構(gòu)造函數(shù)
//迭代器區(qū)間構(gòu)造函數(shù)
template <class InputIterator>
list(InputIterator first, InputIterator last)
{empty_init();while (first != last){push_back(*first);++first;}
}4、拷貝構(gòu)造的傳統(tǒng)寫法
傳統(tǒng)方法就是一個個拷貝過去
//拷貝構(gòu)造函數(shù)傳統(tǒng)寫法
list(const list<T>& lt)
{empty_init();for (auto e : lt)push_back(e);
}5、拷貝構(gòu)造的現(xiàn)代寫法+swap
? ? ? 現(xiàn)代寫法就是，我先創(chuàng)建一個臨時對象讓他利用被拷貝對象的迭代器構(gòu)造出來，然后再交換，竊取革命成功，被利用完后的臨時對象會在棧幀結(jié)束后被清除（典型的資本家思維）
//交換函數(shù)void swap(list<T>& temp){std::swap(_head, temp._head);}//拷貝構(gòu)造函數(shù)的現(xiàn)代寫法list(const list<T>& lt){empty_init();list<T> temp(lt.begin(), lt.end());//復(fù)用迭代器區(qū)間構(gòu)造，讓別人構(gòu)造好了，我再竊取革命成果swap(temp);}3.2 clear和析構(gòu)函數(shù)
? ? list不像vector一樣，不能直接用頭指針delete，因?yàn)榭臻g不連續(xù)，所以要一個個節(jié)點(diǎn)去delete，所以在這之前，我們可以先實(shí)現(xiàn)clear，clear的作用是把鏈表清空，只剩一個頭節(jié)點(diǎn)，然我們的析構(gòu)函數(shù)再復(fù)用clear，然后再單獨(dú)delete頭節(jié)點(diǎn)就行了！！
//clear 只留一個頭節(jié)點(diǎn)void clear(){iterator it = begin();while (it != end())it = erase(it);}//析構(gòu)函數(shù)~list(){clear();delete _head;_head = nullptr;}3.3 賦值重載和assign
?
?
? ? ? ?assign和=的本質(zhì)上都是，先將原來的空間的內(nèi)容給清空，換成的內(nèi)容。?只不過區(qū)別就是assign可以利用迭代器去控制被替換的范圍，也可以自己去換成n個一樣的元素。所以我們先實(shí)現(xiàn)assign，再實(shí)現(xiàn)=
1、assign直接替換
//assign(直接替換)
void assign(size_t n, const T& val)
{clear();for (size_t i = n; i > 0; --i)push_back(val);
}2、assign迭代器區(qū)間替換
//assign(迭代器區(qū)間替換)template <class InputIterator>void assign(InputIterator first, InputIterator last){clear();while (first != last){push_back(*first);++first;}}3、assign直接替換重載（防止間接尋址）
?
思考：我們的本意是將lt2替換成5個2，我們發(fā)現(xiàn)我們調(diào)的竟然是迭代器區(qū)間構(gòu)造的assign，為什么會這樣呢？？？？？? ? ?
? ? ? 因?yàn)橹剌d類型會優(yōu)先找最匹配的，assign的第一個版本的n是size_t類型，我們傳的整數(shù)默認(rèn)是int所以會發(fā)生強(qiáng)制類型轉(zhuǎn)化，而第二個版本恰好可以變成兩個int，所以他會走迭代器區(qū)間版本。所以此時有兩個方案，第一個方案是我們要在第一個參數(shù)后面加u，但是這不符合我們的使用習(xí)慣，所以我們可以采用第二個方案，寫個重載版本。
//assign重載版本 防止間接尋址
void assign(int n, const T& val)
{clear();for (size_t i = n; i > 0; --i)push_back(val);
}4、賦值重載傳統(tǒng)寫法?
直接復(fù)用assign
// 賦值重載的傳統(tǒng)寫法list<T>& operator=(const list<T>& lt){assign(lt.begin(), lt.end());return *this;}5、賦值重載的現(xiàn)代寫法
list<T>& operator=(list<T> lt)
{swap(lt);//利用值傳遞拷貝的臨時對象進(jìn)行交換return *this;
}3.4 修改相關(guān)函數(shù)（Modifiers）
1、empty、size
//size
size_t size() const
{size_t n = 0;for (auto e : *this)++n;return n;
}
//empty
bool empty() const
{return node->next == node;
}2、insert
我們先實(shí)現(xiàn)insert和erase，其他的就可以直接復(fù)用了
//insert
iterator insert(iterator pos, const T& val)
{node* cur = pos._node;//記錄當(dāng)前節(jié)點(diǎn)node* prev = cur->_prev;//記錄前驅(qū)節(jié)點(diǎn)node* newnode = new node(val);//建立新節(jié)點(diǎn)//開始改變指向newnode->_next = cur;cur->_prev = newnode;prev->_next = newnode;newnode->_prev = prev;return iterator(newnode);
}3、erase
//erase
iterator erase(iterator pos)
{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);//利用匿名對象返回
}4、尾插尾刪頭插頭刪
//pushback 尾插
void push_back(const T& val)
{insert(end(), val);
}
//pushfront 頭插
void push_front(const T& val)
{insert(begin(), val);
}
//popback 尾刪
void pop_back()
{erase(--end());
}
//popfront 頭刪
void pop_front()
{erase(begin());
}5、resize
//resize 如果n小于當(dāng)前容量的大小，則內(nèi)容將減少到前n個元素 當(dāng)n大于容器大小時，則在末尾插入任意容量的內(nèi)容。
void resize(size_t n, const T& val = T())
{size_t sz = size();//記錄當(dāng)前的有效元素的個數(shù)while (n < sz){pop_back();--sz;}while (n > sz){push_back(val);++sz;}
}六、反向迭代器的實(shí)現(xiàn)
sgi版本下的反向迭代器，其實(shí)就是將構(gòu)建一個反向迭代器的類將正向迭代器封裝起來，這個時候正向迭代器的++就是反向迭代器的--
template<class iterator, class Ref, class Ptr>
struct list_reverse_iterator
{typedef list_reverse_iterator<iterator, Ref, Ptr> self;//用正向迭代器去構(gòu)造反向迭代器list_reverse_iterator(iterator it):_cur(it){}//解引用Ref operator*() const{iterator temp = _cur;--temp;return *temp;}//實(shí)現(xiàn)->Ptr operator->() const{return &operator*();}//前置++self& operator++(){--_cur;return *this;}//后置++self operator++(int){iterator temp(_cur);--*this;return temp;}//前置--self& operator--(){++_cur;return *this;}//后置--self operator--(int){iterator temp(_cur);++*this;return temp;}//不等于bool operator!=(const self& s){return _cur != s._cur;}//等于bool operator==(const self& s){return _cur == s._cur;}iterator _cur;
};思考：為什么解引用的是前一個位置的元素？？？
?
通過這個我們來看看vector下的反向迭代器代碼：
?
? ? ? ? ?復(fù)用性很高，和list的區(qū)別就是因?yàn)槭请S機(jī)迭代器，所以多了+和-的接口，第二個就是不需要->,所以其實(shí)模版也可少傳一個?
?七、list模擬實(shí)現(xiàn)的全部代碼
//c++喜歡ListNode駝峰法命名 為了和STL風(fēng)格一致，我們也用小寫
//但是STL版本和java喜歡小寫帶_
namespace cyx
{//節(jié)點(diǎn)的封裝template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _data;//節(jié)點(diǎn)的構(gòu)造函數(shù)list_node(const T& val = T()):_prev(nullptr), _next(nullptr), _data(val){}};//封裝迭代器template<class T, class Ref, class Ptr>//Ref用于struct list_iterator{typedef list_node<T> node;typedef list_iterator<T, Ref, Ptr> self;node* _node;//迭代器的構(gòu)造函數(shù)list_iterator(node* n)//迭代器的構(gòu)造:_node(n){}//實(shí)現(xiàn)*Ref operator*() const{return _node->_data;}//實(shí)現(xiàn)->Ptr operator->() const{return &operator*(); //本來是兩個->,為了增強(qiáng)可讀性，我們封裝了這個函數(shù) 比如當(dāng)我們存儲的結(jié)構(gòu)體解引用后有多個成員，那么我們可以通過箭頭的直線去找到對應(yīng)我們想要的成員 }//前置++self& operator++(){_node = _node->_next;return *this;}//后置++self operator++(int){self temp(*this);++*this;return temp;}//前置--self& operator--(){_node = _node->_prev;return *this;}//后置--self operator--(int){self temp(*this);--*this;return temp;}//！=bool operator!=(const self& s) const{return _node != s._node;}//==bool operator==(const self& s) const{return _node == s._node;}};template<class iterator, class Ref, class Ptr>struct list_reverse_iterator{typedef list_reverse_iterator<iterator, Ref, Ptr> self;//用正向迭代器去構(gòu)造反向迭代器list_reverse_iterator(iterator it):_cur(it){}//解引用Ref operator*() const{iterator temp = _cur;--temp;return *temp;}//實(shí)現(xiàn)->Ptr operator->() const{return &operator*();}//前置++self& operator++(){--_cur;return *this;}//后置++self operator++(int){iterator temp(_cur);--*this;return temp;}//前置--self& operator--(){++_cur;return *this;}//后置--self operator--(int){iterator temp(_cur);++*this;return temp;}//不等于bool operator!=(const self& s){return _cur != s._cur;}//等于bool operator==(const self& s){return _cur == s._cur;}iterator _cur;};template<class T>class list{typedef list_node<T> node;//typedef可以幫助我們簡潔代碼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 list_reverse_iterator<iterator, T&, T*> reverse_iterator;typedef list_reverse_iterator<iterator, const T&, const T*> const_reverse_iterator;//可讀可寫正向迭代器iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}//可讀不可寫正向迭代器const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}//可讀可寫的反向迭代器reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}//可讀不可寫的反向迭代器const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}//默認(rèn)構(gòu)造函數(shù)list(){empty_init();}//有參構(gòu)造函數(shù)list(size_t n, const T& val = T()){empty_init();for (size_t i = n; i > 0; --i)push_back(val);}//迭代器區(qū)間構(gòu)造函數(shù)template <class InputIterator>list(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);++first;}}//拷貝構(gòu)造函數(shù)傳統(tǒng)寫法/*list(const list<T>& lt){empty_init();for (auto e : lt)push_back(e);}*///交換函數(shù)void swap(list<T>& temp){std::swap(_head, temp._head);}//拷貝構(gòu)造函數(shù)的現(xiàn)代寫法list(const list<T>& lt){empty_init();list<T> temp(lt.begin(), lt.end());//復(fù)用迭代器區(qū)間構(gòu)造，讓別人構(gòu)造好了，我再竊取革命成果swap(temp);}//assign(迭代器區(qū)間替換)template <class InputIterator>void assign(InputIterator first, InputIterator last){clear();while (first != last){push_back(*first);++first;}}//assign(直接替換)void assign(size_t n, const T& val){clear();for (size_t i = n; i > 0; --i)push_back(val);}//assign重載版本 防止間接尋址void assign(int n, const T& val){clear();for (size_t i = n; i > 0; --i)push_back(val);}// 賦值重載的傳統(tǒng)寫法list<T>& operator=(const list<T>& lt){assign(lt.begin(), lt.end());return *this;}// 賦值重載的現(xiàn)代寫法//list<T>& operator=(list<T> lt)//{// swap(lt);//利用值傳遞拷貝的臨時對象進(jìn)行交換// return *this;//}//析構(gòu)函數(shù)~list(){clear();delete _head;_head = nullptr;}//sizesize_t size() const{size_t n = 0;for (auto e : *this)++n;return n;}//insertiterator insert(iterator pos, const T& val){node* cur = pos._node;//記錄當(dāng)前節(jié)點(diǎn)node* prev = cur->_prev;//記錄前驅(qū)節(jié)點(diǎn)node* newnode = new node(val);//建立新節(jié)點(diǎn)//開始改變指向newnode->_next = cur;cur->_prev = newnode;prev->_next = newnode;newnode->_prev = prev;return iterator(newnode);}//eraseiterator erase(iterator pos){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);//利用匿名對象返回}//pushback 尾插void push_back(const T& val){insert(end(), val);}//pushfront 頭插void push_front(const T& val){insert(begin(), val);}//popback 尾刪void pop_back(){erase(--end());}//popfront 頭刪void pop_front(){erase(begin());}//clear 只留一個頭節(jié)點(diǎn)void clear(){iterator it = begin();while (it != end())it = erase(it);}//resize 如果n小于當(dāng)前容量的大小，則內(nèi)容將減少到前n個元素 當(dāng)n大于容器大小時，則在末尾插入任意容量的內(nèi)容。void resize(size_t n, const T& val = T()){size_t sz = size();//記錄當(dāng)前的有效元素的個數(shù)while (n < sz){pop_back();--sz;}while (n > sz){push_back(val);++sz;}}//emptybool empty() const{return node->next == node;}private:node* _head;//用來初始化 類內(nèi)部自己用，設(shè)私有void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}};? ? 接口暫時就搞這些，如果后面有時間再寫些比較復(fù)雜的接口，這一篇不太好理解，講解不到位還請見諒
?