C++的list类（一）：list类的常见操作和模拟实现

前言

List类的迭代器

List类的模拟实现

list.h文件

test.cpp文件

前言

vector的insert和erase都会导致迭代器失效
list的insert不会导致迭代器失效，erase会导致迭代器失效

insert导致失效的原因是开辟了新空间后，迭代器扔指向原空间
erase导致失效的原因是销毁的空间不是连续的空间，迭代器找不到下一块小空间的位置

List类的迭代器问题

类模板：C++模板初阶

内部类：C++的类和对象（七）：友元、内部类

问题1：原生指针不能充当迭代器（原生指针是天然的迭代器的前提是空间连续）

原因：原生指针指向的是连续空间的情况下才可以充当迭代器

数组：是一片连续的存储空间，数组的原生指针数组名，++即是下一个元素的地址
链表：不是一片连续的存储空间，链表的原生指针Node*，++不是下一个结点的地址

问题2：对结点的原生指针的解引用得不到当前所在结点的数据

List类的模拟实现

难点：Node、iterator、list三个类的间接嵌套使用

Node、iterator、list都是一个类
Node类负责表示的单个结点的结构，并提供相关的方法来操作单个结点
list类负责管理所有结点间的关系及提供对外接口来让用户操作整个链表
iterator类负责实现封装原生指针和实现迭代器需要的方法

结点类模板

template <class T>
struct ListNode
{
	ListNode<T>* _next;//结点的后继指针
	ListNode<T>* _prev;//结点的前驱指针
	T _data;//结点中存放的数据
	
	ListNode(const T& x = T())//构造Node类类型的对象（一个结点对象）
		:_next(nullptr)//未传入指定数据，x就会等于该匿名对象
		,_prev(nullptr)//传入指定数据，x会等于那个指定的数据，T()不起作用
		,_data(x)
	{}
};

涉及知识点

1、在定义一个类时，如果类中的数据可以公用就选struct，需要保护一部分就用class，结点中的数据和前驱后继指针应该都能被访问到，所以可以直接选用struct

2、T()是一个T类型匿名对象，在构造结点时未传入有效数据，x就会给予T()进行初始化：

若T是内置类型（如 int、float、指针等），将x将被初始化为0、0.0或nullptr等默认值
若T是自定义类类型，则将调用该类的默认构造函数来创建一个匿名对象

普通迭代器类模板

构造迭代器对象

template<class T>
struct ListIterator
{
	typedef ListNode<T> Node;//此时迭代器类可以使用结点类
	typedef ListIterator<T> iterator;//将迭代器类重名名为iterator

	Node* _node;
	ListIterator(Node* node)//用_node封装原生指针，_node会被传入的原生指针初始化
        :_node(node)        //_node = _head->_next
	{}                      //_node就相当于原生指针
}

*运算符重载

//*it
T& operator*()//传引用返回避免了拷贝，且该数据可读可修改
{
	return _node->_data;//返回_node指向的结点对象中存放的数据_data
}

_node->_data会被编译器转变为*(_node)._data

->运算符重载

//a->b
T* operator->()//返回值为T*，T*表示T类型的指针
{
	return &_node->_data;//获取T类类型对象的地址，将它交给一个指向T类类型的对象的“匿名”指针，该指针的类型是T*，之后利用该指针去访问该对象中的成员变量的值
}

问题：为什么要返回_data的地址而不是返回_data？

答：用->访问对象中的成员，左操作数是指向该对象的指针而不是该对象本身，右操作数是要访问对象的成员（A* ptr = &aa1，ptr->_a1，ptr存放的是该对象的地址，此后就可以用ptr访问_a1了），返回的地址不用一个有名的指针承接，直接接->，此时返回的内容就类似T*类型的匿名指针（ (指向对象的匿名指针)->对象的成员）

问题：返回值类型可不可以是T&？

答：不可以，T* + 返回的地址 = 一个T*类型的指向返回地址的匿名指针，返回的地址被存放在了一个匿名指针中，T& + 返回的地址 = 未定义行为（函数返回一个对象的地址，则该函数的返回值类型必须是该对象的类型*）

前置和后置++、--、==、!=重载

//前置++
terator& operator++()//iterator&的意思是，在使用迭代器时，++操作是在该迭代器自身进行的
{
	_node = _node->_next;
	return *this;
}

//后置++（返回++前的值）
iterator operator++(int)
{
	iterator tmp(*this);//拷贝构造一个新的

	_node = _node->_next;

	return tmp;
}

//前置--
iterator& operator--()
{
	_node = _node->_prev;
	return *this;
}

//后置--（返回--前的值）
iterator operator--(int)
{
	iterator tmp(*this);

	_node = _node->_prev;

	return tmp;
}

//不等于
bool operator!=(const iterator& it)//（const iterator& this,const iterator& it）
{
	return _node != it._node;//this->_node != it.node
}

//等于
bool operator==(const iterator& it)
{
		return _node == it._node;
}