【STL】list模拟实现

---

一、接口大框架函数声明速览

#pragma oncenamespace JRH
{// list当中的结点template<class T>struct _list_node{// 成员变量T _val;    // 数据域_list_node<T>* _prev;  // 前驱指针_list_node<T>* _next;  // 后继指针// 成员函数_list_node(const T& val = T()); // 构造函数};// list迭代器template<class T, class Ref, class Ptr>struct _list_iterator{typedef _list_node<T> node;typedef _list_iterator<T, Ref, Ptr> self;// 成员变量node* _pnode; // 指向结点的指针// 成员函数_list_iterator(node* pnode); // 构造函数// 运算符重载的各类函数self operator++(); // 前置self operator--();self operator++(int); // 后置self operator--(int);bool operator==(const self& s) const;bool operator!=(const self& s) const;Ref operator*();Ptr operator->();};// listtemplate<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; // const迭代器public:// 成员函数// 1、默认成员函数list(); // 构造list(const list<T>& ltnode); // 拷贝构造list<T>& operator=(const list<T>& ltnode); // 拷贝赋值~list(); // 析构// 2、迭代器相对应函数iterator begin(); // 开始iterator end(); // 结尾const_iterator begin() const; // const开始const_iterator end() const; // const结尾// 3、访问容器T& front(); // 访问头T& back(); // 访问尾const T& front(); // const访问头const T& back(); // const访问尾// 4、插入、删除函数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(); // 头删// 5、其他函数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* _phead; // 指向头结点的指针};
}

二、结点类的模拟实现

list是一个带头双向循环链表，我们如下图所示：

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

构造节点只需要构造一个节点即可（利用构造函数），释放结点只需要析构结点即可（利用析构函数）。

1、构造函数

结点类的构造函数直接根据所给数据构造一个结点即可，构造出来的结点的数据域存储的就是所给数据，而前驱指针和后继指针均初始化为空指针即可。而若构造结点时未传入数据，则默认以list容器所存储类型的默认构造函数所构造出来的值为传入数据。

		_list_node(const T& val = T()) // 构造函数:_val(val),_prev(nullptr),_next(nullptr){}

三、迭代器类的模拟实现

1、迭代器类存在的意义

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

但是对于list来说，其各个结点在内存当中的位置是随机的，并不是连续的，我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作。

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

既然list的结点指针的行为不满足迭代器定义，那么我们可以对这个结点指针进行封装，对结点指针的各种运算符操作进行重载，使得我们可以用和string和vector当中的迭代器一样的方式使用list当中的迭代器。list迭代器类，实际上就是对结点指针进行了封装，对其各种运算符进行了重载，使得结点指针的各种行为看起来和普通指针一样。

2、迭代器类的模板参数说明

这里我们所实现的迭代器类的模板参数列表当中为什么有三个模板参数？

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; // const迭代器

迭代器类的模板参数列表当中的Ref和Ptr分别代表的是引用类型和指针类型。即当我们使用普通迭代器时，编译器就会实例化出一个普通迭代器对象；当我们使用const迭代器时，编译器就会实例化出一个const迭代器对象。说白了就是为了区分普通迭代器和const迭代器的。

3、构造函数

我们构造函数其实只有一个结点指针，其构造函数直接根据所给结点指针构造一个迭代器对象即可。

		_list_iterator(node* pnode) // 构造函数:_pnode(pnode){}

4、++运算符的重载（前置和后置）

self的定义如下：

typedef _list_iterator<T, Ref, Ptr> self;

（1）前置++

先让结点指针指向后一个结点，然后再返回“自增”后的结点指针即可。

		self operator++() // 前置{_pnode = _pnode->_next; // 先让结点指针指向后一个节点return *this; // 返回自增后的结点指针}

（2）后置++

先记录当前结点指针的指向，然后让结点指针指向后一个结点，最后返回“自增”前的结点指针即可。

		self operator++(int) // 后置{self tmp(*this); // 记录当前指针的指向_pnode = _pnode->_next; // 让结点指针指向后一个节点return tmp; // 返回自增前的结点指针}

5、–运算符的重载（前置和后置）

（1）前置–

先让结点指针指向前一个结点，然后再返回“自减”后的结点指针即可。

		self operator--(){_pnode = _pnode->_prev; // 先让结点指针指向前一个节点return *this; // 返回自减后的结点指针}

（2）后置–

先记录当前结点指针的指向，然后让结点指针指向前一个结点，最后返回“自减”前的结点指针即可。

		self operator--(int){self tmp(*this); // 记录当前指针指向_pnode = _pnode->_prev; // 让结点指针指向前一个节点return tmp; // 返回自减前的结点指针}

5、==运算符的重载

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

		bool operator==(const self& s) const{return _pnode == s._pnode; // 判断两个结点指针指向是否相同}

6、!=运算符的重载

!=运算符刚好和==运算符的作用相反，我们判断这两个迭代器当中的结点指针的指向是否不同即可。

		bool operator!=(const self& s) const{return _pnode != s._pnode; // 判断两个结点指针指向是否不同}

7、*运算符的重载

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

		Ref operator*(){return _pnode->_val; // 返回结点指针所指结点的数据}

8、->运算符的重载

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

为什么会有这个->运算符重载呢？原因是因为我们之前写过一个日期类，我们用日期类的时候是里面有很多自定义的变量，所以就需要我们进行箭头的指向，我们如下代码：当我们拿到一个位置的迭代器时，我们可能会使用->运算符访问Date的成员：

// main.cclist<Date> lt;Date d1(2021, 8, 10);Date d2(1980, 4, 3);Date d3(1931, 6, 29);lt.push_back(d1);lt.push_back(d2);lt.push_back(d3);list<Date>::iterator pos = lt.begin();cout << pos->_year << endl; //输出第一个日期的年份

所以我们只需要返回地址即可，我们写如下代码：

		Ptr operator->(){return &_pnode->_val; // 返回结点指针所指结点的数据的地址}

但肯定是有缺陷的，按照这种重载方式的话，这里使用迭代器访问日期类当中的成员变量时不是应该用两个->吗？

这里本来是应该有两个->的，第一个箭头是pos ->去调用重载的operator->返回Date* 的指针，第二个箭头是Date* 的指针去访问对象当中的成员变量_year。但是一个地方出现两个箭头，程序的可读性太差了，所以编译器做了特殊识别处理，为了增加程序的可读性，省略了一个箭头。

四、list的模拟实现

1、默认成员函数

（1）构造函数

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

		list() // 构造{_phead = new node; // 申请一个头结点_phead->_next = _phead; // 后继指向自己_phead->_prev = _phead; // 前驱指向自己}

（2）拷贝构造函数

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

		list(const list<T>& ltnode) // 拷贝构造lt2(lt1){_phead = new node; // 创建一个新的头结点_phead->_next = _phead; // head后继结点指向本身_phead->_prev = _phead; // head前驱结点指向本身for (const auto& e : ltnode){push_back(e); // 将容器ltnode中的值一个个push_back到_head结点后}}

（3）赋值运算符重载函数

两种写法：

i、写法一：老式写法

先调用clear函数将原容器清空，然后将容器lt当中的数据，通过遍历的方式一个个尾插到清空后的容器当中即可。

		// 1、老式写法list<T>& operator=(const list<T>& ltnode) // 拷贝赋值{if (this != &ltnode) // 防止自己给自己拷贝{clear(); // 先清空容器for (auto& e : ltnode){push_back(e); // 将ltnode中数据全部尾插到清空的容器中}return *this; // 支持连续赋值}}

ii、写法二：现代写法

首先利用编译器机制，故意不使用引用接收参数，通过编译器自动调用list的拷贝构造函数构造出来一个list对象，然后调用swap函数将原容器与该list对象进行交换即可。

		// 2、现代写法list<T>& operator=(const list<T>& ltnode){swap(ltnode); // 交换这两个对象return *this; // 支持连续赋值}

（4）析构函数

首先调用clear函数清理容器当中的数据，然后将头结点释放，最后将头指针置空即可。

		~list() // 析构{clear(); // 清空容器delete _phead; // 删除申请的节点_phead = nullptr; // 置空}

2、迭代器相关的函数

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

（1）begin和end

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

		iterator begin() // 开始{return iterator(_phead->_next); // 头结点的下一个结点}iterator end() // 结尾{return iterator(_phead); // 头结点}const_iterator begin() const // const开始{return const_iterator(_phead->_next); // 头结点的下一个结点}const_iterator end() const // const结尾{return const_iterator(_phead); // 头结点}

3、访问容器相关函数

（1）front和back

front和back函数分别用于获取第一个有效数据和最后一个有效数据，因此，实现front和back函数时，直接返回第一个有效数据和最后一个有效数据的引用即可。重载一对用于const对象的front函数和back函数，因为const对象调用front和back函数后所得到的数据不能被修改。

		T& front() // 访问头{return *begin(); // 返回第一个有效数据的引用}T& back() // 访问尾{return *(--end()); // 返回头结点的引用}const T& front() const // const访问头{return *begin(); // 返回第一个有效数据的const引用}const T& back() const // const访问尾{return *(--end()); // 返回头结点的const引用}

4、插入、删除函数

（1）插入insert函数

insert函数可以在所给迭代器之前插入一个新结点。

步骤为：先有cur的结点，其_prev是prev结点，再创建一个新结点，新结点的_next是cur，cur的_prev是新结点。prev的_next是新结点，新结点的-prev是prev结点。

		void insert(iterator pos, const T& x) // 插入{assert(pos._pnode); // 确保合法性node* cur = pos._pnode; // cur结点为当前所处的结点位置node* prev = cur->_prev; // prev结点为当前结点的前一个结点node* newnode = new node(x);// 链接newnode->_next = cur;cur->_prev = newnode;prev->_next = newnode;newnode->_prev = prev;}

（2）删除erase函数

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

		iterator erase(iterator pos) // 删除{assert(pos._pnode); // 检测合法性assert(pos != end()); // 不能删除头结点node* cur = pos._pnode; // cur结点为当前结点node* prev = cur->_prev; // prev结点为前一个结点node* next = cur->_next; // next结点为后一个结点delete cur; // 删除当前节点// 建立关系prev->_next = next;next->_prev = prev;return iterator(next); // 返回所给迭代器pos的下一个迭代器}

5、push_back和pop_back

push_back和pop_back函数分别用于list的尾插和尾删，在已经实现了insert和erase函数的情况下，我们可以通过复用函数来实现push_back和pop_back函数。push_back函数就是在头结点前插入结点，而pop_back就是删除头结点的前一个结点。

		void push_back(const T& x) // 尾插{insert(end(), x); // 头结点前插入结点}void pop_back() // 尾删{erase(--end()); // 删除头结点的前一个节点}

6、push_front和pop_front

当然，用于头插和头删的push_front和pop_front函数也可以复用insert和erase函数来实现。
push_front函数就是在第一个有效结点前插入结点，而pop_front就是删除第一个有效结点。

		void push_front(const T& x)  // 头插{insert(begin(), x); // 在第一个有效结点前插入结点}void pop_front() // 头删{erase(begin()); // 删除第一个有效节点}

7、其他函数

（1）size

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

		size_t size() const // 容量大小{int sz = 0; // 统计的有效容量大小个数const_iterator it = begin(); // 开头元素while (it != end()) // 通过遍历累加{++sz;++it;}return sz; // 返回有效大小的个数}

（2）resize

函数规则：

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

实现resize函数时，不要直接调用size函数获取当前容器的有效数据个数，因为当你调用size函数后就已经遍历了一次容器了，而如果结果是size大于n，那么还需要遍历容器，找到第n个有效结点并释放之后的结点。

这里实现resize的方法是，设置一个变量len，用于记录当前所遍历的数据个数，然后开始变量容器，在遍历过程中：

1. 当len大于或是等于n时遍历结束，此时说明该结点后的结点都应该被释放，将之后的结点释放即可。
2. 当容器遍历完毕时遍历结束，此时说明容器当中的有效数据个数小于n，则需要尾插结点，直到容器当中的有效数据个数为n时停止尾插即可。

		void resize(size_t n, const T& val = T()) // 扩容{iterator it = begin(); // 获取第一个有效数据的迭代器size_t len = 0; // 记录当前所遍历的数据个数while (len < n && it != end()){len++;it++;}if (len == n) // 说明容器当中的有效数据个数大于或是等于n{while (it != end()) // 只保留前n个数据{it = erase(it); // 每次删除后接收下一个数据的迭代器}}else // 说明容器当中的有效数据个数小于n{while (len < n) // 尾插数据为val的结点，直到容器当中的有效数据个数为n{push_back(val);len++;}}}

（3）clear

clear函数用于清空容器，我们通过遍历的方式，逐个删除结点，只保留头结点即可。

		void clear() // 清空{iterator it = begin();while (it != end()) // 逐个删除{it = erase(it);}}

（4）empty

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

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

（5）swap

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

		void swap(list<T>& lt) // 交换{std::swap(_phead, lt._phead);}

（6）Print函数

用来进行验证的代码。

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

五、代码汇总

main.cc

#include"stl_list.h"int main()
{JRH::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);JRH::Print(lt);return 0;
}

stl_list.h

#pragma once
#include<iostream>
#include<cassert>namespace JRH
{// list当中的结点template<class T>struct _list_node{// 成员变量T _val;    // 数据域_list_node<T>* _prev;  // 前驱指针_list_node<T>* _next;  // 后继指针// 成员函数_list_node(const T& val = T()) // 构造函数:_val(val),_prev(nullptr),_next(nullptr){}};// list迭代器template<class T, class Ref, class Ptr>struct _list_iterator{typedef _list_node<T> node;typedef _list_iterator<T, Ref, Ptr> self;// 成员变量node* _pnode; // 指向结点的指针// 成员函数_list_iterator(node* pnode) // 构造函数:_pnode(pnode){}// 运算符重载的各类函数self operator++() // 前置{_pnode = _pnode->_next; // 先让结点指针指向后一个节点return *this; // 返回自增后的结点指针}self operator--(){_pnode = _pnode->_prev; // 先让结点指针指向前一个节点return *this; // 返回自减后的结点指针}self operator++(int) // 后置{self tmp(*this); // 记录当前指针的指向_pnode = _pnode->_next; // 让结点指针指向后一个节点return tmp; // 返回自增前的结点指针}self operator--(int){self tmp(*this); // 记录当前指针指向_pnode = _pnode->_prev; // 让结点指针指向前一个节点return tmp; // 返回自减前的结点指针}bool operator==(const self& s) const{return _pnode == s._pnode; // 判断两个结点指针指向是否相同}bool operator!=(const self& s) const{return _pnode != s._pnode; // 判断两个结点指针指向是否不同}Ref operator*(){return _pnode->_val; // 返回结点指针所指结点的数据}Ptr operator->(){return &_pnode->_val; // 返回结点指针所指结点的数据的地址}};// listtemplate<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; // const迭代器public:// 成员函数// 1、默认成员函数list() // 构造{_phead = new node; // 申请一个头结点_phead->_next = _phead; // 后继指向自己_phead->_prev = _phead; // 前驱指向自己}list(const list<T>& ltnode) // 拷贝构造lt2(lt1){_phead = new node; // 创建一个新的头结点_phead->_next = _phead; // head后继结点指向本身_phead->_prev = _phead; // head前驱结点指向本身for (const auto& e : ltnode){push_back(e); // 将容器ltnode中的值一个个push_back到_head结点后}}// 1、老式写法list<T>& operator=(const list<T>& ltnode) // 拷贝赋值{if (this != &ltnode) // 防止自己给自己拷贝{clear(); // 先清空容器for (auto& e : ltnode){push_back(e); // 将ltnode中数据全部尾插到清空的容器中}return *this; // 支持连续赋值}} 2、现代写法//list<T>& operator=(const list<T>& ltnode)//{//	swap(ltnode); // 交换这两个对象//	return *this; // 支持连续赋值//}~list() // 析构{clear(); // 清空容器delete _phead; // 删除申请的节点_phead = nullptr; // 置空}// 2、迭代器相对应函数iterator begin() // 开始{return iterator(_phead->_next); // 头结点的下一个结点}iterator end() // 结尾{return iterator(_phead); // 头结点}const_iterator begin() const // const开始{return const_iterator(_phead->_next); // 头结点的下一个结点}const_iterator end() const // const结尾{return const_iterator(_phead); // 头结点}// 3、访问容器T& front() // 访问头{return *begin(); // 返回第一个有效数据的引用}T& back() // 访问尾{return *(--end()); // 返回头结点的引用}const T& front() const // const访问头{return *begin(); // 返回第一个有效数据的const引用}const T& back() const // const访问尾{return *(--end()); // 返回头结点的const引用}// 4、插入、删除函数void insert(iterator pos, const T& x) // 插入{assert(pos._pnode); // 确保合法性node* cur = pos._pnode; // cur结点为当前所处的结点位置node* prev = cur->_prev; // prev结点为当前结点的前一个结点node* newnode = new node(x);// 链接newnode->_next = cur;cur->_prev = newnode;prev->_next = newnode;newnode->_prev = prev;}iterator erase(iterator pos) // 删除{assert(pos._pnode); // 检测合法性assert(pos != end()); // 不能删除头结点node* cur = pos._pnode; // cur结点为当前结点node* prev = cur->_prev; // prev结点为前一个结点node* next = cur->_next; // next结点为后一个结点delete cur; // 删除当前节点// 建立关系prev->_next = next;next->_prev = prev;return iterator(next); // 返回所给迭代器pos的下一个迭代器}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()); // 删除第一个有效节点}// 5、其他函数size_t size() const // 容量大小{int sz = 0; // 统计的有效容量大小个数const_iterator it = begin(); // 开头元素while (it != end()) // 通过遍历累加{++sz;++it;}return sz; // 返回有效大小的个数}void resize(size_t n, const T& val = T()) // 扩容{iterator it = begin(); // 获取第一个有效数据的迭代器size_t len = 0; // 记录当前所遍历的数据个数while (len < n && it != end()){len++;it++;}if (len == n) // 说明容器当中的有效数据个数大于或是等于n{while (it != end()) // 只保留前n个数据{it = erase(it); // 每次删除后接收下一个数据的迭代器}}else // 说明容器当中的有效数据个数小于n{while (len < n) // 尾插数据为val的结点，直到容器当中的有效数据个数为n{push_back(val);len++;}}}void clear() // 清空{iterator it = begin();while (it != end()) // 逐个删除{it = erase(it);}}bool empty() const  // 判空 {return end() == begin();}void swap(list<T>& lt) // 交换{std::swap(_phead, lt._phead);}private:// 成员变量node* _phead; // 指向头结点的指针};void Print(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){std::cout << *it << " ";++it;}std::cout << std::endl;}
}