C++第二十五弹---从零开始模拟STL中的list(下)

devtools/2024/9/23 5:06:28/

 ✨个人主页： 熬夜学编程的小林

💗系列专栏： 【C语言详解】 【数据结构详解】【C++详解】

目录

1、函数补充

2、迭代器完善

3、const迭代器

总结

1、函数补充

拷贝构造

思路：

  • 先构造一个头结点，然后将 lt 类中的元素依次尾插到新的结点上。
void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}
list(const list<T>& lt)
{empty_init();//构造一个头结点for (auto& x : lt){push_back(x);}
}

 {}初始化构造

思路：

  • 先构造一个头结点，然后将 il 类中的元素依次尾插到新的结点上。
list(initializer_list<T> il)
{empty_init();for (auto& x : il){push_back(x);}
}

赋值操作符重载

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

大小相关函数

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

clear()

清空list的内容，保留头结点。

//清空数据
void clear()
{iterator it = begin();while (it != end()){it = erase(it);//更新迭代器}
}

~list()

析构函数，清空list的内容并释放头结点。

~list()
{clear();//清空内容函数delete _head;//释放头结点_head = nullptr;//置空
}

2、迭代器完善

前面我们处理的都是内置类型的情况，如果我们出现自定义类型，如何解决？

自定义类型举例：

struct A
{int _a1;int _a2;A(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}
};

 首先我们先看看几种自定义类型的尾插方式:

void test_list3()
{list<A> lt;A aa1(1, 1);//实例化对象A aa2{ 2,2 };//多参数的隐式类型转换，C++11lt.push_back(aa1);//有名对象实例化lt.push_back(aa2);lt.push_back(A(3, 3));//匿名对象lt.push_back({ 4,4 });//多参数的隐式类型转换，C++11
}

 对自定义类型进行遍历：

list<A>::iterator it = lt.begin();
while (it != lt.end())
{cout << *it << " ";//自定义类型输出不了it++;
}
cout << endl;

A是自定义类型，不支持留插入，我们解引用得到的_data是A的对象 。在结构体中我们获取到自定义类型的对象可以通过 . 进行访问内部成员，此处我们也可以使用 . 进行访问内部成员。

cout << (*it)._a1 << ":" << (*it)._a2 << " ";

但是如果这么使用会有一点别捏，我们在自定义类型中，也可以通过自定义类型的地址来访问成员，即通过 ->访问，此处我们也可以通过 ->进行访问，因此我们需要重载一个operator->()函数 。

迭代器类中重载operator->

T* operator->()
{return &_node->_data;//取数据的地址
}

使用->访问元素

cout << it->_a1 << ":" << it->_a2 << " ";

使用重载函数版

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

测试结果：

注意：

这里隐藏了一个箭头，一个是重载，一个是原生指针的访问操作。

当重载 operator->，不会直接返回成员的值，而是应该返回一个指针，这个指针指向的对象包含我们想要访问的成员。当使用 ->运算符时，C++ 会自动和透明地调用重载的 operator-> 并继续 “链式” 访问成员，而不需要程序员显示地添加多余的箭头。 

3、const迭代器

 我们上一弹写的普通迭代器对于const对象是无法编译成功的，const不能调用非const成员函数(权限放大)。

下面我们则实现一个const迭代器的类。

与普通迭代器类似，我们需要先在list类中重命名一个const迭代器

typedef ListConstIterator<T> const_iterator;//const迭代器类const_iterator begin() const
{return const_iterator(_head->_next);//匿名对象//return _head->_next;//单参数类型转换
}
const_iterator end() const
{return const_iterator(_head);
}

注意：

const迭代器名字不能写成 const iterator，因为const迭代器的本质是迭代器指向的内容不能修改，而不是迭代器本身不能修改，const_iterator这样定义是迭代器不能修改，内容还是可以修改的

实现const_iterator类有两种方式，如下：

方式一(单独实现一个新的类，修改普通迭代器的部分地方)：

template<class T>
struct ListConstIterator
{typedef ListConstIterator<T> Self;//对迭代器类重定义typedef ListNode<T> Node;Node* _node;//构造ListConstIterator(Node* node):_node(node){}const T& operator*()//只能访问，不能修改值{return _node->_data;}const T* operator->(){return &_node->_data;//返回指针}//前置++ Self& operator++(){_node = _node->_next;return *this;}//后置++Self operator++(int){Self tmp(*this);_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}
};

我们可以看到，const迭代器与普通迭代器的区间只在operator*与operator->的返回的类型上，那么我们是不是可以将两个类封装成一个模板类呢？？？

//普通迭代器和const迭代器只有两个返回值不同，因此我们使用模板封装
template<class T, class Ref, class Ptr>//reference引用 point指针
struct ListIterator
{typedef ListIterator<T, Ref, Ptr> Self;//对迭代器类重定义typedef ListNode<T> Node;Node* _node;//构造ListIterator(Node* node):_node(node){}//T& operator*()//遍历及修改Ref operator*(){return _node->_data;}//T* operator->()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& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}
};

合并之后的三个类模板参数：

  • T：链表结点存储_data值的数据类型
  • Ref：通过迭代器访问数据时的返回类型，可以是T&或者const T&。
  • Ptr：通过迭代器访问数据的指针类型，可以是T*或者const T*。

链表实例化如下：

typedef ListIterator<T, T&, T*> iterator;//普通迭代器类typedef ListIterator<T, const T&, const T*> const_iterator;//const迭代器类

 list实现全部代码

namespace lin
{//链表基本结构template<class T>struct ListNode{ListNode<T>* _prev;ListNode<T>* _next;T _data;ListNode(const T& val = T())//初始化值构造:_prev(nullptr),_next(nullptr),_data(val){}};//原版普通迭代器//迭代器操作类 方法都要被访问，使用struct//template<class T>//struct ListIterator//{//	typedef ListIterator<T> Self;//对迭代器类重定义//	typedef ListNode<T> Node;//	Node* _node;//	//构造//	ListIterator(Node* node)//		:_node(node)//	{}//	T& operator*()//遍历及修改//	{//		return _node->_data;//	}//	T* operator->()//	{//		return &_node->_data;//返回指针//	}//	//前置++ //	Self& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	//后置++//	Self operator++(int)//	{//		Self tmp(*this);//		_node = _node->_next;//		return *this;//	}//	bool operator!=(const Self& it)//	{//		return _node != it._node;//	}//	bool operator==(const Self& it)//	{//		return _node == it._node;//	}//};//原版const迭代器//template<class T>//struct ListConstIterator//{//	typedef ListConstIterator<T> Self;//对迭代器类重定义//	typedef ListNode<T> Node;//	Node* _node;//	//构造//	ListConstIterator(Node* node)//		:_node(node)//	{}//	const T& operator*()//只能访问，不能修改值//	{//		return _node->_data;//	}//	const T* operator->()//	{//		return &_node->_data;//返回指针//	}//	//前置++ //	Self& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	//后置++//	Self operator++(int)//	{//		Self tmp(*this);//		_node = _node->_next;//		return *this;//	}//	Self& operator--()//	{//		_node = _node->_prev;//		return *this;//	}//	Self operator--(int)//	{//		Self tmp(*this);//		_node = _node->_prev;//		return tmp;//	}//	bool operator!=(const Self& it)//	{//		return _node != it._node;//	}//	bool operator==(const Self& it)//	{//		return _node == it._node;//	}//};//普通迭代器和const迭代器只有两个返回值不同，因此我们使用模板封装template<class T, class Ref, class Ptr>//reference引用 point指针struct ListIterator{typedef ListIterator<T,Ref,Ptr> Self;//对迭代器类重定义typedef ListNode<T> Node;Node* _node;//构造ListIterator(Node* node):_node(node){}//T& operator*()//遍历及修改Ref operator*(){return _node->_data;}//T* operator->()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& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};template<class T>class list{typedef ListNode<T> Node;//将链表结构重命名public://普通版本//typedef ListIterator<T> iterator;//需要被访问，放在public内//typedef ListConstIterator<T> const_iterator;//const迭代器类//类模板typedef ListIterator<T,T&,T*> iterator;//需要被访问，放在public内typedef ListIterator<T,const T&,const T*> const_iterator;//const迭代器类//构造哨兵结点void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list()//默认构造{empty_init();//创建哨兵头结点}size_t size(){return _size;}void clear()//清空数据，不销毁哨兵头结点{iterator it = begin();while (it != end()){it = erase(it);}}~list()//析构函数{clear();delete _head;_head = nullptr;}list(const list<T>& lt)//拷贝构造{empty_init();//创建头结点，然后进行尾插for (auto& x : lt){push_back(x);}}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;}iterator begin() {return iterator(_head->_next);//匿名对象//return _head->_next;//单参数类型转换}iterator end() {return iterator(_head);}//解决打印修改值问题const_iterator begin() const{return const_iterator(_head->_next);//匿名对象//return _head->_next;//单参数类型转换}const_iterator end() const{return const_iterator(_head);}//单独实现的尾插//void push_back(const T& val)//{//	//tail //	Node* newnode = new Node(val);//	Node* tail = _head->_prev;//	tail->_next = newnode;//	newnode->_prev = tail;//	newnode->_next = _head;//	_head->_prev = newnode;//}void insert(iterator pos, const T& val)//在pos位置前插入val{Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;//prev newnode curnewnode->_next = cur;cur->_prev = newnode;prev->_next = newnode;newnode->_prev = prev;_size++;}iterator erase(iterator pos)//删除pos位置，防止迭代器失效，返回迭代器后一个位置{Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;//prev nextprev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}//调用insert函数void push_back(const T& val){//insert(--begin(),val);//不能使用+n，在--begin前面插入insert(end(), val);//end()前面}void push_front(const T& val){insert(begin(), val);//begin()前面插入}void pop_back(){erase(--end());//end()前面删除}void pop_front(){erase(begin());//begin()位置删除}private:Node* _head;//链表成员变量size_t _size;//链表大小};
}

总结


本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！


http://www.ppmy.cn/devtools/49681.html

相关文章

请求 响应

请求 响应

在web的前后端分离开发过程中&#xff0c;前端发送请求给后端&#xff0c;后端接收请求&#xff0c;响应数据给前端 请求 前端发送数据进行请求 简单参数 原始方式 在原始的web程序中&#xff0c;获取请求参数&#xff0c;需要通过HttpServletRequest 对象手动获取。 代码…
阅读更多...
c++工程实践——实际工程中的文件读取和日期处理的小问题

c++工程实践——实际工程中的文件读取和日期处理的小问题

一、问题 在实际开发中遇到了两个小问题&#xff0c;一个是文件流的读写中的长度和结尾判断;另外一个是C11库std::chrono::duration的数据类型的问题。这两个问题导致了两个结果&#xff1a; 1、流结尾判断不准确&#xff0c;多读一帧导致长度判断恒为正确&#xff0c;文件不加…
阅读更多...
四六级考前突击之主题词预测

四六级考前突击之主题词预测

考前主题词预测 时政类 Digital Economy 数字经济 (Digitalization数字化) Hong Kong Zhuhai-Macau Bridge 港珠澳大桥 Greater Bay Area 大湾区 Poverty Alleviation 扶贫 Anti-corruption campaign 反腐斗争 Rural Revitalization(注入活力) Strategy(战略,策略) 乡村振兴…
阅读更多...
【Java基础】OkHttp 超时设置详解

【Java基础】OkHttp 超时设置详解

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
Spring Boot：Java 应用开发高效之道

Spring Boot：Java 应用开发高效之道

Spring Boot 是一种革命性的框架&#xff0c;旨在简化 Java 应用的创建和部署过程。通过自动化配置和简化项目搭建流程&#xff0c;Spring Boot 大大加速了开发周期&#xff0c;让 Java 应用开发变得更加高效和便捷。 核心优势&#xff1a; 快速启动和简化配置&#xff1a;Spr…
阅读更多...
Incredibuild for Mac 来了！

Incredibuild for Mac 来了！

Mac 开发者在寻找适合自己需求的工具时可能会遇到一些困难&#xff0c;因为 Mac 操作系统相对封闭&#xff0c;不像其他系统那样开放和灵活。尽管如此&#xff0c;Mac 开发者在开发应用程序时的需求&#xff08;比如功能、效率等&#xff09;和使用其他操作系统的开发者是类似的…
阅读更多...
openresty安装并使用lua进行业务逻辑处理

openresty安装并使用lua进行业务逻辑处理

OpenResty 基础教程及Lua动态脚本实现 OpenResty 简介 OpenResty 是一个基于 Nginx 与 Lua 的高性能 Web 平台&#xff0c;它将 Nginx 的 C 模块和 Lua 脚本相结合&#xff0c;提供了一个强大的 Web 应用服务器和反向代理服务器。OpenResty 特别适合处理高并发的 Web 应用&am…
阅读更多...
OpenCV单词轮廓检测

OpenCV单词轮廓检测

OpenCV单词轮廓检测 0. 前言1. 策略分析2. 检测字符轮廓3. 检测单词轮廓相关链接 0. 前言 在根据文档图像执行单词转录时&#xff0c;通常第一步是识别图像中单词的位置。我们可以使用两种不同的方法识别图像中的单词&#xff1a; 使用 CRAFT、EAST 等深度学习技术使用基于 O…
阅读更多...
最新文章

Copyright @ 2022~2023