list 介紹及底層

list的相關文檔：list - C++ Reference

一、list的介紹及使用

list中的接口比較多，此處類似，只需要掌握如何正確的使用，然后再去深入研究背后的原理，已達到可擴展的能力。以下為list中一些常見的重要接口。我們庫里的list 是一個帶頭雙向循環鏈表。?

1.1 list 的構造

1.2. list 迭代器的使用?

此處，大家可以暫時將迭代器理解成一個指針，該指針指向 list 中的某個節點。

?遍歷鏈表，與vector和string 不同的是， list 不支持 [ ] ，僅支持迭代器和范圍 for 遍歷鏈表。

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>
using namespace std;int main()
{list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int>lt2 = { 1,2,3,4,5 };list<int>::iterator it1 = lt1.begin();while (it1 != lt1.end()){cout << *it1 << " ";++it1;}cout << endl;for (auto& e : lt2){cout << e << " ";}cout << endl;return 0;
}

?1.3 list modifiers

1）emplace_back 和 push_back 都能實現尾插一個數據，有什么區別？?

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>
using namespace std;class Pos
{
public:Pos(int row,int col):_row(row),_col(col){}
private:int _row;int _col;
};int main()
{list<Pos> lt;Pos p1(1, 1);lt.push_back(p1);lt.push_back(Pos(2, 2));lt.push_back({3,3});lt.emplace_back(p1);lt.emplace_back(Pos(2, 2));//lt.emplace_back({ 3,3 });lt.emplace_back(3, 3);return 0;
}

補充 : 單參數的構造函數，支持隱式類型轉化?

?2）刪除指定元素

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<algorithm>
#include<list>
using namespace std;int main()
{list<int> lt1 = { 1,2,3,4,5 };for (auto e : lt1){cout << e << " ";}cout << endl;int x;cin >> x;auto it = find(lt1.begin(), lt1.end(), x);if (it != lt1.end()){lt1.erase(it);}for (auto e : lt1){cout << e << " ";}cout << endl;return 0;
}

1.4?Operations

1）merge : 合并

?2）unique : 去重? ，前提：有序

3）splice : 把一個鏈表的值轉移到另一個鏈表

?可以用來實現類似LRU（最近最少使用）的算法：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<algorithm>
#include<list>
using namespace std;//LRU
int main()
{list<int> lt1 = { 1,2,3,4,5 };for (auto e : lt1){cout << e << " ";}cout << endl;int x;while (cin >> x){auto pos = find(lt1.begin(), lt1.end(), x);if (pos != lt1.end()){lt1.splice(lt1.begin(), lt1, pos);}for (auto e : lt1){cout << e << " ";}cout << endl;}return 0;
}

4）sort : 排序

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<algorithm>
#include<list>
using namespace std;int main()
{list<int> lt1 = { 15,2,31,14,15 };for (auto e : lt1){cout << e << " ";}cout << endl;lt1.sort();for (auto e : lt1){cout << e << " ";}cout << endl;greater<int> gt;lt1.sort(gt);for (auto e : lt1){cout << e << " ";}cout << endl;return 0;
}

?為了簡化，我們一般按照下面的寫法，傳仿函數：

?為什么庫里面有sort ， list 還要實現一個sort , 難道不會是多次一舉嗎？

我們可以看到，不是list 不想用，是list 根本用不了。這就和迭代器的功能分類有關了。

?雖然，算法庫的sort 是一個模板，但是也很明顯的告訴了你，傳的要是隨機迭代器。

二、list 底層

模板不支持分離成兩個文件 ，這里我們僅創建 list.h?

list 的底層很深刻的體現了封裝的優點：

三者的角色分工
- 節點（Node）?- 數據的 "容器" ：?存儲實際的數據，以及連接其他節點的指針（前向和后向指針）
- 迭代器（Iterator）?- 數據的 "導航員" ：?提供訪問節點數據的統一方式，屏蔽底層節點的實現細節
- list 類?- 整個鏈表的 "管理者" ：?負責整體的創建、銷毀、插入、刪除等操作，維護鏈表的完整性

封裝的意義
- 分離關注點
  - 節點只關心數據存儲和連接
  - 迭代器只關心如何訪問數據
  - list 類只關心整體管理
  - 這樣每個部分可以獨立修改，不會互相影響
- 隱藏實現細節
  - 用戶不需要知道節點如何定義
  - 不需要知道迭代器如何移動
  - 只需要調用 list 提供的接口即可
- 統一訪問方式???????
  - 無論是 list、vector 還是其他容器，都可以用類似的迭代器方式訪問
  - 使得算法可以通用（如 sort、find 等）
- 提高安全性???????
  - 防止用戶直接操作節點指針導致的錯誤
  - 迭代器會自動處理邊界檢查等問題

2.1 list 節點類

1. （慣例）?如果成員變量和成員函數全部是公有的，一般用 struct 。既有公有又有私有，則用class

2. 如果把節點類放公有，不是會不安全 ? 能被任意修改 ?

節點類雖然是公開的，但是是隱形的封裝，對 list 才有用，在使用 list 的接口的時候，其實我們并不會知道它底層是雙向帶頭鏈表，也不知道成員變量的具體變量名（不同平臺的變量名會不同），所以是安全的， 在list 的增刪查改的時候，會高頻的調用list 的節點，所以直接放成struct?

	//慣例
//全部是公用，一般用structtemplate<class T>struct list_node{T _data;list_node<T>* _prev;list_node<T>* _next;list_node(const T& x = T()):_data(x), _prev(nullptr), _next(nullptr){}};

?缺省值給匿名對象 ，因為類型是不確定的，給字面量不合適。

2.2 list 迭代器

1.? ?原生指針已經不夠用了；所以list 的迭代器是類封裝指針，重載運算符，模擬指針行為。

2.? 使用struct ，因為需要頻繁訪問內部成員，不建議用訪問限定符限制。

3. 容器迭代器設計思路體現了封裝：屏蔽底層實現細節，屏蔽各容器結構差異，本質封裝底層細節和差異，提供統一的訪問方式。

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* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}//返回局部對象就不能再使用引用返回了Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};

2.3 list 類

1）insert:

返回 iterator ；由于不需要擴容，所以不存在迭代器失效的問題

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

復用insert 實現頭插和尾插：

		void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}

2）erase :

list 的迭代器失效： 迭代器失效即迭代器所指向的節點無效，即該節點被刪除了。 因為 list 的底層結構為帶頭節點的雙向循環鏈表， 因此再 list 中進行插入時是? 不會導致 list 的迭代器失效的， 只有在刪除時才會失效， 并且失效的只是指向被刪除節點的迭代器，其他迭代器不會受到影響。?

注意 : 刪除唯獨不能刪除哨兵位的頭結點！！！

	iterator erase(iterator pos){assert(pos != end());Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;//prev del nextprev->_next = next;next->_prev = prev;delete del;return iterator(next);}

?復用erase 實現頭刪和尾刪 :

		void pop_back(){erase(--end());}void pop_front(){erase(begin());}

3) 析構

		~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}

clear 是清理資源，但是結構依舊保持。 （注意： list 的erase 會導致迭代器失效的問題，需要更新一下迭代器。） 析構不僅清理資源，同時會把頭結點給刪除了。

4）拷貝構造 :?

		//拷貝構造//lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}

5）賦值重載：

//賦值重載
//lt2 = lt3
list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}void swap(list<T>& tmp)
{std::swap(_head, tmp._head);
}

6）所有代碼：list.h

#pragma once
#include<assert.h>namespace LF
{//慣例
//全部是公用，一般用structtemplate<class T>struct list_node{T _data;list_node<T>* _prev;list_node<T>* _next;list_node(const T& x = T()):_data(x), _prev(nullptr), _next(nullptr){}};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* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}//返回局部對象就不能再使用引用返回了Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}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 list_node<T> Node;//	typedef list_const_iterator<T> Self;//	Node* _node;//	list_const_iterator(Node* node)//		:_node(node)//	{}//	const T& operator*()//	{//		return _node->_data;//	}//	const T* operator->()//	{//		return &_node->_data;//	}//	Self& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	Self& operator--()//	{//		_node = _node->_prev;//		return *this;//	}//	Self operator++(int)//	{//		Self tmp(*this);//		_node = _node->_next;//		return tmp;//	}//	Self operator--(int)//	{//		Self tmp(*this);//		_node = _node->_prev;//		return tmp;//	}//	bool operator!=(const Self& s)//	{//		return _node != s._node;//	}//};template<class T>class list{typedef list_node<T> Node;public://typedef list_iterator<T> iterator;//typedef list_const_iterator<T> const_iterator;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);}void empty_init(){_head = new Node();_head->_prev = _head;_head->_next = _head;}list(){empty_init();}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}//n個val構造list(size_t n, const T& val = T()){empty_init();for (size_t i = 0; i < n; i++){push_back(val);}}//拷貝構造//lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}//賦值重載//lt2 = lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}void swap(list<T>& tmp){std::swap(_head, tmp._head);}//void push_back(const T& x)//{//	Node* new_node = new Node(x);//	Node* tail = _head->_prev;//	new_node->_next = _head;//	new_node->_prev = tail;//	_head->_prev = new_node;//	tail->_next = new_node;//}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}iterator insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;//prev newnode curnewnode->_prev = prev;newnode->_next = cur;prev->_next = newnode;cur->_prev = newnode;return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;//prev del nextprev->_next = next;next->_prev = prev;delete del;return iterator(next);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}private:Node* _head;};
}