C++/list

目录

1.list的介绍

 2.list的使用

2.1list的构造 

2.2list iterator的使用

2.3list capacity

 2.4list element access

 2.5list modifers

2.6list的迭代器失效

3.list的模拟实现

4.list与vector的对比


欢迎

1.list的介绍

list的文档介绍

cplusplus.com/reference/list/list/?kw=list

 2.list的使用

2.1list的构造 

 

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构造的使用: 

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

    // 用迭代器方式打印l5中的元素
    list<int>::iterator it = l5.begin();
    while (it != l5.end())
    {
        cout << *it << " ";
        ++it;
    }       
    cout << endl;

    // C++11范围for的方式遍历
    for (auto& e : l5)
        cout << e << " ";

    cout << endl;
}

2.2list iterator的使用

begin+end返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin+rend返回死一个元素的reverse_iterator,即end位置,返回最后一个元素下一个位置的reverse_iterator,即begin位置

 

【注意】
1. begin end 为正向迭代器,对迭代器执行 ++ 操作,迭代器向后移动
2. rbegin(end) rend(begin) 为反向迭代器,对迭代器执行 ++ 操作,迭代器向前移动

 

// 注意:遍历链表只能用迭代器和范围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中的元素
    auto it = l.begin();                    
    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;
}

2.3list capacity

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

 2.4list element access

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

 2.5list modifers

 

push_front在list首元素前插入值为val的元素
pop_front删除list中第一个元素
push_back在list尾部插入值为val的元素
pop_back删除list中最后一个元素
insert在list position位置中插入中为val的元素
erase删除list position位置的元素
clear清空list中的有效元素
list的插入和删除使用代码演示:
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);
}

// resize/swap/clear
void TestList5()
{
    // 用数组来构造list
    int array1[] = { 1, 2, 3 };
    list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
    PrintList(l1);

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

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

2.6list的迭代器失效

迭代器失效即迭代器所指向的节点的无 效,即该节点被删除了 。因为 list 的底层结构为带头结点的双向循环链表 ,因此 list 中进行插入 时是不会导致 list 的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭 代器,其他迭代器不会受到影响

 

#include <list>
using namespace std;

void TestListIterator1()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    // 初始化链表l,使用array数组中的元素
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    auto it = l.begin(); // 创建一个迭代器it,指向链表的开头

    // 遍历链表
    while (it != l.end())
    {
        // 删除当前it指向的节点
        // 这里it已经失效,不能再直接使用
        l.erase(it);
        ++it; // 增加it指向下一个节点,但此时it可能已经无效
    }
}

// 改正后的版本
void TestListIterator()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    // 初始化链表l,使用array数组中的元素
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    auto it = l.begin(); // 创建一个迭代器it,指向链表的开头

    // 遍历链表
    while (it != l.end())
    {
        // 删除当前it指向的节点,并返回指向下一个节点的迭代器
        // it会被更新为l.erase(it)的返回值,即指向下一个有效节点
        it = l.erase(it); // 先删除,然后更新it
    }
}

3.list的模拟实现

#pragma once

#include <iostream>
using namespace std;
#include <assert.h>

namespace pzn
{
	// List的节点类
	template<class T>
	struct ListNode
	{
		ListNode(const T& val = T())
			: _prev(nullptr)
			, _next(nullptr)
			, _val(val)
		{}

		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _val;
	};

	/*
	List 的迭代器
	迭代器有两种实现方式,具体应根据容器底层数据结构实现:
	  1. 原生态指针,比如:vector
	  2. 将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下方法:
		 1. 指针可以解引用,迭代器的类中必须重载operator*()
		 2. 指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()
		 3. 指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)
			至于operator--()/operator--(int)释放需要重载,根据具体的结构来抉择,双向链表可以向前             移动,所以需要重载,如果是forward_list就不需要重载--
		 4. 迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()
	*/
	template<class T, class Ref, class Ptr>
	class ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;

		// Ref 和 Ptr 类型需要重定义下,实现反向迭代器时需要用到
	public:
		typedef Ref Ref;
		typedef Ptr Ptr;
	public:
		//
		// 构造
		ListIterator(Node* node = nullptr)
			: _node(node)
		{}

		//
		// 具有指针类似行为
		Ref operator*() 
		{ 
			return _node->_val;
		}

		Ptr operator->() 
		{ 
			return &(operator*()); 
		}

		//
		// 迭代器支持移动
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self operator++(int)
		{
			Self temp(*this);
			_node = _node->_next;
			return temp;
		}

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

		Self operator--(int)
		{
			Self temp(*this);
			_node = _node->_prev;
			return temp;
		}

		//
		// 迭代器支持比较
		bool operator!=(const Self& l)const
		{ 
			return _node != l._node;
		}

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

		Node* _node;
	};

	template<class Iterator>
	class ReverseListIterator
	{
		// 注意:此处typename的作用是明确告诉编译器,Ref是Iterator类中的一个类型,而不是静态成员变量
		// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
		// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
	public:
		typedef typename Iterator::Ref Ref;
		typedef typename Iterator::Ptr Ptr;
		typedef ReverseListIterator<Iterator> Self;
	public:
		//
		// 构造
		ReverseListIterator(Iterator it)
			: _it(it)
		{}

		//
		// 具有指针类似行为
		Ref operator*()
		{
			Iterator temp(_it);
			--temp;
			return *temp;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		//
		// 迭代器支持移动
		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self operator++(int)
		{
			Self temp(*this);
			--_it;
			return temp;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self operator--(int)
		{
			Self temp(*this);
			++_it;
			return temp;
		}

		//
		// 迭代器支持比较
		bool operator!=(const Self& l)const
		{
			return _it != l._it;
		}

		bool operator==(const Self& l)const
		{
			return _it != l._it;
		}

		Iterator _it;
	};

	template<class T>
	class list
	{
		typedef ListNode<T> Node;

	public:
		// 正向迭代器
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T&> const_iterator;

		// 反向迭代器
		typedef ReverseListIterator<iterator> reverse_iterator;
		typedef ReverseListIterator<const_iterator> const_reverse_iterator;
	public:
		///
		// List的构造
		list()
		{
			CreateHead();
		}

		list(int n, const T& value = T())
		{
			CreateHead();
			for (int i = 0; i < n; ++i)
				push_back(value);
		}

		template <class Iterator>
		list(Iterator first, Iterator last)
		{
			CreateHead();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		list(const list<T>& l)
		{
			CreateHead();

			// 用l中的元素构造临时的temp,然后与当前对象交换
			list<T> temp(l.begin(), l.end());
			this->swap(temp);
		}

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

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

		///
		// List的迭代器
		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); 
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin()const
		{
			return const_reverse_iterator(end());
		}

		const_reverse_iterator rend()const
		{
			return const_reverse_iterator(begin());
		}

		///
		// List的容量相关
		size_t size()const
		{
			Node* cur = _head->_next;
			size_t count = 0;
			while (cur != _head)
			{
				count++;
				cur = cur->_next;
			}

			return count;
		}

		bool empty()const
		{
			return _head->_next == _head;
		}

		void resize(size_t newsize, const T& data = T())
		{
			size_t oldsize = size();
			if (newsize <= oldsize)
			{
				// 有效元素个数减少到newsize
				while (newsize < oldsize)
				{
					pop_back();
					oldsize--;
				}
			}
			else
			{
				while (oldsize < newsize)
				{
					push_back(data);
					oldsize++;
				}
			}
		}
		
		// List的元素访问操作
		// 注意:List不支持operator[]
		T& front()
		{
			return _head->_next->_val;
		}

		const T& front()const
		{
			return _head->_next->_val;
		}

		T& back()
		{
			return _head->_prev->_val;
		}

		const T& back()const
		{
			return _head->_prev->_val;
		}

		
		// List的插入和删除
		void push_back(const T& val) 
		{ 
			insert(end(), val); 
		}

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

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

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

		// 在pos位置前插入值为val的节点
		iterator insert(iterator pos, const T& val)
		{
			Node* pNewNode = new Node(val);
			Node* pCur = pos._node;
			// 先将新节点插入
			pNewNode->_prev = pCur->_prev;
			pNewNode->_next = pCur;
			pNewNode->_prev->_next = pNewNode;
			pCur->_prev = pNewNode;
			return iterator(pNewNode);
		}

		// 删除pos位置的节点,返回该节点的下一个位置
		iterator erase(iterator pos)
		{
			// 找到待删除的节点
			Node* pDel = pos._node;
			Node* pRet = pDel->_next;

			// 将该节点从链表中拆下来并删除
			pDel->_prev->_next = pDel->_next;
			pDel->_next->_prev = pDel->_prev;
			delete pDel;

			return iterator(pRet);
		}

		void clear()
		{
			Node* cur = _head->_next;
			
			// 采用头删除删除
			while (cur != _head)
			{
				_head->_next = cur->_next;
				delete cur;
				cur = _head->_next;
			}

			_head->_next = _head->_prev = _head;
		}

		void swap(bite::list<T>& l)
		{
			std::swap(_head, l._head);
		}

	private:
		void CreateHead()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
	private:
		Node* _head;
	};
}


///
// 对模拟实现的list进行测试
// 正向打印链表
template<class T>
void PrintList(const bite::list<T>& l)
{
	auto it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		++it;
	}

	cout << endl;
}

4.list与vector的对比

vector与list都是STL中非常重要的序列式容器,由于两个容器的底层结构不同,导致其特性以及
应用场景不同,其主要不同如下:

 

vectorlist
底层结构动态顺序表,一段连续空间带头结点的双向循环链表
随机访问支持随机访问,访问某个元素效率O(1)不支持随机访问,访问某个元素效率O(N)
插入和删除任意位置插入和删除效率低,需要搬移元素,时间复杂度为O(N),插入是有可能需要增容;增容:开辟新空间拷贝元素,释放旧空间,导致效率更低任意位置插入和删除效率高,不需要搬移元素,时间复杂度O(1)
空间利用率底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高底层结点动态开辟,小结点容易造成内存碎片,缓存利用率低
迭代器原生态指针对原生态指针(结点指针)进行封装
迭代器失效在插入元素时,要给所有的迭代器重新赋值,因为插入元素有可能会导致重新扩容,使原来迭代器失效,删除时,当前迭代器需要迭代器重新赋值否则会失效插入元素不好导致迭代器失效,删除元素时,只会导致当前迭代器失效,其他迭代器不受影响
使用场景需要高效存储,支持随机访问,不关心插入删除效率大量插入和删除操作,不关心随机访问

感谢

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

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

相关文章

人工智能证书合集

本文将对目前市面上主流官方机构颁发的人工智能证书进行整理和介绍&#xff0c;由于整理的证书较多&#xff0c;本文共一万八千多字&#xff0c;请根据自己的考证需求阅读对应部分的内容&#xff0c;希望本文对人工智能行业的从业人员和计划从事人工智能相关岗位工作的人员有所…

TongWeb7.0.E.6_P11嵌入式版本使用指引(by lqw)

文章目录 声明相关概念手册的使用示范工程安装工程介质 安装前准备示范工程参考&#xff08;spring-boot-helloWorld-2.x&#xff09;示范参考 声明 1.本文参考001_TongWeb_V7.0嵌入式版_JavaEE标准容器用户指南_70E6_P11A01.pdf&#xff0c;实际以最新更新的手册为准。 2.本文…

鸿蒙开发融云demo发送图片消息

鸿蒙开发融云demo发送图片消息 融云鸿蒙版是不带UI的&#xff0c;得自己一步步搭建。 这次讲如何发送图片消息&#xff0c;选择图片&#xff0c;显示图片消息。 还是有点难度的&#xff0c;好好看&#xff0c;好好学。 一、思路&#xff1a; 选择图片用&#xff1a;photoVie…

开源OCR免费助力法律文档数字化,提升文档管理效率

一、在法律行业&#xff0c;每天需要处理大量纸质文件&#xff0c;从合同到判决书&#xff0c;手动录入不仅费时&#xff0c;还容易出错。为解决这一问题推出了一款免费开源的OCR智能识别平台&#xff0c;通过先进的光学字符识别&#xff08;OCR&#xff09;技术&#xff0c;将…

详解ReentrantLock--三种加锁方式

目录 介绍AQS: 直观方式解释加锁的流程&#xff1a; Node是什么&#xff1a;它里面有什么属性呢 图解队列的排队过程&#xff1a; 源码分析三种加锁流程&#xff1a; 我们先讲解一下非公平锁的加锁流程&#xff1a; Lock()方式加锁&#xff1a; 在源码里对于Lock()的解…

【教程】Git 标准工作流

目录 前言建仓&#xff0c;拉仓&#xff0c;关联仓库修改代码更新本地仓库&#xff0c;并解决冲突提交代码&#xff0c;合入代码其他常用 Git 工作流删除本地仓库和远程仓库中的文件日志打印commit 相关 前言 Git 是日常开发中常用的版本控制工具&#xff0c;配合代码托管仓库…

Postman断言与依赖接口测试详解!

在接口测试中&#xff0c;断言是不可或缺的一环。它不仅能够自动判断业务逻辑的正确性&#xff0c;还能确保接口的实际功能实现符合预期。Postman作为一款强大的接口测试工具&#xff0c;不仅支持发送HTTP请求和接收响应&#xff0c;还提供了丰富的断言功能&#xff0c;帮助测试…

百度SEO与SEM到底有什么区别?福建企业老板们需要了解的关键点【百度SEO专家】

大家好&#xff0c;我是林汉文&#xff0c;一名百度SEO专家。最近在与一些企业Boss沟通时&#xff0c;我发现很多人对SEO与SEM的区别并不清楚&#xff0c;有时甚至会混为一谈。SEO和SEM确实都是搜索引擎营销的重要手段&#xff0c;但它们在实现方式、效果和适用场景上都有着明显…

JavaFX WebView + Vue初始化加载数据解决方案

一般WebView加载Vue时&#xff0c;我们需要注入一些数据&#xff0c;而我发现当WebView加载完毕再注入脚本&#xff0c;Vue是无法正确识别注入的脚本函数&#xff0c;也无法正确获取所要注入的数据&#xff0c;因此可以采用以下方法解决Vue无法正确加载数据问题 1、配置WebView…

Ubuntu 安装CUDA, cuDNN, TensorRT(草稿)

文章目录 写在前面一、CUDA, cuDNN, TensorRT 三个库的版本的确定二、解决方法参考链接 写在前面 自己的测试环境&#xff1a; Ubuntu20.04, 本文安装的版本&#xff1a; cuda_11.1.0&#xff1b;cuDNN-8.2.1&#xff1b;TensorRT-8.2.4.2 一、CUDA, cuDNN, TensorRT 三个库…

传输层协议TCP详解(上篇)

目录 一. TCP协议 1.1 什么是TCP协议 1.2 TCP为什么叫传输控制协议 二. TCP协议段格式 三. 确认应答&#xff08;ACK&#xff09;机制 3.1 什么是确认应答机制 3.2 推导确认应答机制 四. 超时重传机制 五. 连接管理机制 5.1 六位标志位 5.2 如何…

wps宏代码学习

推荐学习视频&#xff1a;https://space.bilibili.com/363834767/channel/collectiondetail?sid1139008&spm_id_from333.788.0.0 打开宏编辑器和JS代码调试 工具-》开发工具-》WPS宏编辑器 左边是工程区&#xff0c;当打开多个excel时会有多个&#xff0c;要注意不要把…

ffmpeg视频滤镜:膨胀操作-dilation

滤镜介绍 dilation 官网链接 > FFmpeg Filters Documentation 膨胀滤镜会使图片变的更亮&#xff0c;会让细节别的更明显。膨胀也是形态学中的一种操作&#xff0c;在opencv中也有响应的算子。此外膨胀结合此前腐蚀操作&#xff0c;可以构成开闭操作。 开操作是先腐蚀…

【补补漏洞吧 | 02】等保测评ZooKeeperElasticsearch未授权访问漏洞补漏方法

一、项目背景 客户新系统上线&#xff0c;因为行业网络安全要求&#xff0c;需要做等保测评&#xff0c; 通过第三方漏扫工具扫描系统&#xff0c;漏扫报告显示ZooKeeper和 Elasticsearch 服务各拥有一个漏洞&#xff0c;具体结果如下&#xff1a; 1、ZooKeeper 未授权访问【…

C语言进阶之我与指针的爱恨情仇(1)

一.前言 我们在初阶《指针》初阶C语言-指针-CSDN博客已经讲过了一些基础知识&#xff0c;知道了关于指针的一些概念-> 1.指针就是个变量&#xff0c;用来存放地址&#xff0c;地址唯一标识一块内存空间 2.指针的大小是固定的4/8个字节&#xff08;32位平台/64位平台&#xf…

对象池的作用以及简单示例

在游戏当中&#xff0c;有很多时候需要重复地创建或删除某些游戏对象&#xff0c;此时会耗费系统资源&#xff0c;从而影响性能&#xff0c;利用对象池可以解决这个问题。对象池能够节省内存&#xff0c;优化程序流畅程度。 把对象放在一个集合里&#xff0c;通过集合来管理对象…

java并发编程-volatile的作用

文章目录 volatile的作用1.改变线程间的变量可见性2.禁止指令重排序 参考的学习视频 volatile的作用 1.改变线程间的变量可见性 每个线程都有一个专用的工作集内存&#xff0c;下图里面粉色的表示专用工作集内存&#xff0c;黄色的是共享内存工作区&#xff0c;如果加入了vol…

Netty 组件介绍 - EventLoop

概要 把 channel 理解为数据的通道把 msg 理解为流动的数据&#xff0c;最开始输入是 ByteBuf&#xff0c;但经过pipeline 的加工&#xff0c;会变成其它类型对象&#xff0c;最后输出又变成 ByteBuf把 handler 理解为数据的处理工序 工序有多道&#xff0c;合在一起就是 pi…

oracle 对应的JDBC驱动 版本

下载网址&#xff1a;JDBC and UCP Downloads page

整理 【 DBeaver 数据库管理工具 】的一些基础使用

目录 连接设置切换工作空间SQL编辑器&#xff08;写sql语句&#xff09;打开方式新建查询&#xff08;sql编辑器&#xff09;打开写的 sql 查询&#xff08;项目浏览器&#xff09; 备份sql文件查看历史执行语句自动保存sql语句的文件&#xff08;编辑器&#xff09;关闭自动生…