C++:关于模拟实现vector和list中迭代器模块的理解

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

本篇是关于vectorlist的模拟实现中,关于迭代器模块的更进一步理解,以及在前文的基础上增加对于反向迭代器的实现和库函数的对比等

本篇是写于前面模拟实现的一段时间后,重新回头看迭代器的实现,尤其是在模板角度对list中迭代器封装的部分进行解析,希望可以对迭代器的封装实现有更深层次的理解,同时将与库内的实现做对比进行优化处理

list和vector的迭代器对比

listvector的迭代器实现是不一样的,在vector中的迭代器就是一个原生指针,因此在实现的时候也就是用的原生指针即可,但是对于list来说不能这样,list的迭代器中例如++--这样的操作,是不能和vector中的原生指针一样直接去实现的,而是需要用next或者是prior来模拟这个过程,还有例如*和->这样的访问数据的模式,因此在list的迭代器实现中是使用了封装来进行实现的

STL中有六大组件,其中迭代器算其中一个,那么也就意味着迭代器具有通用的功能,例如下面的代码,在使用构造函数时可以使用迭代器进行构造,而这个构造的过程使用的迭代器对于各种容器来说都是通用的:

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

int main()
{
	vector<int> v1{ 1,2,3,4,5,3,2,2 };
	vector<int> v2(v1.begin(), v1.end());
	list<int> l1(v1.begin(), v1.end());
	return 0;
}

那么就意味着,在实现迭代器的过程中也是就可以根据迭代器来进行不同容器间的构造

list的实现过程

首先,在list的实现过程中要有下面几个部分组成:list中包含的节点,list的迭代器访问,list的节点之间的关系

那么首先就是list中节点的定义,用到了模板,现在再对该部分进行解析,其实就是在创建的时候可以根据需要的内容开辟出对应的节点类型

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

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

有了节点信息,就可以对list做一些基础的操作,例如头插头删,尾插尾删等操作,但对于inserterase这些操作还不能够实现,因此就要实现迭代器模块的内容

不管是对于vector还是list,迭代器的本质就是用一个原生指针去进行访问等等,但是listvector不同的是,list的存储地址并不是连续的,因此在访问的过程中就需要对迭代器进行一定程度的封装,例如在++或者--的操作符上可以进行一些体现,因此list迭代器的实现是需要进行单独的封装的

// 定义正向迭代器
template <class T, class Ref, class Ptr>
class __list_iterator
{
public:
	typedef list_node<T> Node;
	typedef __list_iterator<T, T&, T*> self;
	__list_iterator(Node* node)
		:_node(node)
	{}

	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	self& operator++(int)
	{
		self 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;
	}
	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;
	}
	Node* _node;
};

上面的片段对list进行了一些封装,实现了它的一些基础功能,从代码中也能看出来,迭代器的本质确确实实就是指针,用指针来进行一系列的操作,对下面这几个片段单独进行解析:

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

这是对于迭代器中解引用的运算符重载,这里使用的是&_node->_data的写法,看似很怪,但是实际上这里的函数调用过程应该是这样

C++:关于模拟实现vector和list中迭代器模块的理解,C++,# 模拟实现,知识总结,c++,list
也就是说,这里对于->进行运算符重载后,还需要进行解引用,这个运算符重载函数返回的是一个指针,而这个指针还要继续进行解引用才能得到用户想要得到的值,编译器在这里进行了特殊处理,两个->使得可读性下降,因此将两个->进行了一定程度的合并,只需要一个->就可以实现解引用的目的

其次是对模板的使用部分

template <class T, class Ref, class Ptr>

	typedef list_node<T> Node;
	typedef __list_iterator<T, T&, T*> self;

这里在最开始定义的时候,就定义了数据类型,引用和指针三种模板参数,借助这个参数就可以用模板将复杂的内容实现简单化,只需要一份代码,模板就可以直接实例化出用户在调用的时候需要的代码,在进行封装const迭代器的时候,只需要提供的参数改为const版本就可以实现目的,很便捷

这样就实现了正向迭代器的普通版本,而对于const迭代器的版本也只需要进行不同的模板参数就可以实例化出const版本的迭代器

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

有了迭代器,在实现链表的各种函数功能就更加方便,例如可以实现eraseinsert的操作,实现了这两个函数,在进行头插头删,尾插尾删的时候就更加方便,只需要进行原地的调用即可

	// Modifiers
	void push_front(const T& val)
	{
		//Node* newnode = new Node;
		//newnode->_data = val;
		//newnode->_next = _head->_next;
		//_head->_next->_prev = newnode;
		//_head->_next = newnode;
		//newnode->_prev = _head;
		//_size++;
		insert(begin(), val);
	}
	void pop_front()
	{
		//Node* delnode = _head->_next;
		//_head->_next = _head->_next->_next;
		//_head->_next->_prev = _head;
		//delete delnode;
		//delnode = nullptr;
		//_size--;
		erase(begin());
	}
	void push_back(const T& val)
	{
		//Node* newnode = new Node;
		//newnode->_data = val;
		//newnode->_prev = _head->_prev;
		//_head->_prev->_next = newnode;
		//newnode->_next = _head;
		//_head->_prev = newnode;
		//_size++;
		insert(end(), val);
	}
	void pop_back()
	{
		//Node* delnode = _head->_prev;
		//delnode->_prev->_next = _head;
		//_head->_prev = delnode->_prev;
		//delete delnode;
		//delnode = nullptr;
		//_size--;
		erase(--end());
	}
	iterator insert(iterator pos, const T& val)
	{
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* newnode = new Node(val);

		_size++;
		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;

		delete cur;
		cur = nullptr;
		_size--;

		prev->_next = next;
		next->_prev = prev;
		return iterator(next);
	}

那么上面是对前面已经有过的内容进行的重新温故,但是上面的代码其实是没有实现反向迭代器的,而在STL的库中,反向迭代器的定义和正向迭代器其实并不相同,它是直接借助正向迭代器对反向迭代器进行适配,有些类似于用vectorlist或者deque对栈和队列进行的适配,也体现了封装和代码复用

template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:
	typedef ReverseIterator<Iterator, Ref, Ptr> Self;

	ReverseIterator(Iterator it)
		:_it(it)
	{}

	Self& operator++()
	{
		--_it;
		return *this;
	}

	Ref operator*()
	{
		return *_it;
	}

	Ptr operator->()
	{
		return _it.operator->();
	}

	bool operator!=(const Self& s)
	{
		return _it != s._it;
	}
private:
	Iterator _it;
};

上面的代码就是对于反向迭代器的封装,从中可以看出反向迭代器是使用了正向迭代器的,并且在它的基础上进行的修改,因此这个反向迭代器是可以适配于vector也可以适配于list的

整体来说,对于反向迭代器就是用正向迭代器进行适配出来的,体现了模板的好处文章来源地址https://www.toymoban.com/news/detail-726757.html

完整代码

#pragma once

namespace mylist
{
	// 定义节点内容
	template <class T>
	struct list_node
	{
		list_node(const T& x = T())
			:_data(x)
			, _next(nullptr)
			, _prev(nullptr)
		{}
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;
	};

	// 定义正向迭代器
	template <class T, class Ref, class Ptr>
	class __list_iterator
	{
	public:
		typedef list_node<T> Node;
		typedef __list_iterator<T, T&, T*> self;
		__list_iterator(Node* node)
			:_node(node)
		{}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator++(int)
		{
			self 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;
		}
		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;
		}
		Node* _node;
	};

	// 定义反向迭代器
	template<class Iterator, class Ref, class Ptr>
	class reverse_iterator
	{
		typedef reverse_iterator<Iterator, Ref, Ptr> self;
	public:
		reverse_iterator(Iterator it)
			:_it(it)
		{}

		self& operator++()
		{
			_it--;
			return *this;
		}
		self& operator++(int)
		{
			self tmp(*this);
			_it--;
			return tmp;
		}
		self& operator--()
		{
			_it++;
			return *this;
		}
		self& operator--(int)
		{
			self tmp(*this);
			_it++;
			return tmp;
		}
		Ref operator*()
		{
			Iterator cur = _it;
			return *(--cur);
		}
		Ptr operator->()
		{
			return &(operator*());
		}
		bool operator !=(const self& s)
		{
			return _it != s._it;
		}
		bool operator ==(const self& s)
		{
			return _it == s._it;
		}

		Iterator _it;
	};

	// 定义链表
	template <class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		typedef reverse_iterator<iterator, T&, T*> reverse_iterator;
		//typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
		// Constructor
		list()
		{
			empty_init();
		}
		list(const list<T>& lt)
		{
			for (auto x : lt)
			{
				push_back(x);
			}
		}
		list(iterator begin, iterator end)
		{
			empty_init();
			while (begin != end)
			{
				push_back(begin._node->_data);
				begin++;
			}
		}
		//list(reverse_iterator rbegin, reverse_iterator rend)
		//{
		//	empty_init();
		//	while (rbegin != rend)
		//	{
		//		push_back(rbegin._node->_data);
		//		rbegin++;
		//	}
		//}

		// Destructor
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		// Operator=
		list<T>& operator=(const list<T>& lt)
		{
			swap(lt);
			return *this;
		}

		// Iterators
		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(end());
		}
		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}
		//const_reverse_iterator rbegin() const
		//{
		//	return const_reverse_iterator(end());
		//}
		//const_reverse_iterator rend() const
		//{
		//	return const_reverse_iterator(begin());
		//}

		// Capacity
		bool empty()
		{
			return _size == 0;
		}
		size_t size()
		{
			return _size;
		}

		// Element access
		T& front()
		{
			return begin()._node->_data;
		}
		T& back()
		{
			return (--end())._node->_data;
		}

		// Modifiers
		void push_front(const T& val)
		{
			//Node* newnode = new Node;
			//newnode->_data = val;
			//newnode->_next = _head->_next;
			//_head->_next->_prev = newnode;
			//_head->_next = newnode;
			//newnode->_prev = _head;
			//_size++;
			insert(begin(), val);
		}
		void pop_front()
		{
			//Node* delnode = _head->_next;
			//_head->_next = _head->_next->_next;
			//_head->_next->_prev = _head;
			//delete delnode;
			//delnode = nullptr;
			//_size--;
			erase(begin());
		}
		void push_back(const T& val)
		{
			//Node* newnode = new Node;
			//newnode->_data = val;
			//newnode->_prev = _head->_prev;
			//_head->_prev->_next = newnode;
			//newnode->_next = _head;
			//_head->_prev = newnode;
			//_size++;
			insert(end(), val);
		}
		void pop_back()
		{
			//Node* delnode = _head->_prev;
			//delnode->_prev->_next = _head;
			//_head->_prev = delnode->_prev;
			//delete delnode;
			//delnode = nullptr;
			//_size--;
			erase(--end());
		}
		iterator insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(val);

			_size++;
			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;

			delete cur;
			cur = nullptr;
			_size--;

			prev->_next = next;
			next->_prev = prev;
			return iterator(next);
		}
		void swap(const list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		void clear()
		{
			Node* cur = _head->_next;
			while (cur != _head)
			{
				Node* next = cur->_next;
				delete(cur);
				cur = next;
			}
			_head->_next = _head;
			_head->_prev = _head;
		}


		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_head->_data = T();
			_size = 0;
		}

		void Print()
		{
			Node* cur = _head->_next;
			while (cur != _head)
			{
				cout << cur->_data << "->";
				cur = cur->_next;
			}
			cout << "null" << endl;
		}
	private:
		Node* _head;
		size_t _size;
	};

	void test_iterator()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		cout << "iterator constructor:";
		list<int> lt1(lt.begin(), lt.end());
		lt1.Print();
		cout << "front():" << lt.front() << endl;
		cout << "back():" << lt.back() << endl;
		mylist::__list_iterator<int, int&, int*> it = lt.begin();
		while (it != lt.end())
		{
			std::cout << *it << " ";
			it++;
		}
		cout << endl;
	}
	void test_clear()
	{
		list<int> lt1;
		cout << "push_back:" << endl;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.Print();
		lt1.clear();
		lt1.push_back(5);
		lt1.push_back(6);
		lt1.push_back(7);
		lt1.push_back(8);
		lt1.Print();
	}
	void test_push_pop()
	{
		list<int> lt1;
		cout << "push_back:" << endl;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.Print();
		cout << "pop_back:" << endl;
		lt1.pop_back();
		lt1.Print();

		list<int> lt2;
		cout << "push_front:" << endl;
		lt2.push_front(1);
		lt2.push_front(2);
		lt2.push_front(3);
		lt2.push_front(4);
		lt2.Print();
		cout << "pop_front:" << endl;
		lt2.pop_front();
		lt2.Print();
	}
	void test_reverse_iterator()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		cout << "iterator constructor:";
		//list<int> lt1(lt.rbegin(), lt.rend());
		//lt1.Print();
		cout << "front():" << lt.front() << endl;
		cout << "back():" << lt.back() << endl;
		mylist::list<int>::reverse_iterator rit = lt.rbegin();
		while (rit != lt.rend())
		{
			std::cout << *rit << " ";
			rit++;
		}
		cout << endl;
	}

	void test()
	{
		test_reverse_iterator();
		//test_push_pop();
		//test_clear();
	}
}

到了这里,关于C++:关于模拟实现vector和list中迭代器模块的理解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

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

    本篇模拟实现简单的list和一些其他注意的点 如下所示是利用拷贝构造将一个链表中的数据挪动到另外一个链表中,构造两个相同的链表 lt作为形参,传引用可以提高传参的效率,同时应该加上const修饰来保证不会因为不小心修改了形参导致外部的实参也被修改,这样的结果是

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

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

    2024年02月09日
    浏览(53)
  • 深入篇【C++】手搓模拟实现list类(详细剖析底层实现原理)&&模拟实现正反向迭代器【容器适配器模式】

    1.一个模板参数 在模拟实现list之前,我们要理解list中的迭代器是如何实现的。 在vector中迭代器可以看成一个指针,指向vector中的数据。它的解引用会访问到具体的数据本身,++会移动到下一个数据位置上去,这些都是因为vector具有天生的优势:空间上是连续的数组,这样指

    2024年02月15日
    浏览(46)
  • 【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改

    list使用文章 析构函数   在定义了一个类模板list时。我们让该类模板包含了一个内部结构体_list_node,用于表示链表的节点。该结构体包含了指向前一个节点和后一个节点的指针以及节点的值。在list中保存了链表的头节点指针和链表长度大小。       因为list的底层实现

    2024年02月14日
    浏览(50)
  • STL之list模拟实现(反向迭代器讲解以及迭代器失效)

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

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

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

    2024年02月10日
    浏览(32)
  • C++ 模拟实现vector

    目录 一、定义 二、模拟实现 1、无参初始化 2、sizecapacity 3、reserve 4、push_back 5、迭代器 6、empty 7、pop_back 8、operator[ ] 9、resize 10、insert 迭代器失效问题 11、erase 12、带参初始化 13、迭代器初始化 14、析构函数 15、深拷贝 16、赋值运算符重载 完整版代码测试代码 本次参考SGI版

    2024年02月04日
    浏览(43)
  • 【C++】vector模拟实现

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸C++  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同

    2024年02月13日
    浏览(43)
  • C++模拟实现vector

    目录 1.代码实现 2.注意事项 1.成员变量 2. 不能使用memcpy函数拷贝数据 1.用string类型测试时,要考虑到vs可能把数据存储在数组buffer里面 3.insert函数中指针的失效性 1.加引用,那么就不能传常量,比如v.begin() + 3 2.加引用,就只能传变量了  4.erase成员函数的指针的失效性 这边以

    2024年02月17日
    浏览(43)
  • 【c++迭代器模拟实现】

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

    2024年02月02日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包