C++STL（六）——list模拟

---

本次所需实现的三个类

一、结点类的模拟实现

list类是由结点类和迭代器类组成

我们经常说list在底层实现时就是一个链表，更准确来说，list实际上是一个带头双向循环链表。

因此，我们若要实现list，则首先需要实现一个结点类。而一个结点需要存储的信息有：数据、前一个结点的地址、后一个结点的地址，于是该结点类的成员变量也就出来了（数据、前驱指针、后继指针）。

而对于该结点类的成员函数来说，我们只需实现一个构造函数即可。因为该结点类只需要根据数据来构造一个结点即可，而结点的释放则由list的析构函数来完成。

构造函数

template<class T>				//由于该list可能是任何类型则使用模板类
struct list_node				//存放结点成员变量
{list_node<T>* _prev;list_node<T>* _next;T _val;list_node(const T& val = T())		//缺省值初始化，T不一定是内置类型所以不能直接给0:_prev(nullptr), _next(nullptr), _val(val){}
};

注意： 若构造结点时没有传入数据，则默认以list容器所存储类型的默认构造函数所构造出来的值为传入数据。

二、迭代器类的模拟实现

引入：

list迭代器是一个自定义类型，内部成员是结点指针（内置类型），我们本身想要的就是结点指针，结点指针就可以做迭代器，它不能像原生指针（如：vector、string）一样地址是连续的而list地址不是，因为底层结构的差异，所以用一个类封装结点指针，然后重载运算符后就可以像内置类型一样访问。

为什么有迭代器类

在学习string和vector时都没有说专门要实现一个迭代器类，为什么实现list的时候就需要实现一个迭代器类呢？

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

但是对于list来说，其各节点在内存中位置可能不都是连续的，大多情况下都是随机的，我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作，需找到下一个结点才能访问。
迭代器的意义是让使用者可以不必关心容器的底层实现，可以用简单统一的方式对容器内的数据进行访问。

既然list的结点指针的行为不满足迭代器定义，那么我们可以对这个结点指针进行封装，对结点指针的各种运算符操作进行重载，使得我们可以用和string和vector当中的迭代器一样的方式使用list当中的迭代器。比如使用list当中的迭代器进行自增操作时，实际上执行了node = node->next语句。

list迭代器类实际上就是对结点指针进行了封装，对其各种运算符进行了重载，使得结点指针的各种行为在使用者角度看起来和普通指针一样。

迭代器类的模板参数说明

list迭代器类的模板参数列表当中有三个模板参数

template<class T, class Ref, class Ptr>

在list的模拟实现当中，我们typedef重命名了两个迭代器类型，普通迭代器和const迭代器。

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;

迭代器类的模板参数列表当中的Ref和Ptr分别代表的是引用类型和指针类型。

构造函数

迭代器类实际上就是对结点指针进行了封装，其成员变量就只有一个，那就是结点指针，其构造函数直接根据所给结点指针构造一个迭代器对象。

Node* _node;__list_iterator(Node* node):_node(node)
{}

++运算符的重载

当然也分为前置和后置++

self& operator++()			//返回类型还是迭代器
{_node = _node->_next;					//下一个位置return *this;
}self operator++(int)
{self<T> 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;
}

==和!=运算符的重载

当使用==运算符比较两个迭代器时，实际上想知道的是这两个迭代器是否是同一个位置的迭代器，判断这两个迭代器当中的结点指针的指向是否相同即可。!=运算符则相反。

//通过结点的指针比较，两数据比较时end返回的数据具有常性要加const
bool operator!=(const self& it)
{return _node != it._node;
}
bool operator==(const self& it)
{return _node == it._node;
}

*运算符的重载

使用解引用操作符时，是想得到该位置的数据内容。因此，直接返回当前结点指针所指结点的数据即可，但是这里需要使用引用返回，因为解引用后可能需要对数据进行修改。

Ref operator*()								//出了作用域还在可以引用返回
{return _node->_val;						//结点指针的数据
}

->运算符的重载

有些情景下我们使用迭代器的时候可能会用到->运算符。

void test2()
{struct A{A(int a=0,int b=0):_a(a),_b(b){}int _a;int _b;};ling::list<A> lt;lt.push_back(A(1,1));lt.push_back(A(2,2));lt.push_back(A(3,3));lt.push_back(A(4,4));ling::list<A>::iterator it = lt.begin();while (it != lt.end()){//cout << *it << " ";					//遍历对象是自定义类型要重载流插入才可以打印//都能实现遍历//cout << (*it)._a << " "<<(*it)._b << endl;	cout << it->_a << " " << it->_b << endl;++it;}cout << endl;
}

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

Ptr operator->()
{return &_node->_val;
}

引入模板第二个和第三个参数

如上例子：

三、list的模拟实现

3.1 默认成员函数

list是一个带头双向循环链表，在构造一个list对象时，申请一个头结点，并让其前驱指针和后继指针都指向自己

由于有时容易忘记写上显示实例化模板参数才构成类型

typedef list_node<T> node;				//重命名一下

构造函数

list()							//初始化构成双链表
{_head = new Node;			//给头节点申请空间head->_prev = head;			//前后指针指向自己head->_next = head;
}

拷贝构造函数

拷贝构造函数就是根据所给list容器，拷贝构造出一个对象。对于拷贝构造函数，先申请一个头结点，并让其前驱指针和后继指针都指向自己，然后将所给容器当中的数据，通过遍历的方式一个个尾插到新构造的容器后面。

//拷贝构造函数
list(const list<T>& lt)
{_head = new node; 		//申请一个头结点_head->_next = _head; 	//头结点的后继指针指向自己_head->_prev = _head; 	//头结点的前驱指针指向自己for (const auto& e : lt)			//记得引用{push_back(e);		 //将容器lt当中的数据一个个尾插到新构造的容器后面}
}

赋值运算符重载函数

一般两种写法

//传统写法
list<T>& operator=(const list<T>& lt)
{if (this != &lt) 			//避免自己给自己赋值{clear(); 				//清空容器for (const auto& e : lt){push_back(e); 		//将容器lt当中的数据一个个尾插到链表后面}}return *this; 				//支持连续赋值
}//现代写法
list<T>& operator=(list<T> lt) //编译器接收右值的时候自动调用其拷贝构造函数
{swap(lt); 					//交换这两个对象return *this; 				//支持连续赋值
}

析构函数

对象进行析构时，首先调用clear函数清理容器当中的数据，然后将头结点释放，最后将头指针置空

//析构函数
~list()
{clear(); 			//清理容器delete _head; 		//释放头结点_head = nullptr; 	//头指针置空
}

3.2 迭代器相关函数

begin和end

begin函数返回的是第一个有效数据的迭代器，end函数返回的是最后一个有效数据的下一个位置的迭代器。

list带头双向循环链表，第一个有效数据的迭代器就是使用头结点的下一个结点的地址构造出来的迭代器，最后一个有效数据的下一个位置的迭代器就是使用头结点的地址构造出来的迭代器。（最后一个结点的下一个结点就是头结点）

//单参数的构造函数支持隐式类型转换,两种写法都可以都是生成匿名对象
iterator begin()					
{return _head->_next;//return iterator(_head->_next);
}
iterator end()
{return _head;//return iterator(_head);
}

3.3 访问容器相关函数

front和back

分别用于获取第一个有效数据和最后一个有效数据，因此，实现front和back函数时，直接返回第一个有效数据和最后一个有效数据的引用即可。

T& front()
{return *begin(); 		//返回第一个有效数据的引用
}
T& back()
{return *(--end()); 		//返回最后一个有效数据的引用
}//不可修改
const T& front() const
{return *begin(); 		//返回第一个有效数据的const引用
}
const T& back() const
{return *(--end()); 		//返回最后一个有效数据的const引用
}

3.4 插入、删除函数

insert和erase

当然还是任意位置插入和删除，由于会迭代器失效所以有返回值

//插入
iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;
}//删除
iterator erase(iterator pos)
{assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return next;
}

有了这对增删函数就可以复用在其它增删的函数身上了

push_back和pop_back

分别对应尾插、尾删

//尾插
void push_back(const T& x)
{Node* tail = _head->prev;				//找到尾Node* newnode = new Node(x);			//调用结点的构造函数//更新尾结点tail->_next = newnode;newnode->_prev = tail;_head->_prev = newnode;newnode->_next = _head;//可直接复用insertinsert(end(),x);
}//尾删
void pop_back()
{erase(--end());
}

push_front和pop_front

//头插
void push_front(const T& x)
{insert(begin(), x);
}//头删
void pop_front()
{erase(begin());
}

3.5 其他函数

size

获取当前容器当中的有效数据个数，因为list是链表，所以只能通过遍历的方式逐个统计有效数据的个数。

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

clear

用于清空容器，通过遍历的方式，逐个删除结点，只保留头结点

void clear()
{iterator it = begin();while (it != end()){it = erase(it);}
}

empty

用于判断容器是否为空，直接判断该容器的begin函数和end函数所返回的迭代器，是否是同一个位置的迭代器即可。（此时说明容器当中只有一个头结点）

bool empty() const
{return begin() == end(); //判断是否只有头结点
}

swap

用于交换两个容器，list容器当中存储的实际上就只有链表的头指针，将这两个容器当中的头指针交换即可。

void swap(list<T>& lt)
{std::swap(_head, lt._head); 		//交换两个容器当中的头指针即可
}

总结

由于list类不一定只接收一个类型如：内置类型（int、double），自定义类型，所以三个类都使用了模板。
类名+模板参数才构成类型容易忘记，往往typedef重命名一下它们也更方便使用。