10.列表的模拟实现（普通迭代器和常量迭代器的类模板）

1. list的介绍及使用

1.1 list的介绍

list的文档介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素）

1.2 list的使用

头插、尾插、尾删、头删

#include <vector>
#include <algorithm>
#include <time.h>
#include <set>
using namespace std;

#include "List.h"

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;

    // 头插
	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;

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

insert的用法

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

	auto pos = find(lt.begin(), lt.end(), 3);
	if (pos != lt.end())
	{
        // insert就是在pos位置前插入一个节点
		// insert以后pos是否失效呢？（此处不存在失效）
        // 在vector中，扩容后，pos的形参发生改变，但是实参不会发生改变
        // 但是list是用链表结构，就算扩容，也不会使pos的形参发生变化
		lt.insert(pos, 30);
	}

    // 下面两个代码的测试可以发现，pos并不会失效
	cout << *pos << endl;
	(*pos)++;

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

	// 此处pos失效，因为pos指向的节点都被释放了，那么再访问pos指向的空间，就会造成野指针
	lt.erase(pos);
	//cout << *pos << endl;
    
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

remove的用法

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

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	// 打印结果为：10 2 5 3 4 4 6 4 3

	// void remove (const value_type& val);
	// 从容器中删除所有与 val 相等的元素。这将调用这些对象的析构函数，并按删除的元素数减小容器大小。
	// 因此，会将链表中val值为3的节点全部删除，并缩小容器的大小
	lt.remove(3);

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	// 打印结果为：10 2 5 4 4 6 4

	lt.remove(30);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	// 打印结果为：10 2 5 4 4 6 4

	lt.sort();   // 链表自带的排序功能

	/*
	sort(lt.begin(), lt.end());   // 库里面自带的排序功能，参数为迭代器的起始和结束位置
	*/
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	// 先排序，才能实现去重
	/*
	void unique();
	没有参数的版本从容器中每个连续的相等元素组中删除除第一个元素之外的所有元素。
	请注意，只有当元素与紧接其前面的元素相等时，才会从列表容器中删除该元素。因此，此函数对于排序列表特别有用。
	*/
	lt.unique();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

vector和list排序速度的比较

void test_op()
{
	srand(time(0));
	const int N = 100000;
	// 创建一个vector对象，并提前预留足够大的空间
	vector<int> v;
	v.reserve(N);

	// 创建两个list对象
	list<int> lt1;
	list<int> lt2;
	for (int i = 0; i < N; ++i)
	{
		// 将生成的随机数，尾插到两个链表中
		auto e = rand();
		//v.push_back(e);
		lt1.push_back(e);
		lt2.push_back(e);
	}

	// 将链表lt1中的数据，拷贝到vector对象v中
	int begin1 = clock();
	for (auto e : lt1)
	{
		v.push_back(e);
	}
	// 使用std::sort对vector对象v中的数据进行排序
	sort(v.begin(), v.end());

	size_t i = 0;
	for (auto& e : lt1)
	{
		// e是lt1数据的引用
		// 所以对e进行赋值，就是拷贝v中的数据到lt1中
		e = v[i++];
	}
	int end1 = clock();




	// 直接使用链表中自带的排序函数，对链表2中的数据进行排序
	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);
	/*
	// 打印结果为：
	vector sort : 246
	list sort : 118
	*/
	// 综上可知，vector的排序速度是远大于list的排序速度的
}

2. list的模拟实现

list的私有成员变量

private:
	node* _head;  // 链表的头节点
	size_t _size; // 链表的大小

list_node(节点的类)

// 此处的T和list<T>是同一个模板参数
template<class T>
struct list_node
{
    // _next指向下一个节点
    list_node<T>* _next;
    // _prev指向前一个节点
    list_node<T>* _prev;
    // 该节点存放的数据
    T _data;

    // 节点的构造函数
    list_node(const T& x)   
        :_next(nullptr) 
        , _prev(nullptr)
        , _data(x)
    {}
};

__list_iterator(迭代器的类)

迭代器的价值：
1.封装底层实现，不暴露底层实现的细节。
2.提供统一的访问方式，降低使用成本。

// 迭代器的类类型就是__list_iterator<T>
// 类名就是__list_iterator
template<class T>
struct __list_iterator        
{
    // list_node<T> 就是节点的类类型，将节点的类类型定义为node
	typedef list_node<T> node;
    
    // 定义了一个节点指针，但是并没有进行初始化
	node* _pnode;          

    // 迭代器的构造函数
	__list_iterator(node* p)   
		:_pnode(p)              // 使用传递的节点p来初始化_pnode
	{}

    // 迭代器的解引用
    // it为迭代器，(*it)++ 其实就是对_pnode->_data进行++, 因为是传引用返回
    // T会根据_pnode->_data的类型，实例化对应的类型
	T& operator*()              // 解引用，就是返回 _pnode->data
	{
		return _pnode->_data;
	}

    // 迭代器++
    // ++ 也就是返回_pnode->next指向节点的地址
    // 此处是传引用返回，因为_pnode->_next指向的节点存在于主函数中，
    // 所以传引用返回后依旧可以进行读写操作
    // __list_iterator<T>& 就是对迭代器对象的引用
    // __list_iterator<T>是迭代器的类型
	__list_iterator<T>& operator++()   
	{
        // 修改迭代器成员变量_pnode指向的节点
		_pnode = _pnode->_next;
        // this就是迭代器对象的指针
        // 返回*this，就是返回迭代器对象
		return *this;    
	}

	bool operator!=(const __list_iterator<T>& it)
	{
        // 判断是否相等，也就是判断两个迭代器的_pnode是否相等，比较地址是否相等
		return _pnode != it._pnode;    
	}
};

__list_const_iterator(const迭代器的类)

// 跟普通迭代器的区别：遍历，不能用*it修改数据
// it就是迭代器对象，*it就是迭代器指向的节点的数据，
// 对于const迭代器，const修饰的是*it，因此对于*it只能读，不能够进行修改

/*
1.const T* p1;   // const在*左侧，修饰的是*p1
2.T* const p2;   // const在*右侧，修饰的是p2
// const迭代器类似于第一种情况，保护指向的对象不被修改，但是迭代器本身是可以修改的

注：普通迭代器前加const可不是const迭代器，如下：
const list<int>::iterator cit = lt.begin();
// 这里的const修饰的是cit，也就是保护迭代器本身不可以进行修改，那么就不可以对cit进行++，或者--的操作，这不符合迭代器的行为
*/

template<class T>
struct __list_const_iterator
{
    // list_node<T> 就是节点的类类型，将节点的类类型定义为node
	typedef list_node<T> node;
    // 定义了一个节点指针，但是并没有进行初始化
	node* _pnode;

    // const迭代器的构造函数
	__list_const_iterator( node* p)
		:_pnode(p)
	{}
    
    // const迭代器的解引用
	const T& operator*() 
	{
        // 会根据_pnode->_data类型，来实例化const T& 的类型
        // const修饰的是返回值，因此返回值无法进行修改
        // 之所以可以进行引用返回，是因为_pnode->_data不会随着函数而结束自身的生命周期
		return _pnode->_data;
	}

    // const迭代器++
    // __list_const_iterator<T>是const迭代器的类型
    // __list_const_iterator<T>& 是对const迭代器对象的引用
    // 此处的返回值，可以被传引用返回
	__list_const_iterator<T>& operator++()
	{
        // 更新const迭代器对象的成员变量_pnode指向的节点
		_pnode = _pnode->_next;
        // 返回迭代器对象
		return *this;
	}

    // const迭代器--
    __list_const_iterator<T>& operator--()
	{
		_pnode = _pnode->_prev;
		return *this;
	}

    // const迭代器判断是否相等
	bool operator!=(const __list_const_iterator<T>& it)
	{
		return _pnode != it._pnode;
	}
};

对普通迭代器和const迭代器的合并

// 我们发现迭代器和const迭代器，有大量的冗余代码，因此做出合并
/*
Ref 是reference的缩写
ref就是引用，ptr就是指针
template<class T, class Ref, class Ptr>

同一个类模板实例化出的两个类型，
Ref可以被实例化为T&，也可以被实例化为const T&
Ptr可以被实例化为T*，也可以被实例化为const T*
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

如果是节点类型为 list<int>
则template<class T, class Ref, class Ptr>将被实例化为下面两种类类型
也就是将一个迭代器类模板，实例化为了两个类，一个普通迭代器的类，一个const迭代器的类
typedef __list_iterator<int, int&, int*> iterator;
typedef __list_iterator<int, const int&, const int*> const_iterator;
*/

template<class T, class Ref, class Ptr>
struct __list_iterator
{
    // 将节点的类类型定义为node
	typedef list_node<T> node;
    // 将迭代器的类类型定义为Self
	typedef __list_iterator<T, Ref, Ptr> Self;
    
    // 定义了一个节点指针，但是并没有进行初始化
	node* _pnode;

    // 迭代器的构造函数
	__list_iterator(node* p)
		:_pnode(p)
	{}

    // 迭代器的->操作
    // 通过指针访问节点对象的成员变量data
    // 在主函数中，如果创建const迭代器，也就是 const_iterator cit(head->next)
    // 因为typedef __list_iterator<T, const T&, const T*> const_iterator;
    // template<class T, class Ref, class Ptr>
    // 所以Ptr对应的类型是const int*，
    // 如果链表的类类型是list<int>
    // 那么Ptr的类型是const int*，
	Ptr operator->()
	{ 
        // _pnode是链表节点的指针
        // _pnode->_data，可以拿到链表节点存放的数据
        // &_pnode->_data，也就是取链表节点存放的数据的地址
		return &_pnode->_data;
	}
    /*
        // (详细看test_list5)下面这两种方法是等价的
        cout << it->_row << ":" << it->_col << endl;
		cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;
        // it-> 是一个函数调用，即it.operator->()
        // it.operator->() 的返回对象类类型是pos*，所以再次使用-> ，返回pos类型的成员变量row的值
        // 本来面貌：it->->_row，编译器为了可读性，做了特殊处理，省略了一个->
    */
    

    // 同上，Ref的类型应该是const int&
	Ref operator*()
	{
		return _pnode->_data;
	}

	// ++it  前置
    // 因为typedef __list_iterator<T, Ref, Ptr> Self;所以Self就是一个迭代器的类类型
	Self& operator++()
	{
		_pnode = _pnode->_next;
        // 返回一个迭代器对象（++之后的迭代器对象）
		return *this;
	}

	// it++  后置:括号中的int为占位符
	Self operator++(int)
	{
        // 使用this指针指向的迭代器对象构造一个临时的迭代器对象
		Self tmp(*this);
		_pnode = _pnode->_next;	
        // 返回++之前的迭代器对象，这个对象是一个临时对象，因此不可以进行传引用返回
		return tmp;
	}

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

    // 后置：括号中的int为占位符
	Self operator--(int)
	{
		Self tmp(*this);
		_pnode = _pnode->_prev;
		return tmp;
	}

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

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

反向迭代器的类模板

// reverse_iterator.h
// 如果要使用反向迭代器，必须要使用反向迭代器的头文件
// 给我不同容器的正向迭代器，适配出对应的这个容器需要的反向迭代器
template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
	typedef ReverseIterator<Iterator, Ref, Ptr> Self;

public:
    // 构造函数
	ReverseIterator(Iterator it)
		:_it(it)
	{}

    // 以list为例
    // begin() 对应的是 rend()  ;  begin() 指向首个元素 --> rend() 指向首个元素
    // end()   对应的是 rbegin() ; end() 指向的是哨兵位 --> rbegin() 指向的是哨兵位
    /*
    end()     begin()
    哨兵位        1      2      3      4
    rbegin()   rend()
    rend()                          rbegin()    进行--操作之后的位置
    */
    // 因此  解引用指向的元素时，必须 --tmp
    // 因为begin() 进行--操作之后，与rbegin()对应的节点是一致的
    // 如 return reverse_iterator(begin()); 使用正向迭代器的开始迭代器 构造 反向迭代器的结束迭代器
    // 如果要进行解引用，--正向迭代器之后才是其正确的位置
	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) const
	{
		return _it != s._it;
	}

private:
	Iterator _it;
};

list双向链表的构造函数

/*
// 节点的构造函数
list_node(const T& x)   
:_next(nullptr) 
, _prev(nullptr)
, _data(x)
{}
*/

/*
list()
{
	// T()就是构造节点所需要的参数const T& x
    // T()：也就是调用x的默认构造函数去初始化这个参数x 
    // T()：类型为x的一个匿名对象
	_head = new node(T());  
	_head->_next = _head;
	_head->_prev = _head;
}
*/

void empty_initialize()
{
	_head = new node(T());
	_head->_next = _head;
	_head->_prev = _head;
}

// 双向链表的无参构造函数
list()
{
	empty_initialize();
}

list::push_back, push_front, pop_front, pop_back

//尾插
void push_back(const T& x)
{
    // 方法一
    /*
    // 先创建一个新节点
    node* newnode = new node(x);   
   
    // _head->prev中存放的是tail节点的地址
	node* tail = _head->_prev;     
	
	// _head    newnode   tail
    // 将上面三个节点按顺序双向链接起来
	tail->_next = newnode;    
	newnode->_prev = tail;
	newnode->_next = _head;
	_head->_prev = newnode;
	*/
    
    // 方法二
    // 当我们实现insert()之后，我们就可以通过insert()来实现 push_back
    // 也就是在end()位置前插入
    insert(end(), x);
}

// 头插   
void push_front(const T& x)
{
    // 头插就是在begin()位置前插入
	insert(begin(), x);
}

// 头删
void pop_front()
{
    // 头删就是删除begin()位置的节点
	erase(begin());
}

// 尾删
void pop_back()
{
    // 尾删就是删除end()位置前的节点
    // --end() 会调用operator--
	erase(--end());
}    

list的拷贝构造函数的传统写法

void empty_initialize()
{
	_head = new node(T());
	_head->_next = _head;
	_head