【C++ STL】list详解和模拟-EW帮帮网

前言

list文档

相较于vector的连续的空间线性空间，而list是基于节点。每次插入或者删除一个元素的，就配置或释放一个元素的空间。因此，list对于空间的运用是不会产生浪费的……而且，面对插入删除操作，list的常数级别的时间。

事实上，vector和list各有优劣。在各自的擅长领域做到了极致。所以具体场景具体分析使用哪种容器就可以。并且事实上，并非所有容器的使用都是非此即彼的……

主要目的：
1. 学习list的接口使用
2. 锻炼代码能力，尝试体会STL中迭代器设计的思想。体会迭代器在STL中的超核心作用。

1. list的数据结构

list的节点：

list和list node是不同的结构。list相当于是node的集合。我们需要了解，在STL 中的结点的字段会有什么，也方便我们后续设计list：

template<class T>
struct __list_node
{
	typedef void* void_pointer;
	void_pointer prev; //指向前一个节点的指针
	void_pointer next; //指向后一个对象的指针
	T data; //数据
};

我们看到：在STL list源码中，利用的C语言的泛型的思想（利用void*接受任意类型）。但是实际上我们设计的时候不用这么麻烦，因为我们只需要设置类型为：__list_node<T> *即可了……

从上面的节点结构来看，我们可以得出一个目前来说的结论：list是一个双向链表。

SGI的list不仅仅是一个双向链表，更是一个带头节点的双向循环链表。这也符合STL对迭代器的要求。对于list这样的数据结构来说，在逻辑上的线性空间，显然list支持迭代器的遍历效果。而STL要求的迭代器区间是：[begin, end)和[rbegin, rend)的要求的……而且对于插入删除操作来说，才能完成真正意义上的O(1)时间复杂度！！！

因为list是双向循环链表，所以我们仅仅根据一个节点指针就可以得到整个list。而这个指针一般是头节点的指针！

我们来看示意图：

list数据结构示意图

2. list的迭代器

迭代器接口

根据上面所示的list的数据结构图，我们大概率能得知，list的迭代器是不可能像vector那样用原生指针去作为迭代器，因为其node不保证在储存空间中连续存在。list迭代器必须有能力指向list的node，并且有能力进行正确的加、减、取值等等操作。所以，我们就不得不对list的迭代器进行封装。恰好，我们可以通过包装class来描述迭代器，并通过实现operator重载函数来实现迭代器的正常操作！！
由于STL list是一个双向链表（double linked-list），迭代器必须具备前移、后移的能力，所以list提供的是Bidirectional Iterator（双向迭代器）。不支持随机的数据+=这样的操作……
list迭代器有一个重要的性质：insert和erase等等操作，都不会造成原有的list迭代器失效。因为list的数据空间是不连续的，是数据之间的关系是比较独立的。
迭代器操作示意图：

3. list的接口

在这里不再介绍list的构造，增删……的接口了。我们直接看一些可能有用到但是不常用的接口。

3.1 clear

接口原型：
作用：清空链表内容……

例1：

int main()
{
	std::list<int> lt;
	for (int i = 0; i < 5; ++i)
	{
		lt.push_back(i);
		lt.push_back(i);
	}
	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	lt.clear();
	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	return 0;
}

完成对list内容的清空。

3.2 remove

接口原型：
作用：将list中所有值为val的元素删除。

例2：

int main()
{
	int arr[] = { 0,0,1,1,2,2,3,3,4,4,3,4,3 };
	std::list<int> lt(arr, arr + sizeof(arr)/sizeof(arr[0]));

	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	lt.remove(3);
	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	return 0;
}

完成对list中元素值为3的数据，进行删除。

3.3 unique

接口原型：

例3：

int main()
{
	int arr[] = { 0,0,1,1,2,2,3,3,4,4,3,4,3 };
	std::list<int> lt(arr, arr + sizeof(arr)/sizeof(arr[0]));

	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	lt.unique();
	for (const auto& e : lt)
	{
		cout << e << " ";
	}
	return 0;
}

特定：可以用来对有序的list进行去重操作。如果想要对list用unique进行去重，那么需要在使用之前对list进行sort。

例4：

#include <string>

struct Person 
{
    std::string name;
    int age;
};

int main() 
{
    std::list<Person> people = 
    {
        {"Alice", 20},
        {"Bob", 20},
        {"Charlie", 25},
        {"David", 25}
    };
    
    // 按年龄判定重复（年龄相同视为重复）
    people.unique([](const Person& a, const Person& b) 
    {
        return a.age == b.age;
    });
    
    // 输出结果：Alice(20) Charlie(25)
    for (const auto& p : people) {
        std::cout << p.name << "(" << p.age << ") ";
    }
    return 0;
}

自定义比较方法

3.4 splice

接口原型：
作用：在一个list中插入一段list区间。（可以是别人的区间，也可以是自己的……）

例5：

#include <iostream>
#include <list>

// 打印列表内容的辅助函数
void print_list(const std::list<int>& l, const std::string& name) {
    std::cout << name << ": ";
    for (int num : l) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    // 初始化两个列表
    std::list<int> list1 = {1, 2, 3};
    std::list<int> list2 = {4, 5, 6};

    print_list(list1, "初始 list1");  // list1: 1 2 3 
    print_list(list2, "初始 list2");  // list2: 4 5 6 

    // 1. 转移整个列表（将list2所有元素转移到list1末尾）
    auto it = list1.end();  // 插入点：list1的末尾
    list1.splice(it, list2);
    
    print_list(list1, "转移后 list1");  // list1: 1 2 3 4 5 6 
    print_list(list2, "转移后 list2");  // list2: （为空）

    // 重新初始化list2
    list2 = {7, 8, 9};
    print_list(list2, "重置后 list2");  // list2: 7 8 9 

    // 2. 转移单个元素（将list2的第一个元素转移到list1的开头）
    it = list1.begin();  // 插入点：list1的开头
    auto single_it = list2.begin();  // 要转移的元素：7
    list1.splice(it, list2, single_it);
    
    print_list(list1, "转移单个元素后 list1");  // list1: 7 1 2 3 4 5 6 
    print_list(list2, "转移单个元素后 list2");  // list2: 8 9 

    // 3. 转移元素范围（将list2的所有元素转移到list1中3的前面）
    // 找到list1中值为3的元素位置
    for (it = list1.begin(); it != list1.end(); ++it) {
        if (*it == 3) break;
    }
    // 转移list2的所有元素（范围为[begin, end)）
    list1.splice(it, list2, list2.begin(), list2.end());
    
    print_list(list1, "转移范围后 list1");  // list1: 7 1 2 8 9 3 4 5 6 
    print_list(list2, "转移范围后 list2");  // list2: （为空）

    return 0;
}

3.5 merge

接口原型：
作用：将两个元素有序list进行按照方法进行合并……

例6：

#include <iostream>
#include <list>

// 打印列表内容
void print_list(const std::list<int>& l, const std::string& name) {
    std::cout << name << ": ";
    for (int num : l) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    // 1. 基本用法（默认升序合并）
    std::list<int> list1 = {1, 3, 5};
    std::list<int> list2 = {2, 4, 6};
    
    print_list(list1, "合并前 list1");  // list1: 1 3 5 
    print_list(list2, "合并前 list2");  // list2: 2 4 6 
    
    list1.merge(list2);  // 合并list2到list1（均为升序）
    
    print_list(list1, "合并后 list1");  // list1: 1 2 3 4 5 6 
    print_list(list2, "合并后 list2");  // list2: （为空）


    // 2. 自定义比较规则（降序合并）
    std::list<int> list3 = {6, 4, 2};
    std::list<int> list4 = {5, 3, 1};
    
    print_list(list3, "合并前 list3");  // list3: 6 4 2 
    print_list(list4, "合并前 list4");  // list4: 5 3 1 
    
    // 自定义降序比较器
    auto desc_comp = [](int a, int b) { return a > b; };
    list3.merge(list4, desc_comp);  // 按降序合并
    
    print_list(list3, "降序合并后 list3");  // list3: 6 5 4 3 2 1 
    print_list(list4, "降序合并后 list4");  // list4: （为空）

    return 0;
}

3.6 reverse 和 sort

reverse：将list进行元素的反转。
sort：

由于list的迭代器类型是双向迭代器，而C++库<algorithm>中的sort方法底层采用快排的算法，这就要求我们不能用库中sort方法排序。所以list自己实现了排序方法。但是，list的内部的排序方法时间复杂度特别高……甚至不如我们将list的数据拷贝到vector中，再利用库中的sort进行排序，再拷贝会去的效率高（我们可以写程序验证）：

例7：

int main()
{
	srand((unsigned int)time(nullptr));
	std::list<int> lt1;
	for (int i = 0; i < 10000000; ++i) //1000w的数据量
	{
		lt1.push_back(rand());
	}
	
	std::list<int> lt2(lt1);
	
	int begin1 = clock();
	lt1.sort();
	int end1 = clock();

	int begin2 = clock();
	std::vector<int> v;
	for (auto e : lt2) //不用列表，效率低
	{
		v.push_back(e); 
	}
	std::sort(v.begin(), v.end());
	//lt2 = { v.begin(), v.end() }; //列表，效率很低
	auto it = lt2.begin();
	int i = 0;
	for (auto& e : lt2)
	{
		e = v[i++];
	}
	int end2 = clock();

	cout << "lt1的直接排序时间" << end1 - begin1 << endl;
	cout << "lt2的拷贝排序时间" << end2 - begin2 << endl;
	return 0;
}

在这里插入图片描述

4. list模拟实现

节点：

我们先把节点搭建出来：

template <class T>
struct list_node
{
	list_node(const T& val = T()) 
		: _data(val),_prev(nullptr), _next(nullptr)
	{ }
	list_node(T&& val = T()) //移动构造，为了让数据调用移动构造
		: _data(std::forward<T>(val)), _prev(nullptr), _next(nullptr)
	{}	
	list_node<T>* _prev;
	list_node<T>* _next;
	T _data;
};

框架：

template <class T>
class list
{
	typedef list_node<T> node; 
public:
	//……对外接口
private:
	node* _head;
};

4.1 默认成员函数

实现比较简单，我们的大多默认成员函数可以通过复用的方式进行。
注：大多数接口都需要迭代器完成。

public:
	list() //默认构造函数
	{
		empty_initnode(); //调用函数构造一个节点
	}
	list(const list<T>& lt) //拷贝构造函数
	{
		empty_initnode();
		for (const auto& e : lt)
		{
			//push_back(e); //一直尾插即可，后面实现尾插接口
		}
	}
	list(list<T>&& tmp) //移动构造函数
	{
		empty_initnode();
		swap(tmp); //调用类中实现的方法
	}
	~list() //析构函数
	{
		clear(); //直接调用clear函数，将链表节点全部清空
		delete _head;
		_head = nullptr;
	}
	const list<T>& operator=(const list<T>& obj) //赋值重载
	{
		if (this != &obj)
		{
			for (const auto& e : obj)
			{
				//push_back(lt); //同
			}
		}
		return *this;
	}
	const list<T>& operator=(list<T>&& tmp) //移动赋值
	{
		if (this != &tmp)
		{
			swap(tmp);
		}
		return *this;
	}
	void clear()
	{
		//调用pop_front/pop_back即可
		//TODO
	}
private:
	void empty_initnode() //一个空的构造
	{
		if (nullptr == _head)
		{
			_head = new node(); //默认构造一个头节点
			_head->_next = _head; //下一个节点指向自己
			_head->_prev = _head; //上一个节点也指向自己
		}
	}
	void swap(list<T>& tmp)
	{
		std::swap(_head, tmp._head); //交换指针即可
	}
private:
	node* _head;
};

4.2 迭代器设计

与库中迭代器设计不同！！！
list的迭代器设计，小编会和大家一步一步设计list的迭代器：
1. iterator
2. const_iterator
3. reverse_iterator

4.2.1 正向迭代器

对于代码的编写，我们有一个常用的方式：复用。我们尝试着：将const_iterator用iterator包装成const属性即可。

版本一：

template<class T>
class list_iterator
{	
	typedef list_node<T> node;
	typedef list_iterator<T> self; //将自己重命名
public:
	list_iterator(node* obj_node) //一般上不会是const node*
		:_node(obj_node)
	{ }
	self& operator++() //前置++
		{
		_node = _node->_next; //指向下一个节点
		return _node; //返回新node即可，会自己发生构造
	}
	T& operator*() //返回节点的数据
	{
		return _node->_data;
	}
	T* operator->() //返回节点数据的指针
	{
		return &(_node->_data);
	}
private:
	node* _node; //指向的节点
};

版本一的代码，我们可以正常的写完这样的是可以正常被普通list对象所使用的：

我们只需要在list类中重命名：typedef list_iterator<T> iterator;即可。

同时我们思考：这样的迭代器设计，能实现我们的const_iterator的复用需求吗？
1. 方案一：typedef const list_iterator<T> const_iterator;
  
  行不通。因为这个迭代器是不可能完成的。因为我们迭代器是需要改变属性的指针（成员变量）的指向的，但是const修饰的是list_iterator<T>，导致这个指针不能改变。
2. 方案二：typedef list_iterator<const T> const_iterator;
  
  行不通。对于类模板来说list<int>和list<const int>是不同的两种类别，我们从底层来看，当我们使用了const T这样的类型之后，你就会发现，迭代器中的指针类型为node<const T>这个类型和node<T>不是一个类型！！！无法作为list中节点的指针！
我们尝试将模板参数进行扩张。添加一个Ptr的模板参数，用于接受不同的指针类型。

同时我们的T&也面临类似的问题。对于调用函数：operator*。由于不管是普通迭代器还是常性迭代器本质类型都是没有常性的（不是一个类型），但是其内置的成员属性是会有常性的，所以我们需要在函数的返回值上面做文章。根据不同的传入的参数类型，打造不同的迭代器。
在这里插入图片描述

版本二：

/*只写部分接口*/
// typedef list_iterator<T, T&, T*> iterator 普通迭代器
// typedef list_iterator<T, const T&, const T*> const_iterator 常量迭代器
template<class T, class Ref, class Ptr>
class list_iterator
{
	typedef list_node<T> node;
	typedef list_iterator<T, Ref, Ptr> self; //将自己重命名
public:
	list_iterator(node* n)
		:_node(n)
	{ }
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	Ref operator*() const //如果Ref是T&，就是普通；如果是const T&就是常量
	{
		return _node->_data;
	}
	Ptr operator->() const //如果Ptr是T*，就是普通；如果是const T*就是常量
	{
		return &(operator*());
	}
	bool operator==(const self& iter) const
	{
		return _node == iter._node;
	}
	node* _node;
};

4.2.2 反向迭代器

事实上：反向迭代器的++操作，对于正向迭代器来说就是--操作。它们二者的操作在迭代器的移动上几乎就是相反的操作！！所以，我们可以进行如下的包装，直接使用正向迭代器来包装反向迭代器。

反向迭代器的实现：复用正向迭代器的实现！

所以我们或许会用正向迭代器作为反向迭代器的成员变量……这样的话，我们又该如何得知，迭代器指向的数据类型呢？继续作为参数传入！！！

/*只写部分接口*/
template<class Iterator, class Ref, class Ptr>
class list_reverse_iterator
{
	typedef list_reverse_iterator<Iterator, Ref, Ptr> self;
public:
	list_reverse_iterator(Iterator iter)
		:_iter(iter)
	{ }
	self& operator++()
	{
		--_iter;
		return *this;
	}
	self& operator--()
	{
		++_iter;
		return *this;
	}
	Ref operator*() const //如果Ref是T&，就是普通；如果是const T&就是常量
	{
		return *_iter;
	}
	Ptr operator->() const//如果Ptr是T*，就是普通；如果是const T*就是常量
	{
		return &(operator*()); //复用
	}
	bool operator==(const self& iter) const
	{
		return _iter == iter._iter;
	}
private:
	Iterator _iter;
};

4.2.3 list的迭代器

我们最后在list类模板中为各种迭代器类型声明即可！
然后设计list的迭代器函数：

iterator begin()
{
	return _head->_next;
}
const_iterator begin() const
{
	return _head->_next;
}
iterator end()
{
	return _head;
}
const_iterator end() const
{
	return _head;
}
//反向同理

4.3 增删改

插入一个节点的逻辑图：

4.3.1 insert和erase……

/*只写部分接口*/
iterator insert(iterator pos, const T& val)
{
	//1、构建新节点
	node* newnode = new node(val);
	//2、找到插入位置的前一个位置
	iterator pos_prev = pos._node->_prev; //不能--
	//3、改变链接关系
	pos_prev._node->_next = newnode;
	newnode->_prev = pos_prev._node;
	newnode->_next = pos._node;
	pos._node->_prev = newnode;

	return newnode;
}
iterator insert(iterator pos, T&& val)
{
	//完美转发的细节
	//1、构建新节点
	node* newnode = new node(std::forward<T>(val)); //保持val的属性，调用
	//2、找到插入位置的前一个位置
	iterator pos_prev = pos._node->_prev; 
	//3、改变链接关系
	pos_prev._node->_next = newnode;
	newnode->_prev = pos_prev._node;
	newnode->_next = pos._node;
	pos._node->_prev = newnode;

	return newnode;
}
iterator erase(iterator pos)
{
	assert(pos != end()); //头节点不能删除
	//1、找到这个节点的前一个节点和后一个节点
	node* pos_prev = pos._node->_prev;
	node* pos_next = pos._node->_next;
	//2、更改链接关系
	pos_prev->_next = pos_next;
	pos_next->_prev = pos_prev;
	//3、析构
	delete pos._node;
	return pos_next;
}
//复用

4.3.2 emplace

主要细节在于将参数包向下传递……

在这里插入图片描述
小编这里为了简单，直接将接口设计为参数设计为iterator。不然还有const_iterator与iterator之间的构造转化问题。有需要写隐式转换运算符过于麻烦，小编这里偷个懒，之间写普通迭代器版本：

/*新增的可变参数模板接口*/
template <class T>
struct list_node
{
	template<class... Args>
	list_node(Args&&... args)
		:_data(std::forward<Args>(args)...), _prev(nullptr), _next(nullptr)
	{ }

	list_node<T>* _prev;
	list_node<T>* _next;
	T _data;
};

/*list类成员函数的实现*/
template<class... Args>
iterator emplace(iterator pos, Args&&...args)
{
	//1、构造节点
	node* newnode = new node(std::forward<Args>(args)...); //将参数包往下传递
	//2、找到插入位置的前一个位置
	iterator pos_prev = pos._node->_prev;
	//3、改变链接关系
	pos_prev._node->_next = newnode;
	newnode->_prev = pos_prev._node;
	newnode->_next = pos._node;
	pos._node->_prev = newnode;

	return newnode;
}

模拟源码

#pragma once
#include <algorithm>
#include <cassert>

/*	STL中的list节点设计 */
//template<class T>
//struct __list_node
//{
//	typedef void* void_pointer;
//	void_pointer prev;
//	void_pointer next;
//	T data;
//};

namespace LL
{
	template <class T>
	struct list_node
	{
		list_node(const T& val = T()) 
			: _data(val), _prev(nullptr), _next(nullptr)
		{ }
		list_node(T&& val)
			: _data(std::forward<T>(val)), _prev(nullptr), _next(nullptr)
		{}
		template<class... Args>
		list_node(Args&&... args)
			:_data(std::forward<Args>(args)...), _prev(nullptr), _next(nullptr)
		{ }

		list_node<T>* _prev;
		list_node<T>* _next;
		T _data;
	};

	// 版本一：
	//template<class T>
	//class list_iterator
	//{	
	//	typedef list_node<T> node;
	//	typedef list_iterator<T> self; //将自己重命名
	//public:
	//	list_iterator(node<T>* obj_node)
	//		:_node(obj_node)
	//	{ }
	//	self& operator++() //前置++
 //		{
	//		_node = _node->_next; //指向下一个节点
	//		return _node; //返回新node即可，会自己发生构造
	//	}
	//	T& operator*()
	//	{
	//		return _node->_data;
	//	}
	//	T* operator->()
	//	{
	//		return _node;
	//	}
	//private:
	//	node* _node; //指向的节点
	//};

	//版本二：
	// typedef list_iterator<T, T&, T*> iterator 普通迭代器
	// typedef list_iterator<T, const T&, const T*> const_iterator 常量迭代器
	template<class T, class Ref, class Ptr>
	class list_iterator
	{
		typedef list_node<T> node;
		typedef list_iterator<T, Ref, Ptr> self; //将自己重命名
	public:
		list_iterator(node* n)
			:_node(n)
		{ }
		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;
		}
		Ref operator*() const//如果Ref是T&，就是普通；如果是const T&就是常量
		{
			return _node->_data;
		}
		Ptr operator->() const//如果Ptr是T*，就是普通；如果是const T*就是常量
		{
			return &(_node->_data);
		}
		bool operator==(const self& iter) const
		{
			return _node == iter._node;
		}
		bool operator!=(const self& iter) const
		{
			return _node != iter._node;
		}
		node* _node;
	};

	template<class Iterator, class Ref, class Ptr>
	class list_reverse_iterator
	{
		typedef list_reverse_iterator<Iterator, Ref, Ptr> self;
	public:
		list_reverse_iterator(Iterator iter)
			:_iter(iter)
		{ }
		self& operator++()
		{
			--_iter;
			return *this;
		}
		self operator++(int)
		{
			self tmp(*this);
			--_iter;
			return tmp;
		}
		self& operator--()
		{
			++_iter;
			return *this;
		}
		self operator--(int)
		{
			self tmp(*this);
			++_iter;
			return tmp;
		}
		Ref operator*() const //如果Ref是T&，就是普通；如果是const T&就是常量
		{
			return *_iter;
		}
		Ptr operator->() const//如果Ptr是T*，就是普通；如果是const T*就是常量
		{
			return &(operator*()); //复用
		}
		bool operator==(const self& iter) const
		{
			return _iter == iter._iter;
		}
		bool operator!=(const self& iter) const
		{
			return _iter != iter._iter;
		}
	private:
		Iterator _iter;
	};



	template <class T>
	class list
	{
		typedef list_node<T> node; 
	public:
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;
		typedef list_reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

		list() //默认构造函数
		{
			empty_initnode(); //调用函数构造一个节点
		}
		list(const list<T>& lt) //拷贝构造函数
		{
			empty_initnode();
			for (const auto& e : lt)
			{
				push_back(e); //一直尾插即可，后面实现尾插接口
			}
		}
		list(list<T>&& tmp) //移动构造函数
		{
			empty_initnode();
			swap(tmp); //调用类中实现的方法
		}
		~list() //析构函数
		{
			clear(); //直接调用clear函数，将链表节点全部清空
			delete _head;
			_head = nullptr;
		}
		const list<T>& operator=(const list<T>& obj) //赋值重载
		{
			if (this != &obj)
			{
				for (const auto& e : obj)
				{
					//push_back(lt); //同
				}
			}
			return *this;
		}
		const list<T>& operator=(list<T>&& tmp) //移动赋值
		{
			if (this != &tmp)
			{
				swap(tmp);
			}
			return *this;
		}
		void clear()
		{
			//调用pop_front/pop_back即可
			//TODO wait erase
			auto it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

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

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

		iterator insert(iterator pos, const T& val)
		{
			//1、构建新节点
			node* newnode = new node(val);
			//2、找到插入位置的前一个位置
			iterator pos_prev = pos._node->_prev; //不能--
			//3、改变链接关系
			pos_prev._node->_next = newnode;
			newnode->_prev = pos_prev._node;
			newnode->_next = pos._node;
			pos._node->_prev = newnode;

			return newnode;
		}
		iterator insert(iterator pos, T&& val)
		{
			//完美转发的细节
			//1、构建新节点
			node* newnode = new node(std::forward<T>(val)); //保持val的属性，调用
			//2、找到插入位置的前一个位置
			iterator pos_prev = pos._node->_prev; 
			//3、改变链接关系
			pos_prev._node->_next = newnode;
			newnode->_prev = pos_prev._node;
			newnode->_next = pos._node;
			pos._node->_prev = newnode;

			return newnode;
		}
		iterator erase(iterator pos)
		{
			assert(pos != end()); //头节点不能删除
			//1、找到这个节点的前一个节点和后一个节点
			node* pos_prev = pos._node->_prev;
			node* pos_next = pos._node->_next;
			//2、更改链接关系
			pos_prev->_next = pos_next;
			pos_next->_prev = pos_prev;
			//3、析构
			delete pos._node;
			return pos_next;
		}
		//复用
		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());
		}

		template<class... Args>
		iterator emplace(iterator pos, Args&&...args)
		{
			//1、构造节点
			node* newnode = new node(std::forward<Args>(args)...); //将参数包往下传递
			//2、找到插入位置的前一个位置
			iterator pos_prev = pos._node->_prev;
			//3、改变链接关系
			pos_prev._node->_next = newnode;
			newnode->_prev = pos_prev._node;
			newnode->_next = pos._node;
			pos._node->_prev = newnode;

			return newnode;
		}

	private:
		void empty_initnode() //一个空的构造
		{
			if (nullptr == _head)
			{
				_head = new node(); //默认构造一个头节点
				_head->_next = _head; //下一个节点指向自己
				_head->_prev = _head; //上一个节点也指向自己
			}
		}
		void swap(list<T>& tmp)
		{
			std::swap(_head, tmp._head); //交换指针即可
		}
	private:
		node* _head;
	};
}

【C++ STL】list详解和模拟

文章目录

前言