【C++】13.list的模拟实现

首先，我们需要把链表管理起来，也就是把一个个节点管理起来，但是每个节点的信息我们也需要管理，例如节点的前驱指针和后驱指针，以及节点的值，所以我们这里先封装两个类来管理节点和链表。

namespace Ro
{template<class T>struct list_node{list_node(const T& val = T()):_data(val),prev(nullptr),next(nullptr){}T _data;list_node<T>* prev;list_node<T>* next;};template<class T>class list{typedef list_node<T> Node;public:list(){_head = new Node;_head->prev = _head;_head->next = _head;_size = 0;}private:Node* _head;size_t _size;};
};

先将list的模子给写好，同时介绍以下几点：

list_node:

在list中我们需要经常访问list_node中的成员变量，所以需要将list_node中的成员变量公有，干脆使用结构体struct，因为struct默认公有。

注意：成员变量的类型list_node<T>需要显示实例化，不可以直接list_node，虽然之前在函数模板章节有讲过模板也可以不显式的写，让编译器自动推导类型，但是那是函数模板可以让编译器推导，在这里是类模板，类模板是不能自动推导类型的，所以需要显式实例化。

另外在list_node中我们不需要显式定义拷贝构造函数和析构函数，只需要写构造函数

原因如下：

1. 默认行为已足够

• 如果节点类只包含简单的数据成员（如基本数据类型或指针），默认的拷贝构造函数和析构函数已经能够正确工作。
• 拷贝构造函数：默认拷贝构造函数会逐成员拷贝 data、next 和 prev 指针。对于指针成员，这只会复制指针的值（即地址），而不会复制指针指向的对象。
• 析构函数：默认析构函数会自动销毁 data（如果 T 是一个非指针类型且需要销毁），但不会自动释放 next 和 prev 指针指向的内存（因为它们只是指针，不负责管理内存）。

---

2. 避免不必要的复杂性

• 显式定义拷贝构造函数和析构函数可能会引入复杂性，尤其是当节点类包含动态分配的资源时。
• 如果手动定义拷贝构造函数，需要确保深拷贝逻辑正确实现，否则可能导致悬空指针或双重释放等问题。
• 如果手动定义析构函数，需要确保释放所有动态分配的资源，否则可能导致内存泄漏。
• 通过依赖默认的拷贝构造函数和析构函数，可以避免这些潜在问题。

---

3. 链表本身的内存管理

• 在实现一个链表时，通常由链表类本身负责管理节点的内存分配和释放，而不是由节点类负责。
• 例如，链表的插入和删除操作会负责创建和销毁节点，而节点类只需要存储数据和指针。
• 因此，节点类不需要显式定义析构函数来释放内存。

---

4. 性能考虑

• 显式定义拷贝构造函数和析构函数可能会引入额外的开销，尤其是在节点类被频繁拷贝或销毁的情况下。
• 依赖默认的拷贝构造函数和析构函数可以避免这种开销，尤其是在节点类只包含简单数据成员的情况下。

---

5. 指针语义的合理性

• 在链表节点中，指针成员（如 next 和 prev）通常只是指向其他节点的指针，而不是拥有这些节点的所有权。
• 因此，默认的浅拷贝行为（即复制指针值）是合理的，因为链表类本身会管理节点的生命周期。

---

6. C++ 的规则五（Rule of Five）

• 根据 C++ 的规则五，如果一个类需要显式定义拷贝构造函数、拷贝赋值运算符、移动构造函数、移动赋值运算符或析构函数中的任何一个，那么通常需要显式定义所有这些函数。
• 如果节点类不需要显式定义这些函数中的任何一个（因为默认行为已经足够），那么就没有必要显式定义它们。

---

7. 现代 C++ 的智能指针

• 如果需要更复杂的内存管理，可以在链表实现中使用智能指针（如 std::unique_ptr 或 std::shared_ptr）来管理节点的生命周期。
• 例如，可以使用 std::unique_ptr<list_node<T>> 来管理节点的内存，从而避免手动管理内存的复杂性。

list:

我们这里实现的双向带头循环链表，所以我们需要一个指向哨兵位头节点的指针，方便我们管理链表，另外为方便得到list的size()，省去遍历一遍链表的繁琐，我们定义两个成员变量_head和_size。同时在构造函数中，我们初始化头节点，并把list_node<T>typedef一下为Node。

接下来我们正式来模拟实现list

1. push_back()

还是老规矩，我们先来实现尾插，让list能够跑起来

void push_back(const T& data)
{Node* newnode = new Node(data);Node* ptail = _head->prev;ptail->next = newnode;newnode->next = _head;newnode->prev = ptail;_head->prev = newnode;_size++;
}

测试一下：

void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);
}

---

2.迭代器实现

在string和vector中，迭代器是原生指针typedef来的，但是在list中这样是不行的，因为string和vector是连续的空间，++就能得到下一个数据的地址，对迭代器解引用就能得到数据，但是list空间是不连续的，直接++是不行的，直接解引也是不行的，因为此时指针指向的是一个结构体，对结构体解引用得到的是该结构体的左值引用，但是我们想做到解引用直接拿到结构体中存的数据。

那要怎么做呢？在之前我们有提过，迭代器是一个像原生指针一样的东西，我们要让迭代器能够模拟指针一样的操作，所以这里我们可以将迭代器封装成一个类，通过operator++，operator*等运算符重载来模拟指针的行为。

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

我们需要获取list_node中的值和前驱指针以及后驱指针，所以我们可以让指向list_node的指针_node作为成员变量，同时迭代器++的返回值同样是迭代器，所以我们也对迭代器类型也typedef一下

---

2.1 operator*()

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

直接返回节点的数据

---

2.2 operator++()

operator++分为前置++和后置++，在前面的章节中我们有讲过，前置++和后置++，可以通过占位符来区分。

前置++：

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

后置++：

Self operator++(int)
{Self tmp(*this);//先储存原来的值_node = _node->next;//再++return tmp;//返回原来的值
}

后置++需要返回++前的指针，所以我们先拷贝构造储存一下++前的指针，再++，然后返回tmp

---

2.3 operator--()

有++就有--，和++一样也分为前置--和后置--

前置--：

//前置--
Self& operator--()
{_node = _node->prev;return *this;
}

后置--：

//后置--
Self operator--(int)
{Self tmp(*this);_node = _node->prev;return tmp;
}

---

2.4 operator!=()和operator==()

迭代器是有比较的，例如我们在使用迭代器遍历容器的时候经常会这样用：it != lt.end()

所以还需要比较运算符

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

---

2.5 operator->()

我们知道对结构体的解引用还有箭头运算符，如果我们list_node中的数据_data是自定义类型，例如是一个日期类Date的话，虽然我们可以 { (*it)._year，(*it)._month 和 (*it)._day }这样的操作来访问，但是对于 .  这种对结构体成员访问，使用 -> 访问结构体成员还是更为普遍的

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

直接取结构体的地址返回就行，因为结构体指针能够使用->运算符访问结构体成员

---

2.6 begin()和end()

typedef list_iterator<T> iterator;
iterator begin()
{//return iterator(_head->next);return _head->next;
}iterator end()
{//return iterator(_head);return _head;
}

这里我们可以返回一个iterator的临时对象，不过这里也可以直接返回_head->next，让它自己走隐式类型转换，begin()指向第一个数据，end()指向最后一个数据的下一个位置，最后一个数据的下一个位置就是头节点

---

2.7 测试

迭代器的基本功能已经实现的差不多了，接下来我们来测试一下

void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << ' ';it++;}cout << endl;//范围forfor (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.operator->()->a1 << ':' << it.operator->()->a2 << endl;cout << it->a1 << ':' << it->a2 << endl;it++;}}

需要注意的是这里本来应该是两个->才合理的，第一个operator->()返回的是AA*的指针，第二个->是访问结构体AA的成员，但是为了可读性，省略了一个->

---

2.8 const迭代器

上面实现的迭代器是普通迭代器可读可写，但是还有const迭代器，可读不可写。

那const迭代器要怎么实现呢？其实只需要复用一下迭代器的代码，然后在修改一下细节就行

const迭代器：

template<class T>
struct const_list_iterator
{typedef list_node<T> Node;typedef const_list_iterator<T> Self;Node* _node;const_list_iterator(Node* node):_node(node){ }//前置++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) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}const T* operator->(){return &_node->_data;}const T& operator*(){return _node->_data;}
};

这里我们只需要将返回值修改，返回const迭代器，const T&和const T*。这样就可以限制写的功能

在list中，我们同样typedef一下const迭代器

template<class T>
class list
{typedef list_node<T> Node;
public:typedef list_iterator<T> iterator;typedef const_list_iterator<T> const_iterator;list(){_head = new Node;_head->prev = _head;_head->next = _head;_size = 0;}iterator begin(){//return iterator(_head->next);return _head->next;}iterator end(){//return iterator(_head);return _head;}const_iterator begin() const{return _head->next;}const_iterator end() const{return _head;}void push_back(const T& data){Node* newnode = new Node(data);Node* ptail = _head->prev;ptail->next = newnode;newnode->next = _head;newnode->prev = ptail;_head->prev = newnode;_size++;}
private:Node* _head;size_t _size;
};

注意:const迭代器是const迭代器修饰的对象是const，可读不可写，不是迭代器不可写，同样const迭代器的begin()和end()需要用const修饰，与const迭代器兼顾，同时防止意外修改容器中的元素

I 测试一下

这里我们发现报错了，为什么呢？

因为这里我们定义的lt并非const对象，所以 lt.begin() 和 lt.end() 调用的是普通迭代器，但是我们把普通迭代器赋值给const迭代器的对象 it ，造成权限的放大（it的权限放大为普通迭代器），在之前的章节中，我们有讲过权限可以缩小，但是不能放大，所以这里会报错，同时这里 const迭代器对象 it 和普通迭代器 lt.end() 是不能比较的，因为两个不同类型的对象不能比较，所以这里会报错没有匹配的 != 运算符

那怎么解决呢？由于我们目前实现的list只是一些简单的功能，像拷贝构造等还没有实现，不然可以拷贝构造一个const对象 

像这样的话就不会出问题，但是我们还没实现拷贝构造，那我们干脆实现一个print的函数专门打印，后面测试的时候也可以直接调用

template<class Container>
void print(const Container& con)
{typename Container::const_iterator it = con.begin();while (it != con.end()){//*it += 10;cout << *it << ' ';it++;}cout << endl;//范围forfor (auto e : con){cout << e << ' ';}cout << endl;
}

在形参处使用const，所以这里con是const对象，我们要使用const迭代器

这里我们自定义了一个Container容器类，这样我们传不同的容器都能打印，不止于list

注意这里需要用typename来声明一下Container::const_iterator是一个类，不然编译器会分不清这是类还是静态成员变量

如果我们对const迭代器的对象修改（*it += 10），编译器会报错

只读不写的话const迭代器就不会报错

II 巧用模板实现迭代器

虽然我们直接cv一份代码修改一下细节就能实现const迭代器，但是这样写代码太冗余了，而且普通迭代器和const迭代器只是在返回值类型上不同，其余都一样，那有没有什么更好的方法实现呢？我们来看看STL3.0中是怎么做的

我们可以看到在STL3.0中使用了3个类模板参数，这样就可以让编译器给我们实例化出两个不同的类，这样写确实很妙，那我们也这样模拟岂不美哉

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):_node(node){ }//前置++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;}Ptr operator->(){return &_node->_data;}Ref operator*(){return _node->_data;}
};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;
}

这样我们传什么样的类模板，就能实例化出不同的迭代器

---

3.list的增删查改

3.1 insert()

iterator insert(iterator pos, const T& data)
{Node* newnode = new Node(data);Node* cur = pos._node;//pos位置的节点Node* pre = cur->prev;//在pos前插入，先找到pos前的节点//pre newnode curpre->next = newnode;newnode->next = cur;newnode->prev = pre;cur->prev = newnode;_size++;return newnode;
}

在pos位置前插入，我们要先找到pos位置和pos位置前的节点，然后再将新节点插入其中

测试一下：

void test_list4()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();int k = 3;while (k--){it++;}lt.insert(it, 20);print(lt);
}

insert实现好了，我们可以把之前的push_back()直接复用insert()的代码

push_back:

在头节点前插入

void push_back(const T& data)
{/*Node* newnode = new Node(data);Node* ptail = _head->prev;ptail->next = newnode;newnode->next = _head;newnode->prev = ptail;_head->prev = newnode;_size++;*/insert(end(), data);
}

push_front:

在begin()前插入

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

---

3.2 erase()

删除pos位置的数据

iterator erase(iterator pos)
{assert(pos != end());Node* nxt = pos._node->next;Node* pre = pos._node->prev;pre->next = nxt;nxt->prev = pre;delete pos._node;_size--;return nxt;
}

注意：不能把哨兵位头节点删除了，所以我们这里加一个断言，如果删除的是头节点就断言报错

删除pos位置的数据后，pos位置的迭代器就会失效，所以我们这里返回pos位置的下一个位置的迭代器，这里我们返回nxt节点让它自己走隐式类型转换

测试一下：

删除所有偶数

void test_list5()
{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()){if (*it % 2 == 0) it = lt.erase(it);else it++;}print(lt);
}

pop_back:

直接复用erase()，删除头节点前的数据

void pop_back()
{erase(_head->prev);
}

pop_front:

删除头节点后的数据

void pop_front()
{erase(_head->next);
}

---

3.3 size()和empty()

size_t size() const
{return _size;
}bool empty() const
{return _size == 0;
}

---

3.4 front() 和 back()

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

比较简单就不多介绍了

---

3.5 clear()

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

清除所有节点，但不能清除头节点，所有我们可以直接复用erase

---

4.list的拷贝构造和赋值重载

4.1 析构函数

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

这里直接复用clear()，将所有节点清除，最后释放头节点。

---

4.2拷贝构造

和string，vector一样，list也有涉及深浅拷贝的问题，如果不写自己的深拷贝的话，走编译器自己默认的浅拷贝，那么两个对象指向的就是同一份链表，会导致析构两次。

这里我们可以试一下浅拷贝：

void test_list7()
{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> lt2(lt);print(lt);print(lt2);
}

直接运行崩溃了，所以还是要动手完成自己的深拷贝

但是拷贝构造也得要有自己的头节点，所以我们要先空初始化，创建一个头节点，那我们干脆直接将构造函数中的初始化头节点封装为一个空初始化的函数，在拷贝构造之前先调用空初始化创造自己的头节点

void empty_init()
{_head = new Node;_head->prev = _head;_head->next = _head;_size = 0;
}

不过我们要将空初始化给私有，因为我们不希望外面可以调用这个接口

//构造函数
list()
{empty_init();
}//拷贝构造
list(const list<T>& l)
{empty_init();for (auto e : l){push_back(e);}
}

空初始化之后，在遍历链表，尾插重新创建一个自己的链表。

---

4.3赋值重载

list<T>& operator=(list<T> tmp)
{swap(_head, tmp._head);return *this;
}

直接使用现代写法

---

4.4其余构造函数

可以看到这里还有两种构造函数，一个是构造n个值为value的链表，另一个是迭代器区间构造

我们都来实现一下

list(int n, const T& value = T())
{empty_init();for (int i = 0; i < n; i++) push_back(value);
}template<class InputIterator>
list(InputIterator first, InputIterator last)
{empty_init();while (first != last){push_back(*first);first++;}
}

迭代器区间构造在vector模拟实现时有讲过，这里也不多介绍了

代码如下

list.h:

#pragma once
#include <iostream>
#include <assert.h>using namespace std;namespace Ro
{template<class T>struct list_node{list_node(const T& val = T()):_data(val),prev(nullptr),next(nullptr){}T _data;list_node<T>* prev;list_node<T>* next;};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):_node(node){ }//前置++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;}Ptr operator->(){return &_node->_data;}Ref operator*(){return _node->_data;}};//template<class T>//struct const_list_iterator//{//	typedef list_node<T> Node;//	typedef const_list_iterator<T> Self;//	Node* _node;//	const_list_iterator(Node* node)//		:_node(node)//	{ }//	//前置++//	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) const//	{//		return _node != s._node;//	}//	bool operator==(const Self& s) const//	{//		return _node == s._node;//	}//	const T* operator->()//	{//		return &_node->_data;//	}//	const T& operator*()//	{//		return _node->_data;//	}//};template<class T>class list{typedef list_node<T> Node;void empty_init(){_head = new Node;_head->prev = _head;_head->next = _head;_size = 0;}public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;//构造函数list(){empty_init();}list(int n, const T& value = T()){empty_init();for (int i = 0; i < n; i++) push_back(value);}//迭代器区间构造template<class InputIterator>list(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);first++;}}//拷贝构造list(const list<T>& l){empty_init();for (auto e : l){push_back(e);}}//析构~list(){clear();delete _head;_head = nullptr;}//赋值重载-现代写法list<T>& operator=(list<T> tmp){swap(_head, tmp._head);return *this;}iterator begin(){//return iterator(_head->next);return _head->next;}iterator end(){//return iterator(_head);return _head;}const_iterator begin() const{return _head->next;}const_iterator end() const{return _head;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}T& front(){return *begin();}T& back(){return *(--end());}const T& front() const{return *begin();}const T& back() const{return *(--end());}size_t size() const{return _size;}bool empty() const{return _size == 0;}void pop_back(){erase(_head->prev);}void pop_front(){erase(_head->next);}iterator erase(iterator pos){assert(pos != end());Node* nxt = pos._node->next;Node* pre = pos._node->prev;pre->next = nxt;nxt->prev = pre;delete pos._node;_size--;return nxt;}iterator insert(iterator pos, const T& data){Node* newnode = new Node(data);Node* cur = pos._node;//pos位置的节点Node* pre = cur->prev;//在pos前插入，先找到pos前的节点//pre newnode curpre->next = newnode;newnode->next = cur;newnode->prev = pre;cur->prev = newnode;_size++;return newnode;}void push_front(const T& data){insert(begin(), data);}void push_back(const T& data){/*Node* newnode = new Node(data);Node* ptail = _head->prev;ptail->next = newnode;newnode->next = _head;newnode->prev = ptail;_head->prev = newnode;_size++;*/insert(end(), data);}private:Node* _head;size_t _size;};template<class Container>void print(const Container& con){typename Container::const_iterator it = con.begin();while (it != con.end()){//*it += 10;cout << *it << ' ';it++;}cout << endl;//范围forfor (auto e : con){cout << e << ' ';}cout << endl;}void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << ' ';it++;}cout << endl;//范围forfor (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.operator->()->a1 << ':' << it.operator->()->a2 << endl;cout << it->a1 << ':' << it->a2 << endl;it++;}}void test_list3(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);print(lt);}void test_list4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();int k = 3;while (k--){it++;}lt.insert(it, 20);print(lt);}void test_list5(){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()){if (*it % 2 == 0) it = lt.erase(it);else it++;}print(lt);}void test_list6(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);cout << lt.front() << endl;cout << lt.back() << endl;//print(lt);}void test_list7(){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> lt2(2);//lt2 = lt;print(lt);print(lt2);}
};