C++学习之STL学习：list的模拟实现

        在上一篇学习了list的使用后，在本篇我们将通过模拟实现的方式深入了解list的底层运作原理。

        作者的个人gitee：楼田莉子 (riko-lou-tian) - Gitee.com

        感兴趣的读者可以看一看

目录

前置准备

        结点的定义

        链表类的定义

迭代器 

        普通迭代器

        const迭代器 

        list中关于迭代器的声明 

        误区：

相关函数

        push_back

        insert

        erase

源代码

前置准备

        结点的定义

        我们需要定义一个结点的类（参考之前双向链表那篇博客：数据结构学习之双向循环链表-CSDN博客），因为这个类中的成员我们都想要访问，如果想要方便写的话，可以用struct（struct中默认为公开），并且用命名空间封装

namespace Boogiepop
{
	template<class T>
	//当我们不需要也不想要让访问限定符限制的时候
	//可以用struct来定义类，而不是用class
	struct list_node
	{
		T _data;			//数据
		list_node<T>* _next;//指向下一个节点的指针
		list_node<T>* _prev;//指向前一个节点的指针
	};
}

        同时因为list模拟实现中使用了模板，所以函数的定义也只能在.h文件中（） 

        同时切记，模板只能给对应的类或函数使用，是“一次性”的，想再次使用一样的模板必须重新定义

        链表类的定义

template<class T>
class list
{
	typedef list_node<T> node;
public:
	//构造函数
	list()
	{
		_head = new node;
		_head->_next = _head;
		_head->_prev = _head;
	}
private:
	node* _head;		//指向头节点的指针

};

迭代器 

        双链表迭代器相关图解：

         迭代器用node*封装无法达到预期行为；用类封装node*重载运算符，就可以控制迭代器的行为。

        迭代器行为模拟的是普通指针访问数组的行为

        普通迭代器

	//迭代器
	template<class T,class Ref>
	//当我们不需要也不想要让访问限定符限制的时候
	//可以用struct来定义类，而不是用class
	//普通迭代器
	struct _list_iterator
	{
		typedef list_node<T> node;
		typedef _list_iterator<T, Ref> Self;
		node* _node;
		//构造迭代器
		_list_iterator(node* node) :_node(node)
		{

		}
		//解引用不是结点
		//用引用返回可以修改这个数值
		T& operator*()
		{
			return _node->_data;
		}
		不能实现，因为const list_iterator对象才能调用这个重载
		但是在这种情况下const list_iterator对象不能调用++和--
		//const T& operator*()const
		//{
		//	return _node->_data;
		//}
		//迭代器++
		//前置++
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置
		Self& operator++(int)
		{
			_list_iterator<T,Ref> tmp (*this);//浅拷贝
			_node = _node->_next;
			return *this;
		}
		//前置--
		Self& operator--()
		{
			_node = _node->prev;
			return *this;
		}
		//后置--
		Self& operator--(int)
		{
			Self tmp (*this);//浅拷贝
			_node = _node->prev;
			return *this;
		}
		//返回是否相等
		bool operator!=(const Self& it)const
		{
			return _node!= it._node; 
		}
		bool operator==(const Self& it)const
		{
			return _node == it._node;
		}
	};

        const迭代器 

	//const迭代器
	template<class T,class Ref>
	//当我们不需要也不想要让访问限定符限制的时候
	//可以用struct来定义类，而不是用class
	struct _list_const_iterator
	{
		typedef list_node<T> node;
		typedef _list_const_iterator<T, Ref> Self;
		node* _node;
		//构造迭代器
		_list_const_iterator(node* node) :_node(node)
		{

		}
		//解引用不是结点
		//用引用返回可以修改这个数值
		const Self& operator*()
		{
			return _node->_data;
		}
		//迭代器++
		//前置++
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置
		Self& operator++(int)
		{
			Self tmp(*this);//浅拷贝
			_node = _node->_next;
			return *this;
		}
		//前置--
		Self& operator--()
		{
			_node = _node->prev;
			return *this;
		}
		//后置--
		Self& operator--(int)
		{
			Self tmp(*this);//浅拷贝
			_node = _node->prev;
			return *this;
		}
		//返回是否相等
		bool operator!=(const Self& it)const
		{
			return _node != it._node;
		}
		bool operator==(const Self& it)const
		{
			return _node == it._node;
		}
	};

        list中关于迭代器的声明 

//链表
template<class T>
class list
{
	typedef list_node<T> node;
public:
	//普通迭代器
    typedef _list_iterator<T,Ref> iterator;
    //const迭代器
    typedef const _list_iterator<T,Ref> const_iterator;
	//返回迭代器
	iterator begin()
	{
		return iterator(_head->_next);
	}
	//返回迭代器
	iterator end()
	{
		return iterator(_head);
	}
    //其余部分在此处省略。。。。。。
}

 测试：

void test1()
{
	Boogiepop::list<int> list;
	list.push_back(1);
	list.push_back(2);
	list.push_back(3);
	list.push_back(4);
	list.push_back(5);
	Boogiepop::list<int>::iterator it = list.begin();
	while (it != list.end())
	{
		cout << *it << " ";
		++it;
	}
	cout<<endl;
}

        普通迭代器可以修改指向的内容，const迭代器不可以修改指向的内容

        误区：

        1、

        这么写是不对的，这样迭代器本身无法修改,无法进行++和--

typedef const iterator const_iterator;

        string和vector可以这么干是因为const修饰的指向的内容 

        但是list只能重新搞一个类型实现

         2、还有这种情况，写重载能否实现？答案是不能

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

        因为：

T& operator*()
{
	return _node->_data;
}
//不能实现，因为const list_iterator对象才能调用这个重载
//但是在这种情况下const list_iterator对象不能调用++和--
const T& operator*()const
{
	return _node->_data;
}

相关函数

        push_back

void push_back(const T&x)
{
	node* new_node = new node(x);//头结点
	node* tail=_head->_prev;//尾节点
	tail->_next = new_node;
	new_node->_prev = tail;
	new_node->_next = _head;
	_head->_prev = new_node;
}

        insert

void insert(iterator pos, const T& x)
{
	node* cur = pos._node;
	node*new_node = new node(x);
	node*prev = cur->_prev;
	//prev  new_node  cur
	prev->_next = new_node;
	new_node->_next = cur;
	cur->_prev = new_node;
	new_node->_prev = prev;
}

        erase

iterator erase(iterator pos)
{
	node* cur=pos._next;
	node*prev=cur->_prev;
	node*next=cur->_next;
	prev->_next=next;
	next->_prev=prev;
	delete cur;
	return iterator(next);
	//也可以这么写return next
}

源代码

list.h

#pragma once
#include<iostream>
using namespace std;
namespace Boogiepop
{
	//节点
	template<class T>
	//当我们不需要也不想要让访问限定符限制的时候
	//可以用struct来定义类，而不是用class
	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)
		{

		}
	};
	//迭代器
	template<class T, class Ref>
	//当我们不需要也不想要让访问限定符限制的时候
	//可以用struct来定义类，而不是用class
	//普通迭代器
	struct _list_iterator
	{
		typedef list_node<T> node;
		typedef _list_iterator<T, Ref> Self;
		node* _node;
		//构造迭代器
		_list_iterator(node* node) :_node(node)
		{

		}
		//解引用不是结点
		//用引用返回可以修改这个数值
		T& operator*()
		{
			return _node->_data;
		}
		不能实现，因为const list_iterator对象才能调用这个重载
		但是在这种情况下const list_iterator对象不能调用++和--
		//const T& operator*()const
		//{
		//	return _node->_data;
		//}
		//迭代器++
		//前置++
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置
		Self& operator++(int)
		{
			_list_iterator<T, Ref> tmp(*this);//浅拷贝
			_node = _node->_next;
			return *this;
		}
		//前置--
		Self& operator--()
		{
			_node = _node->prev;
			return *this;
		}
		//后置--
		Self& operator--(int)
		{
			Self tmp(*this);//浅拷贝
			_node = _node->prev;
			return *this;
		}
		//返回是否相等
		bool operator!=(const Self& it)const
		{
			return _node != it._node;
		}
		bool operator==(const Self& it)const
		{
			return _node == it._node;
		}
	};
	//const迭代器
	template<class T, class Ref>
	//当我们不需要也不想要让访问限定符限制的时候
	//可以用struct来定义类，而不是用class
	//普通迭代器
	struct _list_const_iterator
	{
		typedef list_node<T> node;
		typedef _list_const_iterator<T, Ref> Self;
		node* _node;
		//构造迭代器
		_list_const_iterator(node* node) :_node(node)
		{

		}
		//解引用不是结点
		//用引用返回可以修改这个数值
		const Self& operator*()
		{
			return _node->_data;
		}
		//迭代器++
		//前置++
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置
		Self& operator++(int)
		{
			Self tmp(*this);//浅拷贝
			_node = _node->_next;
			return *this;
		}
		//前置--
		Self& operator--()
		{
			_node = _node->prev;
			return *this;
		}
		//后置--
		Self& operator--(int)
		{
			Self tmp(*this);//浅拷贝
			_node = _node->prev;
			return *this;
		}
		//返回是否相等
		bool operator!=(const Self& it)const
		{
			return _node != it._node;
		}
		bool operator==(const Self& it)const
		{
			return _node == it._node;
		}
	};
	//链表
	template<class T, class Ref>
	class list
	{
		typedef list_node<T> node;
		typedef _list_iterator<T, Ref> Self;
		typedef _list_const_iterator<T, Ref> const_Self;
	public:
		//普通迭代器
		typedef _list_iterator<T, Ref> iterator;
		//const迭代器
		typedef const _list_iterator<T, Ref> const_iterator;
		//返回迭代器
		iterator begin()
		{
			return iterator(_head->_next);
		}
		//返回迭代器
		iterator end()
		{
			return iterator(_head);
		}
		//构造函数
		list()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		//拷贝构造函数
		list(const list<T>& lt)
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			for (const auto& x : lt)
			{
				push_back(x);
			}
		}
		//花括号初始化
		list(initializer_list<T> il)
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			for (const auto& x : lt)
			{
				push_back(x);
			}
		}
		//=运算符重载
		list<T>& operator=(const list<T>& lt)
		{
			if (this != &lt)
			{
				clear();
				for (const auto& x : lt)
				{
					push_back(x);
				}
			}
			return *this;
		}
		//析构函数
		//释放结点
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		void push_back(const T& x)
		{
			node* new_node = new node(x);//头结点
			node* tail = _head->_prev;//尾节点
			tail->_next = new_node;
			new_node->_prev = tail;
			new_node->_next = _head;
			_head->_prev = new_node;
		}
		//交换数据
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		//插入元素
		void insert(iterator pos, const T& x)
		{
			node* cur = pos._node;
			node* new_node = new node(x);
			node* prev = cur->_prev;
			//prev  new_node  cur
			prev->_next = new_node;
			new_node->_next = cur;
			cur->_prev = new_node;
			new_node->_prev = prev;
		}
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_front()
		{
			erase(begin());
		}
		void pop_back()
		{
			erase(--end());
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		iterator erase(iterator pos)
		{
			node* cur = pos._next;
			node* prev = cur->_prev;
			node* next = cur->_next;
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			return iterator(next);
			//也可以这么写return next
		}
		//返回链表大小
		size_t size()const
		{

		}
	private:
		node* _head;		//指向头节点的指针

	};
};

        提示：类的模板没有实例化不能去类模板中找后面的东西编译器无法区分const_iterator 是嵌套内类还是静态成员变量，typename是告诉编译器确认过是类型

        本期内容就到这里，感兴趣的可以点个赞谢谢

封面图自取：