【C++】list的模拟实现

🚀个人主页：奋斗的小羊 🚀所属专栏：C++ 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

---

💥1、list的模拟实现

💥1.1 list简单介绍

list是带头双向循环链表，它与我们之前学习的string和vector的最大区别是物理结构不同，string和vector在逻辑上和物理上都是连续的，但list只在逻辑上连续。
list由一个个节点组合而成，一个节点内存有数据、上一个节点的地址和下一个节点的地址，为了方便处理这里我们将一个节点封装成一个类，这个类还需要我们显示写构造函数，当我们创建一个新节点时需要调用这个默认构造完成对新节点的初始化。
为了使节点类存储不同类型的数据，可以将这个节点类设计为节点类模版。

template<class T>
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x),_next(nullptr),_prev(nullptr){}
};

• 对于构造函数，参数部分我们给一个缺省值，为了同时照顾类类型和内置类型，需要使用匿名对象默认构造

同时将list类也封装成一个模版，其成员变量是节点类类型的指针，指向list的哨兵节点，我们需要在list的默认构造函数中创建一个哨兵节点并初始化。
为了方便得到list中的节点个数，可以在list类中多加一个成员变量_size用于记录list的节点个数：

template<class T>
class list
{typedef list_node<T> Node;
public:list(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}private:Node* _head;size_t _size;
}

---

💥1.2 list主要函数接口

💥1.2.1 构造

构造一个哨兵节点，并使前后指针都指向自己。

list()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}

---

💥1.2.2 拷贝构造

拷贝构造一个list，首先这个list需要有哨兵节点，然后再将节点一个一个取出尾插。

void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}
list(const list<T>& lt)
{empty_init();for (auto& e : lt){push_back(e);}
}

• list中有存类类型的可能，范围for这里最好使用引用

---

💥1.2.3 赋值重载

void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}

• swap函数参数传引用，但不能用const修饰
• 赋值重载返回链表的引用，参数部分要用传值传参，为的是调用拷贝构造

---

💥1.2.4 迭代器

本来需要先通过指向节点的指针来构造一个迭代器再返回，不过我们可以返回指向节点的指针，利用隐式类型转换构造一个临时迭代器返回。

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

• begin()是指向第一个节点的迭代器，end()是指向哨兵节点的迭代器

---

💥1.2.5 插入

在指定位置插入一个节点，首先需要先得到指定位置的前一个节点和当前位置的节点，构造一个新节点后将新节点和前后节点连接起来，最后++_size即可。

void insert(const iterator& pos, const T& x)
{Node* pcur = pos._node;Node* prev = pcur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = pcur;pcur->_prev = newnode;++_size;
}

| 头插：

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

| 尾插：

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

---

💥1.2.6 删除

void erase(const iterator& pos)
{//不能删除哨兵节点assert(pos != end());Node* pcur = pos._node;Node* prev = pcur->_prev;Node* next = pcur->_next;prev->_next = next;next->_prev = prev;delete pcur;--_size;
}

| 头删：

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

| 尾删：

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

• 尾删删除的是最后一个节点，而end()是指向哨兵位的迭代器

---

💥1.2.7 迭代器失效的问题

对于list的迭代器，插入操作不会使迭代器失效，因为list的迭代器指向某一个节点，插入一个节点不会改变迭代器的指向。
对于删除操作，删除pos位置的节点后迭代器指向的空间已经被释放不能访问，迭代器就失效了。解决这个问题的办法还是和之前一样删除某个节点后返回下一个节点的迭代器。

iterator erase(const iterator& pos)
{//不能删除哨兵节点assert(pos != end());Node* pcur = pos._node;Node* prev = pcur->_prev;Node* next = pcur->_next;prev->_next = next;next->_prev = prev;delete pcur;--_size;return next;
}

虽然插入操作不会使迭代器失效，但是库中insert也有返回值，其返回的是刚插入节点的迭代器。

iterator insert(const iterator& pos, const T& x)
{Node* pcur = pos._node;Node* prev = pcur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = pcur;pcur->_prev = newnode;++_size;return newnode;
}

---

💥1.2.8 clear

clear的功能是从列表容器中删除所有元素，但是不删除哨兵节点。

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

---

💥1.2.9 析构

我们需要遍历链表一个节点一个节点的释放，可以先调用clear，再释放掉哨兵节点即可。

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

---

💥1.3 list迭代器

因为list在物理结构上不连续，所以其迭代器不能像string和vector的迭代器一样可以直接++和- -等操作，需要特殊封装重载运算符才能实现。
虽然我们对list的迭代器进行了封装，但其核心还是指向节点的指针。
list迭代器的成员变量是指向节点的指针。

template<class T>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;
}

💥1.3.1 构造

用节点的地址初始化迭代器的成员变量_node：

list_iterator(Node* node = nullptr):_node(node)
{}

---

💥1.3.2 ++重载

| 前置++：

list的迭代器++得到的是下一个节点的迭代器：

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

| 后置++：

Self operator++(int)
{Self tmp(*this);//使用编译器默认生成的拷贝构造就行_node = _node->_next;return tmp;}

后置++重载需要先保存当前迭代器指向的节点，然后再++指向下一个节点，返回临时节点。

• 后置++需要用int占位
• 这里拷贝构造了一个临时节点，只能传值返回，不能传引用返回，因为这个临时节点在出了作用域后就销毁了
• 这里虽然有拷贝构造，但是我们不需要显示的写拷贝构造函数，使用编译器默认生成的就行，编译器默认生成的拷贝构造函数完成的是浅拷贝，而我们需要的就是浅拷贝
• 也不需要写析构，因为迭代器的目的只是遍历list，不能释放节点

---

💥1.3.3 - -重载

和++重载保持一致。

| 前置- -：

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

| 后置- -：

Self operator--(int)
{Self tmp(*this);_node = _node->_prev;return tmp;
}

---

💥1.3.4 解引用重载

list迭代器是一个类，直接解引用不行，需要重载*运算符才能得到节点中存的数据。

| * 重载：

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

| -> 重载：

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

当list中存的数据类型是类类型时就需要使用到->运算符，其运算符重载返回的是节点中数据地址，再用这个地址+->来得到类中的数据。

void test_list2()
{struct aa{int _a1 = 1;int _a2 = 2;};list<aa> lt;lt.push_back(aa());lt.push_back(aa());lt.push_back(aa());lt.push_back(aa());list<aa>::iterator it = lt.begin();while (it != lt.end()){//cout << *it << " ";cout << it->_a1 << " " << it->_a2 << " ";++it;}cout << endl;
}

事实上这里的解引用操作应该是下面这样的：

cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << " ";

只是为了方便省略了其中的一个->。

---

💥1.3.5 ==和!= 重载

判断两个迭代器中的_node指向的节点是否相同。

bool operator==(const Self& s) const
{return _node = s._node;
}bool operator!=(const Self& s) const
{return _node != s._node;
}

---

💥1.3.6 普通迭代器和const迭代器

我们之前实现的其他类的const迭代器是const_iterator，为什么const迭代器不是const iterator呢？它们有什么区别？
迭代器笼统的说就是指针，其作用是遍历数据，所以其指向是需要改变的，const iterator表示的是迭代器的指向不能改变，而const_iterator表示的才是迭代器指向的内容不能改变。

普通迭代器和const迭代器我们都需要，常规的做法就是普通迭代器和const迭代器分开实现，但是这样实现的两个迭代器中很多内容都是重复的，因为改变迭代器指向的内容只能通过重载的*和->来完成，所以两个迭代器只有这两个运算符重载不同，其他都是一样的。

为了避免过多重复的代码，我们可以在模版参数上下手：

template<class T, class Ref, class Ptr>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}
}

在list类中这样重定义普通迭代器和const迭代器：

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

传不同的模版参数，按需实例化出合适的类。 如果多个类高度相似，我们就可以想方设法的搞成模版，避免过多重复。

---

💥2、list模拟实现完整代码

list.h:

#pragma once#include <iostream>
#include <assert.h>
using namespace std;namespace yjz
{template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x),_next(nullptr),_prev(nullptr){}};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* node = nullptr):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);//使用编译器默认生成的拷贝构造就行_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator==(const Self& s) const{return _node = s._node;}bool operator!=(const Self& s) const{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;void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}//void push_back(const T& x)//{//	Node* newnode = new Node(x);//	Node* tail = _head->_prev;//	tail->_next = newnode;//	newnode->_prev = tail;//	_head->_prev = newnode;//	newnode->_next = _head;//	++_size;//}void push_front(const T& x){insert(begin(), x);}void push_back(const T& x){insert(end(), x);}iterator insert(const iterator& pos, const T& x){Node* pcur = pos._node;Node* prev = pcur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = pcur;pcur->_prev = newnode;++_size;return newnode;}iterator erase(const iterator& pos){//不能删除哨兵节点assert(pos != end());Node* pcur = pos._node;Node* prev = pcur->_prev;Node* next = pcur->_next;prev->_next = next;next->_prev = prev;delete pcur;--_size;return next;}void pop_front(){erase(begin());}void pop_back(){erase(--end());}iterator begin(){//iterator it(_head->_next);//return it;return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}size_t size() const{return _size;}bool empty() const{return _size == 0;}private:Node* _head;size_t _size;};
}

test.cpp:

#define  _CRT_SECURE_NO_WARNINGS#include "list.h"namespace yjz
{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;lt.erase(++lt.begin());lt.insert(--lt.end(), 10);for (auto e : lt){cout << e << " ";}cout << endl;}void test_list2(){struct aa{int _a1 = 1;int _a2 = 2;};list<aa> lt;lt.push_back(aa());lt.push_back(aa());lt.push_back(aa());lt.push_back(aa());list<aa>::iterator it = lt.begin();while (it != lt.end()){//cout << *it << " ";cout << it->_a1 << " " << it->_a2 << " ";cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << " ";++it;}cout << endl;}void test_list3(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);list<int> lt2 = lt1;list<int>::iterator it = lt2.begin();while (it != lt2.end()){cout << *it << " ";++it;}cout << endl;list<int> lt3;lt3.push_back(10);lt3.push_back(20);lt3.push_back(30);lt3.push_back(40);lt2 = lt3;list<int>::iterator i = lt2.begin();while (i != lt2.end()){cout << *i << " ";++i;}cout << endl;}
}int main()
{yjz::test_list3();return 0;
}

---