list(c++)

list介绍

list是STL容器中的容器,且元素在容器中的位置是分散的并与大小无关。list的底层是双向链表,其优势是在任意位置插入和删除元素的时间复杂度为O(1),但无法通过“下标[ ]”直接访问元素,需要通过从头(尾)遍历元素找到元素,多用于需要大量数据的插入和删除,且对数据的随机访问比较少。

list使用

一、list的构造

构造函数接口说明
list (size_type n, const value_type& val = value_type())
构造的 list 中包含 n 个值为 val 元素
list()
构造空的 list
list (const list& x)
拷贝构造函数
list (InputIterator first, InputIterator last)
[first, last) 区间中的元素构造 list

 

// list的构造
    list<int> l1;                         // 构造空的l1
    list<int> l2(4, 100);                 // l2中放4个值为100的元素
    list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end())左闭右开的区间构造l3
    list<int> l4(l3);                    // 用l3拷贝构造l4

    // 以数组为迭代器区间构造l5
    int array[] = { 16,2,77,29 };
    list<int> l5(array, array + sizeof(array) / sizeof(int));

    // 列表格式初始化C++11
    list<int> l6{ 1,2,3,4,5 };

二、list 的iterator的使用

 

接口说明
begin + end
返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器
rbegin
+ rend
返回第一个元素的 reverse_iterator, end 位置 返回最后一个元素下一个位 置的 reverse_iterator, begin 位置

 

// list迭代器的使用
// 注意:遍历链表只能用迭代器和范围for
void PrintList(const list<int>& l)
{
    // 注意这里调用的是list的 begin() const,返回list的const_iterator对象
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";
        // *it = 10; 编译不通过
    }

    cout << endl;
}

void TestList2()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    // 使用正向迭代器正向list中的元素
    // list<int>::iterator it = l.begin();   // C++98中语法
    auto it = l.begin();                     // C++11之后推荐写法
    while (it != l.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    // 使用反向迭代器逆向打印list中的元素
    // list<int>::reverse_iterator rit = l.rbegin();
    auto rit = l.rbegin();
    while (rit != l.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
}

三、list capacity

接口说明
empty
检测 list 是否为空,是返回 true ,否则返回 false
size
返回 list 中有效节点的个数

 四、list element access

接口说明
front
返回 list 的第一个节点中值的引用
back
返回 list 的最后一个节点中值的引用

五、list modifiers 

接口说明
push_front
list 首元素前插入值为 val 的元素
pop_front
删除 list 中第一个元素
push_back
list 尾部插入值为 val 的元素
pop_back
删除 list 中最后一个元素
insert
list position 位置中插入值为 val 的元素
erase
删除 list position 位置的元素
swap
交换两个 list 中的元素
clear
清空 list 中的有效元素
// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList3()
{
    int array[] = { 1, 2, 3 };
    list<int> L(array, array + sizeof(array) / sizeof(array[0]));

    // 在list的尾部插入4,头部插入0
    L.push_back(4);
    L.push_front(0);
    PrintList(L);

    // 删除list尾部节点和头部节点
    L.pop_back();
    L.pop_front();
    PrintList(L);
}

// insert /erase 
void TestList4()
{
    int array1[] = { 1, 2, 3 };
    list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));

    // 获取链表中第二个节点
    auto pos = ++L.begin();
    cout << *pos << endl;

    // 在pos前插入值为4的元素
    L.insert(pos, 4);
    PrintList(L);

    // 在pos前插入5个值为5的元素
    L.insert(pos, 5, 5);
    PrintList(L);

    // 在pos前插入[v.begin(), v.end)区间中的元素
    vector<int> v{ 7, 8, 9 };
    L.insert(pos, v.begin(), v.end());
    PrintList(L);

    // 删除pos位置上的元素
    L.erase(pos);
    PrintList(L);

    // 删除list中[begin, end)区间中的元素,即删除list中的所有元素
    L.erase(L.begin(), L.end());
    PrintList(L);

 // 交换l1和l2中的元素
    list<int> l2;
    l1.swap(l2);
    PrintList(l1);
    PrintList(l2);

    // 将l2中的元素清空
    l2.clear();
    cout << l2.size() << endl;
}

 六、list的迭代器失效

可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点的无 效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此list中进行插入 时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭 代器,其他迭代器不会受到影响
void TestListIterator1()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array+sizeof(array)/sizeof(array[0]));
    auto it = l.begin();
    while (it != l.end())
      {
      // erase()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给
        其赋值
        l.erase(it);
        ++it;
      }
}
// 改正
void TestListIterator()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array+sizeof(array)/sizeof(array[0]));
    auto it = l.begin();
    while (it != l.end())
    {
        l.erase(it++); // it = l.erase(it);
    }
}

 

模拟实现

一、节点

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

二、构造

        void empty_init()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
       //无参构造
		list()
		{
			empty_init();
		}
        //拷贝构造
		// lt2(lt1)
		list(const list<T>& lt)
		{
			empty_init();

			for (auto& e : lt)
			{
				push_back(e);
			}
		}
        //n个val构造
        list(size_t n, const T& val = T())
 		{
			empty_init();
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

三、迭代器

迭代器:类封装节点指针,重载运算符,模拟指针的行为

	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)
		{}

		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)
		{
			return _node != s._node;
		}

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



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

        iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

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

		const_iterator end() const
		{
			return const_iterator(_head);
		}

四、insert

        iterator insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(val);
			Node* prev = cur->_prev;

			// prev newnode cur
			prev->_next = newnode;
			newnode->_prev = prev;

			newnode->_next = cur;
			cur->_prev = newnode;
			++_size;

			return iterator(newnode);
		}

五、erase

        iterator erase(iterator pos)
		{
			assert(pos != end());

			Node* del = pos._node;
			Node* prev = del->_prev;
			Node* next = del->_next;

			prev->_next = next;
			next->_prev = prev;
			delete del;

			--_size;

			return iterator(next);
		}

六、头(尾)插(删)

        void push_back(const T& x)
		{
			/*Node* new_node = new Node(x);
			Node* tail = _head->_prev;

			tail->_next = new_node;
			new_node->_prev = tail;

			new_node->_next = _head;
			_head->_prev = new_node;*/

			insert(end(), x);
		}

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

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

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

七、析构

        ~list()
		{
			clear();

			delete _head;
			_head = nullptr;
		}

八、赋值运算符重载

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

九、clear

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/904720.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

开关灯问题(c语言)

样例&#xff1a;10 10 &#xff0c;输出&#xff1a;1&#xff0c;4&#xff0c;9 5 5 &#xff0c;输出&#xff1a;1&#xff0c;4 代码如下 #include<stdio.h> //引入bool值的概念 #include<stdbool.h> int main() {int n 0;//n为灯的数量int m 0;…

扫雷游戏(C语言详解)

扫雷游戏&#xff08;C语言详解&#xff09; 放在最前面的1、前言&#xff08;扫雷游戏的简介&#xff09;2、扫雷游戏的规则&#xff08;简易版&#xff09;3、代码实现&#xff08;3.1&#xff09;提醒一下&#xff1a;( i ) 提醒1&#xff1a;( ii ) 提醒2&#xff1a; &…

在面试了些外包以后,我有了些自己的思考

大家好&#xff0c;我是洋子&#xff0c;最近公司在降本增效&#xff0c;需要把外包从北京迁移到陕西的某新一线城市&#xff0c;其实就是变相裁员&#xff0c;减少外包的成本&#xff0c;裁掉现有的员工&#xff0c;重新招聘新人 在整个测试行业&#xff0c;外包测试的比重是…

论文 | Ignore Previous Prompt: Attack Techniques For Language Models

这篇论文探讨了针对大型语言模型&#xff08;LLM&#xff09;的“提示注入”攻击&#xff0c;并提出了一种名为 PROMPTINJECT 的框架来研究这类攻击。 论文的主要内容包括&#xff1a;1. 提示注入攻击&#xff1a; 论文定义了“提示注入”的概念&#xff0c;即通过在用…

Django-中间件

定义&#xff1a; 编写中间件&#xff1a; 注册中间件&#xff1a; 添加中间件&#xff1a; 1.在项目目录下添加一个文件夹&#xff08;名字随意&#xff09;&#xff0c;然后文件夹下创建.py文件 2.将中间件添加到setting文件中 MIDDLEWARE [django.middleware.security.Se…

MBR20100CT-ASEMI半塑封肖特基二极管MBR20100CT

编辑&#xff1a;ll MBR20100CT-ASEMI半塑封肖特基二极管MBR20100CT 型号&#xff1a;MBR20100CT 品牌&#xff1a;ASEMI 封装&#xff1a;TO-220 安装方式&#xff1a;插件 批号&#xff1a;最新 最大平均正向电流&#xff08;IF&#xff09;&#xff1a;20A 最大循环…

操作数据表

创建表 创建表语法&#xff1a; CREATE TABLE table_name ( field1 datatype [COMMENT 注释内容], field2 datatype [COMMENT 注释内容], field3 datatype ); 注意&#xff1a; 1. 蓝色字体为关键字 2. CREATE TABLE 是创建数据表的固定关键字&#xff0c;表…

一、ARMv8寄存器之通用、状态、特殊寄存器

ARMV8核心寄存器数量是非常大的&#xff0c;为了更好的学习&#xff0c;可以划分为以下几大类&#xff1a; 通用寄存器。这类寄存器主要是用来暂存数据和参与运算。通过load\store指令操作。状态寄存器。AArch64体系结构使用PSTATE寄存器表示当前处理器状态。特殊寄存器。有专门…

WPF+MVVM案例实战(六)- 自定义分页控件实现

文章目录 1、项目准备2、功能实现1、分页控件 DataPager 实现2、分页控件数据模型与查询行为3、数据界面实现 3、运行效果4、源代码获取 1、项目准备 打开项目 Wpf_Examples&#xff0c;新建 PageBarWindow.xaml 界面、PageBarViewModel.cs ,在用户控件库 UserControlLib中创建…

【Docker】构建Linux云桌面环境

目录 一、说明 二、离线安装Docker 1&#xff09;将下载的包上传到服务器上去 2&#xff09;安装docker 3) 启动docker 4&#xff09;配置加速器 三、安装云桌面镜像 四、启动云桌面 方式一&#xff1a;docker命令直接运行 方式二&#xff1a;docker-compose方式 五…

Easysearch 与 LLM 融合打造知识库系统

文章目录 一、LangChain 简介二、RAG 产生的背景及其局限性三、RAG 工作流程四、 Easysearch 结合 LLM 实现 RAG&#xff08;1&#xff09;Easysearch 简介&#xff08;2&#xff09;结合实现RAG 五、 Easysearch 结合 LLM 实现 RAG 的优势&#xff08;1&#xff09;提高检索准…

驱动-----adc

在key1.c的基础上进行对adc1.c进行编写 首先将文件里面的key全部改为adc 再修改一下设备号 按键和adc的区别是什么,按键只需要按一下就触发了,并且不需要返回一个值出来, adc要初始化,启动,返回值 以下是裸机adc的代码: #include <s3c2440.h> #include "ad…

快速生成高质量提示词,Image to Prompt 更高效

抖知书老师推荐&#xff1a; 随着 AI 技术的不断发展&#xff0c;视觉信息与语言信息之间的转换变得越来越便捷。在如今的数字化生活中&#xff0c;图像与文字的交互需求愈发旺盛&#xff0c;很多人都希望能轻松将图像内容直接转化为文本描述。今天我们来推荐一款实用的 AI 工…

FileLink跨网文件传输与传统文件传输对比

在数字化时代&#xff0c;文件传输已成为企业日常运营不可或缺的一部分。然而&#xff0c;随着企业规模的扩大和业务的复杂化&#xff0c;传统的文件传输方式逐渐暴露出诸多不足。本文将对比FileLink跨网文件传输与传统文件传输方式&#xff0c;揭示FileLink在高效性、安全性和…

渗透测试-百日筑基—文件上传篇特征截断渲染%00绕过——下篇

目录 day10-渗透测试文件上传篇&绕过&特征&截断&渲染 一、黑名单大小写绕过代码分析 1、获取文件后缀名进行判断&#xff0c;如果后缀在这个字典里就禁止上传。 2、黑名单大小写绕过攻击 二、利用 windows 系统特征绕过上传 1、windows 系统特征绕过漏洞…

YoloV9改进策略:Block改进|RFE模块,提高小物体的识别精度|即插即用|代码+修改过程

摘要 论文介绍 本文介绍了一种基于YOLOv5的人脸检测方法,命名为YOLO-FaceV2。该方法旨在解决人脸检测中的尺度变化、简单与困难样本不平衡以及人脸遮挡等问题。通过引入一系列创新模块和损失函数,YOLO-FaceV2在WiderFace数据集上取得了优异的表现,特别是在小物体、遮挡和困…

CodeQL学习笔记(3)-QL语法(模块、变量、表达式、公式和注解)

最近在学习CodeQL&#xff0c;对于CodeQL就不介绍了&#xff0c;目前网上一搜一大把。本系列是学习CodeQL的个人学习笔记&#xff0c;根据个人知识库笔记修改整理而来的&#xff0c;分享出来共同学习。个人觉得QL的语法比较反人类&#xff0c;至少与目前主流的这些OOP语言相比&…

QT-使用QSS美化UI界面

一、QSS简介&#xff1a; Qt Style Sheet&#xff1a;Qt样式表&#xff0c;用来自定义控件外观的一种机制&#xff0c;可以把他类比成CSS&#xff08;CSS主要功能与最终目的都是能使界面的表现与界面的元素分离&#xff09;。QSS机制使应用程序也能像web界面那样随意地改变外观…

江协科技STM32学习- P23 DMA 直接存储器存取

&#x1f680;write in front&#x1f680; &#x1f50e;大家好&#xff0c;我是黄桃罐头&#xff0c;希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流 &#x1f381;欢迎各位→点赞&#x1f44d; 收藏⭐️ 留言&#x1f4dd;​…

Adb命令大全

本文列举了几乎所有的adb命令&#xff0c;方便Android学习者或者开发工程师在日常学习开发过程中查询使用。建议收藏。 Adb Server adb kill-server adb start-server 重启 adb reboot adb reboot recovery adb reboot-bootloader adb root //restarts adb with root permis…