C++STL详解（五）——list类的具体实现

一.本次所需实现的三个类及其成员函数接口

链表首先要有结点，因此我们需要实现一个结点类。

链表要有管理结点的结构，因此我们要有list类来管理结点。

链表中还要有迭代器，而迭代器的底层其实是指针。但是我们现有的结点类无法完成迭代器的行为，因此我们还需要实现一个迭代器类。

因此，我们要实现的三个类分别是：结点类、迭代器类、链表类。

namespace trousers
{template<class T>struct _list_node{//初始化_list_node();//变量T data;//数值域_list_node<T>* prev;//前驱指针_list_node<T>* next;//后继指针};//迭代器    //由于list_node无法遍历和支持迭代器，因此我们需要手动实现一个迭代器版本//Ref和Ptr分别代表引用和指针类型，我们可以用一个类模板重载出两个迭代器版本。（迭代器里面需要用到指针和引用），一个模板的话不够用template<class T, class Ref, class Ptr>struct _list_iterator{typedef _list_node<T> node;typedef _list_iterator<T,Ref,Ptr> self;self operator++();self operator++(int);self operator--();self operator--(int);Ref operator*();Ptr operator->();//_pnode->_val  operator->(*this)->_valself operator==(const self& t)constself operator!=(const self& t)const//变量node* _pnode;};//链表template <class T>class list{public:typedef _list_node<T> node;typedef _list_iterator<T,T&,T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;//默认成员函数list();list(const list<T>& lt);list<T>& operator=(const list<T>& lt);~list();//迭代器相关函数iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;//访问容器相关函数T& front();T& back();const T& front() const;const T& back() const;//插入、删除函数void insert(iterator pos, const T& x);iterator erase(iterator pos);void push_back(const T& x);void pop_back();void push_front(const T& x);void pop_front();//其他函数size_t size() const;void resize(size_t n, const T& val = T());void clear();bool empty() const;void swap(list<T>& lt);//私有变量private:node* _head;//指向哨兵位};
}

二.结点类的模拟实现

list的底层其实是一个带头双向循环链表。

因此，我们需要实现的结点类中需要的成员为：数据、前一个结点的指针、后一个结点的指针。

对于该类而言，我们不需要在类中完成任何行为，因此我们仅仅只需要实现一个构造函数即可。而该类由于都是内置成员，因此我们的析构函数可以由编译器生成。

2.1结点类的构造函数

结点类的构造函数实现起来是比较简单的，我们仅仅需要将val置想要的值，并将两个指针置空即可。

		_list_node(const T& data=T()):_data(),_prev(nullptr),_next(nullptr){}

三.迭代器类的模拟实现

3.1迭代器的设计思路

在实现了结点类之后，我们就要开始实现迭代器类了。

由于我们无法通过只有一个参数的类模板实现const和非const的两个迭代器

因此我们这里的类模板有三个参数。

	template<class T, class Ref, class Ptr>

其中的Ref表示引用，Ptr表示解引用。 

3.2迭代器类存在的意义

在之前实现string和vector的时候，我们都不需要实现一个迭代器类，为什么实现list的时候就需要实现一个迭代器类了呢？

这是因为，string和vector对象都将数据存储在了一块连续的内存空间，我们通过指针操纵空间从而完成自增、自减、解引用等操作，然后就可以对数据进行一系列的操作，因此string和vector当中的迭代器就是原生的指针。

 但是，对于list而言，各个结点在内存中的分布并不连续，因此我们不能通过对结点的自增自减等操作来完成迭代器的行为。

而迭代存在的意义就是，让使用者不必关心底层的实现，可以用简单统一的方式对容器内的数据进行访问。

 既然list的结点指针的行为不满足迭代器的定义，那么我们就需要对结点指针进行封装，对结点指针的各个运算符进行重载，使得其支持像vector、string中的迭代器一样的操作。

举个例子，我们在用list的自增行为时，实际上是执行了p=p->next语句。

总结：list的迭代器类，实际上只是对结点的指针进行了封装，并对其各个操作符进行了重载，使得结点指针的各种行为看起来和普通指针一样。

3.3构造函数

迭代器类的构造函数实际上是对结点指针进行了封装而已，其成员变量只有一个结点的指针，因此我们的构造函数直接根据所给的结点指针构造出一个迭代器对象即可。

		_list_iterator(node* pnode):_pnode(pnode){}

3.4++运算符的重载

3.4.1前置++操作符

对于前置++操作符，我们的实现思路非常简单，直接将结点指针指向next，然后返回自增后的结果即可。

		self operator++(){_pnode = _pnode->_next;return *this;}

3.4.2后置++操作符

对于后置++操作符，我们采取使用一个临时变量记录该结点的方式，对结点指针完成自增，并返回临时变量即可。

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

3.5--运算符的重载

--操作符的逻辑和++操作符的逻辑基本上是一样的，只不过是将自身修改为prev而不是next。

		self operator--(){_pnode = _pnode->_prev;return *this;}self operator--(int){self tmp(*this);_pnode = _pnode->_prev;return tmp;}

3.6==运算符的重载

在使用迭代器遍历时，难免会比较两个迭代器是否相同，因此我们还需要实现==操作符。

而两个迭代器是否相同，实际上就是判断这两个迭代器是不是同一个位置上的迭代器，因此，我们只需要比较这两个迭代器的地址即可。

		bool operator==(const self& t)const{return _pnode == t._pnode;}

3.7!=运算符的重载

！=操作符和==操作符的作用相反，我们要判断的是这两个迭代器的地址是不是不同。

		bool operator!=(const self& t)const{return _pnode != t._pnode;}

3.8*运算符的重载

当我们使用*操作符时，其实就是想要得到这个地址的数据，因此我们直接返回当前指针数据所指向的数据即可，但由于我们可能会通过解引用修改数据，因此我们这里可以返回引用。

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

3.9->运算符的重载

在一些场景下，我们可能还会使用到->操作符。

譬如如下场景：

当list容器内的每个结点存储的是自定义类型时，那么当我们拿到一个位置的迭代器，我们可能还会通过->操作符来访问该类型内部的成员。

如下例：

list<vector> d;
vector<int> v1 = { 1,2,3 };
vector<int> v2 = { 4,5,6 };
vector<int> v3 (3,5);
d.push_back(v1);
d.push_back(v2);
d.push_back(v3);
list <vector>::iterator pos = it.begin();
cout << pos->size() << endl;

因此，有些情况下我们会使用到->操作符。

对于->操作符的重载，我们直接返回结点当中所存储数据的地址即可。

		Ptr operator->()//_pnode->_val  operator->(this)->_val{//(*this)->_data;return &(_node->_data);}

说到这里，你可能会觉得有些不对，按照这种重载方式的话，我们似乎需要两个->才能调到我们想要的数据，也就是这样：

因为（）内部的this是被省略的，因此我们实际上写应该是这样的

但是一个地方出现两个箭头的可读性有些过于差劲了，因此编译器在这里做了一些特殊的处理，省略了一个箭头，也就是我们所写的版本。

四.list的模拟实现

4.1默认成员函数

4.1.1构造函数

list是一个带头双向循环链表，因此在构造一个list对象时，直接申请一个头节点并让前驱指针和后继指针都指向自己即可。

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

4.2.2拷贝构造函数

拷贝构造函数，我们需要先申请一个结点，然后申请一个头结点，之后我们再将原list链表一个一个通过尾插拷贝过去即可。

		list(const list<T>& lt){_head = new node;_head->_next = _head;_head->_prev = _head;for (const auto& e : lt){push_back(e);}}

4.2.3赋值运算符重载函数

赋值运算符重载和拷贝构造的实现方式是类似的，我们可以先将被赋值的链表清空然后一个一个通过尾插拷贝过去。

		list<T>& operator=(const list<T>& lt){if (this != &lt)//防止自己给自己赋值，以避免性能浪费{clear();for (const auto& e : lt){push_back(e);}}return *this;}

但是这种写法过于繁琐，我们也可以换一种思路，我们不采取引用传参，那么我们将会传入一个形参，之后我们和形参进行交换即可完成任务，而当我们的函数运行结束后还会自动销毁掉形参。

		list<T>& operator=(const list<T> lt)//编译器接受右值时自动调用其拷贝构造函数，构造出形参。{swap(lt);return *this;}

 4.2.4析构函数

对于析构函数，我们首先使用clear清理一下容器内的数据，然后将头结点释放，之后再将指针置空即可。

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

五.迭代器相关函数

begin和end

begin是返回第一个有效数据的迭代器，因此我们要返回头节点的下一个结点

		iterator begin(){return iterator(_head->_next);}

这里需要大家注意的是，我们要返回迭代器而不是结点指针，因此我们需要用迭代器的构造函数构造出指向同一块空间的迭代器类型的匿名变量用于返回。 

end是返回最后一个有效数据的后一个数据的迭代器，在双向循环链表中要返回的是头结点

		iterator end(){return iterator(_head);}

当然，除了这两个之外，我们还需要实现两个const版本的函数

		const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}

 六.访问容器相关函数

6.1front和back

front返回第一个有效数据，back返回最后一个有效数据，因此我们在实现front和back函数时，直接返回第一个有效数据的引用和最后一个有效数据的引用即可。

		T& front(){return *begin();}T& back(){return *(--end());}

除此之外，我们还需要重载一对用于const对象的front和back函数。

		const T& front() const{return *begin();//我们已经重载了解引用}const T& back() const{return *(--end());}

6.2插入、删除函数

6.2.1insert

对于insert函数，我们是这样写的：

1. 首先检查一下插入位置的合法性。
2. 然后用要插入的数据新建一个结点。
3. 然后记录下要插入位置处结点的指针
4. 之后建立节点之间的双向关系

		void insert(iterator pos, const T& x){assert(pos._pnode);node* newnode = new node(x);node* cur = pos._pnode;node* prev = cur->_prev;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;}

6.2.2erase

erase可以删除所给的迭代器位置的结点。

实现思路为：

1. 先根据迭代器得到该位置处的结点cur
2. 然后通过cur找到prev和next指针
3. 之后删掉cur，并建立prev和next之间的双向关系。
4. 返回next位置

		iterator erase(iterator pos){assert(pos._pnode);assert(pos != end());node* cur = pos._pnode;node* prev = cur->_prev;node* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;return iterator(next);}

6.2.3对头尾的插入和删除函数

我们直接复用insert和erase即可。

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

七.其他函数

7.1size

对于size函数，我们可以通过迭代器的遍历获取个数。

		size_t size() const{size_t sz = 0;const_iterator it = begin();while (it != end()){it++;sz++;}return sz;}

除了这个方法外，还有一个方法可以获取到个数。

我们可以多设置一个私有成员size，在插入逻辑中，每插入一个则size+1，在删除逻辑中，每删除一个，则size-1。这样也可以获取到size 的个数。

7.2resize

resize函数规则：

1. 若当前容器的size小于所给n，则尾插结点，直到size等于n
2. 若当前容器的size大于所给n，则只保留前n个有效数据。

那么，如何实现resize函数呢？

1. 首先，我们定义一个len表示链表的长度
2. 遍历到结尾后，比较len和n的大小
3. 若len较大，则删除掉多余的结点
4. 若len较小，则尾插数值为x的结点。

		void resize(size_t n, const T& val = T()){iterator it = begin();size_t len = 0;while (it != end()){it++;len++;}while (len < n){push_back(val);len++;}while (len > n){pop_back();len--;}}

7.3clear

对于clear函数，我们需要做的是清空链表的有效数据。

因此我们逐个删除掉链表的结点，只保留头节点即可。

		void clear(){iterator it=begin();while (it != begin()){it = erase(it);//防止迭代器失效}}

7.4empty

empty函数是判空的，我们有很多种方法判断链表是否为空。

这里我们通过判断该容器的begin函数和end函数所返回的迭代器是否相同来进行判断。（如果相同，则代表只有一个头结点）

		bool empty() const{return begin() == end();}

7.5swap

swap函数用于交换两个容器，在list容器当中存储的实际上只有头结点的指针，因此我们只要交换一下头节点的指针即可。

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

注意点：在此处调用的swap是库中的swap，我们在swap前面加上域作用限定符，即可告诉编译器优先在全局范围内寻找swap函数。