1. Toy模板网首页
  2. > Toy博客

【C++】STL中List的详细实现解析

7月前 作者：Q_hd 分类：Toy博客 阅读(29) 违法举报

这篇具有很好参考价值的文章主要介绍了【C++】STL中List的详细实现解析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

在 C++ STL（标准模板库）中，List 是一个带头双向链表，可以存储多个元素并且支持动态调整大小，适合频繁插入和删除操作；而 Vector 是一个动态数组，元素在内存中是连续存储的，适合需要快速随机访问的场景。List 提供了添加、删除、查找等操作，而 Vector 除了这些基本操作外，还提供了按索引访问元素、在指定位置插入元素等功能，进而就可以很好的支持排序算法，二分查找，堆算法等，它的缺点是扩容要付出一定的代价，而且除了尾上的插入和删除外其他位置的插入和删除都不快（因为要挪动数据）。

list 代码实现

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

namespace hd 
{
	template<class T> 
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _data;

		ListNode(const T& x = T()) // ListNode的构造函数
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}
	};
	
	template<class T, class Ref, class Ptr>  
	struct _list_iterator	// 链表迭代器
	{
		typedef ListNode<T> Node;
		typedef _list_iterator<T, Ref, Ptr> self;
		Node* _node;	//存放一个节点的指针变量

		_list_iterator(Node* node) 
			:_node(node)
		{}
		
		//++it
		self& operator++() {
			_node = _node->_next;
			return *this;
		}
		//it++
		self operator++(int) {
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		//--it
		self& operator--() {
			_node = _node->_prev;
			return *this;
		}
		//it--
		self operator--(int) {
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		
		// 模仿指针的 *
		Ref operator*() {
			return _node->_data;
		}
		// 模仿指针的 ->
		Ptr operator->() {
			return &_node->_data;
		}

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

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

	template<class T>
	class list	// 带头双向循环链表
	{
		typedef ListNode<T> Node;	// 节点的重定义
	public:
		typedef _list_iterator<T, T&, T*> iterator;	// 迭代器的重定义
		typedef _list_iterator<T, const T&, const T*> const_iterator; // const迭代器的重定义
		
		//迭代器相关
		iterator begin() {
			return _head->_next;
		}
		iterator end() {
			return _head;
		}
		const_iterator begin() const {
			return _head->_next;
		}

		const_iterator end() const {
			return _head;
		}
		
		void empty_init() {	// 初始化链表
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		list() {	//构造函数
			empty_init();
		}

		void clear() {	//清除链表元素
			iterator it = begin();
			while (it != end()) {
				it = erase(it);
			}
		}

		~list() {	//析构函数
			clear();
			delete _head;
			_head = nullptr;
		}

		list(const list<T>& It) {	// 拷贝构造
			empty_init();
			for (const auto& e : It) {
				push_back(e);
			}
		}

		void swap(list<T> tmp) {
			std::swap(_head, tmp._head);
		}
		
		//It1 = It2;
		list<T> operator=(const list<T> It) const {
			clear();
			for (const auto& e : It) {
				push_back(e);
			}
			return *this;
		}
		list<T>& operator=(list<T>/*&*/ It) {
			//if (this != &It) {
			//	clear();
			//	for (const auto& e : It) {
			//		push_back(e);
			//	}
			//}
			// 现代写法
			swap(It);
			return *this;
		}

		void push_back(const T& x) {
			//Node* newnode = new Node(x);
			//Node* tail = _head->_prev;
			//tail->_next = newnode;
			//newnode->_prev = tail;
			//_head->_prev = newnode;
			//newnode->_next = _head;
			
			insert(end(), x);	// 复用insert
		}

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

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

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

		// vector insert会导致迭代器失效
		// list intert 不会导致迭代器失效
		iterator insert(iterator pos, const T& x)
		{
			Node* newnode = new Node(x);
			Node* cur = pos._node;
			Node* prev = cur->_prev;

			newnode->_prev = prev;
			prev->_next = newnode;
			newnode->_next = cur;
			cur->_prev = newnode;
			//return iterator(newnode); //单参数的构造函数可以隐式类型转换
			return newnode;		// 返回插入节点迭代器
		}

		// 节点被delete掉了，存在迭代器失效
		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 next;	//返回被删除元素元素的下一个元素的迭代器
		}

	private:
		Node* _head;	//头节点
	}; 
}

1. 构造函数和析构函数

1.1 构造函数

目的是对链表以及节点进行初始化

template<class T>
struct ListNode
{
	ListNode<T>* _next;
	ListNode<T>* _prev;
	T _data;

	ListNode(const T& x = T()) // ListNode的构造函数
		:_next(nullptr)
		, _prev(nullptr)
		, _data(x)
	{}
};

template<class T>
class list	// 带头双向循环链表
{
	typedef ListNode<T> Node;	// 节点的重定义
	void empty_init() {	// 初始化链表
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
	}

	list() {	// list的构造函数
		empty_init();
	}
}

1.2析构函数

析构函数主要完成对资源的清理，这里通过调用clear对链表的节点进行删除。最后在将头结点空间进行释放，然后置空。

void clear() {	//清除链表元素
	iterator it = begin();
	while (it != end()) {
		it = erase(it);
	}
}

~list() {	//析构函数
	clear();
	delete _head;
	_head = nullptr;
}

2.operator=的重载 和 拷贝构造函数

2.1 拷贝构造

对链表进行初始化，之后调用push_back函数尾插数据，完成拷贝构造。

void empty_init() {	// 初始化链表
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
}
list(const list<T>& It) {	// 拷贝构造
	empty_init();
	for (const auto& e : It) {
		push_back(e);
	}
}

2.2 operator=的重载

下面分别是对const对象和非const对象的operator=的重载 /

void swap(list<T> tmp) {
	std::swap(_head, tmp._head);
}
//It1 = It2;
list<T> operator=(const list<T> It) const {
	clear();
	for (const auto& e : It) {
		push_back(e);
	}
	return *this;
}
list<T>& operator=(list<T>/*&*/ It) {
	//if (this != &It) {
	//	clear();
	//	for (const auto& e : It) {
	//		push_back(e);
	//	}
	//}
	// 现代写法
	swap(It);
	return *this;
}

3. 迭代器的实现

list 的迭代器与 vector 不同，它不是原生指针，而是将节点的指针进行封装，然后重载operator*，operator++,operator-- 等与指针相关的操作符来模拟指针的行为。

3.1 普通迭代器

template<class T>
struct ListNode
{
	ListNode<T>* _next;
	ListNode<T>* _prev;
	T _data;

	ListNode(const T& x = T()) // ListNode的构造函数
		:_next(nullptr)
		, _prev(nullptr)
		, _data(x)
	{}
};

template<class T>
struct _list_iterator	// 链表迭代器
{
	typedef ListNode<T> Node;
	typedef _list_iterator<T> self;
	Node* _node;	//存放一个节点的指针变量

	_list_iterator(Node* node)
		:_node(node)
	{}

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

	// 模仿指针的 *
	T& operator*() {
		return _node->_data;
	}
	// 模仿指针的 ->
	T* operator->() {
		return &_node->_data;
	}

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

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

注意：operator-> 在调用时，后面还会有一个->，相当于 it.operator->()->_a1 ，只不过特殊处理被省略掉了

struct AA
{
	int _a1;
	int _a2;
	AA(int a1 = 1, int a2 = 1)
		:_a1(a1)
		, _a2(a2)
	{}
};

void test_list3() {
	list<AA> It;
	AA aa1;
	It.push_back(aa1);
	It.push_back(AA());
	AA aa2(2, 2);
	It.push_back(aa2);
	It.push_back(AA(2, 2));
	list<AA>::iterator it = It.begin();
	while (it != It.end()) {
		cout << (*it)._a1 << ":" << (*it)._a2 << endl;
		cout << it.operator*()._a1 << ":" << it.operator*()._a2 << endl;

		cout << it->_a1 << ":" << it->_a2 << endl; //为了可读性，简化了一个->,特殊处理
		cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl; //相当于上面一行的
		++it;
	}
	cout << endl;
}

其实 it->_a1是it->_node->_a1，只是编译器对其进行了简化。

3.2 const迭代器

const类型的对象只能使用const类型的迭代器，那么const类型的迭代器如何实现呢、需要再重新封装吗，像上面那样？为了减少代码量，我们只需要给模板增加两个参数就可以了。template<class T, class Ref, class Ptr>。实现如下：

	template<class T, class Ref, class Ptr>
	struct _list_iterator	// 链表迭代器
	{
		typedef ListNode<T> Node;
		typedef _list_iterator<T, Ref, Ptr> self;
		Node* _node;	//存放一个节点的指针变量

		_list_iterator(Node* node)
			:_node(node)
		{}

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

		// 模仿指针的 *
		Ref operator*() {
			return _node->_data;
		}
		// 模仿指针的 ->
		Ptr operator->() {
			return &_node->_data;
		}

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

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

const 迭代器与普通迭代器只是在operator*() 和 operator->（）的返回值上有所不同所以，只需要在实例化模板的时候给不同的参数就可以实例化不同的内容。

typedef _list_iterator<T, T&, T*> iterator;	// 迭代器的重定义
typedef _list_iterator<T, const T&, const T*> const_iterator; // const迭代器的重定义

4. 插入和删除

// vector insert会导致迭代器失效
// list intert 不会导致迭代器失效
iterator insert(iterator pos, const T& x)
{
	Node* newnode = new Node(x);
	Node* cur = pos._node;
	Node* prev = cur->_prev;

	newnode->_prev = prev;
	prev->_next = newnode;
	newnode->_next = cur;
	cur->_prev = newnode;
	//return iterator(newnode); //单参数的构造函数可以隐式类型转换
	return newnode;		// 返回插入节点迭代器
}

// 节点被delete掉了，存在迭代器失效
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 next;	//返回被删除元素元素的下一个元素的迭代器
}

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

	insert(end(), x);	// 复用insert
}

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

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

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

5. 测试代码

namespace hd 
{
	void test_list()
	{
		list<int> It;
		It.push_back(1);
		It.push_back(2);
		It.push_back(3);
		It.push_back(4);
		It.push_back(5);
		It.push_back(6);

		list<int>::iterator it = It.begin();
		while (it != It.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
		for (auto e : It) {
			cout << e << " ";
		}
		cout << endl;

		list<int> It1 = It;
		list<int>::iterator it1 = It1.begin();
		while (it1 != It1.end())
		{
			cout << *it1 << " ";
			++it1;
		}
		cout << endl;
		for (auto e : It1) {
			cout << e << " ";
		}
		cout << endl;
	}

	void print_list(const list<int>& It) {
		list<int>::const_iterator it = It.begin();
		while (it != It.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
		for (auto e : It) {
			cout << e << " ";
		}
		cout << endl;
	}

	void test_list2() {
		list<int> It;
		It.push_back(1);
		It.push_back(2);
		It.push_back(3);
		It.push_back(4);
		It.push_back(5);
		It.push_back(6);

		print_list(It);
	}

	struct AA
	{
		int _a1;
		int _a2;
		AA(int a1 = 1, int a2 = 1)
			:_a1(a1)
			, _a2(a2)
		{}
	};

	void test_list3() {
		list<AA> It;
		AA aa1;
		It.push_back(aa1);
		It.push_back(AA());
		AA aa2(2, 2);
		It.push_back(aa2);
		It.push_back(AA(2, 2));
		list<AA>::iterator it = It.begin();
		while (it != It.end()) {
			cout << (*it)._a1 << ":" << (*it)._a2 << endl;
			cout << it.operator*()._a1 << ":" << it.operator*()._a2 << endl;

			cout << it->_a1 << ":" << it->_a2 << endl; //为了可读性，简化了一个->,特殊处理
			cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl; //相当于上面一行的
			++it;
		}
		cout << endl;
	}
}

总结

文章详细介绍了 C++ STL 中 List 的实现。List 是一个带头双向链表，适用于频繁插入和删除操作。构造函数、析构函数、拷贝构造函数、operator= 的重载、迭代器的实现以及插入和删除操作的具体实现方式。通过这些内容，可以深入了解 List 的内部工作原理，并学习如何使用和优化 List 数据结构。文章来源地址https://www.toymoban.com/news/detail-831628.html

到了这里，关于【C++】STL中List的详细实现解析的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • C++ ——STL容器【list】模拟实现

    C++ ——STL容器【list】模拟实现

    代码仓库： list模拟实现 list源码 数据结构——双向链表 源码的list是双向带头循环链表，所以我们定义两个节点，一个指向下一个，一个指向前一个 list类包含一个 _head 头节点，然后为了方便查出当前有多少个节点，还能多定义一个 _size 源码的迭代器设置了三个模板参数：

    2024年02月15日
    浏览(32)
  • C++ [STL之list模拟实现]

    C++ [STL之list模拟实现]

    本文已收录至《C++语言》专栏！ 作者：ARMCSKGT list的底层与vector和string不同，实现也有所差别，特别是在迭代器的设计上，本节将为大家介绍list简单实现，并揭开list迭代器的底层！ 本文介绍list部分简单接口，以list迭代器的介绍为主！ list底层是一个带头双向循环链表，在节

    2024年02月09日
    浏览(28)
  • 【C++】STL---list的模拟实现

    【C++】STL---list的模拟实现

    上次模拟实现了一个vector容器，那么我们这次来实现一个list(链表)容器，链表在实际的开发中并不常见。但是也是一种很重要的数据结构，下面给大家介绍一下链表(list) 和 vector(顺序表)的区别。 list 和 vector 一样，是一个存储容器。不同的是vector在内存中是连续存储的，而

    2024年01月22日
    浏览(38)

  • STL容器 -- list的模拟实现（配详细注释）

    C++ STL（Standard Template Library，标准模板库）提供了一组通用的模板类和函数，用于实现常用的数据结构和算法。其中之一是 std::list，它实现了一个双向链表。 std::list 是一个容器，用于存储一系列的值。与数组和向量等连续存储的容器不同，std::list 使用链表作为底层数据结构

    2024年02月16日
    浏览(34)
  • stl_list类（使用+实现）（C++）

    stl_list类（使用+实现）（C++）

    list是一个可以在常熟范围内任意位置进行插入和删除的序列式容器。 底层是带头双向循环链表 （链接中有对带头双向循环链表的逻辑分析）。 (constructor)构造函数声明 接口说明 list() 无参构造 list(size_type n, const T val = T() 构造并初始化n个val list(const list x) 拷贝构造 list(InputI

    2024年02月14日
    浏览(39)
  • 【C++】STL——list深度剖析 及 模拟实现

    【C++】STL——list深度剖析 及 模拟实现

    这篇文章我们来继续STL的学习，今天我们要学习的是list，也是STL中容器的一员。 和之前一样，我们还是先学习它的使用，然后再对它进行一个深度剖析和模拟实现。 1.1 list的介绍 list的文档介绍 list的底层实现其实就是我们之前数据结构学过的带头双向循环链表： 1.2 list的使

    2024年02月05日
    浏览(33)
  • C++ STL学习之【list的模拟实现】

    C++ STL学习之【list的模拟实现】

    ✨个人主页： 北 海 🎉所属专栏： C++修行之路 🎊每篇一句： 图片来源 A year from now you may wish you had started today. 明年今日，你会希望此时此刻的自己已经开始行动了。 STL 中的 list 是一个双向带头循环链表，作为链表的终极形态，各项操作性能都很优秀，尤其是 list 中迭代器

    2024年02月04日
    浏览(29)
  • 【C++】STL之list容器的模拟实现

    【C++】STL之list容器的模拟实现

    个人主页：🍝在肯德基吃麻辣烫 分享一句喜欢的话：热烈的火焰，冰封在最沉默的火山深处。 本文章进入C++STL之list的模拟实现。 在STL标准库实现的list中，这个链表是一个== 双向带头循环链表==。 说明： list是一个类，成员变量为_head 节点类node，是每一个节点。 list的迭代

    2024年02月17日
    浏览(37)
  • C++ stl容器list的底层模拟实现

    C++ stl容器list的底层模拟实现

    目录 前言： 1.创建节点 2.普通迭代器的封装 3.反向迭代器的封装 为什么要对正向迭代器进行封装？ 4.const迭代器 5.构造函数 6.拷贝构造 7.赋值重载 8.insert 9.erase 10.析构 11.头插头删，尾插尾删 12.完整代码+简单测试 总结： 1.创建节点 注意给缺省值，这样全缺省就会被当做默认

    2024年04月23日
    浏览(34)
  • 【C++进阶(五)】STL大法--list模拟实现以及list和vector的对比

    【C++进阶(五)】STL大法--list模拟实现以及list和vector的对比

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 本篇文章立足于上一篇文章: list深度剖析(上) 请先阅读完上一篇文章后再阅读这篇文章! 本章重点: 本章着重讲解list的模拟实现 list模拟实

    2024年02月09日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包