【C++】list类的模拟实现

🏖️作者：@malloc不出对象
⛺专栏：C++的学习之路
👦个人简介：一名双非本科院校大二在读的科班编程菜鸟，努力编程只为赶上各位大佬的步伐🙈🙈

---

前言

本篇文章我们要来模拟实现的是list类，它的底层是用带头结点的双向循环链表实现的。

一、list类的模拟实现

1.1 list的主体框架

既然我们是用双向循环链表实现的，那么每个结点肯定都存储着next、prev与data信息，那么接下来我们就来定义一个类对它的结点进行初始化操作。

template<class T>  // 模板参数T
struct list_node
{list_node<T>* _next; 	//list_node<T>* 是类型list_node<T>* _prev;T _data;list_node(const T& val = T())  // 匿名对象初始化: _next(nullptr), _prev(nullptr), _data(val){}
};

我们把节点定义好之后，我们就来定义list类了，list类的成员变量只需要一个哨兵位的头结点就可以了。

template <class T>
class list
{typedef list_node<T> node;	
private:node* _head;	// 哨兵位头节点
};

1.2 无参构造函数

list()
{_head = new node;		// 申请一个节点_head->_next = _head;   // _head->_next指向自己_head->_prev = _head;   // _head->_prev也指向自己
}

1.3 push_back

双向链表的插入和删除都是非常好实现的，因为每个结点都有上一个节点和下一个节点的信息。这里我们要想实现尾插，我们要找到尾结点再改变它的指向就行了，非常的简单这里我就不做过多的赘述了。另外后续在我们实现insert和erase之后全都可以进行复用，这里只是先给大家打个样。

void push_back(const T& x)
{node* tail = _head->_prev;node* newnode = new node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;
}

1.4 正向迭代器

有了尾插之后我们可以往链表里面插入数据，下面我们想遍历一下链表，我们知道list不支持[]下标访问，原因是因为它是不连续的空间，所以我们必须使用迭代器对它进行遍历。

我们知道在实现vector类(SGI版本)时，我们的迭代器是作为一个原生指针来使用的，而在vector类(P.J.版本)中我们的迭代器是自定义类型对原生指针的封装，但本质上它们都是在模拟指针的行为！！！那么在list类中迭代器到底充当什么角色呢？我们知道迭代器支持++ - -操作这是为了找到后一个数据和前一个数据的位置，对于list而言它是双向链表它的空间是不连续的，假设迭代器是一个原生指针的话，指针++ - -一步取决于指针所指向的类型，对于不连续的空间来说++ - -能否刚好指向下一个位置或者上一个位置一切都是未知数，因此我们的迭代器在list中是对自定义类型原生指针的封装！！！

我们先来看看SGI版本下对正向迭代器的封装源码：

好了，也许我们有些地方可能有些不太懂，而且标准库的源码采用了非常多的命名替换，这是命名规范的问题，接下来我们模拟实现的时候不采用标准库这种方式，我们尽量的实现简洁易懂些。

最原始的代码

template<class T>
struct __list_iterator
{typedef list_node<T> node;typedef __list_iterator<T> self;node* _node;__list_iterator(node* x)  // 初始化结点: _node(x){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){__list_iterator tmp = *this;_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){__list_iterator tmp = *this;_node = _node->_prev;return tmp;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}
};

这是我们最原始的代码，那么大家知道为什么源码为什么会多出两个模板参数吗？这里我们实现的是正向迭代器，那么我们要实现const正向迭代器版本呢？难道要再去写一个__list_const_iterator类吗？

显然这样出现了大量的代码重复，我们是极其不支持这种实现方式的，所以我们必须想办法让他们之间可以进行复用，我们只需要改变一下返回值类型、参数类型就能实现iterator和const_iterator版本，这里模板参数的作用就体现出来了，我们可以添加一个模板参数，到时候我们可以实例化一份iterator和const_iterator。至于第三个模板参数是为了重载->运算符函数的，它同样的有T*版本和const T*版本。

为什么要重载->运算符？

struct AA
{int _a1;int _a2;AA(int a1, int a2): _a1(a1), _a2(a2){}
};void test()
{list<AA> lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));list<AA>::iterator it = lt.begin();while (it != lt.end()){cout << (*it)._a1 << " " << (*it)._a2 << endl;  ++it;}cout << endl;
}

我们可以看到上诉代码对于一个自定义类型要想访问它的成员变量就必须得写成(*it)._a1、(*it)._a2，先*it得到AA对象，再访问它的成员变量，这种写法是不是未免有些麻烦了？我们平常可以直接使用->去访问它的成员变量，就像这段代码我们可以写成it->_a1、it->_a2，但是我们此时未重载->运算符，所以为了方便使用这里我们还需要重载一下->运算符。

对于__list_iterator类我们可以重载->写出下面的代码：

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

但你有没有发现一些奇怪之处？？

好了，关于为什么要重载->运算符这里我们已经讲清楚了，那么为什么这跟添加第三个模板参数有什么关系呢？原因很简单，一个T*版，一个const T*版，添加第三个模板参数Ptr也是为了复用T*版本。

所以最终我们的__list_iterator可以写成这种版本：

template<class T, class Ref, class Ptr>
struct __list_iterator
{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;node* _node;__list_iterator(node* x)  // 初始化结点: _node(x){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self 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;}bool operator==(const self& s){return _node == s._node;}bool operator!=(const self& s){return _node != s._node;}};

我们在list类中就可以实例化iterator和const_iterator这两种版本的迭代器，list类中迭代器的定义如下：

typedef list_node<T> node;
public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}

我们来进行测试一下：

我们可以看到对应的过程，当list<int>显式声明模板类时，此时我们的类模板就根据类型实例化出一个具体的类。

1.5 反向迭代器

我们知道C++追求极致的性能，既然能复用绝不会写出两份差不多的代码，，所以我们实现反向迭代器并不会像正向迭代器那样倒着来，而是去复用正向迭代器！！！

反向迭代器其实也是一种适配器，它可以适配出各种容器的反向迭代器，其中最重要的就是将正向迭代器作为底层结构来封装反向迭代器，反向迭代器 ++ 就复用正向迭代器的 - -，反向迭代器 - - 就复用正向迭代器的 ++。

我们的反向迭代器既然是作为适配器去使用，那么我们就把它封装到单独的一个类中对它进行模拟实现，并且正向迭代作为它的模板参数进行复用它的功能！！

反向迭代器的模拟实现

// iterator.h
namespace curry
{template<class Iterator, class Ref, class Ptr>struct ReverseIterator{typedef ReverseIterator<Iterator, Ref, Ptr> Self;Iterator _cur;  // _cur就是一个正向迭代器ReverseIterator(Iterator it)  : _cur(it){}Ref operator*(){Iterator tmp = _cur;--tmp;return *tmp;}Self& operator++(){--_cur;return *this;}Self operator++(int){Self tmp = *this;--_cur;return tmp;}Self& operator--(){++_cur;return *this;}Self operator--(int){Self tmp = *this;++_cur;return tmp;}// 返回当前对象的地址Ptr operator->(){return &(operator*());}bool operator!=(const Self& s){return _cur != s._cur;}bool operator==(const Self& s){return _cur == s._cur;}};
}

只要知道了反向迭代器与正向迭代器的特性，我们就能够很容易的通过复用正向迭代器的成员函数来实现反向迭代器的成员函数！！同时反向迭代器其实解决了所有的双向迭代器的问题，因为只要将对应容器的正向迭代器作为反向迭代器的模板参数我们就能够对反向迭代器进行复用，所以我们之前的vector类的反向迭代器也能够直接使用它的正向迭代器复用实现！！这是一种非常巧妙的思想！！

1.6 insert

void insert(iterator pos, const T& x)
{node* cur = pos._node;   // 当前位置node* prev = cur->_prev; // 前一个位置node* newnode = new node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;
}

实现了insert接口函数，那么我们的push_back与push_front都是可以复用的。

push_back(int x)

void push_back(const T& x)
{insert(end(), x);
}

push_front(int x)

void push_back(const T& x)
{insert(begin(), x);
}

list类与vector类的insert不同之处在于list类insert不会导致迭代器失效，因为它的空间的不连续的，并且没有挪动数据造成迭代器失效，所以我们也可以看到它的返回值为void，并不需要放回插入位置的迭代器。

1.7 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);
}

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了，所以对于list类的erase会导致指向删除节点的迭代器失效，其他迭代器不会受到影响而vector类进行erase会导致当前位置或者后续迭代器失效，所以正确的解决办法是给迭代器重新赋值！！

实现了erase函数接口，pop_back()以及pop_front()就可以进行复用了。

pop_back()

void pop_back()
{erase(--end());
}

pop_front()

void pop_front()
{erase(begin());
}

1.8 clear

void clear()
{iterator it = begin();while (it != end()){it = erase(it);	// erase返回下一个位置的迭代器}
}

clear释放链表中的结点，_head哨兵位头结点除外。

1.9 析构函数

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

析构函数的作用是释放所有结点，我们可以先调用clear依次释放链表中的结点，最后再释放头结点。

1.10 构造函数

传统写法

void empty_init()
{// 创建并初始化哨兵位头节点_head = new node;_head->_prev = _head;_head->_next = _head;
}// 拷贝构造传统写法 lt2(lt1)
list(const list<T>& lt)
{empty_init();for (auto& e : lt)	// 加引用避免自定义类型的拷贝构造{push_back(e);}
}

现代写法

template <class Iterator>  // 双向迭代器类型构造
list(Iterator first, Iterator last)
{empty_init();while (first != last){push_back(*first);++first;}
}void swap(list<T>& tmp)
{std::swap(_head, tmp._head);	// 交换哨兵位的头节点
}// 拷贝构造现代写法 lt2(lt1)
list(const list<T>& lt)
{empty_init();	list<T> tmp(lt.begin(), lt.end());	// 迭代器区间初始化swap(tmp);	
}

1.11 赋值运算符重载

传统写法

list<T>& operator=(const list<T>& lt)
{if (this != &lt)	// 防止自己给自己赋值{clear();	// 清理数据for (auto& e : lt){push_back(e);}}return *this;
}

现代写法

list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}

一些常用的函数接口就讲到这里了，还有一些简单的函数接口读者下来也可以自己去尝试实现一下。

1.12 empty

bool empty()
{return _head->_next == _head &&_head->_prev == _head;
}

1.13 front && back

T& front()
{assert(!empty());return *begin();
}const T& front() const
{assert(!empty());return *begin();
}T& back()
{assert(!empty());return *(--end());
}const T& back() const
{assert(!empty());return *(--end());
}

1.14 完整代码

// list.h#include "iterator.h"namespace curry
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _data;list_node(const T& val = T()): _next(nullptr), _prev(nullptr), _data(val){}};template<class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;node* _node;__list_iterator(node* x)  // 初始化结点: _node(x){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self 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;}bool operator==(const self& s){return _node == s._node;}bool operator!=(const self& s){return _node != s._node;}};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;typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;iterator begin(){return iterator(_head->_next);}reverse_iterator rbegin(){return reverse_iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_reverse_iterator rbegin() const{return const_reverse_iterator(_head);}iterator end(){return iterator(_head);}reverse_iterator rend(){return reverse_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}const_reverse_iterator rend() const{return const_reverse_iterator(_head->_next);}list(){empty_init();}// 现代写法list(const list<T>& lt){empty_init();list<T> tmp(lt.begin(), lt.end());swap(tmp);}template<class Iterator>list(Iterator first, Iterator last){empty_init();while (first != last){push_back(*first);++first;}}list<T>& operator=(list<T> lt){swap(lt);return *this;}// 释放所有结点~list(){clear();delete _head;_head = nullptr;}void swap(list<T>& tmp){std::swap(_head, tmp._head);}// 释放结点，但是_head头结点不处理void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void insert(iterator pos, const T& x){node* cur = pos._node;node* prev = cur->_prev;node* newnode = new node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}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);}T& front(){assert(!empty());return *begin();}const T& front() const{assert(!empty());return *begin();}T& back(){assert(!empty());return *(--end());}const T& back() const{assert(!empty());return *(--end());}bool empty(){return _head->_next == _head &&_head->_prev == _head;}private:node* _head;};
}

二、vector与list的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

	vector	list
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素效率O(1)	不支持随机访问，访问某个元素效率O(N)
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1）
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针(节点指针)进行封装
迭代器失效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景	需要高效存储，支持随机访问，不关心插入删除效率	大量插入和删除操作，不关心随机访问

---

以上就是本文的所有内容了，如有错处或者疑问欢迎大家在评论区相互交流orz~🙈🙈