STL之list模拟实现（内含图解）

来源：华佗小知识

🔥list_node节点（这是一个结构体）

template<class T>
	//节点
	//节点有什么
	//数据，前一个节点的指针(结构体类型的指针)，后一个节点的指针（结构体类型的指针）
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;

		//初始化
		list_node(const T& val = T())//传引用减少拷贝，
			//初始化的值是T的默认构造函数，不能传0，
			//万一T是string类型或者其他类型呢，所以传引用
			:_data(val)
			, _next(nullptr)
			,_prev(nullptr)
		{}
	};

🔥 iterator迭代器（这是一个结构体）

🌧️构造函数

我们构造好了一个_node，但是没有给他赋值，就等着外面传过来一个node，把node给给里面的_node即可。

//构造函数
		__list_iterator(Node* node)
			:_node(node)
		{}

🌧️ *it

我们把迭代器比作指针，方便理解，这个函数就是对“指针”解引用，拿到它的值。
注意结果返回引用，减少拷贝

		//*it
		//对“指针”解引用，拿到它的值,结果返回引用，减少拷贝
		Ref operator*()
		{
			return _node->_data;
		}

🌧️ ->

		//->
		//拿到节点的值的地址，结果返回一个指针
		/*举个例子 _node->_data  得到了_node的_data的地址*/
		Ptr operator->()
		{
			return &_node->_data;
		}

🌧️ it++/++it

还是把迭代器比作一个指针，假设指针原本指向头节点，现在要指向下一个节点，那么就让指针++一下，但是注意前置++和后置++的区别

		//it++
		//迭代器向后走一步，返回加过的值(还是一个迭代器)
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		//++it
	    //迭代器向后走一步，返回没加过的值(还是一个迭代器)
		Self operator++(int)
		{
			Self tmp(*this);//保存一份原来的值
			_node = _node->_next;//迭代器向后走一步
			return tmp;
		}

🌧️it–/–it

这两个和++的同理

		//it--
        //迭代器向前走一步，返回减过的值(还是一个迭代器)
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}


		//--it
		//迭代器向前走一步，返回没减过的值(还是一个迭代器)
		Self operator--(int)
		{
			Self tmp(*this);//保存一份原来的值
			_node = _node->_prev;//迭代器向前走一步
			return tmp;
		}

🌧️ !=/==

外面有一个it，我们要比较it和里面的this是否一样
这里传值用的是引用，可以减少拷贝

bool operator!=(const Self& it)
		{
		//左边的——node前省略了this
			return _node != it._node;
		}

		bool operator==(const Self& it)
		{
			return _node == it._node;
		}

🔥list类（重点）

🌧️begin/const_begin

		const_iterator begin()const
		{
			return const_iterator(_head->_next);//返回头结点的下一个，就是第一个元素，强转成只读的迭代器
		}

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

🌧️end/const_end

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

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

🌧️构造函数


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

🌧️empty_init

大家可以发现，这个函数和构造函数一摸一样，那为什么要给他换个名字再写一次呢？

假设有一种情况，先创建了一个lt，但是在调用了clear函数之后，所有的数据都被清空了，又想接着操作，那怎么办呢？
这时就到empty_init出场了，他就相当于是又一次构造函数，调用了这个函数就可以接着操作了。

		//这个函数主要是用在clear后的，给lt初始化
		void empty_init()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;

		}

🌧️拷贝构造的子函数

		template<class InputIterator>
		list(InputIterator first,InputIterator last)
		{
			empty_init();
			while (first!=last)
			{
				push_back(*first);
				++first;

			}
		}

🌧️swap


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

🌧️lt2(lt1)

（原本没有lt2）赋值构造lt2，让lt2的值和lt1的值一样


		//lt2(lt1)
		list(const list <T>& lt)
		{
			empty_init();
			//调用了   list(InputIterator first,InputIterator last)，把数据一个一个拷贝过来
			list<T>tmp(lt.begin(), lt.end());
			swap(tmp);
		}

🌧️ lt2=lt1

（原本有lt2）更换lt2的值，让lt2的值和lt1的值一样

		//lt2=lt1
		//结果返回引用
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

🌧️析构函数

复用clear函数，提高程序的健壮性。
释放空间，让head指向空，避免出现野指针

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

🌧️clear

从head开始释放空间，注意这个函数最后会释放头节点。

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

		}

🌧️push_back


		void push_back(const T& x)
		{
			Node* tail = _head->_prev;
			Node* newnode = new Node(x);

			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;

			//复用insert函数
			//insert(end(),x);
		}

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

🌧️pop_back/pop_front

void pop_back()
		{
			erase(--end());

		}


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

🌧️insert

在pos前的位置插入一个数据

		//insert
		//插在pos之前,并且返回新的节点
		iterator insert(iterator pos, const T& x)
		{
			Node* newnode = new Node(x);
			Node* cur = pos._node;
			Node* prev = cur->_prev;

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

			return iterator(newnode);
		}

🌧️erase

清除pos位置的数据

		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;

			return iterator(next);
		}

🌧️打印函数

	void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//*it = 10; // 不允许修改
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

🔥 一些测试用例

test1

	void test1()
	{
		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;
		print_list(lt);

		cout << "头插" << endl;
		lt.push_front(100);
		print_list(lt);
		cout << "头删" << endl;
		lt.pop_front();
		print_list(lt);
		cout << "尾删" << endl;
		lt.pop_back();
		print_list(lt);


	}

测试结果

test2


	void test2()
	{
		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;
		print_list(lt);
		cout << "clear" << endl;
		lt.clear();
		print_list(lt);
		cout << "再插入数据" << endl;
		lt.push_back(1000);
		lt.push_back(2000);
		lt.push_back(3000);
		lt.push_back(4000);
		lt.push_back(5000);

		print_list(lt);
	}

测试结果

test3

void test3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		//在偶数前插入这个数乘以10
		auto it = lt.begin();
		while (it != lt.end())
		{
			if (*it % 2 == 0)
				lt.insert(it, *it * 10);
			++it;
		}

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

测试结果

test4

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

		list<int> lt2 = lt1;
		cout << "lt2:";
		print_list(lt2);
		cout << "lt1:";
		print_list(lt1);
	}

测试结果

🔥完整代码

这篇博客字数有限，有很多细节我没有写，比如什么是self，ptr，ref，为什么要传引用，为什么传指针。详细的解释我写在注释了。

这里我贴上完整代码的连接，供大家参考。

如果小伙伴想要思维导图我也放在连接，需要的自取。

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文