目錄

?編輯

一，?List的模擬實(shí)現(xiàn)

二，代碼實(shí)現(xiàn)

三、list和vector的區(qū)別

---

一，?List的模擬實(shí)現(xiàn)

?????List?是一個雙向循環(huán)鏈表,由于List的節(jié)點(diǎn)不連續(xù)，不能用節(jié)點(diǎn)指針直接作為迭代器，因此我們要對結(jié)點(diǎn)指針封裝，來實(shí)現(xiàn)迭代器的作用。

迭代器有兩種實(shí)現(xiàn)方式，具體應(yīng)根據(jù)容器底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)：

????????1. 原生態(tài)指針，比如：vector

????????2. 將原生態(tài)指針進(jìn)行封裝，因迭代器使用形式與指針完全相同，因此在自定義的類中必須實(shí)現(xiàn)以下方法：

????????1. 指針可以解引用，迭代器的類中必須重載operator*()

?? ? ? ?2. 指針可以通過->訪問其所指空間成員，迭代器類中必須重載oprator->()

????????3. 指針可以++向后移動，迭代器類中必須重載operator++()與operator++(int)

至于operator--()/operator--(int)釋放需要重載，根據(jù)具體的結(jié)構(gòu)來抉擇，雙向鏈表可以向前 移動，所以需要重載，如果是forward_list就不需要重載--

????????4. 迭代器需要進(jìn)行是否相等的比較，因此還需要重載operator==()與operator!=()

二，代碼實(shí)現(xiàn)

#pragma once
#include<assert.h>
#include<iostream>
#include <initializer_list>
#include<algorithm>
using namespace std;namespace BMH
{template<class T>struct ListNode{typedef ListNode<T> Node;Node* _prev;Node* _next;T _data;ListNode(const T& data = T()):_prev(nullptr), _next(nullptr), _data(data){}};template<class T, class Ref, class Ptr>struct ListIterator{//正向迭代器typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;// Ref 和 Ptr 類型需要重定義下，實(shí)現(xiàn)反向迭代器時需要用到public:typedef Ref Ref;typedef Ptr Ptr;Node* _node;ListIterator(Node* node =nullptr):_node(node){}//++itSelf& operator++(){_node = _node->_next;return *this;//++it 返回自己（迭代器）}//--itSelf& operator--(){_node = _node->_prev;return  *this;}//it++Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}//it--Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}//// 具有指針類似行為//*it  返回值Ref operator*(){return _node->_data;;}//it->  返回指針Ptr operator->(){return &(_node->_data);}////// 迭代器支持比較bool operator == (const Self& it){return _node == it._node;}bool operator != (const Self& it){return _node != it._node;}};template<class T>class List{public:typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;/////初始化創(chuàng)建頭結(jié)點(diǎn)void empty_init(){_head = new Node();_head->_prev = _head;_head->_next = _head;}//構(gòu)造函數(shù)List(){empty_init();}List(int n, const T& value = T()){empty_init();for (int i = 0; i < n; ++i)push_back(value);}//用下面拷貝構(gòu)造函數(shù)來實(shí)現(xiàn)構(gòu)造函數(shù)，拷貝構(gòu)造函數(shù)是構(gòu)造函數(shù)的一種。//List<int> lt2(lt1)//List(const List<T>& lt)//{//	empty_init();//	for (const auto& e : lt)//	{//		Push_Back(e);//	}//}//List<int> lt1 ={1,2,3,4}List(initializer_list<T> il)//不用引用的原因：il本身是兩個指針，拷貝代價小{empty_init();for (const auto& e : il){Push_Back(e);}}template<class Inputiterator >List(Inputiterator p1, Inputiterator p2){empty_init();while (p1 != p2){Push_Back(*p1);++p1;}}//拷貝構(gòu)造//lt2(lt1)List(const List<T>& lt){empty_init();for (const auto& e : lt){Push_Back(e);}}//賦值重載//lt1=lt2List<T>& operator=(List<T> lt){swap(_head, lt._head);return *this;}void clear(){iterator it = begin();while (it != end()){it = erase(it);//用erase時會發(fā)生迭代器失效}}~List(){clear();delete _head;_head = nullptr;}/////迭代器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);}///// 容量相關(guān)//尾插void Push_Back(const T& x){Node* tail = _head->_prev;Node* newnode = new Node(x);newnode->_prev = tail;tail->_next = newnode;newnode->_next = _head;_head->_prev = newnode;}void Pop_Back(){erase(--end());}void Push_Front(const T& x){insert(begin(),x);}void Pop_Front(){erase(begin());}//之前插入，無迭代器失效iterator insert(iterator pos ,const T& data ){Node* cur = pos._node;//pos是迭代器，找到其中的節(jié)點(diǎn)地址即可Node* newnode = new Node(data);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur-> _prev= newnode;return iterator(newnode);}//有迭代器失效,返回刪除節(jié)點(diǎn)下一個的迭代器iterator erase(iterator pos){assert(pos!= (*this).end());//防止將Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);}private:Node* _head;};

三、list和vector的區(qū)別

????????1、任意位置插入刪除時：list可以隨意插入刪除，但是vector任意位置的插入刪除效率低，需要挪動元素，尤其是插入時有時候需要異地擴(kuò)容，就需要開辟新空間，拷貝元素，釋放舊空間，效率很低

????????2、訪問元素時：vector支持隨機(jī)訪問，但是list不支持隨機(jī)訪問
????????3、迭代器的使用上：vector可以使用原生指針，但是list需要對原生指針進(jìn)行封裝
????????4、空間利用上：vector使用的是一個連續(xù)的空間，空間利用率高，而list使用的是零碎的空間，空間利用率低

這個博客如果對你有幫助，給博主一個免費(fèi)的點(diǎn)贊就是最大的幫助?

歡迎各位點(diǎn)贊，收藏和關(guān)注哦?

如果有疑問或有不同見解，歡迎在評論區(qū)留言哦?

后續(xù)我會一直分享雙一流211西北大學(xué)軟工（C，數(shù)據(jù)結(jié)構(gòu)，C++，Linux，MySQL）的學(xué)習(xí)干貨以及重要代碼的分享