【C++第十课 - List】List的使用、list底层实现、list的const迭代器实现

2024-06-19 20:44
文章标签 c++ 实现 使用 底层 list const 迭代 第十课

本文主要是介绍【C++第十课 - List】List的使用、list底层实现、list的const迭代器实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

  • 一、List的使用
    • 构造函数
      • 1、遍历
      • 2、reverse
      • 3、merge
      • 4、unique
      • 5、sort
      • 6、remove
      • 7、splice
  • 二、底层实现
      • 2、迭代器
      • 3、迭代器的补充
      • 4、insert
      • 5、push_front
      • 6、erase
      • 7、析构和clear
      • 8、拷贝构造
      • 9、赋值=
      • 10、const迭代器
      • 11、反向迭代器

一、List的使用

补充
需要使用类域指向的：
1、内部类
2、类里面typedef的

构造函数

（1）构造一个空的list
（2）构造一个list，它里面的数据是n个val
（3）用迭代区间构造list
（4）用已有的一个list构造另一个list
在这里插入图片描述

List就是一个带头双向循环列表

List不支持[]
没有扩容什么的概念了

1、遍历

（1）迭代器
在这里插入图片描述
在这里插入图片描述

（2）范围for
但范围for的底层和迭代器没有区别

	list<double> l2(5, 6.6);for (auto e : l2){cout << e << " ";}cout << endl;

在这里插入图片描述

2、reverse

逆置
在这里插入图片描述

	list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);list<int>::iterator it = l1.begin();while (it != l1.end()){cout << *it << " ";it++;}cout << endl;l1.reverse();for (auto e : l1){cout << e << " ";}cout << endl;

在这里插入图片描述

3、merge

归并：将两个有序的列表归并成一个有序的

使用merge的时候，可以先对列表进行sort排序
在这里插入图片描述

void test2()
{list<int> l1;l1.push_back(3);l1.push_back(5);l1.push_back(2);l1.push_back(9);l1.sort();for (auto e : l1){cout << e << " ";}cout << endl;list<int> l2;l2.push_back(13);l2.push_back(15);l2.push_back(22);l2.push_back(19);l2.sort();for (auto e : l2){cout << e << " ";}cout << endl;l1.merge(l2);for (auto e : l1){cout << e << " ";}cout << endl;
}

在这里插入图片描述

4、unique

去重：一般要求有序，无序必须相同的值是挨着的
在这里插入图片描述

void test3()
{list<int> l1;l1.push_back(3);l1.push_back(5);l1.push_back(2);l1.push_back(9);l1.push_back(2);l1.push_back(2);l1.push_back(9);l1.sort();for (auto e : l1){cout << e << " ";}cout << endl;l1.unique();for (auto e : l1){cout << e << " ";}cout << endl;
}

在这里插入图片描述

5、sort

排序

list不能用算法库里面的sort，算法库里面的sort是快排（需要连续的空间，原地排序，不稳地排序，O(n2)），list自带的sort是归并(稳定排序，O(nlogn))
vector的排序用的是递归
实际中排序：拷贝到vector，进行排序，排完再assign到list里面

在这里插入图片描述

6、remove

相当于先find再删
在这里插入图片描述

void test4()
{list<int> l1;l1.push_back(3);l1.push_back(5);l1.push_back(2);l1.push_back(100);l1.push_back(9);for (auto e : l1){cout << e << " ";}cout << endl;l1.remove(100);for (auto e : l1){cout << e << " ";}cout << endl;
}

在这里插入图片描述

7、splice

把一个链表的值转移到另一个链表，是把一个链接里面的节点直接拿走
在这里插入图片描述

void test5()
{list<int> l1;l1.push_back(3);l1.push_back(5);l1.push_back(2);l1.push_back(100);l1.push_back(9);cout << "l1:";for (auto e : l1){cout << e << " ";}cout << endl;list<int> l2;l2.push_back(13);l2.push_back(15);l2.push_back(22);l2.push_back(19);cout << "l2:";for (auto e : l2){cout << e << " ";}cout << endl;l1.splice(l1.begin(), l2);cout << "l1:";for (auto e : l1){cout << e << " ";}cout << endl;cout << "l2:";for (auto e : l2){cout << e << " ";}cout << endl;
}

在这里插入图片描述

二、底层实现

1、带头双向循环列表

struct和class的区别
（1）继承权限：struct默认为public，而class默认的为private。
（2）访问权限：struct默认的成员变量访问控制权限是public，而class默认的成员变量访问权限则为private。
（3）class可以用于定于template，struct不能。
列表节点的定义

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

列表的定义

template<class T>class list{public:typedef ListNode<T> Node;typedef __listiterator<T> iterator;list(){_head = new Node;_head->_prev = _head;_head->_next = _head;}void push_back(const T& x){Node* tmp = new Node(x);Node* tail = _head->_prev;tail->_next = tmp;tmp->_prev = tail;_head->_prev = tmp;tmp->_next = _head;}private:Node* _head;};

2、迭代器

Node是自定义类型，但Node*是内置类型，是要改变的是Node*的指向，不能改变指针的运算符
对Node*类型进行运算符重载，但Node*是内置类型无法运算符重载，因此需要套一个类__listiterator

namespace zyh
{template<class T>struct ListNode {ListNode(const T& x = T()):_prev(nullptr),_next(nullptr),_data(x){}ListNode<T>* _prev;ListNode<T>* _next;T _data;};template<class T>struct __listiterator{typedef ListNode<T> Node;typedef __listiterator self;Node* _node;__listiterator(Node* node):_node(node){}self& operator++(){_node = _node->_next;return *this;}bool operator!=(const self& x){return _node != x._node;}T operator*(){return _node->_data;}};template<class T>class list{public:typedef ListNode<T> Node;typedef __listiterator<T> iterator;list(){_head = new Node;_head->_prev = _head;_head->_next = _head;}void push_back(const T& x){Node* tmp = new Node(x);Node* tail = _head->_prev;tail->_next = tmp;tmp->_prev = tail;_head->_prev = tmp;tmp->_next = _head;}iterator begin(){//return iterator(_head->_next);return _head->_next;}iterator end(){return _head;}private:Node* _head;};void list_test1(){list<int> lt1;lt1.push_back(10);lt1.push_back(1);lt1.push_back(2);lt1.push_back(9);lt1.push_back(3);list<int>::iterator it = lt1.begin();while (it != lt1.end()){cout << *it << " ";++it;}cout << endl;}
}

在这里插入图片描述

3、迭代器的补充

这些都是在__listiterator类里面
（1）前置++：self& operator++()

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

（2）后置++：self& operator++(int)

		self& operator++(int){//Node* tmp = _node;self tmp(*this);_node = _node->_next;return tmp;

（3）前置- -：self& operator--()

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

（3）后置- -：self& operator--(int)

		self& operator--(int){Node* tmp = _node;_node = _node->_prev;return tmp;}

迭代器这个类里面没有析构函数
默认的析构函数对类里面的成员是不做处理的
这个类里面没有写析构函数，是因为这个类只是listnode的节点给它访问，他不能把人家删除吧

4、insert

不存在迭代器失效的问题

		void insert(const iterator pos, const T& x){Node* tmp = new Node(x);Node* forward = (pos._node)->_prev;forward->_next = tmp;tmp->_prev = forward;tmp->_next = pos._node;(pos._node)->_prev = tmp;}

5、push_front

不存在迭代器失效问题

		iterator push_front(const T& x){Node* tmp = new Node(x);tmp->_next = begin();tmp->_prev = end();end()._node->_next = tmp;begin()._node->_prev = tmp;return tmp;}

6、erase

pos迭代器失效问题

		iterator erase(iterator& pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;delete pos._node;prev->_next = next;next->_prev = prev;return next;}

7、析构和clear

析构：列表的所以节点要释放，哨兵位的头节点也要释放
clear：只释放列表的所以节点，哨兵位的头节点不释放

clear

		bool empty(){if (_head->_next == _head->_prev)return true;elsereturn false;}void clear(){if (empty())return;Node* cur = _head->_next;while (cur != _head){Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;cur = next;}}

问题：写的过于复杂，可以复用erase

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

注意：it = erase(it)这里一定要再赋值给it，因为erase之后的it就是失效了

析构

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

8、拷贝构造

没有加const迭代器

		//list(const list<T>& x)list(list<T>& x){_head = new Node;_head->_prev = _head;_head->_next = _head;iterator it = x.begin();while (it != x.end()){push_back(*it);++it;}}

9、赋值=

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

10、const迭代器

传参的时候会有const的对象

const迭代器不是自身不能修改，是指向的内容不能被修改
const迭代器不是const对象，自己可以修改

const迭代器 - 第一版
与普通迭代不同的地方
__const_listiterator类里面
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

	template<class T>struct __const_listiterator{typedef ListNode<T> Node;typedef __const_listiterator self;Node* _node;__const_listiterator(Node* node):_node(node){}self& operator++(){_node = _node->_next;return *this;}self& operator++(int){//Node* tmp = _node;self tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const self& x){return _node != x._node;}const T& operator*(){return _node->_data;}self& operator--(){_node = _node->_prev;return *this;}self& operator--(int){Node* tmp = _node;_node = _node->_prev;return tmp;}};

list类里面
在这里插入图片描述

	template<class T>class list{public:typedef ListNode<T> Node;typedef __listiterator<T> iterator;typedef __const_listiterator<T> const_iterator;list(){_head = new Node;_head->_prev = _head;_head->_next = _head;}//list(const list<T>& x)list(list<T>& x){_head = new Node;_head->_prev = _head;_head->_next = _head;iterator it = x.begin();while (it != x.end()){push_back(*it);++it;}}list<T>& operator=(list<T> lt){swap(lt);return *this;}void push_back(const T& x){Node* tmp = new Node(x);Node* tail = _head->_prev;tail->_next = tmp;tmp->_prev = tail;_head->_prev = tmp;tmp->_next = _head;}iterator begin(){//return iterator(_head->_next);return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}iterator insert(const iterator pos, const T& x){Node* tmp = new Node(x);Node* forward = (pos._node)->_prev;forward->_next = tmp;tmp->_prev = forward;tmp->_next = pos._node;(pos._node)->_prev = tmp;return tmp;}//iterator push_front(const T& x)//{//	Node* tmp = new Node(x);//	tmp->_next = begin();//	tmp->_prev = end();//	end()._node->_next = tmp;//	begin()._node->_prev = tmp;//	return tmp;//}iterator push_front(const T& x){return insert(begin(), x);}iterator erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;delete pos._node;prev->_next = next;next->_prev = prev;return next;}iterator pop_back(){return erase(--end());}iterator pop_front(){return erase(begin());}bool empty(){if (_head->_next == _head->_prev)return true;elsereturn false;}//void clear()//{//	if (empty())//		return;//	Node* cur = _head->_next;//	while (cur != _head)//	{//		Node* prev = cur->_prev;//		Node* next = cur->_next;//		prev->_next = next;//		next->_prev = prev;//		delete cur;//		cur = next;//	}//}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}private:Node* _head;};

问题：迭代器的类和const迭代器的类两个类有点冗余
const迭代器 - 第二版

template<class T, class Ref>struct __listiterator{typedef ListNode<T> Node;typedef __listiterator self;Node* _node;__listiterator(Node* node):_node(node){}self& operator++(){_node = _node->_next;return *this;}self& operator++(int){//Node* tmp = _node;self tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const self& x){return _node != x._node;}Ref operator*(){return _node->_data;}self& operator--(){_node = _node->_prev;return *this;}self& operator--(int){Node* tmp = _node;_node = _node->_prev;return tmp;}};

在这里插入图片描述

在const迭代器中实现->的运算符重载
当ListNode里面的data是个结构体时，使用->进行访问

11、反向迭代器

这篇关于【C++第十课 - List】List的使用、list底层实现、list的const迭代器实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1076103。

相关文章

中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
使用SecondaryNameNode恢复NameNode的数据

使用SecondaryNameNode恢复NameNode的数据

1）需求： NameNode进程挂了并且存储的数据也丢失了，如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2）故障模拟 （1）kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 （2）删除NameNode存储的数据（/opt/module/hadoop-3.1.4/data/tmp/dfs/na
阅读更多...
Hadoop数据压缩使用介绍

Hadoop数据压缩使用介绍

一、压缩原则 （1）运算密集型的Job，少用压缩 （2）IO密集型的Job，多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1）为了支持多种压缩/解压缩算法，Hadoop引入了编码/解码器 2）要在Hadoop中启用压缩，可以配置如下参数
阅读更多...
Makefile简明使用教程

Makefile简明使用教程

文章目录 规则makefile文件的基本语法：加在命令前的特殊符号：.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具，常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2