十四、模拟实现 list 类

news/2024/11/15 4:48:46/

Ⅰ . list 基本框架的实现

01 结点的建立

为了实现链表,我们首先要做的应该是建立结点

为了和真正的 list 进行区分,我们仍然在自己的命名空间内实现

代码实现:

namespace yxt
{// 建立结点template<class T>struct ListNode{T _data;ListNode<T>* _next;		// 指向后继节点ListNode<T>* _prev;		// 指向前驱节点};
}

这里为什么 ListNode 要加  <T> 呢?

因为类模板不支持自动推类型,结构体模板或类模板在定义时可以不加 <T>,但使用时必须加 <T>

准备好 _data,放置好前驱 _next 和后继结点 _prev 后,我们的结点就有了 "结构“

我们知道,结构体 struct 在 C++ 中升级成了类,因此它也有调用构造函数的权利。

也就是说,在创建结构体对象的时会调用构造函数。

既然如此,结点的初始化工作,我们可以考虑写一个构造函数去初始化

02 结点初始化

其实结点初始化就是创建新结点,我们先不考虑开空间的事,完成初始化主要有两个方面:

① 将数据给 _data

② 将 _next 和 _prev 都置成空

这些任务我们可以写到构造函数中,还可以设计成全缺省,给一个匿名对象,这样一来,如果没有指定初始值,它就会按模板类型给对应的初始值

代码实现:

namespace yxt
{// 建立结点template<class T>struct ListNode{T _data;ListNode<T>* _next;		// 指向后继节点ListNode<T>* _prev;		// 指向前驱节点// 结点初始化ListNode(const T& data = T()):_data(data),_next(nullptr),_prev(nullptr){}};
}

这样,结点就写好了

03 结点的连接

设计好结点后,我们就可以开始实现 list 类了

因为是带头双向循环链表,我们首先要把头节点设计出来

代码实现:

	/* list */template<class T>class list{typedef ListNode<T> Node;public:/* 构造函数 */list(){_pHead = new Node();_pHead->_next = _pHead;		// 默认指向头结点_pHead->_prev = _pHead;		// 默认指向头结点    }private:Node* _pHead;};

04 push_back

我们先实现一下 push_back,好让 list 先跑起来

步骤一:找到尾结点并创建新结点

虽然我们没有定义 _pTail,但对于双向带头循环链表来说,找到尾结点很容易,尾结点就是头结点的前驱指针,这里创建新结点也很容易,我们直接 new 一个新结点,自动调用我们刚才写的建立结点

步骤二:连接新结点与原链表

这里连接我们主要分两步:一是把新结点与尾结点连接起来 二是把新结点和头结点连接起来

我们直接来看代码

代码实现:

		/* push_back */void push_back(const T& x){// 找尾结点并建立新结点Node* _pTail = _pHead->_prev;Node* new_node = new Node(x);// 新结点和尾结点相连_pTail->_next = new_node;new_node->_prev = _pTail;// 新结点和头结点相连new_node->_next = _pHead;_pHead->_prev = new_node;}

尾插写好之后,我们调试一下:

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

调试结果如下: 

Ⅱ . list 迭代器的实现

01 引入

list 的重点是迭代器,因为这里迭代器的实现和我们之前讲的实现方式都不同

我们之前实现的 string 和 vector 的迭代器都是一个原生指针,实现很简单

list 是一个链表,空间上不连续,又如何实现呢?

在链表中,想要找到下一个结点,通常需要解引用和 ++

而自带的解引用和 ++ ,并不能满足我们的要求,但我们可以对其进行重载

02 迭代器的构造

代码实现:

	/* 定义迭代器 */template<class T>struct _list_iterator{typedef ListNode<T> Node;Node* _node;/* 迭代器的构造 */_list_iterator(Node* x):_node(x){}};

03 operator ++

加加分前置和后置,我们先实现前置

代码实现:

		/* ++it */_list_iterator<T>& operator++(){_node = _node->_next;return *this;}

因为前置直接改变主体,我们直接 return *this 即可

因为出了作用域还在,所以可以返回引用

对应的,后置++ 我们可以拷贝构造出一个 tmp 来保存原来的值,这样虽然改变了主体

但返回的还是之前的值,这样就实现了后置++

因为前置++后置++都是 operator++,区分方式是后置++用占位符 (int) 占位

代码实现:

		/* it++ */_list_iterator<T>& operator++(int){_list_iterator<T> tmp(*this);_node = _node->_next;return tmp;}

04 operator *

解引用就是取结点里的数据

并且operator* 和指针一样,不仅能读数据,还能写数据

为了使其支持修改的操作,我们这里用引用返回

代码实现:

		/* 解引用 */T& operator*(){return _node->_data;}

05 测试 实现 begin() 和 end()

有了 operator++ 和 operator* ,我们就可以来测试一下我们的迭代器了

begin 是第一个存有效数据的结点,即 _pHead 的下一个位置的结点。

而 end 返回的是最后一个数据的下一个位置,即 _pHead

代码实现:

		typedef _list_iterator<T> iterator;iterator begin(){return _pHead->_next;}iterator end(){return _pHead;}

因为迭代器要用到 != ,所以我们要实现操作符的重载

06 operator!=

如何判断是否相等呢?

如果两个迭代器结点的指针指向的是同一个结点,那就说明是相等的迭代器。

代码实现:

		/* != */bool operator!=(const _list_iterator<T>& it){return _node != it._node;}

测试:

	void list_test1(){list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;}

运行结果如下:

07 迭代器的拷贝构造、赋值和析构

拷贝构造和赋值重载是否需要自己实现?析构呢?

list 的拷贝构造和赋值不需要自己实现,默认生成的即可

it2(it1)
it2 = it1 浅拷贝

当前迭代器赋值给另一个迭代器使不需要深拷贝的,浅拷贝即可

我们再谈谈析构为什么不需要自己实现

template<class T> 
struct __list_iterator 
{typedef ListNode<T> Node; Node* _node;...
}

迭代器这里虽然有一个结点的指针,但它并不是迭代器管的,是 list 管的

list 的析构函数会把这个结点给释放掉

所以它的释放和迭代器没什么关系

总结:迭代器是借助结点的指针访问修改链表的,结点属于链表,不属于迭代器,所以不用管它的释放问题,因此,拷贝构造、赋值重载和析构,这些都不需要自己实现,默认生成的即可

08 打印链表

我们刚才实现好了迭代器:

		list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;

不用范围 for 的前提下,用迭代器似乎挺麻烦,我们可以放到一个函数里

这里为了减少拷贝,使用引用返回,我们没有实现 const 迭代器,会导致没法遍历:

测试:

	void print_list(const list<int>& l){list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;}void list_test1(){list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);print_list(l);}

运行结果:报错

const 迭代器和普通迭代器的区别是什么?

普通迭代器访问普通对象,可读可写;const 迭代器访问 const 对象,可读不可写。

所以我们自然是要实现 const 迭代器

09 const 迭代器的实现

传统方法是把 list_iterator 直接 CV,然后改成 const 的

代码实现:

		/* 定义const迭代器 */template<class T>struct _const_list_iterator{typedef ListNode<T> Node;Node* _node;/* 迭代器的构造 */_const_list_iterator(Node* x):_node(x){}/* ++it */_const_list_iterator<T>& operator++(){_node = _node->_next;return *this;}/* it++ */_const_list_iterator<T>& operator++(int){_const_list_iterator<T> tmp(*this);_node = _node->_next;return tmp;}/* 解引用 */const T& operator*(){return _node->_data;}/* != */bool operator!=(const _const_list_iterator<T>& it){return _node != it._node;}

这里我们把 __list_iterator 都修改成 __const_list_iterator,

并且对于解引用 operator* 的重载,我们将其改成 const 引用返回,这样就只能读不能写了。

代码:们这里再在 list 中 typedef 一下 const 迭代器

	/* list */template<class T>class list{typedef ListNode<T> Node;public:/* 迭代器 */typedef _list_iterator<T> iterator;typedef _const_list_iterator<T> const_iterator;iterator begin(){return iterator(_pHead->_next);}iterator end(){return iterator(_pHead);}

const 迭代器和普通迭代器不是一个类型

不是迭代器是 const ,而是对象是 const,所以要调用 const 的 begin  和 end才行

所以还要写 __const_list_iterator 类型的 begin 和 end,我们用 const 去修饰,限制它写的权限

代码实现:

		const_iterator begin() const{return const_iterator(_pHead->_next);}const_iterator end() const{return const_iterator(_pHead);}

测试:

	void print_list(const list<int>& l){list<int>::const_iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;}void list_test1(){list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);print_list(l);}

运行结果如下:

10 使用模板实现 const 迭代器

通过加一个额外的模板参数去控制 operator 的返回值,你能想到吗?

在定义 template 模板的时增加一个参数 Ref :

这样的话,我们 operator* 的返回值我们不要用 T&了,我们改成 Ref:

也就是说,让 operator* 的返回值变成 Ref 这个模板参数!

代码:之后我们在 list 中 typedef 的时候就可以传 T& 或 const T&

	public:/* 迭代器 */typedef _list_iterator<T, T&> iterator;typedef _const_list_iterator<T, const T&> const_iterator;iterator begin(){return iterator(_pHead->_next);}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(_pHead->_next);}const_iterator end() const{return const_iterator(_pHead);}

一:Ref 是 T& ,可读可写

这里 test_list1 是一个普通对象,调用的自然是普通的 begin。 begin 返回的是普通迭代器 __list_iterator<T, T&>,第二个模板参数是 T&,Ref 就是 T& 了。operator* 的返回值 Ref 是 T& 了,这样就做到了可读可写了。

二:Ref 是 const T& ,可读不可写

比如这里的 print_list 就是一个 const 对象,它调用的就是 const 的 begin。const begin 返回的是 const 迭代器 __list_iterator<T, const T&>,第一个值传的都是 T,第二个值 const T& 传给 Ref。那么 operator* 的返回值 Ref 就是 const T& 了,这样就做到了可读但不可写的。

模板重命名

时去编译,是编译不通过的。

因为我们多定义了一个 Ref,所以  __list_iterator 中的所有类模板都得加上它,比如:

这样加来加去是不是太不方便了?我们来看看设计 STL 的大佬是怎么做的:

把这些都 typedef 一下,这样我们就可以把 __list_iterator<T, Ref> 写成 Self 了:

代码实现:

	/* 定义迭代器 */template<class T, class Ref>struct _list_iterator{typedef ListNode<T> Node;typedef _list_iterator<T, Ref> Self;Node* _node;/* 迭代器的构造 */_list_iterator(Node* x):_node(x){}/* ++it */Self& operator++(){_node = _node->_next;return *this;}/* it++ */Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}/* --it */Self& operator--(){_node = _node->_prev;return *this;}/* it-- */Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}/* 解引用 */Ref operator*(){return _node->_data;}/* != */bool operator!=(const Self& it){return _node != it._node;}};

箭头操作符

迭代器是像指针一样的东西,所以要重载两个解引用

为什么呢?指针如果指向的类型是原生的普通类型,要取对象是可以用解引用的

但如果指向的是一个结构,并且我们又要取它的每一个成员变量,比如这样:

代码:比如是一个日期类,我们没有实现流提取

	struct Date {int _year;int _month;int _day;Date(int year = 1, int month = 1, int day = 1) : _year(year), _month(month), _day(day) {}};void test_list3() {list<Date> L;L.push_back(Date(2022, 5, 1));L.push_back(Date(2022, 5, 2));L.push_back(Date(2022, 5, 3));list<Date>::iterator it = L.begin();while (it != L.end()) {// cout << *it << " ";  假设我们没有实现流提取,我们自己访问cout << (*it)._year << "/" << (*it)._month << "/" << (*it)._day << endl;it++;}cout << endl;}

运行结果如下:

我们发现,在没有实现流提取的前提下,想遍历链表L

我们就需要用 *(it)._xxx 去访问,大多数主流习惯是用 -> 去访问的

所以我们这里去实现一下 ->:

		/* 解引用 */Ref operator*(){return _node->_data;}T* operator->(){return &_node->_data;}

总结:所以类型重载 operator-> 时都会省略一个箭头

这里还面临一个问题——const 迭代器

如果是一个 const 迭代器用箭头也是可以去修改数据的,基于这样一个原因

我们还需要增加一个模板参数:Ptr

此时刚才 typedef 的 Self 就体现出价值了

我们只需要在 Self 中加个 Ptr:

我们直接把 operator-> 的返回值修改成 Ptr 就行了

到时候我们传一个 T* 或 const T* 给 Ptr 就做到适配普通迭代器和 const 迭代器的 operator-> 了。

代码:

	/* 定义迭代器 */template<class T, class Ref, class Ptr>struct _list_iterator{typedef ListNode<T> Node;typedef _list_iterator<T, Ref, Ptr> Self;Node* _node;/* 解引用 */Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}};/* 链表 */template<class T>class list{typedef ListNode<T> Node;public:/* 迭代器 */typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;};

这里我们把传递的值增加一个 T* 和 const T* ,如此一来就做到了完美的适配

11 反向迭代器的实现

我们来看一下源代码是如何实现的:

反向迭代器其实就是对正向迭代器的一种封装——适配器模式

代码:

namespace yxt
{// Iterator是哪个容器的迭代器,reverse_iterator<Iterator>就可以// 适配出哪个容器的反向迭代器。复用的体现template<class Iterator, class Ref, class Ptr>class reverse_iterator{typedef reverse_iterator<Iterator, Ref, Ptr> Self;public:reverse_iterator(Iterator it):_it(it){}Ref operator*(){Iterator prev = _it;return *--prev;}Ptr operator->(){return &operator*();}Self& operator++(){--_it;return *this;}Self operator++(int){Self tmp(*this);--_it;return tmp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self tmp(*this);++_it;return tmp;}bool operator!=(const Self& l) const{return _it != l._it;}private:Iterator _it;};
}

Ⅲ . list 增删查改

01 在 pos 位置前插入 - insert

在 pos 位置插入,我们通过 pos 找到前驱 prev,之后创建新结点,再连接起来

代码实现:

		/* 在pos位置前插入 */void insert(iterator pos, const T& x){// 找到pos位置的结点Node* cur = pos._node;Node* cur_prev = cur->_prev;// 创建新结点Node* new_node = new Node(x);// 连接cur_prev->_next = new_node;new_node->_prev = cur_prev;new_node->_next = cur;cur->_prev = new_node;}

insert 以后,pos 是否失效?不会

优化:

		/* 在pos位置前插入 */iterator insert(iterator pos, const T& x){// 找到pos位置的结点Node* cur = pos._node;Node* cur_prev = cur->_prev;// 创建新结点Node* new_node = new Node(x);// 连接cur_prev->_next = new_node;new_node->_prev = cur_prev;new_node->_next = cur;cur->_prev = new_node;return iterator(new_node);}

有了 insert 之后,我们可以直接复用实现 push_back

代码实现:

		/* push_back */void push_back(const T& x){找尾结点并建立新结点//Node* _pTail = _pHead->_prev;//Node* new_node = new Node(x);新结点和尾结点相连//_pTail->_next = new_node;//new_node->_prev = _pTail;新结点和头结点相连//new_node->_next = _pHead;//_pHead->_prev = new_node;insert(end(), x);}

push_back 复用 insert,pos 我们给 end() 。因为 end() 是头结点 _pHead

在头结点前面插入,insert 的 cur_prev 就会代表尾结点,会在 cur_prev 后面插入 new_node

并完成连接,这就做到了尾插

02 push_front

代码实现:

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

03 删除 pos 位置的结点 erase

步骤如下:

① 找到 pos 的前驱和后继

② 释放 pos 位置的结点

③ 将已经删除的 pos 结点的前驱和后继连接

注意:我们还要防止哨兵位头结点 _pHead 被删的情况,头不小心卸了就没法玩了。

这里我还是习惯用暴力的方式去解决,用 assert 断言处理。

代码实现:

		/* 任意位置删除 */void erase(iterator pos){// 防止头结点被删assert(pos != end());// 找到pos位置的结点Node* cur = pos._node;Node* cur_prev = cur->_prev;Node* cur_next = cur->_next;// 删除pos位置的结点delete[] cur;cur = nullptr;// 连接cur_prev->_next = cur_next;cur_next->_prev = cur_prev;}

erase 以后,pos 是否失效?

一定会失效!因为结点的指针指向的结点被干掉了,这当然会失效

 我们可以学着文档里的处理方式 —— 返回刚刚被删除的元素的下一个元素

		/* 任意位置删除 */iterator erase(iterator pos){// 防止头结点被删assert(pos != end());// 找到pos位置的结点Node* cur = pos._node;Node* cur_prev = cur->_prev;Node* cur_next = cur->_next;// 删除pos位置的结点delete[] cur;cur = nullptr;// 连接cur_prev->_next = cur_next;cur_next->_prev = cur_prev;return iterator(cur_next);}

04 pop_back

代码实现:

		/* 尾删 */void pop_back(){erase(_pHead->_prev);}

当然你也可以这么写:

/* 尾删 */
void pop_back() 
{erase(--end());  // 删除最后一个元素,即尾结点
}

05 pop_front

代码实现:

		/* 头删 */void pop_front(){erase(begin());}

Ⅳ . 拷贝构造和赋值重载

01 list 同样涉及深浅拷贝问题

这里的拷贝构造是深拷贝还是浅拷贝?

	void list_test2(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);list<int> l2(l1);for (auto e : l2)cout << e << " ";cout << endl;}

运行结果如下:

这里默认生成的拷贝构造是浅拷贝

浅拷贝导致 l1 和 l2 指向同一块地址,析构的时候导致同一块空间被释放两次

02 clear 清空链表中的所有数据

代码实现:

		/* 清空链表所有数据 */void clear(){iterator cur = begin();while (cur != end()){iterator del = cur++;delete del._node;}_pHead->_next = _pHead;_pHead->_prev = _pHead;}

测试:

	void list_test3(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);cout << "删除前:";print_list(l1);cout << "删除后:";l1.clear();print_list(l1);}

运行结果如下:

当然,这里的删除结点我们也可以用 erase 去完成。

用 erase 可以省去我们将其恢复 _pHead 的前驱和后继指向自己的操作。

简化:

		/* 清空链表所有数据 */void clear(){iterator cur = begin();while (cur != end()){erase(cur++);}}

 03 析构

代码实现:

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

实现好了析构函数,我们再回过头来测刚才 "逃过一劫" 的浅拷贝导致的两个结点指向同一地址的问题,现在问题就变得严重起来了,因为它会被析构两次:

	void list_test2(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);list<int> l2(l1);for (auto e : l2)cout << e << " ";cout << endl;}

运行结果:崩溃

自动生成的拷贝构造是浅拷贝,为了解决这个问题,我们需要手动实现一个深拷贝的拷贝构造!

04 拷贝构造

代码实现:传统写法

		/* 拷贝构造 */list(const list<T>& l){_pHead = new Node();_pHead->_next = _pHead;_pHead->_prev = _pHead;for (auto e : l)push_back(e);}

代码实现:现代写法

		list(const list<T>& l){_pHead = new Node();_pHead->_next = _pHead;_pHead->_prev = _pHead;list<T> tmp(l.begin(), l.end());swap(_pHead, tmp._pHead);}

05 赋值重载

代码实现:传统写法

		/* 赋值(传统写法) */list<T>& operator=(list<T> l){if (this != &l){clear();for (auto e : l)push_back(e);}return *this;}

 代码实现:现代写法

		/* 赋值(现代写法) */list<T>& operator=(list<T> l){swap(_pHead, l._pHead);return *this;}

Ⅴ . 完整代码

list.h

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;namespace yxt
{/* 建立结点 */template<class T>struct ListNode{T _data;ListNode<T>* _next;		// 指向后继节点ListNode<T>* _prev;		// 指向前驱节点/* 结点初始化 */ListNode(const T& data = T()):_data(data), _next(nullptr), _prev(nullptr){}};/* 定义迭代器 */template<class T, class Ref, class Ptr>struct _list_iterator{typedef ListNode<T> Node;typedef _list_iterator<T, Ref, Ptr> Self;Node* _node;/* 迭代器的构造 */_list_iterator(Node* x):_node(x){}/* ++it */Self& operator++(){_node = _node->_next;return *this;}/* it++ */Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}/* --it */Self& operator--(){_node = _node->_prev;return *this;}/* it-- */Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}/* 解引用 */Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}/* != */bool operator!=(const Self& it){return _node != it._node;}};///* 定义const迭代器 *///template<class T>//struct _const_list_iterator//{//	typedef ListNode<T> Node;//	Node* _node;//	/* 迭代器的构造 *///	_const_list_iterator(Node* x)//		:_node(x)//	{}//	/* ++it *///	_const_list_iterator<T>& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	/* it++ *///	_const_list_iterator<T>& operator++(int)//	{//		_const_list_iterator<T> tmp(*this);//		_node = _node->_next;//		return tmp;//	}//	/* 解引用 *///	const T& operator*()//	{//		return _node->_data;//	}//	/* != *///	bool operator!=(const _const_list_iterator<T>& it)//	{//		return _node != it._node;//	}//};/* 链表 */template<class T>class list{typedef ListNode<T> Node;public:/* 迭代器 */typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return iterator(_pHead->_next);}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(_pHead->_next);}const_iterator end() const{return const_iterator(_pHead);}/* 构造函数 */list(){_pHead = new Node();_pHead->_next = _pHead;		// 默认指向头结点_pHead->_prev = _pHead;		// 默认指向头结点    }/* push_back */void push_back(const T& x){找尾结点并建立新结点//Node* _pTail = _pHead->_prev;//Node* new_node = new Node(x);新结点和尾结点相连//_pTail->_next = new_node;//new_node->_prev = _pTail;新结点和头结点相连//new_node->_next = _pHead;//_pHead->_prev = new_node;insert(end(), x);}/* push_front */void push_front(const T& x){insert(begin(), x);}/* 在pos位置前插入 */iterator insert(iterator pos, const T& x){// 找到pos位置的结点Node* cur = pos._node;Node* cur_prev = cur->_prev;// 创建新结点Node* new_node = new Node(x);// 连接cur_prev->_next = new_node;new_node->_prev = cur_prev;new_node->_next = cur;cur->_prev = new_node;return iterator(new_node);}/* 任意位置删除 */iterator erase(iterator pos){// 防止头结点被删assert(pos != end());// 找到pos位置的结点Node* cur = pos._node;Node* cur_prev = cur->_prev;Node* cur_next = cur->_next;// 删除pos位置的结点delete[] cur;cur = nullptr;// 连接cur_prev->_next = cur_next;cur_next->_prev = cur_prev;return iterator(cur_next);}/* 尾删 */void pop_back(){erase(_pHead->_prev);}/* 头删 */void pop_front(){erase(begin());}/* 清空链表所有数据 */void clear(){iterator cur = begin();while (cur != end()){erase(cur++);}}/* 析构 */~list(){clear();delete _pHead;_pHead = nullptr;}template<class InputInterator>list(InputInterator first, InputInterator last){_pHead = new Node();_pHead->_next = _pHead;_pHead->_prev = _pHead;while (first != last){push_back(*first);++first;}}/* 拷贝构造(现代写法) */list(const list<T>& l){_pHead = new Node();_pHead->_next = _pHead;_pHead->_prev = _pHead;list<T> tmp(l.begin(), l.end());swap(_pHead, tmp._pHead);}/* 拷贝构造(传统写法) */list(const list<T>& l){_pHead = new Node();_pHead->_next = _pHead;_pHead->_prev = _pHead;for (auto e : l)push_back(e);}/* 赋值(传统写法) */list<T>& operator=(list<T> l){if (this != &l){clear();for (auto e : l)push_back(e);}return *this;}/* 赋值(现代写法) */list<T>& operator=(list<T> l){swap(_pHead, l._pHead);return *this;}private:Node* _pHead;};
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"namespace yxt
{void print_list(const list<int>& l){list<int>::const_iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;}void list_test1(){list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);print_list(l);}void list_test2(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);list<int> l2(l1);for (auto e : l2)cout << e << " ";cout << endl;}void list_test3(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);cout << "删除前:";print_list(l1);cout << "删除后:";l1.clear();print_list(l1);}
}int main()
{//yxt::list_test1();yxt::list_test2();//yxt::list_test3();return 0;
}

reverse_list.h

#pragma once
#include"list.h"namespace yxt
{// Iterator是哪个容器的迭代器,reverse_iterator<Iterator>就可以// 适配出哪个容器的反向迭代器。复用的体现template<class Iterator, class Ref, class Ptr>class reverse_iterator{typedef reverse_iterator<Iterator, Ref, Ptr> Self;public:reverse_iterator(Iterator it):_it(it){}Ref operator*(){Iterator prev = _it;return *--prev;}Ptr operator->(){return &operator*();}Self& operator++(){--_it;return *this;}Self operator++(int){Self tmp(*this);--_it;return tmp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self tmp(*this);++_it;return tmp;}bool operator!=(const Self& l) const{return _it != l._it;}private:Iterator _it;};
}


http://www.ppmy.cn/news/1513924.html

相关文章

每日一问:深入理解MySQL中的锁机制

每日一问&#xff1a;深入理解MySQL中的锁机制 MySQL作为最流行的关系型数据库管理系统之一&#xff0c;其锁机制在保证数据一致性和并发性方面发挥了关键作用。MySQL的锁机制复杂且多样&#xff0c;涵盖了表级锁、行级锁、共享锁、排他锁、意向锁等多个层面。理解这些锁及其互…

CSS的:required和:optional伪类:提升表单可访问性与用户体验

在Web表单设计中&#xff0c;清晰地指示哪些字段是必填的&#xff0c;哪些是可选的&#xff0c;对于提升用户体验和表单的可访问性至关重要。CSS提供了两个非常有用的伪类&#xff1a;:required和:optional&#xff0c;它们允许开发者为必填和非必填的表单输入字段应用特定的样…

达梦表字段、字段类型,精度比对及更改字段SQL生成

达梦表字段、字段类型&#xff0c;精度比对及更改字段SQL生成&#xff1a; 依赖 <!-- 达梦 Connector --><dependency><groupId>com.dameng</groupId><artifactId>DmJdbcDriver18</artifactId><version>8.1.3.62</version>&l…

JavaEE:http请求 | 同步与异步请求 | 跨域问题 | axios框架 有这一篇就够!

前言 HTTP请求是现代Web开发中前后端沟通的基础。在开发过程中&#xff0c;开发者面临同步与异步请求的选择、跨域问题的挑战以及选择合适的HTTP库等问题。同步请求简单却往往阻塞用户界面&#xff0c;而异步请求能提高效率但增加复杂性。跨域问题则源自浏览器的同源政策&…

大模型,读论文,提示词:让任何人,任何时间,读懂,任何领域,任何论文

大模型&#xff0c;读论文&#xff0c;提示词&#xff1a;让任何人&#xff0c;任何时间&#xff0c;读懂&#xff0c;任何领域&#xff0c;任何论文 为什么要读论文&#xff1f;使用装备秒懂大纲提出背景结构化分析问题解法拆解到点全流程分析画出分析性关联图理解数学公式创意…

如何从电脑/外部硬盘驱动器/USB 驱动器/内存卡恢复数据?

奇客数据恢复软件将向您展示如何使用此 PC 模块从桌面、回收站、特定文件夹、逻辑驱动器、丢失的分区和未分配的空间中检索已删除的文件。 此 PC 显示您 PC 上所有检测到的驱动器和设备&#xff0c;包括外部硬盘驱动器、可移动 USB 驱动器、内存卡等。 您可以从逻辑分区、损坏…

【Qt从摄像头视频中获取数据】

有时候需要在视频上画图&#xff0c;所以需要能获取到每一帧视频数据。 以前从视频文件或视频流中得到帧&#xff0c;一般都是使用qt ffmpeg或qt vlc。 qt对显示处理视频大体有以下方法&#xff1a; QMediaPlayer QVideoWidget 这种方法只适合简单的显示视频功能&#xff…

亚信科技转型持久战:扎根行业大模型,深耕行业数字化

有人说&#xff1a;“AI大模型时代&#xff0c;每个行业和产品都值得重新做一遍。” 深以为然。自大模型2023年迅速崛起以来&#xff0c;AI技术不断取得突破&#xff0c;并开始深刻影响多个领域。这其中&#xff0c;AI大模型如何从通用走向垂直行业成为当下产业界最为关心的话…