【C++】SLT — list的使用 + 模拟实现

📖前言：

本章我们将学习STL中另一个重要的类模板list…

• list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
• list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
• list与forward_list非常相似：主要区别在于forward_list对象是单链接列表，因此它们只能向前迭代，以换取更小、更高效。
• 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
• 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，需要线性的时间开销

list的学习文档：👉 传送门

---

1. list的使用

我们学习的STL中的list是一种：带头双向循环链表。（带有哨兵位头结点的）

• 带头双向循环链表 – 链表中的最优设计
• 可以实现任意位置〇(1)的插入删除，只需要改前后的关系

1.1 list的初始化 + 迭代器的使用：

在我们使用list之前我们需要先包一下头文件#include< list >。

直接见代码：

尾插：

void test_list1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		//正向迭代器
		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		
		//反向迭代器
		//list::reverse_iterator rit = lt.rbegin();
		auto rit = lt.rbegin();
		while (rit != lt.rend())
		{
			cout << *rit << " ";
			++rit;
		}
		cout << endl;
	}

头插：

void test_list2()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

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

		lt.push_front(10);
		lt.push_front(20);
		lt.push_front(30);
		lt.push_front(40);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.pop_back();
		lt.pop_back();
		lt.pop_front();
		lt.pop_front();

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

list::push_back的使用方法和vector::push_back的使用方法一样。

---

1.2 对list的排序：

对于一般的容器而言，我们包一个算法库 #incldue < alogrithm > 可以对普通的容器进行排序。

void test_list2()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(4);
	v.push_back(2);
	v.push_back(4);
	v.push_back(3);
	sort(v.begin(), v.end());
	
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	list<int> lt;
	lt.push_back(1);
	lt.push_back(4);
	lt.push_back(2);
	lt.push_back(4);
	lt.push_back(3);
	lt.sort();
	
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

}

• 像vector和string而言，这种连续的容器可以直接用库中的sort
• 而对于list而言和之前的顺序容器有所区别，因为其链式结构，库中的算法不支持
• list单独实现了一个自己的排序
• 但是list的排序效率很低
  

排序需用时间：

void TestOP()
	{
		srand(time(0));
		const int N = 10000000;
		vector<int> v;
		v.reserve(N);

		list<int> lt1;
		list<int> lt2;

		for (int i = 0; i < N; ++i)
		{
			//v.push_back(rand());
			auto e = rand();
			lt1.push_back(e);
			lt2.push_back(e);
		}

		//拷贝到vector排序，排完以后再拷贝回来
		int begin1 = clock();
		for (auto e : lt1)
		{
			v.push_back(e);
		}

		sort(v.begin(), v.end());
		size_t i = 0;
		for (auto& e : lt1)
		{
			e = v[i++];
		}
		int end1 = clock();

		int begin2 = clock();
		//sort(lt.begin(), lt.end());
		lt2.sort();
		int end2 = clock();

		printf("vector Sort:%d\n", end1 - begin1);
		printf("list Sort:%d\n", end2 - begin2);
	}

注意：
可见把list的数据拷贝到vector中再，用sort算法对vector中排序，再将vector中的数据拷贝到list中都比直接用list排序要快，所以list的排序效率很低。

2. list的模拟实现（list.h）

2.1 链表结点的申请：

namespace Joker
{
	template<class T>

//结点
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;

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

	//复用性很差
	//单独实现一个类，支持不能修改迭代器指向结点的数据
	//template
	//struct __list_const_iterator;
	
	//软件工程中很讲究复用原则 -- 尽量不去写重复的代码
	//重复的代码不方便维护
	
	//typedef __list_iterator iterator;
	//typedef __list_iterator const_iterator;

2.2 用类封装list迭代器：

为了在上层用户使用迭代器的方式和使用原生指针迭代器一样，所以我们做了如下的操作。

• 用一个类将迭代器封装起来 – 来模拟指针的行为。

这样我们在上层使用上和普通迭代器的使用没有区别但是，底层是不一样的，实现了一个封装。

见如下代码：

template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef list_node<T> Node;
	typedef __list_iterator<T, Ref, Ptr> self;
       
       //用来支持反向迭代器
	typedef Ptr pointer;
	typedef Ref reference;
	
	Node* _node;

	//list_node*
	explicit __list_iterator(Node* node)
		:_node(node)
	{}

	//解引用 -- *it
	//返回const别名的引用
	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->() 
	{
		//return &(operator*());0
		return &_node->_data;
	}
	
	//前置++
	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;
	}

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

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

};

template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
	Iterator _it;
	typedef Reverse_iterator<Iterator, Ref, Ptr> Self;

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

	//返回上一个位置的数据
	Ref operator*()
	{
		Iterator tmp = _it;
		return *(--tmp);
	}

	//返回指针
	Ptr operator->()
	{
		return &(operator*());
	}

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

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

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

//在模板声明类型关键字的时候，typename 和 class没有区别
template<class Iterator>
struct Reverse_iterator
{
	Iterator _it;

	//以list为例子：
	//这里的Iterator的类型是__list_iterator，
	//虽然list中的迭代器类型被实例化成了假如是int类型的，在list的迭代器的类中T就是int
	//但是这里却没有实例化，还是T，是个虚拟的类型
	//取迭代器中的内嵌类型 -- 要按照标准去走 -- 标准迭代器中都是有标准规定格式的

	typedef Reverse_iterator<Iterator> Self;
	
	//取内嵌类型都要加上typename
	typedef typename Iterator::reference reference;
	typedef typename Iterator::pointer pointer;

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

	//**类模板 模板虚拟类型 没有实例化之前不能去它里面找内嵌定义的类型
	//类模板没有实例化，找出来也是虚拟类型，后期无法处理 -- 编译报错
	
	//typname 告诉编译器后面这一串是一个类型，等Iterator实例化之后
	//再去它里面找这个内嵌类型

	//返回上一个位置
	//typename Iterator::reference operator*()
	reference operator*()
	{
		Iterator tmp = _it;
		return *(--tmp);
	}

	//typename Iterator::pointer operator->()
	pointer operator->()
	{
		return &(operator*());
	}

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

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

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

注意：

• 析构函数（不需要写）-- 节点不属于迭代器，不需要迭代器释放

• 结点不是属于迭代器的，拿结点的指针构造迭代器

• 迭代器的目标是遍历链表，访问和修改这个链表

• 迭代器不能拿着结点的指针把链表的结点给释放了

• • 编译器生成的默认析构函数，对内置类型不敢处理，只对自定义类型处理
• • 因为指针不能乱释放

• 拷贝构造和赋值重载（不需要写）

• 默认生成的浅拷贝就可以

补充：

• 传引用返回和支持返回值修改
• 还可以减少拷贝构造

（1）对封装迭代器的使用：

1.为了使我们使用的时候更顺畅，更接近于平时的使用，我们将迭代器在list这个类中再次重命名。

• 这样我们在使用的过程中就可以这样使用： list::iterator it = lt.begin();

（2）运算符重载 - > ：

为什么这里返回的是一个地址呢？

那么这个时候一定有个疑问，为啥这时，不直接返回要取的值呢？

• 由上图可见，当list的链表中的结点数据内容不是内置类型数据时
• 上图中链表结点的数据是一个一个的对象，这时候传值返回就不行了
• 若是返回值的话，此时返回的是一个对象

解决办法：

• 方法一：（->操作符重载，传值返回，类内操作） 把类中的成员函数给改了，在类中再去调用一层
  缺点： 不能广泛的用，不符合泛型编程的思维，要根据不同的场景改动。
• 方法二：（不重载->操作符，多次调用 . 操作符，类外操作） 在类外对象创建完成之后，拿到迭代器，在调用的时候（*it）对象用 “.” 操作符，一层一层调用去找到所需要的数据内容。
  缺点： 当调用的层数多时，写起来很麻烦。
• 方法三：（->操作符重载，传迭代器返回，类外操作） 返回的是迭代器，再通过返回的迭代器调用->的运算符重载，和方法二一样，当调用的层数多时，写起来很麻烦。但是编译器对此进行了优化。

优化如下：

• it.operator->() – 返回类型是AA*的迭代器
• it.operator->()->_a1;
• 编译器为了可读性进行了优化处理
• 如果不优化应该是it->->_a1;
• 优化以后，省略了一个->

---

2.3 链表的资源管理：

这里我们实现的是带头双向循环链表，和之前我们数据结构中实现的结构一样，我们写起来更是轻车熟路了~

• 这里的拷贝构造和赋值重载都运用到了现代写法
• 和之前模拟实现容器的时候用到的现代方法一样

//list的实现：
	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:

//资源管理：
		list()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}

//拷贝构造传统写法：（创造一个哨兵位，挨个尾插）

		//lt2(lt1)
		/*list(const list& lt)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;

			for (auto e : lt)
			{
				push_back(e);
			}
		}*/

//拷贝构造现代写法：（利用一个迭代器区间构造）

        //创造一个哨兵位头结点出来
		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++;
			}
		}
		
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
		}

		//lt2(lt1) -- 现代写法
		list(const list<T>& lt)
		{
			empty_init();
			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		//lt2 = lt1 -- 所有的深拷贝的赋值都可以这么写
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

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

		//clear不是把数据清掉，大结构还在，没有清掉哨兵位
		void clear()
		{
			//在成员函数内部不需要对象. 来访问
			iterator it = begin();
			while (it != end())
			{
				//erase就会往后走起到了迭代的作用
				//这样写哨兵位还在
				it = erase(it);
			}
		}

交换完之后，拷贝构造结束之后，tmp此时管理的是只有一个哨兵位的链表，tmp对象会被调用的析构函数销毁掉。

---

2.4 list的主要成员函数：

//迭代器：
	    //同样一个类模板，给不同的模板参数，就实例化不同的类型
		
		//typedef的类型是受到作用域的限制的
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		//反向迭代器适配支持
		/*typedef Reverse_iterator reverse_iterator;
		typedef Reverse_iterator const_reverse_iterator;*/

		typedef Reverse_iterator<iterator> reverse_iterator;
		typedef Reverse_iterator<const_iterator> const_reverse_iterator;

//正向迭代器：
		//正向迭代器和const修饰的迭代器
		iterator begin()
		{
			//返回一个匿名对象，用匿名对象还能被优化成直接构造
			return iterator(_head->_next);

			//可以直接返回_head->_next
			//因为单参数的构造函数支持隐式类型的转换
			//return _head->_next;
		}

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

		const_iterator begin() const
		{
			//返回一个匿名对象，用匿名对象还能被优化成直接构造
			
			//list_node
			return const_iterator(_head->_next);

			//可以直接返回_head->_next
			//因为单参数的构造函数支持隐式类型的转换
			//return _head->_next;
		}

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

//反向迭代器：
		//反向迭代器和const修饰的反向迭代器
		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}
		   
		const_reverse_iterator rbegin() const
		{
			return reverse_iterator(end());
		}

		const_reverse_iterator rend() const
		{
			return reverse_iterator(begin());
		}
		
//增添和删除:
		void push_back(const T& x)
		{
			//Node* tail = _head->_prev;
			//Node* newnode = new Node(x);

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

			insert(end(), x);
		}

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

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

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

		//插入在pos位置之前
		iterator insert(iterator pos, const T& x)
		{
			//pos是任意位置，也不需要检查 -- 断言
			Node* newnode = new Node(x);
			Node* cur = pos._node;
			Node* prev = cur->_prev;

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

			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			//prev next
			prev->_next = next;
			next->_prev = prev;
			delete cur;

			return iterator(next);
		}
	private:
		Node* _head;

	};
}

3. 迭代器失效的问题

• list insert迭代器不失效，不存在野指针的问题，也不存在意义变了的问题
• ist erase(it)以后，迭代器是会失效的
• 经典野指针失效，因为这个迭代器指向的结点，已经被释放了

void test_list5()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		lt.push_back(6);

		要求：删除所有的偶数

		list::iterator it1 = lt.begin();

		迭代器会失效
		//auto it1 = lt.begin();

		//while (it1 != lt.end())
		//{
		//	if (*it1 % 2 == 0)
		//	{
		//		lt.erase(it1);
		//	}

		//	it1++;
		//}

		//list::iterator it1 = lt.begin();
		auto it1 = lt.begin();

		while (it1 != lt.end())
		{
			if (*it1 % 2 == 0)
			{
				it1 = lt.erase(it1);
			}
			else
			{
				it1++;
			}
		}
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

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

		lt.push_back(10);
		lt.push_back(20);
		lt.push_back(30);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

当删除结点的时候，it迭代器指向的空间不存在了，此时再对这块空间解引用就会产生非法访问。

解决办法和之前vector容器迭代器失效时解决办法一样。

参考：
vector的使用和模拟实现：👉 传送门