【C++】list的使用与模拟实现

2024-05-13 1547阅读

🔥个人主页：北辰水墨

🔥专栏：C++学习仓

本节内容我们来讲解list的使用和模拟实现。本节难点：list迭代器的模拟实现。

一、list的介绍：

列表

列表是一种序列容器，允许在序列的任何位置进行时间复杂度为O(1)的插入和删除操作，并可在前后两个方向上进行迭代。

列表容器被实现为双向链表；双向链表可以将它们包含的每个元素存储在不同且不相关的存储位置中。通过将每个元素关联到其前面的元素和后面的元素的链接来在内部保持顺序。

它们与forward_list非常相似：主要区别在于forward_list对象是单向链表，因此forward_list对象只能向前迭代，作为交换，forward_list对象相对较小和更高效。

与其他基本标准序列容器（数组，向量和双端队列）相比，列表在已获得迭代器的情况下通常在容器内的任何位置执行插入、提取和移动元素方面表现更好，因此在那些大量使用这些操作的算法（如排序算法）中也表现更好。

与其他序列容器相比，列表和forward_list的主要缺点是它们缺乏通过位置直接访问元素的能力；例如，要访问列表中的第六个元素，需要从已知位置（如开头或结尾）迭代到该位置，这在这两者之间的距离上需要线性时间。它们还会消耗一些额外的内存来保存与每个元素关联的链接信息（对于大量小尺寸元素的大型列表可能是一个重要因素）。

总结：list是一个带头双向循环列表。

二、接口函数：

2.1 构造函数：

2.1.1 Default constructor (构造一个空的 std::list):
std::list myList1; // 创建一个空的整型链表

2.1.2 Fill constructor (构造一个有特定数量元素且每个元素都有相同初始值的 std::list):

std::list myList2(5, 10); // 创建一个有5个元素的链表，每个元素都初始化为10

2.1.3 Range constructor (从另一个迭代器定义范围的容器中构建 std::list):

std::vector myVector{1, 2, 3, 4, 5};

std::list myList3(myVector.begin(), myVector.end()); // 使用vector的范围来初始化链表

2.1.4 Copy constructor (使用另一个 std::list 来构造一个新的 std::list, 是副本):

std::list myOriginalList{1, 2, 3, 4, 5};

std::list myList4(myOriginalList); // 使用另一个list来初始化这个新的list

Fill constructor构造函数前面加explicit,表示不能隐式类型转换

2.2 迭代器

用法保持不变：

#include
#include
using namespace std;
int main()
{
	list lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	list::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout member 即可。编译器会自动将其 “转换” 为 it.operator->()->member 
在 ListIterator 示例里，it->_a1 意味着： 
1.  调用 it.operator->() 拿到 ListNode 中 _data 成员的地址（这是一个 A 类型的对象）。
2.  使用返回的指针来访问 A 对象的 _a1 成员。 
 
 整个过程对于编程者来说是透明的，不需要编写多个 ->。这种处理方式使得重载 -> 可以更自然地使用，就像处理普通的指针一样。 
 
const迭代器 
我们上面写的迭代器对于const对象是无法编译成功的，const不能调用非const成员函数 
对于const类迭代器，我们需要在list类里面重新增加重载： 
typedef _const__list_iterator const_iterator;
const_iterator begin() const
{
    return _head->_next;
}
const_iterator end() const
{
    return _head;
}
 
 
 这样子我们就有两个版本：iterator 和 const_iterator 
     普通对象调用iterator版本     const对象调用iterator版本  
 
1.  这里的const版本不是对普通迭代器进行const修饰。（想象当我们使用const修饰指针，指针不能移动，指针指向的内容可以修改，不符合我们的预期） 
2.  const迭代器是一个重新定义的类型，本身可以修改，指向的内容不可以修改 
 
 总结：const_interator 是一个单独的类，我们要实现的是 不能修改数据的（不能改变迭代器指向内容的值），而不是不能移动的迭代器（让迭代器++/--等等操作，这样子就需要能改变迭代器的值）。 
 
方法一：单独再实现一个const_iterator类 
	template
	struct _const__list_iterator
	{
		typedef __list_node Node;
		typedef _const__list_iterator self;
		//成员变量
		Node* _PtrNode;
		_const__list_iterator(Node* x)
			:_PtrNode(x)
		{}
		self& operator++()
		{
			_PtrNode = _PtrNode->next;//节点的指针
			return  *this; // 迭代器
		}
		self& operator++(int)
		{
			self tmp(*this);
			_PtrNode = _PtrNode->next;
			return tmp;
		}
		self& operator--()
		{
			_PtrNode = _PtrNode->prev;//节点的指针
			return  *this; // 迭代器
		}
		self& operator--(int)
		{
			self tmp(*this);
			_PtrNode = _PtrNode->prev;
			return tmp;
		}
		const T& operator*()
		{
			return _PtrNode->_val;
		}
		bool operator!=(const self& it)  //it!=lt.end()
		{
			return _PtrNode != it._PtrNode;
		}
		const T* operator->()
		{
			return &_PtrNode->_val;
		}
	}; 
  
 合并两中迭代器： 
 
 这里仅仅只是两种返回类型不同，这里我们利用模版来对这里内容进行合并  
 
	template
	struct __list_iterator
	{
		typedef __list_node Node;
		typedef __list_iterator self;
		//成员变量
		Node* _PtrNode;
		__list_iterator(Node* x)
			:_PtrNode(x)
		{}
		Ref operator*()
		{
			return _PtrNode->_val;
		}
		Ptr operator->()
		{
			return &_PtrNode->_val;
		}
		self& operator++()
		{
			_PtrNode = _PtrNode->next;//节点的指针
			return  *this; // 迭代器
		}
		self& operator++(int)
		{
			self tmp(*this);
			_PtrNode=_PtrNode->next;
			return tmp;
		}
		self& operator--()
		{
			_PtrNode = _PtrNode->prev;//节点的指针
			return  *this; // 迭代器
		}
		self& operator--(int)
		{
			self tmp(*this);
			_PtrNode = _PtrNode->prev;
			return tmp;
		}
		bool operator!=(const self& it)  //it!=lt.end()
		{
			return _PtrNode != it._PtrNode;
		}
		
	}; 
 我们只提取不同的部分，其他部分与原来相同 
Ref代表引用，Ptr代表指针 
让我们来看一下这个合并后的迭代器的模板参数：

T：列表节点存储的数据类型
Ref：通过迭代器访问数据时的返回类型，可以是T&或者const T&。

Ptr：通过迭代器访问数据的指针类型，可以是T*或者const

这样，我们可以创建一个常量迭代器，为Ref和Ptr参数指定常量类型，例如：

__list_iterator const_iterator;

对于非常量迭代器，就简单地传递非常量类型的引用和指针：

__list_iterator iterator;

在list类中，我们需要相应地声明两种类型的迭代器：

	template
	class list
	{
	public:
		typedef __list_node Node;
		typedef __list_iterator iterator;
		typedef __list_iterator const_iterator;
		list()
		{
			_head = new Node;
			_head->prev = _head;
			_head->next = _head;
			_size = 0;
		}
		iterator begin()
		{
			return _head->next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator begin() const
		{
			return _head->next;
		}
		const_iterator end() const
		{
			return _head;
		}
		iterator insert(iterator pos,const T& val)
		{
			Node* newnode = new Node(val);
			Node* cur = pos._PtrNode;//pos是__list_iterator类的一个实例化对象，pos._PtrNode是去取对象中的成员
			Node* prev = cur->prev;
			// prev newnode cur
			prev->next = newnode;
			newnode->prev = prev;
			cur->prev = newnode;
			newnode->next = cur;
			_size++;
			return newnode;
		}
		iterator erase(iterator pos)
		{
			Node* cur = pos._PtrNode;
			Node* prev = cur->prev;
			Node* next = cur->next;
			prev->next = next;
			next->prev = prev;
			delete(cur);
			_size--;
			return next;
		}
		void push_back(const T& val)
		{
			insert(end(), val);
		}
		void  push_front(const T& val)
		{
			insert(begin(), val);
		}
		void pop_back()
		{
			erase(--end());
		}
		void pop_front()
		{
			erase(begin());
		}
		size_t size()
		{
			return _size;
		}
		bool empty()
		{
			return _size == 0;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it); //_size在erase函数中会减小
			}
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
	private:
		Node* _head;
		size_t _size;
	};
}

list类中的其他成员函数像begin、end需要按照是否接收常量类型来适配这两种迭代器。

list::const_iterator it=lt.begin();

list:: iterator it=lt.begin();

需要在list类里面访问

通过左边的类型，推出右边是用哪一种迭代器。

模拟实现list的源码，仅供参考，纯手打的代码，可能会有bug，还请各位大佬批评指正。

namespace moon
{
	template
	struct __list_node
	{
		T _val;
		__list_node* prev;
		__list_node* next;
		__list_node(const T& x=T())
			:_val(x)
			,prev(nullptr)
			,next(nullptr)
		{}
	};
	template
	struct __list_iterator
	{
		typedef __list_node Node;
		typedef __list_iterator self;
		//成员变量
		Node* _PtrNode;
		__list_iterator(Node* x)
			:_PtrNode(x)
		{}
		Ref operator*()
		{
			return _PtrNode->_val;
		}
		Ptr operator->()
		{
			return &_PtrNode->_val;
		}
		self& operator++()
		{
			_PtrNode = _PtrNode->next;//节点的指针
			return  *this; // 迭代器
		}
		self& operator++(int)
		{
			self tmp(*this);
			_PtrNode=_PtrNode->next;
			return tmp;
		}
		self& operator--()
		{
			_PtrNode = _PtrNode->prev;//节点的指针
			return  *this; // 迭代器
		}
		self& operator--(int)
		{
			self tmp(*this);
			_PtrNode = _PtrNode->prev;
			return tmp;
		}
		bool operator!=(const self& it)  //it!=lt.end()
		{
			return _PtrNode != it._PtrNode;
		}
		
	};
	template
	class list
	{
	public:
		typedef __list_node Node;
		typedef __list_iterator iterator;
		typedef __list_iterator const_iterator;
		list()
		{
			_head = new Node;
			_head->prev = _head;
			_head->next = _head;
			_size = 0;
		}
		iterator begin()
		{
			return _head->next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator begin() const
		{
			return _head->next;
		}
		const_iterator end() const
		{
			return _head;
		}
		iterator insert(iterator pos,const T& val)
		{
			Node* newnode = new Node(val);
			Node* cur = pos._PtrNode;//pos是__list_iterator类的一个实例化对象，pos._PtrNode是去取对象中的成员
			Node* prev = cur->prev;
			// prev newnode cur
			prev->next = newnode;
			newnode->prev = prev;
			cur->prev = newnode;
			newnode->next = cur;
			_size++;
			return newnode;
		}
		iterator erase(iterator pos)
		{
			Node* cur = pos._PtrNode;
			Node* prev = cur->prev;
			Node* next = cur->next;
			prev->next = next;
			next->prev = prev;
			delete(cur);
			_size--;
			return next;
		}
		void push_back(const T& val)
		{
			insert(end(), val);
		}
		void  push_front(const T& val)
		{
			insert(begin(), val);
		}
		void pop_back()
		{
			erase(--end());
		}
		void pop_front()
		{
			erase(begin());
		}
		size_t size()
		{
			return _size;
		}
		bool empty()
		{
			return _size == 0;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it); //_size在erase函数中会减小
			}
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
	private:
		Node* _head;
		size_t _size;
	};
}

本篇list的使用与模拟实现，纯干货！！！

VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

【C++】list的使用与模拟实现

一、list的介绍：

二、接口函数：

2.1 构造函数：

2.2 迭代器

相关阅读

怎么把织梦的模板替换?

dedecms怎么调用特定的栏目文档?

怎么抓包一个网页?

wap怎么封装app?

目录[+]