【c++】STL容器-list的模拟实现（迭代器由浅入深逐步完善2w字讲解）

06-02 1802阅读

小编个人主页详情 template list_node} }; template typedef list_node _head = new Node; _head-_next = _head; _head-_prev = _head; _size = 0; } list() { empty_init(); } Node* tail = _head-_prev; Node* newnode = new Node(val); tail->_next = newnode; newnode->_prev = tail; _head->_prev = newnode; newnode->_next = _head; //insert(end(), val); }

iterator迭代器对应的 begin end（浅度讲解）

list::iterator it = lt.begin();
while (it != lt.end())
{
	cout 
	typedef list_node}						   //调用构造时支持将类型隐式类型转换为Node*类型
	__list_iterator							//返回++之后迭代器
		_node = _node-_next;   //并且由于this指针指向的迭代器出了这个重载运算符
							    //++的函数仍然存在，所以这里返回迭代器的引用即可
		return *this;
	}
	__list_iterator							   //拷贝一下this指针指向的迭代器，并且让this
		__list_iterator             //并且由于这个数据出了这个重载运算符*函数的范围后还在，所以
		return _node-_val;//返回引用即可
	}
	bool operator!=(const __list_iterator it) const
	{                            //由于不修改迭代器中指针的值，所以这里的this指针
		return _node != it._node;//指向的内容我们采用const进行修饰，参数中的迭代器
	}                            //同样只是进行比较，不修改迭代器中指针的值，所以
};                               //我们同样也使用const修饰参数中的迭代器
								 //接下来直接比较两个迭代器中的指针是否不相等即可
  1. 同时我们还应该注意小编给这个封装了节点指针的迭代器命名为__list_iterator而不是采用iterator进行命名，其原因是在实际的库中会出现抢占名称的可能，每一个容器都有迭代器，那么你list容器用了，那其它容器呢？是不是，所以容器统一不使用iterator的名称而是采用自己独立命名的名称，这个名称命名完成之后，在容器中typedef为iterator即可，__list_iterator其类型为__list_iterator，在list类模板进行调用的时候应该使用__list_iterator创建这个迭代器对象，为了接口是迭代器iterator的统一性，我们使用typedef将__list_iterator命名为iterator，并且这个typedef命名要在list容器中的public访问限定符下，因为这个命名是给调用list容器的外部使用的
  2. 那么搞定完成，接下来我们编写list中的迭代器对应的begin和end函数让其返回对应的头尾节点的指针即可，由于头节点中不存放数据，头节点中指向的下一个节点才存储数据，所以迭代器对应的begin函数返回对头应该是头节点指向的下一个节点的指针，迭代器对应end函数对应的是存储的最后一个有效数据的节点的下一个节点位置，那么就为头节点，这里我们返回头结点的指针即可

    【c++】STL容器-list的模拟实现（迭代器由浅入深逐步完善2w字讲解）

iterator begin()
{
	return _head->_next;
}
iterator end()
{
	return _head;
}
测试
  1. 我们使用如下代码进行测试构造函数，尾插，迭代器
void test_list1()
{
	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 
	typedef list_node}						 
	self operator++()
	{							
		_node = _node-_next;   
		
		return *this;
	}
	self operator++(int)
	{							   
		self tmp(*this);
		_node = _node-_next;       
		
		return tmp;    				
	}
	Ref operator*()
	{             
		return _node-_val;
	}
	bool operator!=(const self& it) const
	{                            
		return _node != it._node;
	}
};

	return _head-_next;
}
const_iterator end() const
{
	return _head;
}
  1. 接下来小编在命名空间内，list模板类外实现一个print函数，其参数是const对象，由于const对象中的数据类型可能是任意类型，所以这里同样需要使用模板，这里传引用因为我们不知道list中数据的类型是自定义类型还是内置类型，如果是自定义类型采用拷贝传参消耗大，所以我们统一使用引用传参，那么使用const对象调用const_iterator迭代器，用于打印测试
template
void print(const list& lt)
{
	list::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		cout 
	list，返回取出结构体对象的地址进行返回，即返回结构体的指针的方式使用->访问结构体的成员变量
  • 这里其实编译器做了优化，我们知道当我们使用->调用了迭代器重载运算符->返回结构体的指针之后应该再使用一个指针才能够进行访问结构体的成员变量即 lt->->_a 的方式才可以，这里直接使用 lt->_a 就可以进行访问是什么原因呢？这里其实是编译器做的优化，再你调用迭代器类模板中重载的运算符->之后会默认再给你添加一个->用于指针访问结构体对象的成员变量
    • struct A
{
	A(int a=0,int b=0)
		:_a(a)
		,_b(b)
	{}
	int _a;
	int _b;
};
void test_list3()
{
	list 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));
	list::iterator it = lt.begin(); 
	while (it != lt.end())
	{
		cout 
	typedef list_node}						 
	self operator++()
	{							
		_node = _node-_next;   
		
		return *this;
	}
	self operator++(int)
	{							   
		self tmp(*this);
		_node = _node-_next;       
		
		return tmp;    				
	}
	Ref operator*()
	{             
		return _node-_val;
	}
	Ptr operator-()
	{
		return &(_node-_val);//取结构体对象的地址进行返回，即返回结构体对象的指针
	}
	bool operator!=(const self& it) const
	{                            
		return _node != it._node;
	}
};
    1. 那么由于迭代器类型改变为了__list_iterator，所以在list中我们对于迭代器的重命名也应该对应进行修改
    typedef __list_iterator iterator;
typedef __list_iterator const_iterator;
    测试
    1. 测试使用迭代器对象使用重载运算符->访问结构体对象的成员变量
    struct A
{
	A(int a=0,int b=0)
		:_a(a)
		,_b(b)
	{}
	int _a;
	int _b;
};
void test_list3()
{
	list 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));
	list::iterator it = lt.begin(); 
	while (it != lt.end())
	{
		//cout 
	typedef list_node}
	self& operator++()
	{
		_node = _node-_next;
		
		return *this;
	}
	self operator++(int)
	{
		__list_iterator tmp(*this);
		_node = _node-_next;
		return tmp;
	}
	self& operator--()
	{
		_node = _node-_prev;
		return *this;
	}
	self operator--(int)
	{
		__list_iterator tmp(*this);
		_node = _node-_prev;
		return tmp;
	}
	Ref operator*()
	{
		return _node-_val;
	}
	Ptr operator-()
	{
		return &(_node-_val);
	}
	bool operator!=(const self& it) const
	{
		return _node != it._node;
	}
	bool operator==(const self& it) const
	{
		return _node == it._node;
	}
};

    迭代器拷贝构造的完善

    1. 那么有的时候我们会想要使用普通对象编译器会根据调用的类型去对应的与其类型最匹配的函数，即调用普通对象的begin和end函数，这时候我们想要使用const_iterator去接收会无法接收，即list::const_iterator it = lt.begin(); 这种形式会报错，显示类型无法转换，那么由于it是一个要进行创建的const的迭代器对象，那么尽管这里使用了=，但是lt.begin()返回的是普通的迭代器对象，那么就是使用一个已经存在的对象去初始化与其相同类型的对象，即还是会被编译器优化为拷贝构造，这里我们没有显示写拷贝构造，期望编译器默认生成的拷贝构造可以帮我们完成指针的值拷贝，因为这里我们仅仅是使用迭代器中的成员变量中的节点指针去访问数据，并不需要进行释放数据，所以这里也就不存在对同一块空间释放两次的可能，所以可以仅完成浅拷贝，但是这里的两者一个是const类型的迭代器，一个是普通的迭代器，编译器默认生成的拷贝构造需要拷贝的对象和被拷贝的对象是同一类型，这里明细不是，所以这里编译器默认生成的拷贝构造不能完成我们的预期，那么就需要我们显示写拷贝构造
    struct A
{
	A(int a=0,int b=0)
		:_a(a)
		,_b(b)
	{}
	int _a;
	int _b;
};
void test_list3()
{
	list 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));
	list::const_iterator it = lt.begin(); 
	while (it != lt.end())
	{
		//cout }

	A(int a=0,int b=0)
		:_a(a)
		,_b(b)
	{}
	int _a;
	int _b;
};
void test_list3()
{
	list
		//cout 
	typedef list_node}
	__list_iterator(const iterator& it)
		:_node(it._node)
	{}
	self& operator++()
	{
		_node = _node-_next;
		
		return *this;
	}
	self operator++(int)
	{
		__list_iterator tmp(*this);
		_node = _node-_next;
		return tmp;
	}
	self& operator--()
	{
		_node = _node-_prev;
		return *this;
	}
	self operator--(int)
	{
		__list_iterator tmp(*this);
		_node = _node-_prev;
		return tmp;
	}
	Ref operator*()
	{
		return _node-_val;
	}
	Ptr operator-()
	{
		return &(_node-_val);
	}
	bool operator!=(const self& it) const
	{
		return _node != it._node;
	}
	bool operator==(const self& it) const
	{
		return _node == it._node;
	}
};

	Node* cur = pos._node;
	Node* newnode = new Node(val);
	Node* prev = cur-_prev;
	prev-_next = newnode;
	newnode-_prev = prev;
	newnode-_next = cur;
	cur-_prev = newnode;
	_size++;
	return newnode;
}

	assert(pos != end());
	Node* cur = pos._node;
	Node* prev = cur-_prev;
	Node* next = cur-_next;
	prev->_next = next;
	next->_prev = prev;
	delete cur;
	cur = nullptr;
	_size--;
	return next;
}

    push_back

    pop_back

    push_front

    pop_front

    1. 这里的插入和删除操作调用insert和erase函数即可完成操作
    2. 此处begin返回的是head头节点的下一个节点的迭代器
    3. 此处end返回的是head头节点的迭代器
    4. 观察下图进行对应位置的插入和删除即可
    5. 同时这里插入的数据应该使用引用传参，避免这里的数据类型是自定义类型进行值传参的消耗大

      【c++】STL容器-list的模拟实现（迭代器由浅入深逐步完善2w字讲解）

    void push_back(const T& val)
{
	insert(end(), val);
}
void pop_back()
{
	erase(--end());
}
void push_front(const T& val)
{
	insert(begin(), val);
}
void pop_front()
{
	erase(begin());
}
    测试
    1. 进行测试头插头删，尾插尾删
    2. 对于类模板实例化出的对象，当我们使用范围for的时候针对这里变量e的初始化一定要采用引用，因为我们不确定对象中存储的类型是自定义类型还是内置类型，如果要是自定义类型进行拷贝给变量e的消耗大，所以这里采用引用
    void test_list4()
{
	list lt;
	lt.push_front(3);
	lt.push_front(2);
	lt.push_front(1);
	lt.push_front(0);
	lt.pop_front();
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(6);
	lt.pop_back();
	for (auto& e : lt)
	{
		cout 
	_head = new Node;
	_head-_next = _head;
	_head-_prev = _head;
	_size = 0;
}
list(const list
	empty_init();
	for (auto& e : lt)
	{
		push_back(e);
	}
}

	std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}

	swap(lt);
	return *this;
}

	list
		cout 
		cout 
	iterator cur = begin();
	while (cur != end())
	{
		cur = erase(cur);
	}
	_size = 0;
}

	clear();
	delete _head;
}

	return begin() == end();
}

	return _size;
}

	list
		cout 
	template
		list_node}
	};
	template
		typedef list_node}
		__list_iterator(const iterator& it)
			:_node(it._node)
		{}
		self& operator++()
		{
			_node = _node-_next;
			
			return *this;
		}
		self operator++(int)
		{
			__list_iterator tmp(*this);
			_node = _node-_next;
			return tmp;
		}
		self& operator--()
		{
			_node = _node-_prev;
			return *this;
		}
		self operator--(int)
		{
			__list_iterator tmp(*this);
			_node = _node-_prev;
			return tmp;
		}
		Ref operator*()
		{
			return _node-_val;
		}
		Ptr operator-()
		{
			return &(_node-_val);
		}
		bool operator!=(const self& it) const
		{
			return _node != it._node;
		}
		bool operator==(const self& it) const
		{
			return _node == it._node;
		}
	};
	template
		typedef list_node
			return _head-_next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator begin() const
		{
			return _head-_next;
		}
		const_iterator end() const
		{
			return _head;
		}
		void empty_init()
		{
			_head = new Node;
			_head-_next = _head;
			_head-_prev = _head;
			_size = 0;
		}
		list()
		{
			empty_init();
		}
		void clear()
		{
			iterator cur = begin();
			while (cur != end())
			{
				cur = erase(cur);
			}
			_size = 0;
		}
		~list()
		{
			clear();
			delete _head;
		}
		list(const list
			empty_init();
			for (auto& e : lt)
			{
				push_back(e);
			}
		}
		void swap(list
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list
			swap(lt);
			return *this;
		}
		//void push_back(const T& val)
		//{
		//	Node* tail = _head-_prev;
		//	Node* newnode = new Node(val);
		//	tail-_next = newnode;
		//	newnode-_prev = tail;
		//	_head-_prev = newnode;
		//	newnode-_next = _head;
		//}
		void push_back(const T& val)
		{
			insert(end(), val);
		}
		void pop_back()
		{
			erase(--end());
		}
		void push_front(const T& val)
		{
			insert(begin(), val);
		}
		void pop_front()
		{
			erase(begin());
		}
		iterator insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(val);
			Node* prev = cur-_prev;
			prev-_next = newnode;
			newnode-_prev = prev;
			newnode-_next = cur;
			cur-_prev = newnode;
			_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;
			cur = nullptr;
			_size--;
			return next;
		}
		size_t empty()
		{
			return begin() == end();
		}
		size_t size()
		{
			return _size;
		}
	private:
		Node* _head;
		size_t _size;
	};
	template
	void print(const list& lt)
	{
		list::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			cout 
		list
			cout 
		list
		A(int a=0,int b=0)
			:_a(a)
			,_b(b)
		{}
		int _a;
		int _b;
	};
	void test_list3()
	{
		list
			//cout 
		list
			cout 
		list
			cout 
			cout 
		list
			cout 
	wzx::test_list6();
	return 0;
}
    免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们。

    相关阅读

    目录[+]

    取消
    微信二维码
    微信二维码
    支付宝二维码