C++模拟实现list容器（源码）

源代码+注释讲解

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

namespace mylist {
	//一.list的结点是一个模板类
	template <class T>
	struct ListNode {//2.为什么使用struct而不用class呢？因为结点的成员是需要公有成员，struct默认成员为公共成员
		//成员函数
		T _data;
		ListNode<T>* _next;
		ListNode<T>* _prev;

		//构造函数
		ListNode(const T& val = T())
			:_data(val)
			, _next(nullptr)
			, _prev(nullptr)
		{}


	};

	三.重新封装一个迭代器类型（重新封装的迭代器本质是一个结点指针，不过该结点指针可以像原生指针一样++、--）
	//template <class T>
	//struct ListIterator {
	//	typedef ListNode<T> Node;
	//	//成员函数
	//	Node* _node;
	//	//构造函数
	//	ListIterator(Node* node)
	//		:_node(node)
	//	{}
	//	//++迭代器
	//	ListIterator<T>& operator++()//4.前置++返回下一个结点的引用
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}
	//	//迭代器++
	//	ListIterator<T> operator++(int)//5.后置++返回当前结点（++之前的结点）
	//	{
	//		ListIterator<T> tmp(*this);
	//		_node = _node->_next;
	//		return tmp;
	//	}
	//	//--迭代器
	//	ListIterator<T> operator--()
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}
	//	//迭代器--
	//	ListIterator<T> operator--(int)
	//	{
	//		ListIterator<T> tmp(*this);
	//		_node = _node->_prev;
	//		return tmp;
	//	}
	//	//*it
	//	T& operator*()
	//	{
	//		return _node->_data;
	//	}

	//	//6.为什么要设计一个->的函数？
	//	//因为如果list容器中存放的是一个自定义类型数据，且该自定义数据类型拥有两个及以上成员时，仅仅靠*无法正确输出数据（除非重载一个输出流）
	//	//所以利用->函数重载，返回数据的地址，it->就相当于数据的地址
	//	//需要注意的是，it->仅仅是数据的地址，实际使用时理论上应当是it->->来指示自定义类型数据的成员变量
	//	//但是连续的->可读性差，因此编译器将连续的->优化了，仅仅一个->即可
	//	//it->
	//	T* operator->()
	//	{
	//		return &_node->_data;
	//	}


	//	//!=
	//	bool operator!=(const ListIterator<T>& it)
	//	{
	//		return _node != it._node;
	//	}
	//	//==
	//	bool operator==(const ListIterator<T>& it)
	//	{
	//		return !(_node != it._node);
	//	}

	//};

	//template <class T>
	//struct ListConstIterator {
	//	typedef ListNode<T> Node;
	//	//成员函数
	//	Node* _node;
	//	//构造函数
	//	ListConstIterator(Node* node)
	//		:_node(node)
	//	{}
	//	//++迭代器
	//	ListConstIterator<T>& operator++()//4.前置++返回下一个结点的引用
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}
	//	//迭代器++
	//	ListConstIterator<T> operator++(int)//5.后置++返回当前结点（++之前的结点）
	//	{
	//		ListConstIterator<T> tmp(*this);
	//		_node = _node->_next;
	//		return tmp;
	//	}
	//	//--迭代器
	//	ListConstIterator<T> operator--()
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}
	//	//迭代器--
	//	ListConstIterator<T> operator--(int)
	//	{
	//		ListConstIterator<T> tmp(*this);
	//		_node = _node->_prev;
	//		return tmp;
	//	}
	//	//*it
	//	const T& operator*()
	//	{
	//		return _node->_data;
	//	}

	//	//6.为什么要设计一个->的函数？
	//	//因为如果list容器中存放的是一个自定义类型数据，且该自定义数据类型拥有两个及以上成员时，仅仅靠*无法正确输出数据（除非重载一个输出流）
	//	//所以利用->函数重载，返回数据的地址，it->就相当于数据的地址
	//	//需要注意的是，it->仅仅是数据的地址，实际使用时理论上应当是it->->来指示自定义类型数据的成员变量
	//	//但是连续的->可读性差，因此编译器将连续的->优化了，仅仅一个->即可
	//	//it->
	//	const T* operator->()
	//	{
	//		return &_node->_data;
	//	}


	//	//!=
	//	bool operator!=(const ListConstIterator<T>& it)
	//	{
	//		return _node != it._node;
	//	}
	//	//==
	//	bool operator==(const ListConstIterator& it)
	//	{
	//		return !(_node != it._node);
	//	}

	//};

	template <class T,class Ref,class Ptr>
	struct ListIterator {
		typedef ListNode<T> Node;
		//成员函数
		Node* _node;
		//构造函数
		ListIterator(Node* node)
			:_node(node)
		{}
		//++迭代器
		ListIterator<T,Ref,Ptr>& operator++()//4.前置++返回下一个结点的引用
		{
			_node = _node->_next;
			return *this;
		}
		//迭代器++
		ListIterator<T, Ref, Ptr> operator++(int)//5.后置++返回当前结点（++之前的结点）
		{
			ListIterator<T, Ref, Ptr> tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		//--迭代器
		ListIterator<T, Ref, Ptr> operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		//迭代器--
		ListIterator<T, Ref, Ptr> operator--(int)
		{
			ListIterator<T, Ref, Ptr> tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		//*it
		Ref operator*()
		{
			return _node->_data;
		}

		//6.为什么要设计一个->的函数？
		//因为如果list容器中存放的是一个自定义类型数据，且该自定义数据类型拥有两个及以上成员时，仅仅靠*无法正确输出数据（除非重载一个输出流）
		//所以利用->函数重载，返回数据的地址，it->就相当于数据的地址
		//需要注意的是，it->仅仅是数据的地址，实际使用时理论上应当是it->->来指示自定义类型数据的成员变量
		//但是连续的->可读性差，因此编译器将连续的->优化了，仅仅一个->即可
		//it->
		Ptr operator->()
		{
			return &_node->_data;
		}
		//!=
		bool operator!=(const ListIterator<T, Ref, Ptr>& it)
		{
			return _node != it._node;
		}
		//==
		bool operator==(const ListIterator<T, Ref, Ptr>& it)
		{
			return !(_node != it._node);
		}
	};


	//三.list容器是一个模板类
	template <class T>
	class list {
		typedef ListNode<T> Node;//未声明成员属性的，默认为私有属性
	public:
		//typedef ListIterator<T> iterator;
		//typedef ListConstIterator<T> const_iterator;
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;

	public:
		//一、构造函数、析构函数、赋值运算符重载

		//无参构造函数
		list()
			:_head(new Node)
		{
			_head->_next = _head;
			_head->_prev = _head;
		}

		//析构函数
		~list()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		//拷贝构造函数
		list(const list<T>& lt)
		{
			empty_init();
			for (auto& e : lt)
			{
				push_back(e);
			}
		}

		//赋值运算符重载
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}


		//二、修改操作

		//push_back尾插
		void push_back(const T& val)
		{
			Node* newnode = new Node(val);//新结点
			Node* tail = _head->_prev;//尾指针
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
		}

		//push_front头插
		void push_front(const T& val)
		{
			insert(begin(), val);
		}
		//pop_back尾删
		void pop_back()
		{
			erase(--end());
		}
		//pop_front头删
		void pop_front()
		{
			erase(begin());
		}
		//insert
		iterator insert(iterator position, const T& val)
		{
			Node* newnode = new Node(val);
			Node* prev = position._node->_prev;
			Node* cur = position._node;
			newnode->_prev = prev;
			prev->_next = newnode;
			newnode->_next = cur;
			cur->_prev = newnode;
			return newnode;
		}

		//erase
		iterator erase(iterator position)
		{
			Node* prev = position._node->_prev;
			Node* next = position._node->_next;
			prev->_next = next;
			next->_prev = prev;
			delete position._node;//1.销毁的是结点指针_node，而不是封装_node的结构体
			return next;
		}

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

		//swap
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
		}

		//三、迭代器
			//list容器中的迭代器和string、vector容器不同，由于list容器中各个结点的地址不连续，因此无法使用原生指针作为
			//迭代器。既然原生指针类型不支持我们进行++、--等操作，那么我们就重新封装一个迭代器类型，来进行++、--等操作

		//begin
		iterator begin()
		{
			return _head->_next;//1.返回值是结点指针，但是返回值类型是ListIterator<T>，所以此处利用的是隐式类型转换
		}
		//end
		iterator end()
		{
			return _head;//2.返回值是结点指针，但是返回值类型是ListIterator<T>，所以此处利用的是隐式类型转换
		}
		
		
		//3.常对象迭代器为什么不能像vector容器那样，在返回值类型前加上const呢？
		//因为list容器中的迭代器是一个结构体，++it不是想vector容器中的迭代器（原生指针）那样改变指针变量指向
		//而是通过修改结构体中的数据（即结点）来让迭代器++
		//因此不能使用const iterator作为返回值类型，这样就会无法修改结构体指针指向的数据（即无法修改it指向的结构体）
		//那么如何防止 常对象容器的迭代器修改数据呢？？？
		//迭代器修改数据的地方就在于 *和->，只有这两个函数重载提供了迭代器修改数据的可能
		//只要将这两个函数的返回值加上const即可
		//然而又出现了一个问题：常对象指的是list容器构造出来的对象，但是实际修改常对象数据的却是iterator迭代器，一个结构体
		//*和->是iterator结构体的函数，如果仅仅是通过重载const版本的*和->函数是没有用的
		//因为迭代器iterator的对象it，永远是普通对象，无法调用到const版本的*和->函数
		//通俗点来说，就是list容器常对象仍然可以调用迭代器普通对象中的*和->函数来修改容器中的数据
		//所以，唯一的解决办法增加一个常对象迭代器，并将其中的*和->函数改为const版本
		//这样的话，常对象使用常对象迭代器，就无法通过*和->函数来修改容器数据了
		//优化操作：将两个版本的迭代器设计为类模板

		//常对象begin
		const_iterator begin() const
		{
			return _head->_next;
		}
		//常对象end
		const_iterator end() const
		{
			return _head;
		}
		
	//四、容量操作
		//size
		size_t size() const
		{
			size_t count = 0;
			iterator it = begin();
			while (it != end())
			{
				++count;
				it++;
			}
			return count;
		}

	//成员变量
	private:
		Node* _head;//哨兵位
	};


	//类外测试函数
	void test()
	{
		list<int> lt;
		lt.push_back(1); lt.push_back(1); lt.push_back(1);
		lt.push_back(1); lt.push_back(1); lt.push_back(1);
		lt.push_front(9); lt.push_front(8); lt.push_front(7);
		list<int>::iterator it = lt.begin();
		const list<int> lt2(lt);
		list<int>::const_iterator it2 = lt2.begin();
		while (it2 != lt2.end())
		{
			//*it2 = 10;
			cout << *it2 << " ";
			++it2;
		}
		cout << endl;

		//for (auto& e : lt)
		//	cout << e << " ";
		//cout << endl;
		//cout << lt.size() << endl;

		//cout << "-------------------------------------------------------------------" << endl;
		自定义数据类型A
		//struct A {
		//	int a;
		//	int b;
		//};
		//list<A> lt2;
		//lt2.push_back({ 1,2 }); lt2.push_back({ 3,4 }); lt2.push_back({ 5,6 });
		//for (auto& e : lt2)
		//{
		//	cout << e.a << " " << e.b << "; ";
		//}
		//cout << endl;
		//list<A>::iterator it = lt2.begin();
		//while (it != lt2.end())
		//{
		//	cout << (*it).a << " " << (*it).b << "; ";
		//	++it;
		//}
		//cout << endl;

		//it = lt2.begin();
		//while (it != lt2.end())
		//{
		//	cout << it->a << " " << it->b << "; ";
		//	++it;
		//}
		//cout << endl;



	}
}

int main()
{
	mylist::test();
	return 0;
}