C++：List的使用和模拟实现

                                                        创作不易，感谢三连！！

一、List的介绍

list的文档介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

要注意的是，list开始就不支持下标访问了，所以要访问都要以迭代器为准

void Print(const list<int>& l)
{//迭代去区间遍历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的使用注意事项 

博主觉得跟之前vector的基本上差不了多少，如果不会看文档用库里面的list的可以去看博主只管关于string和vector的使用。

C++：String类的使用-CSDN博客 

C++：Vector的使用-CSDN博客

下面直接介绍List使用中的易错点

2.1 List的迭代器失效问题

        我们之前学习vector的时候，知道了insert和erase都有可能存在迭代器失效的问题，那list会出现这种情况吗？？下面来进行分析

insert插入新节点的迭代器，因此insert不可能会出现失效的问题。

   而earse必然会失效，因为该迭代器对应的节点被删除了。如果我们想继续用的话，就得利用返回值去更新迭代器，返回值是被删除元素的下一个位置的迭代器。

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调用自己的sortint begin2 = clock();lt2.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}

 会发现哪怕我先拷贝到vector排完再拷贝回去效率都比list的sort效率高，所以list的sort实际中意义不是很大！！

 三、模拟实现的注意事项

     还是跟之前模拟实现一样，先看看SGI版本的源码 ，list本质上是带头双向链表

第一部分    链表节点

​

第二部分   迭代器

​

第三部分、链表

​

这里我们可以先实现链表节点结构体 这里用sturct把权限放开。

//节点的封装
template<class T>
struct list_node
{list_node<T>* _prev;list_node<T>* _next;T _data;//节点的构造函数list_node(const T& val = T()):_prev(nullptr), _next(nullptr), _data(val){}
};

然后封装一个链表，将头结点作为自己的成员变量封装起来

	template<class T>
class list
{typedef list_node<T>  node;//typedef可以帮助我们简洁代码private:node* _head;};

下面开始进行我们的重中之重——迭代器 

四、正向迭代器的实现

2.1 正向迭代器的封装

      在学习Vector的时候，我们发现其实vector的迭代器就是一个原生指针，所以我们将他改了名字

​

      这得益于vector空间连续的特点，所以对指针进行加和减再进行解引用可以访问到我们想要的元素，但是链表可以吗？

 ​

     虽然看似我们好像用箭头连接起来了，但其实他们空间上是不连续的，那我们对一个节点指针进行加减，就很难说能不能找到下一个节点，更多的是找不到的情况

    那我们思考一样，如果我们要搞一个迭代器，我们希望怎么去得到我们的数据呢？？我们希望我们解引用的时候，可以拿到他的data，希望++的时候，可以拿到他的next，--的时候，可以拿到他的prev。  那我们怎么去改变原生操作符的行为呢？答案就是运算符重载！所以我们可以将迭代器单独封装成一个类去管理节点，改变运算符的行为！！

       我们先进行实现，然后再慢慢分析

	//封装迭代器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;//迭代器的构造函数list_iterator(node* n)//迭代器的构造:_node(n){}//实现*Ref operator*() const{return _node->_data;}//实现->Ptr operator->() const{return &operator*();    //本来是两个->,为了增强可读性，我们封装了这个函数 比如当我们存储的结构体解引用后有多个成员，那么我们可以通过箭头的直线去找到对应我们想要的成员	}//前置++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;}};

第一个模版参数是类型，第二个模版参数是引用，第三个模版参数是指针

       Ref和Ptr是用来区分正常的迭代器和const修饰的迭代器，Ref是T&或者是const T&,这样可以在某些时候我们去限制data不能被修改。而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修饰普通迭代器？？

​

       因为typedef碰到const的话，就不是简单的字符串替换  实际上你以为的const T* ，在这里变成了T*const ，因为迭代器我们是希望他可以进行++和--的，而我们只是不希望他指向的内容给改变，所以我们的const要修饰的是指针的内容，而不是修饰指针。

五、list相关的成员函数

3.1  构造函数

​

1、默认构造函数

​

因为无论如何都要有哨兵节点，所以我们直接封装一个

	void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}

所以可以这么写

	//默认构造函数list(){empty_init();}

2、有参构造函数

//有参构造函数
list(size_t n, const T& val = T())
{empty_init();for (size_t i = n; i > 0; --i)push_back(val);
}

 3、迭代器区间构造函数

//迭代器区间构造函数
template <class InputIterator>
list(InputIterator first, InputIterator last)
{empty_init();while (first != last){push_back(*first);++first;}
}

4、拷贝构造的传统写法

传统方法就是一个个拷贝过去

//拷贝构造函数传统写法
list(const list<T>& lt)
{empty_init();for (auto e : lt)push_back(e);
}

5、拷贝构造的现代写法+swap

      现代写法就是，我先创建一个临时对象让他利用被拷贝对象的迭代器构造出来，然后再交换，窃取革命成功，被利用完后的临时对象会在栈帧结束后被清除（典型的资本家思维）

	//交换函数void swap(list<T>& temp){std::swap(_head, temp._head);}//拷贝构造函数的现代写法list(const list<T>& lt){empty_init();list<T> temp(lt.begin(), lt.end());//复用迭代器区间构造，让别人构造好了，我再窃取革命成果swap(temp);}

3.2 clear和析构函数

    list不像vector一样，不能直接用头指针delete，因为空间不连续，所以要一个个节点去delete，所以在这之前，我们可以先实现clear，clear的作用是把链表清空，只剩一个头节点，然我们的析构函数再复用clear，然后再单独delete头节点就行了！！

	//clear 只留一个头节点void clear(){iterator it = begin();while (it != end())it = erase(it);}//析构函数~list(){clear();delete _head;_head = nullptr;}

3.3 赋值重载和assign

​

​

       assign和=的本质上都是，先将原来的空间的内容给清空，换成的内容。 只不过区别就是assign可以利用迭代器去控制被替换的范围，也可以自己去换成n个一样的元素。所以我们先实现assign，再实现=

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迭代器区间替换

	//assign(迭代器区间替换)template <class InputIterator>void assign(InputIterator first, InputIterator last){clear();while (first != last){push_back(*first);++first;}}

3、assign直接替换重载（防止间接寻址）

​

思考：我们的本意是将lt2替换成5个2，我们发现我们调的竟然是迭代器区间构造的assign，为什么会这样呢？？？？？     

      因为重载类型会优先找最匹配的，assign的第一个版本的n是size_t类型，我们传的整数默认是int所以会发生强制类型转化，而第二个版本恰好可以变成两个int，所以他会走迭代器区间版本。所以此时有两个方案，第一个方案是我们要在第一个参数后面加u，但是这不符合我们的使用习惯，所以我们可以采用第二个方案，写个重载版本。

//assign重载版本  防止间接寻址
void assign(int n, const T& val)
{clear();for (size_t i = n; i > 0; --i)push_back(val);
}

4、赋值重载传统写法 

直接复用assign

	// 赋值重载的传统写法list<T>& operator=(const list<T>& lt){assign(lt.begin(), lt.end());return *this;}

5、赋值重载的现代写法

list<T>& operator=(list<T> lt)
{swap(lt);//利用值传递拷贝的临时对象进行交换return *this;
}

3.4 修改相关函数（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

我们先实现insert和erase，其他的就可以直接复用了

//insert
iterator insert(iterator pos, const T& val)
{node* cur = pos._node;//记录当前节点node* prev = cur->_prev;//记录前驱节点node* newnode = new node(val);//建立新节点//开始改变指向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小于当前容量的大小，则内容将减少到前n个元素 当n大于容器大小时，则在末尾插入任意容量的内容。
void resize(size_t n, const T& val = T())
{size_t sz = size();//记录当前的有效元素的个数while (n < sz){pop_back();--sz;}while (n > sz){push_back(val);++sz;}
}

六、反向迭代器的实现

sgi版本下的反向迭代器，其实就是将构建一个反向迭代器的类将正向迭代器封装起来，这个时候正向迭代器的++就是反向迭代器的--

template<class iterator, class Ref, class Ptr>
struct list_reverse_iterator
{typedef list_reverse_iterator<iterator, Ref, Ptr> self;//用正向迭代器去构造反向迭代器list_reverse_iterator(iterator it):_cur(it){}//解引用Ref operator*() const{iterator temp = _cur;--temp;return *temp;}//实现->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下的反向迭代器代码：

​

         复用性很高，和list的区别就是因为是随机迭代器，所以多了+和-的接口，第二个就是不需要->,所以其实模版也可少传一个 

 七、list模拟实现的全部代码

//c++喜欢ListNode驼峰法命名  为了和STL风格一致，我们也用小写
//但是STL版本和java喜欢小写带_  
namespace cyx
{//节点的封装template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _data;//节点的构造函数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;//迭代器的构造函数list_iterator(node* n)//迭代器的构造:_node(n){}//实现*Ref operator*() const{return _node->_data;}//实现->Ptr operator->() const{return &operator*();    //本来是两个->,为了增强可读性，我们封装了这个函数 比如当我们存储的结构体解引用后有多个成员，那么我们可以通过箭头的直线去找到对应我们想要的成员	}//前置++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;//用正向迭代器去构造反向迭代器list_reverse_iterator(iterator it):_cur(it){}//解引用Ref operator*() const{iterator temp = _cur;--temp;return *temp;}//实现->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());}//默认构造函数list(){empty_init();}//有参构造函数list(size_t n, const T& val = T()){empty_init();for (size_t i = n; i > 0; --i)push_back(val);}//迭代器区间构造函数template <class InputIterator>list(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);++first;}}//拷贝构造函数传统写法/*list(const list<T>& lt){empty_init();for (auto e : lt)push_back(e);}*///交换函数void swap(list<T>& temp){std::swap(_head, temp._head);}//拷贝构造函数的现代写法list(const list<T>& lt){empty_init();list<T> temp(lt.begin(), lt.end());//复用迭代器区间构造，让别人构造好了，我再窃取革命成果swap(temp);}//assign(迭代器区间替换)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);}// 赋值重载的传统写法list<T>& operator=(const list<T>& lt){assign(lt.begin(), lt.end());return *this;}// 赋值重载的现代写法//list<T>& operator=(list<T> lt)//{//	swap(lt);//利用值传递拷贝的临时对象进行交换//	return *this;//}//析构函数~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;//记录当前节点node* prev = cur->_prev;//记录前驱节点node* newnode = new node(val);//建立新节点//开始改变指向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 只留一个头节点void clear(){iterator it = begin();while (it != end())it = erase(it);}//resize  如果n小于当前容量的大小，则内容将减少到前n个元素 当n大于容器大小时，则在末尾插入任意容量的内容。void resize(size_t n, const T& val = T()){size_t sz = size();//记录当前的有效元素的个数while (n < sz){pop_back();--sz;}while (n > sz){push_back(val);++sz;}}//emptybool empty() const{return node->next == node;}private:node* _head;//用来初始化  类内部自己用，设私有void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}};

    接口暂时就搞这些，如果后面有时间再写些比较复杂的接口，这一篇不太好理解，讲解不到位还请见谅

​