资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

【C++】list的介绍及模拟实现-创新互联

🌈感谢阅读East-sunrise学习分享——list的介绍及模拟实现

成都创新互联公司是少有的成都网站设计、网站建设、营销型企业网站、重庆小程序开发、手机APP,开发、制作、设计、卖友情链接、推广优化一站式服务网络公司,从2013年成立,坚持透明化,价格低,无套路经营理念。让网页惊喜每一位访客多年来深受用户好评

博主水平有限，如有差错，欢迎斧正🙏感谢有你

码字不易，若有收获，期待你的点赞关注💙我们一起进步

今天想分享介绍一下STL的容器之一list，以及进行模拟实现📌

目录
  • 一、list的介绍
  • 二、list的模拟实现（简易版--过渡）
  • 三、迭代器
    • 1.迭代器的定义
    • 2.迭代器的功能分类
    • 3.迭代器失效
    • 4.list迭代器的模拟实现
      • 1.普通迭代器
      • 2.const迭代器
    • 5.迭代器operator->的重载
    • 6.迭代器的价值
  • 四、vector和list的优缺点
    • 1.vector
    • 2.list
  • 五、代码实现

一、list的介绍
  • list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
  • list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
  • list的底层结构即是链表，这里附上博主之前关于【数据结构】链表的博客【数据结构-链表】有助于熟悉list的底层结构
  • 关于list的使用并不复杂，相信学到这的兄弟以及拥有了查文档的能力，博主就不再赘述list各种接口的具体用法，附上文档介绍list使用文档

有了之前对数据结构——链表的知识基础，其实list的底层结构也并不神秘了，而list相较于前面的string、vector容器特别的地方就在于其迭代器，今天我们重点放在list的模拟实现及迭代器的介绍

二、list的模拟实现（简易版–过渡）

list底层结构是带头双向链表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iCkjCIlz-1672726780572)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20221225161843143.png)]

templatestruct list_node
{list_node* _next;//指向下一个节点
	list_node* _prev;//指向前一个节点
	T _data;//节点数据
    //构造函数
	list_node(const T& x)
		:_next(nullptr)
		, _prev(nullptr)
		, _data(x)
	{}
};

定义完list的节点，接下来即是list的主要结构

namespace qdy
{templatestruct list_node
	{list_node* _next;
		list_node* _prev;
		T _data;

		list_node(const T& x)
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}
	};

	templateclass list
	{typedef list_nodenode;
	public:
		list()
		{	_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;
            _size = 0;
		}
        
		//尾插
		void push_back(const T& x)
		{	node* newnode = new node(x);
			node* tail = _head->_prev;
			// _head         tail   newnode
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
		}

	private:
		node* _head;//哨兵位的头节点
		size_t _size;//记录节点个数
	};

以上便是list的结构框架（简易版实现），目前仅有尾插的接口，用于对list容器中添加数据✏️

添加数据后我们想要遍历打印怎么办呢？那就需要用到STL六大组件之一的迭代器🧮

三、迭代器 1.迭代器的定义

iterator的模式定义：“提供一种方法，使之能够依序巡访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。”

——《STL源码剖析》

🎈通俗理解：容器用于存放数据，存放数据便有访问数据读写数据的需求，STL六大组件之一的迭代器，便是给每个容器提供一个便于读取数据的方法

2.迭代器的功能分类
  1. 单向迭代器：只能++，不能–。例如单链表、哈希表
  2. 双向迭代器：既能++也能–。例如双向链表
  3. 随机访问迭代器：能+±-，也能+和-。例如vector和string

迭代器是内嵌类型，通常定义为内部类或者直接定义在类中

3.迭代器失效

对于list，迭代器在进行insert操作后不失效，在进行erase操作后失效❌

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

void TestListIterator1()
{int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 	listl(array, array+sizeof(array)/sizeof(array[0]));
 	auto it = l.begin();
 	while (it != l.end())
    {// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
        l.erase(it); 
 		++it;
 	}
}
// 改正
void TestListIterator()
{int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 	listl(array, array+sizeof(array)/sizeof(array[0]));
 	auto it = l.begin();
 	while (it != l.end())
 	{it = l.erase(it);
        //为了避免迭代器失效的问题，erase接口提供了返回值可接收，该返回值为删除后的下一节点
 	}
}
4.list迭代器的模拟实现 1.普通迭代器

在对迭代器模拟实现之前，我们要搞清楚list迭代器要有什么功能？

  1. 支持解引用（读取数据）
  2. 支持++和–（访问上一个or下一个节点）

回顾之前string和vector迭代器的模拟实现，我们是直接将指针typedef为迭代器使用，因为string和vector的底层结构是顺序表，是一段连续的物理空间，所以通过使用原生指针便能符合其迭代器的需求了✔️

💥但是list的底层结构是链表，链表是按需开辟空间，并不是一段连续的物理空间，每个节点的物理地址并不连续，我们无法直接使用原生指针去+±-来遍历来访问节点。我们回顾刚开始接触C++学习的日期类，日期类中的“日期”是我们自己定义的一种自定义类型，无法使用内置操作符直接对日期进行运算操作（编译器又不认识那么多）所以我们是通过自己再去重定义日期的操作类，去重载操作符来满足需求。

🚩类和对象说：该我上场表演了
既然原生指针已经无法满足list迭代器的需求，那么我们可以自己定义一个迭代器，然后将节点指针封装起来，然后再根据我们具体的需求情况去重载各种运算符实现迭代器功能。

//用类封装迭代器
templatestruct __list_iterator
{typedef list_nodenode;
	node* _pnode;//封装一个节点的指针
    
	//用节点指针进行构造
	__list_iterator(node* p)
		:_pnode(p)
	{}
	//迭代器运算符的重载
	T& operator*()
	{return _pnode->_data;
	}

	__list_iterator& operator++()
	{_pnode = _pnode->_next;
		return *this;//返回的是迭代器
	}

	bool operator!=(const __list_iterator& it)
	{return _pnode != it._pnode;
	}
};

定义完迭代器后便能对我们添加了数据的list进行遍历打印了
1.迭代器遍历 2.范围for遍历（底层也是调用了迭代器）

void test_list1()
{listlt;
	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<< *it<< " ";
		++it;
	}
	cout<< endl;

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

定义完迭代器后，通过迭代器对容器数据进行访问，实际上是一种函数调用

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pyU84UfV-1672726780573)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20221226124335878.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rUjQ5NTn-1672726780573)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20221226124607339.png)]

2.const迭代器

❌const迭代器的错误写法

typedef __list_iteratoriterator;
const list::iterator cit = lt.begin();

const之前我们修饰指针时有两种方法

const T* p1;
T* const p2;

正确的const迭代器应该是像p1的行为，保护指向的对象不被修改，但是迭代器本身是可以修改的

但是上述的const迭代器写法是保护了迭代器本身不能被修改，那么我们就不能++迭代器了

✔️正确写法：想实现const迭代器，无法对普通迭代器直接加const，需要再写一个const版本迭代器的类

templatestruct __list_const_iterator
{typedef list_nodenode;
	node* _pnode;

	__list_const_iterator(node* p)
		:_pnode(p)
	{}

	const T& operator*()const
	{return _pnode->_data;
	}

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

	__list_const_iterator& operator--()
	{_pnode = _pnode->_prev;
		return *this;
	}

	bool operator!=(const __list_const_iterator& it)
	{return _pnode != it._pnode;
	}
};

typedef __list_iteratorconst_iterator;

但是如果像上述一样，写一个普通迭代器再写一个const迭代器，代码看起来就十分的冗长。那么我们可以利用好类模板，类模板即是能根据模板和调用时的参数，根据实参类型推演产生函数的特定类型版本。这样，我们根据传入参数的不同，可以使得一份类模板生成两种类型的迭代器🧮

templatestruct __list_iterator
{typedef list_nodenode;
	typedef __list_iteratorSelf;
	node* _pnode;

	__list_iterator(node* p)
		:_pnode(p)
	{}
    
	Ref operator*()
	{return _pnode->_data;
	}
	
	Self& operator++()
	{_pnode = _pnode->_next;
		return *this;
	}

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

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

typedef __list_iteratoriterator;
typedef __list_iteratorconst_iterator;
5.迭代器operator->的重载

我们调用对象的成员变量成员函数是用.实现，对指针解引用取其值是用*实现，而当结构体要解引用是使用->，再用->取其成员变量。而假如现在list中就存放的是结构体类型的数据✏️

所以我们有必要对->也进行重载

T* operator->()
{return &_pnode->_data;
}

重载完之后我们要怎么使用呢❓一共有3种方法

//坐标类
struct Pos
{int _row;
	int _col;

	Pos(int row = 0, int col = 0)
		:_row(row)
		,_col(col)
	{}
};
void test()
{listlt;
   	lt.push_back(Pos(1,1));
	lt.push_back(Pos(2,2));
	lt.push_back(Pos(3,3));
    
	// int* p  --->*p
	// Pos* p  --->p->list::iterator it = lt.begin();
	while (it != lt.end())
	{cout<< (&(*it))->_row;
        //*it取出容器数据（POS类） -- 再取地址访问解引用得到_row
		cout<< it.operator->()->_row;
        //it.operator->()是显式调用，然后再->解引用得到_row
        cout<< it->_row;
        //同第二种写法，编译器为了可读性，省略了一个->
        ++it;
	}
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KhMzOZsV-1672726780574)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20221226133619031.png)]

💥但是当实际使用时，会发现有问题，那就是->的重载返回值为T*，这样一来无论是普通迭代器或const迭代器都能对其值进行修改，所以我们需要将operator->的返回值改为泛型，然后针对不同的迭代器给不同的返回参数以示区分，如此一来，我们的迭代器模板又得再多一个参数啦📈

templatePtr operator->()
{return &_pnode->_data;
}

typedef __list_iteratoriterator;
typedef __list_iteratorconst_iterator;
6.迭代器的价值
  1. 封装底层实现，不暴露底层实现的细节
  2. 多种容器提供统一的访问方式，降低容器使用成本
  3. C语言没有运算符重载和引用等语法，是实现不了迭代器的
四、vector和list的优缺点

vector和list就像左右手一样，是互补配合的关系

vector的优点即是list的缺点，list的优点也是vector的缺点，实际使用时可按照需求择优选用或者结合使用

1.vector

vector的优点

  1. 支持下标的随机访问
  2. 尾插尾删效率高（但是扩容的那一次尾插会较慢）
  3. CPU高速缓存命中高（得益于vector的结构是一段连续的物理空间，数据从缓存加载到CPU时，是会加载连续的一段数据，而不是一个个加载，这样一来在加载vector时高速缓存命中就很高）

🎈综上所述vector的优点都得益于其结构优势

vector的缺点

  1. 非尾插尾删效率极低O(N)
  2. 扩容有消耗，还存在一定的空间浪费

🎈迭代器失效

insert和erase均会导致迭代器失效

2.list

list的优点

  1. 按需申请释放，无需扩容
  2. 任意位置插入删除效率高O(1)

list的缺点

  1. 不支持下标的随机访问
  2. CPU高速缓存命中率低

🎈迭代器失效

insert不失效，erase失效

五、代码实现
namespace qdy
{templatestruct list_node
	{list_node* _next;
		list_node* _prev;
		T _data;

		list_node(const T& x)
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}
	};

	templatestruct __list_iterator
	{typedef list_nodenode;
		typedef __list_iteratorSelf;
		node* _pnode;

		__list_iterator(node* p)
			:_pnode(p)
		{}

		Ptr operator->()
		{	return &_pnode->_data;
		}

		Ref operator*()
		{	return _pnode->_data;
		}

		Self& operator++()
		{	_pnode = _pnode->_next;
			return *this;
		}

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

		Self operator--(int)
		{	Self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}

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

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

	templateclass list
	{typedef list_nodenode;
	public:
		typedef __list_iteratoriterator;
		//typedef __list_const_iteratorconst_iterator;
		typedef __list_iteratorconst_iterator;


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

		~list()
		{	clear();

			delete _head;
			_head = nullptr;
		}

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

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

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

		iterator begin()
		{	return iterator(_head->_next);
			//iterator it(_head->_next);
			//return it;
		}

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

		void empty_initialize()
		{	_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}

		templatelist(InputIterator first, InputIterator last)
		{	empty_initialize();
			while (first != last)
			{		push_back(*first);
				++first;
			}
		}

		void swap(list& lt)
		{	std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		// 现代写法
		// lt2(lt1)
		list(const list& lt)
			//list(const list& lt) // 不建议
		{	empty_initialize();

			listtmp(lt.begin(), lt.end());
			swap(tmp);
		}

		// lt3 = lt1
		list& operator=(listlt)
			//list& operator=(list lt) // 不建议
		{	swap(lt);
			return *this;
		}

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

			insert(end(), x);
		}

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

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

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

		iterator insert(iterator pos, const T& x)
		{	node* newnode = new node(x);
			node* cur = pos._pnode;
			node* prev = cur->_prev;

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

			++_size;
			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{	assert(pos != _head);

			node* prev = pos._pnode->_prev;
			node* next = pos._pnode->_next;

			prev->_next = next;
			next->_prev = prev;

			delete pos._pnode;
			--_size;

			return iterator(next);
		}

		size_t size()const
		{	return _size;
		}

		bool empty()const
		{	return _size == 0;
		}

	private:
		node* _head;
		size_t _size;
	};
}

🌈🌈写在最后
我们今天对list的分享就到此结束了
对于这篇博客最精华的部分便是迭代器的实现，迭代器在各种容器中是不可或缺的一部分🚩
🎈感谢能耐心地阅读到此
🎈码字不易，感谢三连
🎈关注博主，我们一起学习、一起进步

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


网页名称：【C++】list的介绍及模拟实现-创新互联
标题网址：http://www.cdkjz.cn/article/idjgg.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
软文平台物流公司网站建设方案航空文化传媒正泰动物制药成都400电话申请网站设计制作报价遂宁网站建设东方电机技改香港云主机邛崃发电机保养

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图