当前位置： 首页 > article >正文

【C++】STL——list的使用与底层实现

article 2025/2/8 1:13:35

目录

💕1.带头双向链表List

💕2.list用法介绍

💕3.list的初始化 

💕4.size函数与resize函数

💕5.empty函数 

💕6.front函数与back函数 

💕7.push_front,push_back,pop_front,pop_back函数 

💕8.begin函数，end函数，rbegin函数，rend函数 

💕9.insert函数，erase函数 

💕10.swap函数 

💕11.clear函数

💕12.sort排序链表

💕13.remove函数

💕14.list使用--完结

🌟1.list的三个类介绍

🌟2.list——节点类 （ListNode）

🌟3.list——链表类 （List）

🌟4.list——迭代器类（重点思考）(ListIterator)

🌟5. list遍历(迭代器，const迭代器)

🌟6.整体代码 

🌟7.测试用例

🌟8.list底层实现--完结 

独帜入渊深未知  身似浮萍命难持

声明:此篇文章需要掌握vector的使用

（最新更新时间——2025.2.7）

💕1.带头双向链表List

在C++中，List是一种带头双向链表

 💦 list 容器的优点
 高效的插入和删除：由于std::list是基于带头双向循环链表实现的，插入和删除操作在任意位置都具有常数时间复杂度O(1)，不需要移动其他元素。这使得std::list在需要频繁插入和删除元素的场景下非常高效。
稳定的迭代器：在std::list中进行插入和删除操作不会使得迭代器失效。这意味着在插入或删除元素后，仍然可以继续使用之前获取的迭代器进行遍历和操作。
动态内存管理：std::list可以动态调整大小，根据需要分配和释放内存。这使得std::list能够有效地处理大量元素的情况，而不会浪费过多的内存空间。

 💦 list 容器的缺点
低效的随机访问：由于std::list的存储结构是带头双向循环链表，访问元素时需要从头或尾开始遍历链表，因此在列表中进行随机访问的效率较低。获取特定位置的元素需要遍历链表，时间复杂度为O(n)，其中n是元素的总数量。
占用额外内存：相较于其他容器，std::list在存储上需要额外的指针来维护链表结构，因此在存储大量元素时，它可能占用更多的内存空间。
迭代器不支持指针算术：std::list的迭代器不支持指针算术运算，无法像指针那样直接进行加减操作，这限制了一些操作的灵活性。

💕2.list用法介绍

 list的用法与vector是类似的，具体如下:

接下来进行逐一讲解使用->:

💕3.list的初始化 

list的初始化与vector一样，写法如下:

#include<iostream>
using namespace std;
#include<list>
int main()
{
	//初始化
	list<int> l1 = { 2,4,5 };
	list<double> l2 = { 4.5,5.5 };

	list<string> s1 = { "hello","world" };
	list<char> c1 = { 'x','p' };

}

💕4.size函数与resize函数

 size函数可以返回链表的有效值个数

resize函数可以更改链表的有效值个数，并且“可以”进行初始化新开辟的size值

这些都与vector的使用是一样的，不懂的可以去看我的这篇文章

vector的使用详解

链表中没有capacity函数的使用，因为链表都是创建一个开辟一个，并不会一次开辟一堆空间

💕5.empty函数 

empty函数用来判断链表是否为空，返回值的类型是bool，如果为空返回true，否则返回false

💕6.front函数与back函数 

front函数用于返回链表的第一个有效元素

bakc函数用于返回链表的最后一个有效元素

这里简单直接展示代码了

💕7.push_front,push_back,pop_front,pop_back函数 

push_front用于链表的头插         push_back用于链表的尾插

pop_front用于链表的头删吗        pop_back用于链表的尾删

这里也简单，代码例题如下->:

💕8.begin函数，end函数，rbegin函数，rend函数 

这里的使用或者概念与顺序表完全相同，不做展示

文章跳转:vector的使用详解

💕9.insert函数，erase函数 

这里的使用或者概念与顺序表完全相同，不做展示

文章跳转:vector的使用详解

💕10.swap函数 

swap函数可以交换两个链表之间的内容

它底层的实现是通过交换头节点，因为头结点一交换后面的内容也等于交换了

代码示例->:

💕11.clear函数

clear函数用于将链表置为空链表

用法如下->:

💕12.sort排序链表

sort排序可以将链表排序为升序或者降序

代码如下->:

如果想排降序，那就加入greater函数

💕13.remove函数

功能描述:

remove 函数会遍历整个链表，将所有值等于 value 的元素从链表中移除，并释放这些元素所占用的内存。移除元素后，链表的长度会相应减少。

💕14.list使用--完结

接下来的内容为list的底层实现

    声明:此文内容基于此文章->:【C++】STL——vector的使用与底层实现

🌟1.list的三个类介绍

在list中存在着三个类，而我们使用的list就是这三个类相辅相成形成的功能

它们分别是节点类,链表类，迭代器类

节点类用来代表每一个节点的内容

迭代器类用来实现链表的遍历，成员为单个节点的地址

而链表类就是用来实现各种链表功能，成员为头结点

🌟2.list——节点类 （ListNode）

节点类是每一个节点的内容，因此需要有前一个节点的地址，后一个节点的地址，以及数据

但因为它的内容需要频繁运用，因此最好用struct，struct中所有都为public，因此很方便，当然class也没有问题，只不过需要显示public

因此需要这样写->:

template<class T>
struct ListNode
{
	ListNode* prev;
	ListNode* next;
	T data;
	//1.T& x可以让形参不开辟新的空间，时间和空间上都有节省
	//2.const保护引用不被修改
	//3.T()是因为节点内容不一定是什么类型，而T()可以更好地初始化
	//例:int(),自动初始化为0，double()，string()
	ListNode(const T& x = T())
		:data(x)
		,prev(nullptr)
		,next(nullptr)
	{

	}
};

🌟3.list——链表类 （List）

链表类的实现主要是具体功能，而我们知道链表是有一个头结点的，因此可以在链表类中实现

	template<class T>
	class List
	{
		typedef ListNode<T> Node;//将节点类重命名为Node
		//创建头节点，让其指向自己
		List()
		{
			phead = new Node();
			phead->next = phead;
			phead->prev = phead;
		}
	private:
		Node* phead;
	};

🌟4.list——迭代器类（重点思考）(ListIterator)

迭代器类需要实现的是链表的遍历，想要实现遍历，必不可少的就是begin()函数，正常来说，begin()函数的返回类型应该是节点的地址，但是仔细思考一下，如果返回的是节点的地址，那这个节点的地址++后，不一定是下一个节点的地址，因此，begiin()函数不应该使用节点的地址作为返回值

新的思路：我们可以利用对象进行遍历，什么意思？

我们在进行遍历时，每一次begin()返回的是一个对象，通过访问这个对象中的节点地址，加上运算符重载，来进行遍历，因为利用这个对象中的节点地址，就进而可以通过这个节点地址访问到节点的数值

因此可以这样写->:

	template<class T>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		Node* node;//单个节点的地址
	};

为什么是结构体?先不要在意，请看后面

🌟5. list遍历(迭代器，const迭代器)

我们的思路是，通过对象进行遍历，因此我们需要实现对象的++,--运算符重载，来一个一个的遍历每一个节点对象

	template<class T>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T> Self;
		ListIterator(Node* x)
		{
			node = x;
		}
		//前置++,作用是遍历，不可以返回节点地址，因为无法进行下一次++，不一定会指向下一个节点
		//利用对象进行遍历，因此返回的应该是一个对象，迭代器类的对象，因为要用迭代器类中的单个节点的地址来遍历
		Self& operator++()
		{
			node = node->next;
			return *this;
		}
		Self& operator--()
		{
			node = node->prev;
			return *this;
		}
		//后置--
		//后置--需要利用一个临时变量来表示原来的值，首先传参传给来的是对象的地址，即this
		Self operator--(int)
		{
			//Self* tep = this;//这种写法不可取，因为两块地址一样，任意一个修改全修改了所以没区别
			Self tep(*this);//拷贝构造函数创建临时对象，但是需要注意区分，这个对象的地址和*this的地址是不一样的，但是它们里面的node地址是一样的
			node = node->prev;
			return tep;
			//后置的返回值不可以用引用，因为临时变量tep出了函数就销毁了，用引用会导致空引用
		}
		Self operator++(int)
		{
			//Self* tep = this;//这种写法不可取，因为两块地址一样，任意一个修改全修改了所以没区别
			Self tep(*this);//拷贝构造函数创建临时对象，但是需要注意区分，这个对象的地址和*this的地址是不一样的，但是它们里面的node地址是一样的
			node = node->next;
			return tep;
		}
		T& operator*()
		{
			return this->node->data;
		}
		bool operator!=(const Self& it)
		{
			return this->node != it.node;
		}
		bool operator==(const Self& it)
		{
			return this->node == it.node;
		}
		Node* node;//单个节点的地址
	};


接下来是begin函数与end函数，写在List类中

		iterator begin()
		{
			//phead->next的类型是Node*类型，而返回类型需要是iterator类型，也就是对象
			//利用匿名对象，将phead->next传给ListIterator的构造函数，使它变为一个匿名对象，再return回去
			return iterator(phead->next);
		}
		iterator end()
		{
			return iterator(phead);
		}

如何实现const迭代器?

我们可以新建一个const的迭代器类，通过const修饰constIterator类中的成员变量，进而实现const迭代器的效果

具体实现如下->:
 

// 新增 const 迭代器
template<class T>
struct ListConstIterator
{
	typedef const ListNode<T> Node;
	typedef ListConstIterator<T> Self;
	ListConstIterator(Node* x)
		:node(x)
	{}

	// 前置++
	Self& operator++()
	{
		node = node->next;
		return *this;
	}

	Self& operator--()
	{
		node = node->prev;
		return *this;
	}

	// 后置++
	Self operator++(int)
	{
		Self tep(*this);
		node = node->next;
		return tep;
	}

	Self operator--(int)
	{
		Self tep(*this);
		node = node->prev;
		return tep;
	}

	const T& operator*() const
	{
		return node->data;
	}

	bool operator!=(const Self& it) const
	{
		return node != it.node;
	}

	bool operator==(const Self& it) const
	{
		return node == it.node;
	}

	//把节点定义为const类，因为const迭代器要实现的是const T* ,限制的是解引用
	const Node* node;
};
template<class T>
class List
{
	
public:
	typedef ListNode<T> Node;//将节点类重命名为Node
	typedef ListIterator<T> iterator;//将迭代器类重命名为iterator
	typedef ListConstIterator<T> const_iterator; // 新增 const_iterator
	//创建头节点，让其指向自己
	const_iterator begin() const
	{
		return const_iterator(phead->next);
	}

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

至此难点就全部完成了，剩下的就只剩拷贝构造等，看看整体代码即可

🌟6.整体代码 

#pragma
#include<assert.h>
namespace yzq
{
	template<class T>
	struct ListNode
	{
		ListNode* prev;
		ListNode* next;
		T data;
		//1.T& x可以让形参不开辟新的空间，时间和空间上都有节省
		//2.const保护引用不被修改
		//3.T()是因为节点内容不一定是什么类型，而T()可以更好地初始化
		//例:int(),自动初始化为0，double()，string()
		ListNode(const T& x = T())
			:data(x)
			,prev(nullptr)
			,next(nullptr)
		{

		}
	};

	template<class T>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T> Self;
		ListIterator(Node* x)
		{
			node = x;
		}
		//前置++,作用是遍历，不可以返回节点地址，因为无法进行下一次++，不一定会指向下一个节点
		//利用对象进行遍历，因此返回的应该是一个对象，迭代器类的对象，因为要用迭代器类中的单个节点的地址来遍历
		Self& operator++()
		{
			node = node->next;
			return *this;
		}
		Self& operator--()
		{
			node = node->prev;
			return *this;
		}
		//后置--
		//后置--需要利用一个临时变量来表示原来的值，首先传参传给来的是对象的地址，即this
		Self operator--(int)
		{
			//Self* tep = this;//这种写法不可取，因为两块地址一样，任意一个修改全修改了所以没区别
			Self tep(*this);//拷贝构造函数创建临时对象，但是需要注意区分，这个对象的地址和*this的地址是不一样的，但是它们里面的node地址是一样的
			node = node->prev;
			return tep;
			//后置的返回值不可以用引用，因为临时变量tep出了函数就销毁了，用引用会导致空引用
		}
		Self operator++(int)
		{
			//Self* tep = this;//这种写法不可取，因为两块地址一样，任意一个修改全修改了所以没区别
			Self tep(*this);//拷贝构造函数创建临时对象，但是需要注意区分，这个对象的地址和*this的地址是不一样的，但是它们里面的node地址是一样的
			node = node->next;
			return tep;
		}
		T& operator*()
		{
			return this->node->data;
		}
		bool operator!=(const Self& it)
		{
			return this->node != it.node;
		}
		bool operator==(const Self& it)
		{
			return this->node == it.node;
		}
		Node* node;//单个节点的地址
	};

	// 新增 const 迭代器
	template<class T>
	struct ListConstIterator
	{
		typedef const ListNode<T> Node;
		typedef ListConstIterator<T> Self;
		ListConstIterator(Node* x)
			:node(x)
		{}

		// 前置++
		Self& operator++()
		{
			node = node->next;
			return *this;
		}

		Self& operator--()
		{
			node = node->prev;
			return *this;
		}

		// 后置++
		Self operator++(int)
		{
			Self tep(*this);
			node = node->next;
			return tep;
		}

		Self operator--(int)
		{
			Self tep(*this);
			node = node->prev;
			return tep;
		}

		const T& operator*() const
		{
			return node->data;
		}

		bool operator!=(const Self& it) const
		{
			return node != it.node;
		}

		bool operator==(const Self& it) const
		{
			return node == it.node;
		}

		//把节点定义为const类，因为const迭代器要实现的是const T* ,限制的是解引用
		const Node* node;
	};

	template<class T>
	class List
	{
		
	public:
		typedef ListNode<T> Node;//将节点类重命名为Node
		typedef ListIterator<T> iterator;//将迭代器类重命名为iterator
		typedef ListConstIterator<T> const_iterator; // 新增 const_iterator
		//创建头节点，让其指向自己
		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;
		}
		//拷贝构造函数，可以开辟新空间然后直接尾插
		//因为l2是const类型的，所以auto时需要const类型的迭代器
		//遍历 const 对象需要 const 迭代器
		List(const List<T>& l2)
		{
			phead = new Node();
			phead->next = phead;
			phead->prev = phead;

			for (const auto& e : l2)
			{
				push_back(e);
			}
		}
		//赋值运算符重载
		//直接更改头结点，后面的访问就全更改了
		List<T>& operator=(List<T> lt)
		{
			swap(phead, lt.phead);

			return *this;
		}
		//析构函数
		~List()
		{
			clear();
			delete phead;
			phead = nullptr;
		}
		//全部遍历一遍s释放
		void clear()
		{
			auto it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		//头删
		void pop_back()
		{
			erase(--end());
		}
		//头插
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		//头删
		void pop_front()
		{
			erase(begin());
		}
		void push_back(const T& x)
		{
			Node* newnode = new Node(x);
			Node* tail = phead->prev;

			tail->next = newnode;
			newnode->prev = tail;
			newnode->next = phead;
			phead->prev = newnode;
		}
		iterator begin()
		{
			//phead->next的类型是Node*类型，而返回类型需要是iterator类型，也就是对象
			//利用匿名对象，将phead->next传给ListIterator的构造函数，使它变为一个匿名对象，再return回去
			return iterator(phead->next);
		}
		iterator end()
		{
			return iterator(phead);
		}
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos.node;
			Node* newnode = new Node(x);
			Node* prev = cur->prev;

			// prev  newnode  cur
			prev->next = newnode;
			newnode->prev = prev;
			newnode->next = cur;
			cur->prev = newnode;

			return iterator(newnode);
		}

		// erase 后 pos失效了，pos指向节点被释放了
		iterator erase(iterator pos)
		{
			assert(pos != end());

			Node* cur = pos.node;
			Node* prev = cur->prev;
			Node* next = cur->next;

			prev->next = next;
			next->prev = prev;

			delete cur;

			return iterator(next);
		}
	private:
		Node* phead;
	};
}

🌟7.测试用例

#define _CRT_SECURE_NO_WARNINGS 
#include <iostream>
using namespace std;
#include"list.h"
int main() {
    yzq::List<int> l1;
    l1.push_back(2);
    l1.push_back(3);
    
    l1.insert(l1.begin(), 5);
    l1.erase(l1.begin());
    yzq::List<int> l2(l1);
     //遍历输出： 2 3
   for (auto e : l2) {
        std::cout << e << " ";
    }
    return 0;
}

🌟8.list底层实现--完结 

​


http://www.kler.cn/a/535785.html

相关文章：

  • javaEE-6.网络原理-http
  • RabbitMQ深度探索：前置知识
  • nuxt3中使用useFetch请求刷新不返回数据或返回html结构问题解决-完整nuxt3useFetchtch请求封装
  • langchain教程-11.RAG管道/多轮对话RAG
  • 低代码提升交付效率的公式计算
  • 解析PHP文件路径相关常量
  • 第二次连接k8s平台注意事项
  • 后端生成二维码
  • 单节锂电池外部供电自动切换的电路学习
  • Git 工作区、暂存区与本地仓库的关系详解
  • TCP | RFC793
  • Django基础篇(1)--介绍
  • IDEA 中集成 Maven，配置环境、创建以及导入项目
  • 如何规避反爬虫机制
  • springBoot开发步骤和知识点
  • 测试驱动开发（TDD）实践：从理论到实践
  • 前端面试项目总结——WebGL篇
  • javaEE-9.HTML入门
  • MySQL——表操作及查询
  • 七大排序思想
  • 深入理解linux中的文件（下）
  • Git登录并解决 CAPTCHA
  • 面向 Workload 级别的灵活可配置 Serverless 弹性解决方案
  • 深入浅出DeepSeek LLM 以长远主义拓展开源语言模型
  • AI对话网站一键生成系统源码
  • Android 约束布局ConstraintLayout整体链式打包居中显示