总言

  主要介绍list的基本函数使用及部分函数接口模拟实现(搭框架)。

  

  

1、常用接口与举例演示

  list介绍：相关参考网址

1.1、接口总览

  有了string、vector相关铺垫，list接口理解起来相对容易，故而我们的重心不在各接口的使用上，而在其模拟实现。进一步理解类和对象的精华，以及学习迭代器、拷贝构造相关内容。

  

1.2、部分例子

1.2.1、头删、头插、尾删、尾插、遍历

  1）、演示实例一

void test_list1()
{list<int> lt;lt.push_back(1);//尾插lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>:: iterator it = lt.begin();//迭代器使用while (it != lt.end()){cout << *it << " ";//遍历++it;}cout << endl;it = lt.begin();while (it != lt.end()){*it *= 2;//修改++it;}for (auto e : lt)//范围for使用{//此处内置类型，所有没使用引用和constcout << e << " ";}cout << endl;lt.push_front(10);//头插lt.push_front(20);lt.push_front(30);lt.push_front(40);lt.push_front(50);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();//尾删lt.pop_back();lt.pop_front();//头删for (auto e : lt){cout << e << " ";}cout << endl;
}

  
  

1.2.2、pos插入删除、迭代器失效问题

  2）、演示实例二

void test_list2()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);auto pos = find(lt.begin(), lt.end(), 3);if (pos != lt.end())//insert插入验证{// 提问：此处的pos是否存在迭代器失效问题？// 回答:不会，pos指向的仍旧是我们find到的3lt.insert(pos, 30);lt.insert(pos, 40);//二次插入*pos *= 100;//修改pos值}for (auto e : lt){cout << e << " ";}cout << endl;pos = find(lt.begin(), lt.end(), 4);if (pos != lt.end())//erase删除验证{// 提问：此处的pos是否存在迭代器失效问题？// 回答：会，因为pos位置的节点被我们干掉了，此时指向为野指针lt.erase(pos);// cout << *pos << endl;}for (auto e : lt){cout << e << " ";}cout << endl;
}

  
  

1.2.3、一些相对陌生接口简介（std::sort和list::sort比较)

  这一部分接口相对list来说属于新内容，但从使用角度用到它们频率很少，从介绍角度还是需要了解一下。

  
  
  1）、list::splice　转移链表元素

  for (int i=1; i<=4; ++i)mylist1.push_back(i);      // mylist1: 1 2 3 4for (int i=1; i<=3; ++i)mylist2.push_back(i*10);   // mylist2: 10 20 30it = mylist1.begin();++it;                         // points to 2mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4// mylist2 (empty)// "it" still points to 2 (the 5th element)

  注意此处mylist2的数据被挪走了。
  
  
  2）、list::remove 删除指定的所有元素

void test_list3()
{list<int> lt;lt.push_back(1);lt.push_back(3);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(3);lt.push_back(5);lt.push_back(3);for (auto e : lt){cout << e << " ";}cout << endl;lt.remove(3);for (auto e : lt){cout << e << " ";}cout << endl;
}

  如下图演示：可看到并非只删除一个指定元素，而是把链表中所有符合元素都删除。

  
  
  3）、list::unique 去重
  介绍：要使用该函数的前提是链表有序。

  
  
  4）、list::sort 为链表排序

  问题：我们的算法库中已经有了一个排序std::sort，为什么链表还要单独实现一个list::sort？
  回答：算法库中实现的sort有一个基本前提，即物理空间必须连续，而List结构为非连续物理空间，因此为其单独设置排序函数。
  
  问题：这二者排序有区别吗？
  回答：一般来说，算法库中的sort底层是以快排实现的，而list中的sort其可以用并归实现。二者有一定区别，比如，访问大量数据并排序，我们使用vector+算法库的sort，还是使用list+自身的sort？
  
  以下为相关验证：
  演示验证一：代码如下

void test01()
{//创建随机数srand(time(0));const int N = 10000000;//实例化vector、listvector<int> v;v.reserve(N);list<int> lt;//将随机数放入二者中for (int i = 0; i < N; ++i){auto e = rand();v.push_back(e);lt.push_back(e);}//对vector排序int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();//对list排序int begin2 = clock();lt.sort();int end2 = clock();printf("vector sort:%d\\n", end1 - begin1);printf("list sort:%d\\n", end2 - begin2);
}

  在release版本下验证结果如下：

  
  演示验证二：代码如下

void test02()
{//创建随机数srand(time(0));const int N = 1000000;//实例化两个list，辅助vectorvector<int> v;v.reserve(N);list<int> lt1;list<int> lt2;//为lt1、lt2赋值相同随机数for (int i = 0; i < N; ++i){auto e = rand();lt1.push_back(e);lt2.push_back(e);}//排序一：将数据拷贝到vector中使用算法库sort排序，然后再拷贝回来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::sort排序int begin2 = clock();lt2.sort();int end2 = clock();//结果输出printf("copy vector sort:%d\\n", end1 - begin1);printf("list sort:%d\\n", end2 - begin2);
}

  在release版本下验证结果如下：

  
  
  

2、list模拟实现

2.1、list中单节点实现：list_node

  1）、list_node 1.0
  list中，链表是带头双向循环链表，我们在之前的数据结构中也曾用C言语实现过相关构造，这里大体逻辑一致，只是融入了C++与类模板等相关内容。
  如下，C中list单个节点node的实现：

typedef int LTDataType;
typedef struct ListNode
{ListNode* prev;//前驱指针ListNode* next;//后续指针LTDataType data;//数据
}LTNode;

  在list中，我们用类将其封装起来，同时，其使用模板参数创建类型：

	//链表中的单个节点:使用了struct，公有；使用模板，类型为Ttemplate<class T>struct list_node{T _data;list_node<T>* _prev;//注意这里前驱指针和后续指针的类型list_node<T>* _next;};

  注意事项：
  1、要注意C++中将结构体升级为类，只是和class相比，其成员默认公有。在后续list中我们将频繁访问节点，故而此处创建使用的是struct。
  2、在这层理解上，对于单个节点list_node，其也有自己的默认成员函数，以及，根据我们的需求，可实现其它函数接口。
  这里，考虑到后续对list的增删查改，我们先手动实现list_node的构造函数：

  2）、list_node 2.0

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

  const T& val = T()
  T()在vector(二)中我们也介绍过，这是缺省参数的使用，此处缺省值为T()，一个T类型的匿名对象，无论是自定义类型还是内置类型，都会调用默认构造。
  const T& 正因为其可以是内置类型，也可以是自定义类型，因此我们加上了const，并使用传引用。
  
  

2.2、list大体框架搭建：list

2.2.1、基本成员变量：_head，构造函数：list

  单个节点以及创建，现在我们来实现list，需要注意list中带有一个哨兵位的头结点：

	template<class T>class list{typedef list_node<T> Node;//私有public://构造函数list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}//其它需要的成员函数//……private:Node* _head;//list中有一个类成员变量：哨兵位的头节点};

  关于list的无参构造，我们要做什么？
  类似于C中实现的ListInit，在那里，我们BuyListNode出一个哨兵位的头结点，并修正其prev、next指向关系。这里，构造函数要起到相同作用。
  

2.2.2、list::push_back (1.0版)

  尾插，从实现逻辑角度，和之前学习的带头双向循环链表大体一致：①找尾；②新增节点；③插入、修改指针间的指向关系。

		void push_back(const T& val)//链表：尾插{//因为已经有哨兵位头节点存在，插入就比较简单，也不必向单链表一样分情况讨论//找尾、插入、关系改变//找尾Node* tail = _head->_prev;//带头双向， _head的前驱指针指向链表尾部//开辟新节点Node* newnode = new Node(val);//注意new的用法，此外，这里new Node(val)是构造//关系更新:_head  ……  tail  newnode_head->prve = newnode;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;}

  
  

2.2、list的迭代器

2.2.1、问题引入与分析

  1）、问题
  如上述尾插，假如我们要遍历测试自己的push_back，则需要遍历链表。那么问题来了，关于list，我们能否像vector、string一样，使用原身指针来作为迭代器呢？

  首先，思考vector、string二者的迭代器，它们的作用是取到对应的头尾数据值，故使用原身类型的指针即可得到所需数据。但在list中，Node*解引用得到的是整个节点，非其中的_data。

  2）、一个演示
  以下为使用标准库中的list实现的迭代器，可以发现从表面看来它与vector、string的使用别无二致，那么说明是底层实现的细节问题。

void mylist_test_01()
{std::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}

  我们可以简略查看一下源码中的实现：

  根据上述代码分析，list中实现了各类运算符重载，来完成迭代器的实现，那么封装后在上层看起来，仍旧没什么区别。
  
  

2.2.2、迭代器基础框架(1.0版本)

2.2.2.1、__list_iterator框架搭建与构造函数

  1）、基本演示
  以下是我们实现的list的迭代器的最基本框架：

	template<class T>struct __list_iterator//list中的迭代器：非原身指针，此处我们是用类来实现的{typedef list_node<T> Node;typedef __list_iterator iterator;//重命名：能在整体上保持一致性Node* _node;//类成员变量：节点__list_iteraotr(Node* node)//迭代器中节点的的构造:_node(node){}};

  1、为什么需要构造函数？
  根据之前vector、string中的内容，我们要实现lsit::begin、list::end。在list中，二者一个为_head->next；另一个为_head，且其返回类型都是迭代器，指向范围为[begin,end)。
  
  

2.2.2.2、list::begin()、list::end()

  二者相关代码如下：注意，begin、end是在list类域中实现的。

	template<class T>class list{public://……typedef __list_iterator iterator;//将迭代器重命名，typedef受制于访问限定符，此处要置为公有iterator begin(){return iterator(_head->next);//匿名对象：构造，并返回一个迭代器类}iterator end(){return iterator(_head);//匿名对象：构造，并返回一个迭代器类}//……private://……};

  
  

2.2.2.3、迭代器中所需运算符重载(1.0版本) ：!=、==、*、->、++、- -

  除了上述的begin、end，在__list_iterator中，我们还需要迭代器实现哪些行为操作？

	list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";//打印对应节点中的数据_data++it;//来到下一个节点}

  回顾一下上述代码，可以看到，该迭代器it还需要完成*、++、!=等各类运算符，由于其是自定义类型，故需要我们自己在__list_iterator中实现。
  
  
  1）、iterator::operator!=

		bool operator!=(const iterator& it)const{return _node != it._node;}

  注意理解：我们需要比较的是两节点是否相等，这在__list_iterator中是比较它的成员变量Node* _node。容易出错的写法：

return *this!=it;//这种写法下，我们比较的是整个迭代器iterator

  
  
  2）、iterator::operator==

		bool operator==(const iterator& it)const{return _node == it._node;}

  
  
  3）、iterator::operator*

		//*it == it.operator*()T& operator*(){return _node->_data;}

  这里需要注意其返回类型：*it我们需要达到什么效果？获取到对应节点中的数据，因此在实现时，我们要返回的是当前节点存储的的有效数据。
  
  相关验证如下：

void mylist_test_01()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";*it *= 2;++it;}cout << endl;for (auto e:lt){cout << e << " ";}cout << endl;
}

  
  4）、iterator::operator->

		T* operator->(){return &(operator*());//&(_node->_data)}

  为什么要实现->运算符重载？
  以下为一个使用举例：我们使用list时，其模板类型不一定是内置类型，对于一些自定义类型，就需要该运算符重载来访问对应元素。（常见于结构体指针中）

struct Pos
{int _a1;int _a2;Pos(int a1=0,int a2=0):_a1(a1),_a2(a2){}
};void mylist_test_02()
{list<Pos> lt;lt.push_back(Pos(2, 3));lt.push_back(Pos(4, 6));list<Pos>::iterator it = lt.begin();while (it != lt.end()){cout << it->_a1 << "," << it->_a2 << endl;++it;}
}

  it->_a1实际上为it->->_a1。只是在语法可读性上做了特殊处理，省略一个->
  如果不用->运算符，访问如下：

cout << (*it)._a1 << ":" << (*it)._a2 << endl;

  
  
  5）、iterator::operator++
  前置自增：

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

  
  后置自增：

		//it++iterator operator++(int){iterator tmp(*this);//拷贝构造：若我们没显示写，编译器自动生成_node = _node->_next;return tmp;}

  
  6）、iterator::operator- -
  前置自减：

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

  
  后置自减：

		//it--iterator operator--(int){iterator tmp(*this);_node = _node->prev;return tmp;}

  
  
  

2.2.3、迭代器基础框架(2.0版本)：引入const的迭代器写法

  根据上述1.0中实现，我们的迭代器只适用于普通类型，若被const修饰，如何实现迭代器？
  例如：下述有一个函数需要List作为参数，如果直接传值传参，代价很大，所以一般而言我们使用的是传引用传参，而传引用传参又通常加上const。此时函数中就需要const迭代器：const_iterator it。

void Func(const list<int>& l)
{list<int>::const_iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;
}

  那么，如何实现呢？
  
  方法一：按照普通迭代器的实现方法，拷贝一份重新实现。
  cosnt迭代器与普通迭代器的一大区别在于一些类型的返回值：例如下述的*lt，普通迭代器可读可写，而const迭代器只能读不能写，因此我们需要控制其返回值。

		T& operator*(){return _node->_data;}const T& operator*(){return _node->_data;}

  然而上述函数只是返回类型不同，并不能构造函数重载，因此我们不能在一个类中同时存在，才有了此处的方法一，重新实现一个const修饰的迭代器类。
  
  
  方法二：考虑到方法一过于繁琐，这里还有另一个解决方案：使用模板参数，让其在实例化时根据迭代器类型自行区分。

	//迭代器实现。原先模板：template<class T>template<class T,class Ref,class Ptr>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T，Ref, Ptr> iterator;//……Ref operator*(){return _node->_data;}Ptr operator->(){return &(operator * ());}//……}

  
  那么在实例化时，就能根据需求来定义这里的class T、class Ref、class Ptr：

		typedef __list_iterator<T, T&, T*> iterator;//普通迭代器typedef __list_iterator<T, const T&, const T*> const_iterator;//const迭代器

  如上述，根据我们实例化时使用的不同的参数类型，就能得到不同的迭代器。
  在list类中整体情况：

	template<class T>class list{typedef list_node<T> Node;//重命名单节点public://迭代器typedef __list_iterator<T, T&, T*> iterator;//普通迭代器typedef __list_iterator<T, const T&, const T*> const_iterator;//const迭代器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;};

  
  
  

2.2.4、迭代器基础框架(3.0版本)：引入反向迭代器

  该部分内容后续补上。
  
  

2.3、list中其它函数完善

2.3.1、list::insert、list::push_back、list::push_front

iterator insert (iterator position, const value_type& val);Return value
An iterator that points to the first of the newly inserted elements.

  可以看到insert中，节点位置也是用迭代器实现的，其返回新增节点位置的迭代器。
  
  相关实现如下:

		iterator insert(iterator pos, const T& val){//保存节点Node* cur = pos._node;Node* prev = cur->_prev;//新增节点Node* newnode = new Node(val);//修改关系: prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;//返回值return iterator(newnode);}

  有了insert，我们就可在此基础上实现push_back、push_front：

		void push_back(const T& val){insert(end(), val);}void Push_front(const T& val){insert(begin(), val);}

  
  

2.3.2、list::erase、list::pop_back、list::pop_front

iterator erase (iterator position);
iterator erase (iterator first, iterator last);

  相关实现如下：

		iterator erase(iterator pos){assert(pos != end());//删除数据有下限，不能无线删除。这里end指向的是尾结点的下一位，即哨兵位的头结点。Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;prev->_next = next;next->_prev = prev;delet cur;return iterator(next);}

  有了erase就可以在pop_front和pop_back中复用：

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

  
  
  

2.4、其它构造函数、析构、拷贝构造相关

  同理，list中拷贝构造我们也有传统写法和现代写法。对于传统写法，即依照给定链表，自己开辟节点空间并逐一赋值。而对于现代写法，则是借助已经实现的构造函数或者对其它函数的复用来完成。
  这里我们模拟实现现代写法。

2.4.1、构造函数:使用迭代区间[first, last)、list::empty_init

  查看库中可得，list中实现了用[first, last)区间中的元素构造list：

template <class InputIterator>  
list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());

  要注意这里对InputIterator模板参数的理解，套用一层模板是为了方便[first, last)构造的类型。
  
  我们可以借助它来完成所需要的拷贝构造的现代写法。但在此之前，需要模拟实现该构造函数：

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

  可以看到这里用了一个empty_init();的函数，其作用是为哨兵位的头结点开辟空间并初始化。后续[first,last)中节点构造是建立在已经拥有哨兵位的头结点的基础上的。
  相关实现如下：

		//开辟空间并初始化哨兵位的头结点void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}//构造函数1.2list(){empty_init();}

  有了它我们顺带可以把无参构造做些修改。
  

2.4.2、拷贝构造、赋值运算符重载、list::swap

  在此基础上我们来实现这两个涉及深拷贝的成员函数。
  拷贝构造：

		//拷贝构造:lt1(lt2)list(const list<T>& lt){list<T>tmp(lt.begin(), lt.end);swap(tmp);}

  
  
  赋值运算符重载：

		//赋值运算符重载:lt1 = lt2list<T>&  operator=(list<T> lt){swap(lt);return *this;}

  
  list中也有一个自己的swap函数：

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

  
  
  相关验证：

void mylist_test_04()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";*it *= 2;++it;}cout << endl;list<int> lt2(lt);//验证拷贝构造for (auto e : lt2){cout << e << " ";}cout << endl;list<int>::iterator pos=lt2.erase(lt2.begin());//验证eraselt2.insert(lt2.end(), 20);//验证insertlist<int>lt3;lt3 = lt2;//验证赋值运算符重载for (auto e : lt3){cout << e << " ";}cout << endl;}

  
  

2.4.3、list::clear、析构

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

  此处使用了一个clear函数，这是因为list中也有该函数，其作用是清除所有有效节点数据。

		//清除list中数据：保留哨兵位的头结点void clear(){iterator it = begin();while (it != end()){it=erase(it);}}