1. list介紹

1.1. list概述

template < class T, class Alloc = allocator<T> > class list;Lists are sequence containers that allow constant time insert 
and erase operations anywhere within the sequence, and iteration in both directions.

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

我們用代碼來體會一下list的缺點：

void test_op1()
{srand(time(0));const int N = 1000000;//一百萬數據//兩個鏈表list<int> lt1;list<int> lt2;//一個順序表vector<int> v;//生成隨機數據，尾插到鏈表1和順序表v中去for (int i = 0; i < N; ++i){auto e = rand()+i;//加上這個i主要是為了減少重復數字概率lt1.push_back(e);v.push_back(e);}//vector排序int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();//list排序int begin2 = clock();lt1.sort();int end2 = clock();//打印比較兩者用時printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}

void test_op2()
{srand(time(0));const int N = 1000000;list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){auto e = rand();lt1.push_back(e);lt2.push_back(e);}// 拷貝vectorint begin1 = clock();vector<int> v(lt2.begin(), lt2.end());// 排序sort(v.begin(), v.end());// 拷貝回lt2lt2.assign(v.begin(), v.end());int end1 = clock();//lt1排序int begin2 = clock();lt1.sort();int end2 = clock();//打印printf("list copy vector sort copy list sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}

1.2. 相關接口的介紹

1.2.1. insert

作用：在指定位置之前插入結點

iterator insert (iterator position, const value_type& val);

注釋: An iterator that points to the first of the newly inserted elements.

問題：我們vector中insert會引發迭代器失效問題，我們list中的insert會有迭代器失效問題嗎？為什么？

答：不會。這是由底層結構決定的。

同理，erase也會引起vector失效，但是對于list就不會引起迭代器失效問題。

1.2.2. splice轉移

作用：把指定位置轉移到指定位置。

前提：轉移的數據元素必須一致！

1.2.3. remove

作用：移除鏈表中是val的值，沒有則不做處理

注意，會全部刪除，而不僅僅是刪除一個

1.2.4. unique去重

作用：排序后，去重復結點

前提：是排序之后才行。

1.2.5. merge合并

作用：合并兩個有序鏈表

前提：兩個鏈表必須排序, 如果不是有序的, 則會斷言報錯, 并且sort和merge使用的比較函數必須要一致!

1.2.6. sort排序

排序效率一般：這里需要重點強調一下list中的sort排序和vector中的sort排序效率差距還是挺大的，建議數據量比較大的話有條件就用vector進行排序，即使是從list把數據拷貝到vector再拷貝回list.

2. list -- 簡單模擬實現

2.1. 實現要點分析

ListNode的成員變量為什么是prev和next兩個指針呢？

因為我們要寫的是雙向鏈表，對于每個結點而言都需要去存儲前一個結點的地址和后一個結點的地址，結點本身還要存儲上自己的數據val這樣才可以。

list::迭代器的設計(為什么不用原生指針設計迭代器?)

但是這里有個問題：迭代器怎么寫？？？用原生指針typedef一下嗎？
當然不行。
在vector中，用原生指針充當迭代器是完全可以的，但是對于list，原生指針++或者--操作之后，會指向內存的下一塊區域，問題就是list在內存中實際的存儲是不確定的。

重要的原因在于，這個原生指針++、--操作之后的行為不是我們想要的，如果我們可以修改他的++、--行為豈不是很好嗎？
于是，我們將原生指針封裝為一個類，重載他的運算符，就解決了這個問題。本質上，封裝原生指針就是為了擴大我們對指針的控制權限。

總結一下: 原生指針迭代器運算不符合我們預期, 因此我們封裝為一個類, 掌控迭代器的行為.

為了便于大家理解，我在這里提出下面幾個問題幫助大家進一步理解上面代碼：

• 為什么list的迭代器需要對原生指針進行封裝？答：為了重載他的操作符, 掌控迭代器的行為.
• 迭代器需要寫構造函數和拷貝構造函數嗎？為什么？構造函數需要寫，拷貝構造不用寫，因為編譯器自動淺拷貝, list迭代器淺拷貝就足夠用了。
• 迭代器需要寫析構函數嗎？不用，因為迭代器不用考慮結點的釋放，釋放結點屬于list的工作
• 迭代器什么操作符需要進行重載？根據需要和實際意義，比如在當前場景下迭代器重載大于和小于就沒有什么實際意義，可以選擇不重載。而需要重點重載的是++, --, 解引用, ... 這些運算符.
• 上面我們寫的iterator類準確來說是類型還是迭代器？是迭代器類型，迭代器是在list中實現的。

請思考一下為什么這個begin()和end()的返回類型是iterator，而不能是iterator&，為什么是迭代器值返回，而不是引用返回呢，畢竟引用返回效率更高啊？

因為迭代器如果返回引用，就會造成很大的問題，畢竟外界可以修改begin和end，這也就會造成begin/end的指向錯誤。
我用下面例子來進行說明：

operator->的理解

對于自定義類型

struct A
{int _a;int _b;//構造函數A(const int& a = 0, const int& b = 0){_a = a;_b = b;}
};

我想弄個list<A>請問此時應該怎么進行數據遍歷呢？
可能你會寫出下面的代碼：

szg::list<A> la;
A a(1, 1);
la.push_back(a); // 有名對象尾插
la.push_back(A(2,2)); // 匿名對象尾插
la.push_back({3,3}); // CPP11新語法，多參數隱式類型轉換//訪問
szg::ListIterator<A> itA = la.begin();
while (itA != la.end())
{std::cout << (*itA)._a << " ";std::cout << (*itA)._b << " ";itA++;
}
std::cout << std::endl;

總感覺很奇怪，但是這是正確的。

倘若這不是struct A，而是class A呢？？？有人可能會說提供Get_A和Get_B函數，一般CPP中不習慣寫Get函數，這種JAVA是常用這樣的方法的。

CPP會重載一個operator->去解決這個問題。
在ListIterator類中，我們可以寫下下面代碼：

T* operator->()//返回對應val值的地址
{return &_iterator->_val;
}

之后，我們可以這樣寫Test：

struct A
{int _a;int _b;//構造函數A(const int a = 0, const int b = 0){_a = a;_b = b;}
};

szg::list<A> la;
A a(1, 1);
la.push_back(a); // 有名對象尾插
la.push_back(A(2,2)); // 匿名對象尾插
la.push_back({3,3}); // CPP11新語法，多參數隱式類型轉換//訪問
szg::list<A>::iterator it = la.begin();
while (it != la.end())
{/*std::cout << (*itA)._a << " ";std::cout << (*itA)._b << " ";*///std::cout << (*it)._a << " ";std::cout << it->_a << " ";std::cout << it->_b << " ";it++;
}
std::cout << std::endl;

這里需要注意的是，在我們調用operator的時候，編譯器對其做了優化，按照邏輯我們需要寫為it.operator->()->_a，這里我們可以少寫一個->，更加符合我們的使用習慣。

const迭代器問題

不知道大家發現了沒有，一直以來都沒用過const迭代器去遍歷，實際上，在上面所寫的代碼中就完全沒有const的影子，如果用const迭代器就會報語法錯誤，因為壓根沒有實現。

倘若你認為這樣寫：

那我可以告訴你這樣的const迭代器跟非const是一樣的行為，一樣可以修改迭代器指向的內容。

辨析：
const迭代器和非const迭代器的區別？？？
const迭代器不可修改迭代器指向的內容，非const迭代器可以修改迭代器指向元素的內容。

倘若你靈機一動，說改成這樣：

那么你這樣就是讓迭代器本身不可更改，而不是迭代器指向的內容不可更改。

實際上，想要正確寫出const迭代器有兩種方法：一是再寫一個const_iterator迭代器類，再一個就是把const作為一個參數傳入ListIterator中，讓其根據模板自動生成一份const迭代器類。

下面來依次介紹兩種方法：
對于兩種方法，都是重新寫一個類而已，只不過前者是自己寫，后置式讓編譯器根據模板進行推導罷了。

template<class T>
struct ConstListIterator
{typedef ListNode<T> node;const node* _iterator;//itrator構造ConstListIterator(const node* node):_iterator(node){}//解引用重載const T& operator* ()const{return _iterator->_val;}const T* operator-> ()const//返回對應val值的地址{return &_iterator->_val;}//前置++重載ConstListIterator<T>& operator++(){_iterator = _iterator->_next;return *this;}//后置++重載//ConstListIterator<T> operator++(int)//{//	ListIterator<T> temp(*this); // 構建一個臨時對象//	_iterator = _iterator->_next; // 讓當前this指向下一個結點//	return temp; // 但是返回臨時變量//} //error：temp類型錯誤。ConstListIterator<T> operator++(int){ConstListIterator<T> tmp(*this);_iterator = _iterator->_next;return tmp;}//!=重載bool operator!=(const ConstListIterator<T>& l){//return this->_iterator != l._iterator;return _iterator != l._iterator;}//==重載bool operator==(const ListIterator<T>& l){return this->_iterator == l._iterator;}
};

上面就是一個寫好的const迭代器類，請注意：在list中使用的時候也要用typedef更改一下名字，這樣struct ConstListIterator就成為了List類中的內部類，自由使用了。

簡單測試：

//test
szg::list<int> li;
li.push_back(1);
li.push_back(2);
li.push_back(3);
li.push_back(4);
li.push_back(5);const szg::list<int> li2 = li;szg::list<int>::const_iterator it = li2.begin();
while (it != li2.end())
{std::cout << *it << " ";it++;
}
std::cout << std::endl;

當然，我們也可以用第二種方式讓編譯器為我們寫const迭代器：

template<class T, class Ref, class Pon>
struct ListIterator
{
public:typedef ListNode<T> node;node* _iterator;
public://itrator構造ListIterator(node* node):_iterator(node){}//解引用重載Ref operator* (){return _iterator->_val;}Pon operator-> ()//返回對應val值的地址{return &_iterator->_val;}//前置++重載ListIterator<T, Ref, Pon>& operator++(){_iterator = _iterator->_next;return *this;}//后置++重載ListIterator<T, Ref, Pon> operator++(int){ListIterator<T, Ref, Pon> temp(*this); // 構建一個臨時對象_iterator = _iterator->_next; // 讓當前this指向下一個結點return temp; // 但是返回臨時變量}//!=重載bool operator!=(const ListIterator<T, Ref, Pon>& l){return this->_iterator != l._iterator;}//==重載bool operator==(const ListIterator<T, Ref, Pon>& l){return this->_iterator == l._iterator;}
};

CPP11快捷構造函數 -- 初始化列表構造

list(std::initializer_list<T> il)
{empty_initialization();//申請一個哨兵位for (auto& node : il)//然后一直尾插數據{push_back(node);}
}

2.2. 代碼示例

接口實現清單

typedef ListNode<T> Node;
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;Node* _head;
size_t _size;

1. 迭代器

• • iterator begin()
  • iterator end()
  • const_iterator begin() const
  • const_iterator end() const

1. 構造

• • void empty_init()
  • list()
  • list(const list<T>& lt)
  • list<T>& operator=(list<T> lt)
  • ~list()

1. 增刪查改

• • void push_back(const T& x)
  • void push_front(const T& x)
  • void insert(iterator pos, const T& val)
  • void pop_back()
  • void pop_front()
  • iterator erase(iterator pos)
  • void clear()

1. 其他

• • size_t size() const
  • bool empty()

#pragma once
#include<assert.h>namespace bit
{template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}};// typedef ListIterator<T, T&, T*> iterator;// typedef ListIterator<T, const T&, const T*> const_iterator;template<class T, class Ref, class Ptr>// T: list里面裝的數據類型// Ref: 迭代器解引用返回值類型 T& or const T&// Ptr: 迭代器箭頭運算符返回值類型 T* or const T*struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;ListIterator(Node* node):_node(node){}// *it//T& operator*()Ref operator*(){return _node->_data;}// it->//T* operator->()Ptr operator->(){return &_node->_data;}// ++itSelf& 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& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};//template<class T>//struct ListConstIterator//{//	typedef ListNode<T> Node;//	typedef ListConstIterator<T> Self;//	Node* _node;//	ListConstIterator(Node* node)//		:_node(node)//	{}//	// *it//	const T& operator*()//	{//		return _node->_data;//	}//	// it->//	const T* operator->()//	{//		return &_node->_data;//	}//	// ++it//	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& it)//	{//		return _node != it._node;//	}//	bool operator==(const Self& it)//	{//		return _node == it._node;//	}//};template<class T>class list{typedef ListNode<T> Node;public://typedef ListIterator<T> iterator;//typedef ListConstIterator<T> const_iterator;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;//iterator begin()//{//	//return iterator(_head->_next);//	iterator it(_head->_next);//	return it;//}iterator begin(){return _head->_next;}iterator end(){return _head;}// const����������?�?����������??����?�����?������?�// ������?������?����??�const iterator����������?const������// T* const p1// const T* p2const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}// lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}// ��?������?�����?�?�д�?��// ����?������?��?���?�?�д�?����?��?�����?���void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}// lt1 = lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}/*void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}*/void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;// prev newnode cur;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}size_t size() const{return _size;}bool empty(){return _size == 0;}private:Node* _head;size_t _size;};

#pragma once
#include <algorithm>
#include <iostream>
#include <cassert>
// #include <list>
using namespace std;namespace zzg
{template<class T>class ListNode{public:T _data;ListNode<T>* _prev;ListNode<T>* _next;public:ListNode(const T& val = T()):_data(val), _prev(nullptr), _next(nullptr){}~ListNode(){// _data = 0; // 模板參數, 不一定可以賦值為0_prev = _next = nullptr;}};template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;public:Node* _ptr;public:ListIterator(Node* ptr = nullptr):_ptr(ptr){}~ListIterator(){_ptr = nullptr;}Self& operator++ (){_ptr = _ptr->_next;return *this;}Self operator++ (int){Self t(*this);_ptr = _ptr->_next;return t;}Self& operator-- (){_ptr = _ptr->_prev;return *this;}Self operator-- (int){Self t(*this);_ptr = _ptr->_prev;return t;}Ref operator* (){return _ptr->_data;}Ptr operator-> (){return &(_ptr->_data);}bool operator != (const Self& it){return _ptr != it._ptr;}bool operator== (const Self& it){return _ptr == it._ptr;}};template <class T>class list{private:typedef ListNode<T> Node;Node* _head;size_t _size;void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;}public: typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}public:// 構造 與 析構list() // 默認構造:_head(nullptr), _size(0){empty_init();}list(const list<T>& lt) // 拷貝構造:_head(nullptr), _size(0){empty_init(); // 初始化節點for(Node * cur = lt._head->_next; cur != lt._head; cur = cur->_next){push_back(cur->_data); // 逐個添加元素}}list<T>& operator=(list<T> lt) // 賦值構造{swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;_size = 0;}// 其他void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}size_t size() const{return _size;}bool empty() const{return _size == 0;}// 增刪改查void push_back(const T& x){// Node* ptail = _head->_prev; // 指向最后一個節點// Node* newNode = new Node(x); // 構造新節點//newNode->_prev = ptail; // 新節點的前驅指向尾節點//newNode->_next = _head; // 新節點的后繼指向頭節點//ptail->_next = newNode; // 尾節點的后繼指向新節點//_head->_prev = newNode; // 頭節點的前驅指向新節點//_size++; // 更新大小insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void insert(iterator pos, const T& val){Node* cur = pos._ptr;Node* prev = cur->_prev;Node* newNode = new Node(val);newNode->_next = cur;newNode->_prev = prev;cur->_prev = newNode;prev->_next = newNode;_size++;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator erase(iterator pos){assert(begin() != end());Node* cur = pos._ptr;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}void clear(){iterator it = begin();while (it != end()){// cout << it._ptr->_data << endl;/*erase(it);it++;*/ // bug: 如果這樣寫, 就等于是先把一個東西刪除, 再用刪除的哪個東西再去取下一個節點的指針it = erase(it);}}// debug函數void print_list(){cout << "-----print_list-----" << endl;for (Node* cur = _head->_next; cur != _head; cur = cur->_next){cout << cur->_data << " ";}cout << endl << "size: " << _size << endl;cout << "-----print_end------" << endl;cout << endl;}};// 構造函數測試void test1(){list<int> l1; // 默認構造l1.push_back(1);l1.push_back(2);l1.print_list();list<int> l2(l1); // 拷貝構造l2.print_list();list<int> l3; // 默認構造l3 = l1; // 賦值構造l3.push_back(7);l3.push_back(9);l3.print_list();}// 增刪 測試void test2(){list<int> l1;l1.insert(l1.begin(), 1); // 頭插 l1.insert(l1.begin(), 2); // 頭插l1.insert(l1.begin(), 3); // 頭插l1.insert(l1.end(), 4); // 尾插l1.insert(l1.end(), 5); // 尾插l1.print_list();l1.push_front(0); // 頭插l1.push_back(10); // 尾插l1.print_list();// 0 3 2 1 4 5 10l1.pop_back(); // 0 3 2 1 4 5l1.print_list();l1.pop_front(); // 3 2 1 4 5l1.print_list();l1.erase(l1.begin()); // 2 1 4 5l1.print_list();l1.clear();l1.print_list();}void test(){// test1();test2();}
};