【C＋＋STL】list的詳細用法和底層實現

🌟個人主頁：第七序章??

🌈專欄系列：C＋＋

??前言：

🌈一：介紹

🌈二：list的創建

??基本框架

🌙節點類

🌙構造函數：

??list類

🌙構造函數

🌙拷貝構造函數

🌙賦值重載

🌙析構函數

??++運算符重載

🌙- -運算符的重載

🌙==運算符重載

🌙!=運算符的重載!=運算符的重載

🌙*運算符的重載

🌙->運算符的重載

??迭代器相關函數

??插入和刪除函數

🌙insert

🌙erase函數

🌙push_fron, pop_back, pop_front

??其他函數

🌙size函數

🌙clear函數

🌙swap函數

??list的sort vs 庫的sort

🌙vector和list的排序效率

??從迭代器類重新理解封裝

🌻共勉:

??前言：

上一篇我們學習了C＋＋STL庫vector的詳細用法，今天我們來學習一下list的詳細用法和底層實現。

🌈一：介紹

?list是一種序列式容器(帶頭雙向循環鏈表)。該容器的底層是用雙向鏈表實現的, 在鏈表的任一位置進行元素的插入、刪除操作都是快速的。

🌈二：list的創建

??基本框架

🌙節點類

template<class T>
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;
};

🌙構造函數：

template<class T>
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T())	//別忘了寫缺省參數:_data(x),_next(nullptr),_prev(nullptr){}
};

?這里我們就用初始化列表對鏈表節點對象進行初始化，對節點存儲的值用匿名對象進行缺省參數賦值。前后節點指針初始化為空指針?
?這里的匿名對象對于自定義類型會去調用他們的默認構造來初始化，內置類型也有構造函數就是int，float,double是0

??list類

🌙構造函數

void empty_init()
{_head = new Node(); //調用構造函數，創造節點初始化,鏈表是一個個節點連接起來_head->_next = _head;_head->_prev = _head;	//帶頭雙向循環
}

?我們實現一個成員函數來初始化哨兵位節點

這里補充一下_head, 是鏈表的哨兵位節點

private:Node* _head;

?構造函數直接調用這個初始化函數就行了

list()
{empty_init();
}

🌙拷貝構造函數

		list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}

?在string和vector兩個容器里面我已經詳細講解了拷貝構造的要求，最重要的就是要完成深拷貝。這里我們就用了push_back這個接口來完成深拷貝。

	void push_back(const T& x){Node* new_node = new Node(x); //new 可以開空間，也能調用構造函數初始化Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;	//改成_head->_prve就沒有問題了_size++;}

?可以看到我們的push_back函數用new開了新空間，并且把對應的指針指向了新空間，這就完成了深拷貝。
?或許有同學疑問，為啥這_head->_prev = new_node;不寫成tail = new_node
原因就是tail是一個指針變量，我們改變指針變量的值是不能改變指針變量指向的值的。

?所以改變tail并不能改變_head->_prev,這里我面的本意是想把_head->_prev這個指針的指向改變

🌙賦值重載

	list<T>& operator=(list<T> lt){swap(lt);return *this;}

?還記得我在前面兩章說vector和string的賦值重載的時候嗎，資本家思想。如果我想要得到lt的并且想扔掉原來的資源，只需要把swap一下，lt這個局部變量在調用完這個函數就會銷毀。因為我現在已經把原來this的資源交換給了lt, 所以銷毀lt就相當于銷毀了原來this指向的資源。

🌙析構函數

	~list(){clear();delete _head;_head = nullptr;}

?這里我們直接先提前看一下clear的內部實現，來了解析構函數

		void clear(){auto it = begin();while (it != end()){it = erase(it);}}

?可以看到就是從頭結點刪除到尾節點，這里的erae方法后面介紹
?所以析構的時候我們就只需要delete一下哨兵節點就行了

??++運算符重載

Self& operator++()
{_node = _node->_next;return *this;
}

?從鏈表節點的類中我們知道節點的下一個節點的位置是用一個_next成員變量指針指向的，所以指向那個位置就行了。

?這就是一個后置++的實現，接下來我們實現前置++

	Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}

?這里我們就是返回自增之前的那個對象
?解釋下Self的類型，其實就是迭代器對象的類型

typedef list_iterator<T, Ref, Ptr> Self;

🌙- -運算符的重載

		Self& operator--(){_node = _node->_prev;return *this;}

?和++相反，++是找到后面的那個節點，而–就是找到前面那個節點。

		Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}

?前置- - 同上面前置++

🌙==運算符重載

bool operagor == (const Self & s)
{return _node == s._node;
}

?判斷兩個節點指針指向的地址是否相同即可

🌙!=運算符的重載!=運算符的重載

?!=運算符剛好和==運算符的作用相反，我們判斷這兩個迭代器當中的結點指針的指向是否不同即可

	bool operator!=(const Self& s){return _node != s._node;}

🌙*運算符的重載

		Ref operator*(){return _node->_data;}

?返回節點指針的存儲數據的成員變量_data就可以了
?這里的Ref是引用的類型，模板推導出來的引用類型

🌙->運算符的重載

		Ptr operator->(){return &_node->_data;}

??迭代器相關函數

	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);}

?這里只需要把節點傳給我們的迭代器類構造一個迭代器對象就可以獲得頭節點和尾部的迭代器。

??插入和刪除函數

🌙insert

iterator insert(iterator pos, const T& val)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);newnode->_next = cur;newnode->_prev = prev;prev->_next = newnode;cur->_prev = newnode;_size++;return iterator(newnode);}

?這里插入很easy，只需要把插入的新節點前后指針更新到對應的指針就行了

?注意這里插入不存在迭代器失效的問題，因為我們的擴容都是一個個獨立的空間，不存在像vector那樣擴容后會導致迭代器無法找到新開的空間，這里的迭代器是通過指針來找到空間的

🌙erase函數

	iterator erase(iterator pos){assert(pos != end()); //注意這里是給end， pos是迭代器的類型對象Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;next->_prev = prev;prev->_next = next;delete cur;_size--;return iterator(next);}

注意：這里釋放節點就要注意迭代器失效的問題了，我們刪除后，指向這個節點的迭代器指向的就是一個無效的內存，這時候就需要更新這個迭代器讓他指向有效的內存。

🌙push_fron, pop_back, pop_front

void push_front(const T& x)
{insert(begin(), x);}
void pop_front()
{erase(begin());
}
void pop_back()
{erase(--end());
}

復用insert和erase接口就行，push_front就是insert到頭結點位置，pop_front就是刪除頭結點位置，pop_back則是刪除end(end是最后一個節點的下一個節點)前一個位置

??其他函數

🌙size函數

size_t size() const
{return _size;
}

我們通過，一個成員變量來實現，如果鏈表插入節點的時候就自增_size,刪除節點的時候就自減_size,可以看看前面的插入和刪除函數

🌙clear函數

	void clear(){auto it = begin();while (it != end()){it = erase(it);}}

析構函數哪里前面已經解釋過

🌙swap函數

		void swap(list<T>& tmp){std::swap(_head, tmp._head);}

這里ist容器當中存儲的實際上就只有鏈表的頭指針，我們就交換兩個變量的頭結點就行了，就讓他們交換了數據，
這里我們還重載了一個全局的swap函數

template<class T>
void swap(list<T>& a, list<T>& b)
{a.swap(b);
}

?為了防止使用算法庫中的i那個很多拷貝構造的swap函數，我們重載一個全局函數通過模板有現成吃現成(兩個鏈表類型的變量，相同的類型)，會優先匹配我們自己實現的swap函數，然后我們這個全局的函數又調用成員函數swap,這個效率比算法庫的那個效率高很多，為啥效率高，請看前面兩個容器的講解很詳細。

??list的sort vs 庫的sort

List為啥要自己實現一個sort函數來排序，不能直接用算法庫中的sort嗎？
1.不能，因為我們的迭代器按功能角度來分類有3種:
?(1)單向迭代器（支持++) 例如:foward_list(單鏈表)
?(2)雙向迭代器(支持++.–)， list
?(3)隨機迭代器(支持++,–, +, -) string,vector

?注意：算法庫中的是必須要是隨機迭代器，而我們 list 實際上是一個帶頭雙向鏈表，只能用雙向迭代器，那么就不能傳給算法庫中的 sort。隨機迭代器就兼容單向和雙向迭代器，相當于是一個包含關系。

🌙vector和list的排序效率

?我們第一組數據是vector用算法庫sort和list用他的成員函數sort單獨排序，第二組數據是list的數據拷貝到vector給算法庫的sort排序和list用他的成員函數sort單獨排序
?可以看到copy到vector給算法庫的sort排序都比list的sort快

原因：
?鏈表這個不連續的結構并不適合大量數據的排序，他的索引訪問不能像vector那樣連續的索引訪問那么高效，需要更多時間來找到索引位置
?算法庫中的sort是快速排序算法，list的sort用的是歸并排序，快速排序還是比歸并排序要厲害一點的。

?想要更高的效率排序，最好拷貝到vector中排序，排完再拷貝回list

??從迭代器類重新理解封裝

?大家可以看到我們的迭代器類實際上是一個

	struct list_iterator

?在類外是可以訪問的，雖然在類外是可以訪問，但是我們通過對迭代器類重命名

	typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;

?提供了類外統一用iterator來訪問的方式，這樣外面并不知道我實際是什么名字，并不能很好的猜出來，可以看到我們stl中容器的迭代器都是統一命名為iterator, 但是每個容器的迭代器的底層細節實現方式可能都有差異，但是用戶都可以通過iterator來訪問各個容器，只能通過我給的接口訪問，這就是一個隱式的封裝。
?為啥要寫成struct,就是為了方便類里面對他的高頻訪問的問題。如迭代器函數begin,插入insert

?舉個通俗例子：
想象你開車時，只需要操作方向盤、油門和剎車等控制系統，來控制車子的前進和停止。這些操作背后涉及了復雜的機械結構、發動機和電控系統等內部實現，但你作為司機并不需要了解這些內部細節，只需要通過車內的接口（方向盤、油門、剎車等）來進行控制。
?
在這個例子中：

車子就是對象，封裝了車的內部組件（發動機、輪胎、剎車系統等）。
方向盤、油門和剎車是暴露出來的接口，司機通過這些接口與車子互動。
司機不需要知道發動機如何工作或者剎車是如何控制的，這些細節被隱藏了。

同樣，封裝在編程中通過類和方法來實現，外界使用對象時，只需要調用公開的接口（方法），而不需要關心類的內部實現。