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

C++：模拟实现list及迭代器类模板优化方法

7月前 作者：海绵宝宝de派小星 分类：Toy博客 阅读(28) 违法举报

这篇具有很好参考价值的文章主要介绍了C++：模拟实现list及迭代器类模板优化方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本篇模拟实现简单的list和一些其他注意的点

C++：模拟实现list及迭代器类模板优化方法,C++,# 模拟实现,知识总结,c++

迭代器

如下所示是利用拷贝构造将一个链表中的数据挪动到另外一个链表中，构造两个相同的链表

list(const list<T>& lt)
{
	emptyinit();
	for (auto e : lt)
	{
		push_back(e);
	}
}

void test_list1()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	list<int> l2(lt);
}

lt作为形参，传引用可以提高传参的效率，同时应该加上const修饰来保证不会因为不小心修改了形参导致外部的实参也被修改，这样的结果是不应该的，因此就要加const把这个形参变成一个const对象

而问题又来了，const对象要使用的是const迭代器，而前面没有写const迭代器，因此这里就引入了const迭代器的实现

从vector的模拟实现中，看似似乎只需要在原来的迭代器的基础上加上一个const即可，但事实上：

const迭代器和普通迭代器是两种不同的迭代器，不能直接在普通的迭代器后面加const，原因？

要解决这个问题，先重新回顾一下vector中const迭代器的定义流程：

对比vector的迭代器，vector中的迭代器const版本和非const版本直接在非const版本后面加const使它变成const迭代器即可，这样在调用的时候就可以直接进行调用

C++：模拟实现list及迭代器类模板优化方法,C++,# 模拟实现,知识总结,c++

对iterator的定义，const版本就是在指针前面加上const，这样返回的就是const修饰的指针，因此就可以做到通过该迭代器只读，不可修改的作用

C++：模拟实现list及迭代器类模板优化方法,C++,# 模拟实现,知识总结,c++

这里的迭代器本质上就是指针在底层进行访问，然后我们定义一个const指针，使得const指针就不能对指针指向的内容进行修改了

下面仿照vector修改的原理修改list

要修改的部分其实就是下面的代码：

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

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

在函数后加const很简单，但是核心是要把返回值也定义为const指针版本，这个过程要如何实现？

由于这里是把iterator封装成了一个类进行的实现，因此需要重新封装一个类进行实现

	template <class T>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef  __list_iterator<T> self;
		// 成员
		Node* _node;

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

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

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

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

		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& pos)
		{
			return _node == pos._node;
		}

		bool operator!=(const self& pos)
		{
			return !(*this == pos);
		}
	};

	template <class T>
	struct __list_const_iterator
	{
		typedef list_node<T> Node;
		typedef  __list_const_iterator<T> self;
		// 成员
		Node* _node;

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

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

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

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

		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

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

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

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

		bool operator!=(const self& pos)
		{
			return !(*this == pos);
		}
	};

但事实上，这两份代码只有很少的地方有区别，更多的内容都是相同的，这样是不满足较好的代码风格，因此在stl源码中，使用了模板对这两个类进行了封装

改进版本如下：

	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)
		{}

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

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

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

		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& pos)
		{
			return _node == pos._node;
		}

		bool operator!=(const self& pos)
		{
			return !(*this == pos);
		}
	};

	template <class T>
	class list
	{
		void emptyinit()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
	public:
		typedef list_node<T> Node;
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		// 构造函数 
		list()
		{
			emptyinit();
		}
		// 拷贝构造
		list(const list<T>& lt)
		{
			emptyinit();
			auto it = lt.begin();
			//*it = 30;
		}

		void push_back(const T& x)
		{
			insert(end(), x);
		}

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

		// head     tail->prev  tail
		void pop_back()
		{
			erase(--end());
		}

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

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

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

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

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

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

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

			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

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

			return iterator(next);
		}

	private:
		Node* _head;
		size_t _size;
	};

这里引入了类模板的概念，简单来说，当需要调用const类型时就会模板实例化出一个const版本的迭代器，再进行相关的操作，这样的操作可以避免代码冗余，也是模板的强大之处文章来源地址https://www.toymoban.com/news/detail-649281.html

模拟实现

#pragma once

// 实现的是双向循环链表，链表中应该包含节点类和迭代器类，节点类用于从内存中申请节点，迭代器类用于获取节点指针
namespace mylist
{
	// 把节点进行封装，可以动态获取一个节点
	template <class T>
	struct list_node
	{
		// 成员
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;

		// 成员函数
		list_node(const T& val = T())
			:_data(val)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};

	// 对迭代器进行封装，使得外界看到的是迭代器
	// 迭代器当中存储的是某个节点的指针
	// 可以对迭代器进行各项操作
	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)
		{}

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

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

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

		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& pos)
		{
			return _node == pos._node;
		}

		bool operator!=(const self& pos)
		{
			return !(*this == pos);
		}
	};

	// 适配器 -- 复用
	template <class T, class Ref, class Ptr >
	struct __reverse_iterator
	{
		typedef list_node<T> Node;
		typedef  __reverse_iterator<T, Ref, Ptr> self;
		// 成员
		Node* _node;

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

		self& operator++()
		{
			_node = _node->_prev;
			return *this;
		}

		self& operator--()
		{
			_node = _node->_next;
			return *this;
		}

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

		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

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

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

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

		bool operator!=(const self& pos)
		{
			return !(*this == pos);
		}
	};


	template <class T>
	class list
	{
		void emptyinit()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
	public:
		typedef list_node<T> Node;
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		typedef __reverse_iterator<T, T&, T*> reverse_iterator;
		typedef __reverse_iterator<T, const T&, const T*> const_reverse_iterator;

		// 构造函数 
		list()
		{
			emptyinit();
		}
		// 拷贝构造
		list(const list<T>& lt)
		{
			emptyinit();
			auto it = lt.begin();
			//*it = 30;
		}

		void push_back(const T& x)
		{
			insert(end(), x);
		}

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

		// head     tail->prev  tail
		void pop_back()
		{
			erase(--end());
		}

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

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

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

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

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

		reverse_iterator rbegin()
		{
			return reverse_iterator(_head->_prev);
		}

		reverse_iterator rend()
		{
			return reverse_iterator(_head);
		}

		const_reverse_iterator rbegin() const
		{
			return const_reverse_iterator(_head->_prev);
		}

		const_reverse_iterator rend() const
		{
			return const_reverse_iterator(_head);
		}

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

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

			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

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

			return iterator(next);
		}

	private:
		Node* _head;
		size_t _size;
	};


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

		cout << "逆序" << endl;
		auto rit = lt.rbegin();
		while (rit != lt.rend())
		{
			cout << *rit << " ";
			rit++;
		}
		cout << endl;
	}
}

到了这里，关于C++：模拟实现list及迭代器类模板优化方法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

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

相关文章

  • STL之list模拟实现(反向迭代器讲解以及迭代器失效)

    这次是关于list的模拟实现的代码，先看看下面的代码： 上面是list的代码，其底层是一个带头双向循环的链表，实现的方法就不说了，相信大家已经都会了，然后自己实心的list我没有写析构函数等，这个也很简单，循环利用成员函数中的删除函数就可以。 先来说说个人认为

    2024年02月11日
    浏览(33)
  • list【2】模拟实现（含迭代器实现超详解哦）

    list【2】模拟实现（含迭代器实现超详解哦）

    在前面，我们介绍了list的使用： 戳我看list的介绍与使用详解哦 在本篇文章中将重点介绍list的接口实现，通过模拟实现可以更深入的理解与使用list 我们模拟实现的 list 底层是一个带头双向循环链表 在实现list时，我们首先需要一个 结构体以表示链表中结点的结构 list_node ，

    2024年02月10日
    浏览(23)
  • [STL-list]介绍、与vector的对比、模拟实现的迭代器问题

    [STL-list]介绍、与vector的对比、模拟实现的迭代器问题

     list的底层是 带头双向链表 结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。 与其他的序列式容器相比(array，vector，deque)，list通常 在任意位置进行插入、移除元素的执行效率更好 list最大的缺陷是 不支持任意位

    2024年04月15日
    浏览(65)
  • 【c++迭代器模拟实现】

    【c++迭代器模拟实现】

    打怪升级：第52天 什么是STL STL(standard template libaray-标准模板库)：是C++标准库的重要组成部分，不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。 STL的版本 原始版本 Alexander Stepanov、Meng Lee 在惠普实验室完成的原始版本，本着开源精神，他们声明允许

    2024年02月02日
    浏览(26)
  • 【C++】vector模拟实现+迭代器失效

    【C++】vector模拟实现+迭代器失效

    铁汁们，今天给大家分享一篇vector模拟实现 + 迭代器失效，来吧，开造⛳️ 指向最后一个空间的下一个位置 💡 iterator _endofstorage 指向存储第一个有效数据空间的位置 💡 iterator _start 指向存储最后一个有效数据空间的下一个位置 💡 iterator _finish 在成员变量声明处给缺省值，

    2024年02月21日
    浏览(33)
  • 【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---反向迭代器的模拟实现

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

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

    2024年04月15日
    浏览(27)

  • 【C++模拟实现】list的模拟实现

    作者：爱写代码的刚子 时间：2023.9.3 前言：本篇博客关于list的模拟实现和模拟实现中遇到的问题 list模拟实现的部分代码 list模拟实现中的要点 const_iterator的实现 我们选择使用模版参数，复用iterator的类，设置三个模版参数： templateclass T,class Ref,class Ptr 并且 typedef __list_iter

    2024年02月09日
    浏览(38)
  • [C++历练之路]优先级队列||反向迭代器的模拟实现

    [C++历练之路]优先级队列||反向迭代器的模拟实现

    W...Y的主页 😊  代码仓库分享💕 🍔前言： 在C++的宇宙中，优先队列似乎是一座巨大的宝库，藏匿着算法的珍宝。而就在这片代码的天空下，我们不仅可以探索优先队列的神奇，还能够揭开反向迭代器的神秘面纱。让我们一同踏入这个编程的探险之旅，在这里，我们将用C

    2024年02月04日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包