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

【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改

7月前 作者：鳄鱼麻薯球 分类：Toy博客 阅读(37) 违法举报

这篇具有很好参考价值的文章主要介绍了【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.模拟实现list

list使用文章

【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改,C++,c++

1.1构造函数

【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改,C++,c++

析构函数

【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改,C++,c++

  在定义了一个类模板list时。我们让该类模板包含了一个内部结构体_list_node，用于表示链表的节点。该结构体包含了指向前一个节点和后一个节点的指针以及节点的值。在list中保存了链表的头节点指针和链表长度大小。

namespace my_list
{	
	//用类模板定义一个list结点
	template<class T>
	struct _list_node
	{
		//list结点的构造函数，T()作为缺省值，当未转参时调用
		_list_node(const T& val = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _val(val)
		{}

		//list_node的成员函数，list为带头双向循环链表
		_list_node* _prev;
		_list_node* _next;
		T _val;
	};
	
	//用类模拟实现list
	template<class T>
	class list
	{
	private:
		typedef _list_node<T> Node;
		
	public:
		//list的构造函数，初始化头节点指针
		list()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;

			_size = 0;
		}

		//析构函数
		~list()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}

			_size = 0;

			delete _head;
			_head = nullptr;
		}

	private:
		//成员函数为list的头节点指针,和链表长度
		Node* _head;
		size_t _size;
	};
}

 

1.2迭代器类的实现

【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改,C++,c++
【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改,C++,c++
 

  因为list的底层实现和之前的vector和string不同，vector和string是数组和顺序表，而list底层是链表。而对于数组和顺序表，我们可以直接使用指针来实现其迭代器，但是对于list类型就无法使用指针来实现它的迭代器，因为迭代器++无法访问到他的下一个节点。所以我们这里建立一个迭代器的结构体，用来封装node指针，来实现list的专属迭代器

  这段代码定义了一个名为__list_iterator的迭代器结构体，用于遍历链表。该结构体模板有三个模板参数：T表示链表中节点的数据类型，Ref表示引用类型T&，Ptr表示指针类型 T* _node：指向链表节点的指针。构造函数__list_iterator(Node* node)：用于初始化迭代器对象，将指针node赋值给_node。通过_node就可以实现各种操作符重载。

  定义了一个迭代器结构体，用于在链表中进行遍历和操作。通过重载运算符，可以使用迭代器对象像指针一样访问链表中的元素。

//使用类进行封装Node*，来实现list的专属迭代器
//list迭代器和一些内置类型迭代器不一样，++无法准确访问到下一个位置
//typedef __list_iterator<T, T&> iterator;
//typedef __list_iterator<T, const T&> iterator;
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->_val;
	}

	//重载->
	Ptr operator->()
	{
		return &_node->_val;
	}

	//重载前置++
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	//重载后置++
	self operator++(int)
	{
		__list_iterator<T> tmp(*this);

		_node = _node->_next;

		return tmp;
	}

	//重载前置--
	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	//重载后置--
	self operator--(int)
	{
		self tmp(*this);

		_node = _node->_prev;

		return tmp;
	}

	//重载!=
	bool operator!=(const self& it) const
	{
		return _node != it._node;
	}

	//重载==
	bool operator==(const self& it) const
	{
		return _node == it._node;
	}
};

  通过建立一个新的结构体来重载迭代器，我们即可实现list专属迭代器对其链表进行++、- -等操作。

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

//list迭代器实现
iterator begin()
{
	//隐式类型转换，内置类型转换为自定义类型，实现迭代器功能
	//return _head->_next;
	return iterator(_head->_next);
}

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

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

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

 

1.3运算符重载

  迭代器的运算符重载在上面的代码中，已经都基本实现了。

【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改,C++,c++

  赋值运算符重载函数operator=首先创建了一个临时的链表对象lt，并将传入的链表对象的副本赋值给lt。然后，调用swap函数，将当前链表对象和临时链表对象进行交换。这样做的原因是为了实现异常安全的赋值操作。通过将传入的链表对象的副本赋值给临时链表对象，可以确保在交换过程中不会影响到传入的链表对象。 最后，返回当前链表对象的引用。

  通过这样的实现逻辑，可以实现链表对象之间的赋值操作，并且保证在异常发生时不会破坏数据的完整性。

//交换
void swap(list<T>& lt)
{
	std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}

//赋值运算符重载
list<T>& operator=(list<T> lt)
	//list& operator=(list lt)
{
	swap(lt);

	return *this;
}

 

1.4增删查改

push_back

【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改,C++,c++
  和带头双向循环链表的尾插一样。首先，创建一个新的链表节点newnode，节点的值为传入的参数x。然后，获取到链表的尾指针tail，即头节点的前一个节点。

  接着，将新节点newnode插入到链表的尾部。首先，将新节点的前驱指针指向尾节点tail，将尾节点的后继指针指向新节点。这样就将新节点连接到了链表的尾部。

  然后，将新节点的后继指针指向头节点，将头节点的前驱指针指向新节点。这样就将新节点连接到了链表的头部。

//尾插
void push_back(const T& x)
{
	//创建一个新的链表结点，且获取到链表的尾指针
	Node* newnode = new Node(x);
	Node* tail = _head->_prev;

	//连接尾结点
	newnode->_prev = tail;
	tail->_next = newnode;

	//连接头节点
	_head->_prev = newnode;
	newnode->_next = _head;

	++_size;
}

 

insert

【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改,C++,c++

  和上面的逻辑类似。

//在pos位置之前插入
iterator insert(iterator pos, const T& x)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* newnode = new Node(x);

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

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

	++_size;

	return newnode;
}

 

erase

【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改,C++,c++
  首先，通过断言判断传入的迭代器pos不等于链表的末尾迭代器。如果等于末尾迭代器，表示要删除的节点不存在，会导致错误。然后，根据传入的迭代器pos获取到要删除的节点cur，以及其前驱节点prev和后继节点next。

  接着，将前驱节点的后继指针指向后继节点，将后继节点的前驱指针指向前驱节点。这样就将要删除的节点从链表中断开。然后，释放要删除的节点的内存。还要将链表的大小减1。

  为了避免迭代器失效，返回下一个节点的指针作为新的迭代器。这样可以保证在删除节点后，仍然可以使用返回的迭代器进行遍历和操作。

//删除
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;

	--_size;

	//为了避免迭代器失效，返回下一个结点指针
	return next;
}

 
完整实现

#pragma once

#include<assert.h>

namespace my_list
{	
	//用类模板定义一个list结点
	template<class T>
	struct _list_node
	{
		//list结点的构造函数，T()作为缺省值，当未转参时调用
		_list_node(const T& val = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _val(val)
		{}

		//list_node的成员函数，list为带头双向循环链表
		_list_node* _prev;
		_list_node* _next;
		T _val;
	};

	//使用类进行封装Node*，来实现list的专属迭代器
	//list迭代器和一些内置类型迭代器不一样，++无法准确访问到下一个位置
	//typedef __list_iterator<T, T&> iterator;
	//typedef __list_iterator<T, const T&> iterator;
	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->_val;
		}

		//重载->
		Ptr operator->()
		{
			return &_node->_val;
		}

		//重载前置++
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		//重载后置++
		self operator++(int)
		{
			__list_iterator<T> tmp(*this);

			_node = _node->_next;

			return tmp;
		}

		//重载前置--
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		//重载后置--
		self operator--(int)
		{
			self tmp(*this);

			_node = _node->_prev;

			return tmp;
		}

		//重载!=
		bool operator!=(const self& it) const
		{
			return _node != it._node;
		}

		//重载==
		bool operator==(const self& it) const
		{
			return _node == it._node;
		}
	};

	//实现const类型迭代器
	/*template<class T>
	struct __list_const_iterator
	{
		typedef list_node<T> Node;
		Node* _node;

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

		const T& operator*()
		{
			return _node->_val;
		}

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

		__list_const_iterator<T> operator++(int)
		{
			__list_const_iterator<T> tmp(*this);

			_node = _node->_next;

			return tmp;
		}

		bool operator!=(const __list_const_iterator<T>& it)
		{
			return _node != it._node;
		}

		bool operator==(const __list_const_iterator<T>& it)
		{
			return _node == it._node;
		}
	};*/

	//用类模拟实现list
	template<class T>
	class list
	{
	private:
		typedef _list_node<T> Node;
		
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		//list迭代器实现
		iterator begin()
		{
			//隐式类型转换，内置类型转换为自定义类型，实现迭代器功能
			//return _head->_next;
			return iterator(_head->_next);
		}

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

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

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

		//初始化
		void empty_init()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;

			_size = 0;
		}

		//list的构造函数，初始化头节点指针
		list()
		{
			empty_init();
		}

		//拷贝构造
		list(const list<T>& lt)
			//list(const list& lt)
		{
			empty_init();

			for (auto& e : lt)
			{
				push_back(e);
			}
		}

		//交换
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		//赋值运算符重载
		list<T>& operator=(list<T> lt)
			//list& operator=(list lt)
		{
			swap(lt);

			return *this;
		}

		//析构函数
		~list()
		{
			clear();

			delete _head;
			_head = nullptr;
		}

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

			_size = 0;
		}

		//尾插
		void push_back(const T& x)
		{
			//创建一个新的链表结点，且获取到链表的尾指针
			Node* newnode = new Node(x);
			Node* tail = _head->_prev;

			//连接尾结点
			newnode->_prev = tail;
			tail->_next = newnode;

			//连接头节点
			_head->_prev = newnode;
			newnode->_next = _head;

			++_size;

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

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

		//尾删
		void pop_back()
		{
			erase(--end());
		}

		//头删
		void pop_front()
		{
			erase(begin());
		}

		//在pos位置之前插入
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);

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

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

			++_size;

			return newnode;
		}

		//删除
		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;

			--_size;

			//为了避免迭代器失效，返回下一个结点指针
			return next;
		}

		//返回size
		size_t size()
		{
			/*size_t sz = 0;
			iterator it = begin();
			while (it != end())
			{
				++sz;
				++it;
			}

			return sz;*/

			return _size;
		}

	private:
		//成员函数为list的头节点指针,和链表长度
		Node* _head;
		size_t _size;
	};

	//打印函数
	void print(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			// (*it) += 1;
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
}

 
测试代码文章来源地址https://www.toymoban.com/news/detail-622614.html

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<list>
using namespace std;

#include"list.h"

void test_list1()
{
	//list<int> lt;
	//lt.push_back(1);
	//lt.push_back(2);
	//lt.push_back(3);
	//lt.push_back(4);
	//for (auto e : lt)
	//{
	//	cout << e << " ";
	//}
	//cout << endl;

	my_list::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	
	my_list::list<int>::iterator it = lt.begin();

	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	auto itt = lt.begin();

	while (itt != lt.end())
	{
		++(*itt);
		++itt;
	}

	for (auto e: lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

struct A
{
	A(int a1 = 0, int a2 = 0)
		:_a1(a1)
		, _a2(a2)
	{}

	int _a1;
	int _a2;
};

void test_list2()
{
	my_list::list<A> lt;
	lt.push_back(A(1, 1));
	lt.push_back(A(2, 2));
	lt.push_back(A(3, 3));
	lt.push_back(A(4, 4));

	auto it = lt.begin();
	while (it != lt.end())
	{
		//cout << *(it)._a1 << " " << *(it)._a2 <<endl;
		cout << it->_a1 << " " << it->_a2 << endl;
		++it;
	}
	cout << endl;
}

void test_list3()
{
	my_list::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	lt.push_front(5);
	lt.push_front(6);

	print(lt);

	lt.pop_front();
	lt.pop_back();

	print(lt);

	lt.clear();
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);

	print(lt);

	cout << lt.size() << endl;
	
}


int main()
{
	//test_list1();
	//test_list2();
	test_list3();
	return 0;
}

到了这里，关于【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

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

相关文章

  • [ C++ ] STL---反向迭代器的模拟实现

    [ C++ ] STL---反向迭代器的模拟实现

    目录 前言： 反向迭代器简介 list反向迭代器的模拟实现  反向迭代器的模拟实现(适配器模式) SGI版本STL反向迭代器源码 STL库中解引用操作与出口设计 适配list的反向迭代器 适配vector的反向迭代器 反向迭代器 是一种特殊类型的迭代器，它可以 逆向遍历容器中的元素 ，与正向

    2024年04月15日
    浏览(27)
  • STL中的string类的模拟实现【C++】

    STL中的string类的模拟实现【C++】

    构造函数设置为缺省参数，若不传入参数，则默认构造为空字符串。字符串的初始大小和容量均设置为传入C字符串的长度（不包括’\\0’） 在模拟实现拷贝构造函数前，我们应该首先了解深浅拷贝： 浅拷贝：拷贝出来的目标对象的指针和源对象的指针指向的内存空间是同一

    2024年02月15日
    浏览(29)
  • 【C++】STL——反向迭代器的模拟实现：迭代器适配器

    【C++】STL——反向迭代器的模拟实现：迭代器适配器

    反向迭代器的使用相信大家都已经比较熟悉了，那我们这篇文章具体讲什么呢？ 🆗，这篇文章我们重点来讲一下 反向迭代器的模拟实现 。 那为什么我们之前不和正向迭代器放在一块讲呢？为什么要等到我们讲完了容器适配器再来讲反向迭代器的模拟实现呢？ 那这个问题我

    2024年02月08日
    浏览(33)
  • 【C++】STL反向迭代器模拟实现，迭代器适配器，迭代器类型简单介绍

    【C++】STL反向迭代器模拟实现，迭代器适配器，迭代器类型简单介绍

    本篇主要讲反向迭代器的模拟实现。 能够加深各位对泛型的理解。 前面我那篇string介绍里面已经提到过反向迭代器是啥了，如果点进来的同学还不知道，可以看看：[string介绍](https://blog.csdn.net/m0_62782700/article/details/130796914? spm=1001.2014.3001.5501) 迭代器，可以在不暴露底层实现细

    2024年02月16日
    浏览(32)
  • 【C++初阶】STL详解（二）string类的模拟实现

    【C++初阶】STL详解（二）string类的模拟实现

    本专栏内容为：C++学习专栏，分为初阶和进阶两部分。 通过本专栏的深入学习，你可以了解并掌握C++。 💓博主csdn个人主页：小小unicorn ⏩专栏分类：C++ 🚚代码仓库：小小unicorn的代码仓库🚚 🌹🌹🌹关注我带你学习编程知识 注：为了防止与标准库当中的string类产生命名冲

    2024年02月05日
    浏览(37)
  • C++ STL-＞list模拟实现

    C++ STL-＞list模拟实现

    list list文档 list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。 list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向 其前一个元素和后一个元素。 list与forward_list非常相似：最主

    2024年02月20日
    浏览(31)
  • 【C++练级之路】【Lv.7】【STL】vector类的模拟实现

    【C++练级之路】【Lv.7】【STL】vector类的模拟实现

    快乐的流畅：个人主页 个人专栏：《C语言》《数据结构世界》《进击的C++》 远方有一堆篝火，在为久候之人燃烧！ 关于STL容器的学习，我们来到了运用 最广泛、最常见的vector 。有了之前关于string的学习，我们对容器设计有了一个大概的了解，而今天在熟悉的基础上去探求

    2024年01月24日
    浏览(40)

  • 【C++练级之路】【Lv.6】【STL】string类的模拟实现

    欢迎各位小伙伴关注我的专栏，和我一起系统学习C语言，共同探讨和进步哦！ 学习专栏 ： 《进击的C++》 关于 STL容器 的学习，我会采用 模拟实现 的方式，以此来更加清楚地了解其 底层原理和整体架构 。而string类更是有100多个接口函数，所以模拟实现的时候只会调重点和

    2024年01月18日
    浏览(35)
  • [ C++ ] STL---list的模拟实现

    [ C++ ] STL---list的模拟实现

    目录 结点类的模拟实现 迭代器类的模拟实现 构造函数 前置++与后置++ 前置- -与后置 - - == 与 !=运算符重载 * 运算符重载 - 运算符重载 普通迭代器总体实现代码 list类的实现 list类的成员变量 构造函数 迭代器 insert(） erase() push_front/push_back/pop_front/pop_back front/back clear() empty()

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

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

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

    2024年01月22日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包