✍作者：阿润菜菜
📖专栏：C++

---

初识list

1. list基本概况

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素.

list实现的基本框架：

1. 与string和vector不同，list的遍历需要通过迭代器来实现，list的迭代器也不再是原生指针，而是模拟原生指针行为的一层封装。
2. 对于范围for的实现，本质就是通过迭代器，范围for可以遍历容器的迭代器，对迭代器进行解引用，然后依次拷贝给元素e，所以C++11的范围for没有什么新花样，本质上使用的还是迭代器实现的。
   下面我们看看list的使用：

2.list常见的重要接口

先贴上官方文档：list文档介绍

一、 对于list的构造我们有四种构造方式：
构造空的list、构造含有n个值为val的元素初始化list、拷贝构造、区间（first，last）元素构造list。

void TestList1()
{
    list<int> l1;                         // 构造空的l1
    list<int> l2(4, 100);                 // l2中放4个值为100的元素
    list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3
    list<int> l4(l3);                    // 用l3拷贝构造l4

    // 以数组为迭代器区间构造l5
    int array[] = { 16,2,77,29 };
    list<int> l5(array, array + sizeof(array) / sizeof(int));

    // 列表格式初始化C++11
    list<int> l6{ 1,2,3,4,5 };

    // 用迭代器方式打印l5中的元素
    list<int>::iterator it = l5.begin();
    while (it != l5.end())
    {
        cout << *it << " ";
        ++it;
    }       
    cout << endl;

    // C++11范围for的方式遍历
    for (auto& e : l5)
        cout << e << " ";

    cout << endl;
}

二、ist迭代器的使用：
1.在使用上时可以将迭代器理解成一个指针，该指针指向list中的某个节点。同时提供了正向迭代器和反向迭代器。
2… 注意：begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

// 注意：遍历链表只能用迭代器和范围for
void PrintList(const list<int>& l)
{
    // 注意这里调用的是list的 begin() const，返回list的const_iterator对象
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";
        // *it = 10; 编译不通过
    }

    cout << endl;
}

void TestList2()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    // 使用正向迭代器正向list中的元素
    // list<int>::iterator it = l.begin();   // C++98中语法
    auto it = l.begin();                     // C++11之后推荐写法
    while (it != l.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    // 使用反向迭代器逆向打印list中的元素
    // list<int>::reverse_iterator rit = l.rbegin();
    auto rit = l.rbegin();
    while (rit != l.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
}

三、list的空间大小

四、list元素获取

五、list的元素操作
1.对于list来说，insert不会导致迭代器失效，vector存在迭代器失效是因为在扩容时reserve采取异地扩容的方式，这就导致原有迭代器指向了已经被释放的空间。
但list并不存在扩容这样的操作，list直接按需申请空间，你要插入多少个节点，那我就申请多少个节点，然后将所有的节点链接到哨兵节点前面就好了，所以insert之后迭代器依旧可以继续使用，因为他对应的节点空间不会被销毁，依旧好好的存在着。
2.对于list的erase来说就不一样了，erase会释放迭代器对应节点的空间，自然erase之后迭代器就会失效，如果想要继续使用迭代器，则可以利用erase的返回值来更新迭代器，erase会返回被删除节点的下一个节点的迭代器，我们可以用erase的返回值来更新迭代器

// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList3()
{
    int array[] = { 1, 2, 3 };
    list<int> L(array, array + sizeof(array) / sizeof(array[0]));

    // 在list的尾部插入4，头部插入0
    L.push_back(4);
    L.push_front(0);
    PrintList(L);

    // 删除list尾部节点和头部节点
    L.pop_back();
    L.pop_front();
    PrintList(L);
}

// insert /erase 
void TestList4()
{
    int array1[] = { 1, 2, 3 };
    list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));

    // 获取链表中第二个节点
    auto pos = ++L.begin();
    cout << *pos << endl;

    // 在pos前插入值为4的元素
    L.insert(pos, 4);
    PrintList(L);

    // 在pos前插入5个值为5的元素
    L.insert(pos, 5, 5);
    PrintList(L);

    // 在pos前插入[v.begin(), v.end)区间中的元素
    vector<int> v{ 7, 8, 9 };
    L.insert(pos, v.begin(), v.end());
    PrintList(L);

    // 删除pos位置上的元素
    L.erase(pos);
    PrintList(L);

    // 删除list中[begin, end)区间中的元素，即删除list中的所有元素
    L.erase(L.begin(), L.end());
    PrintList(L);
}

其实list还提供了一个sort函数，但因为效率很低，我们基本上不会用，对比同样的算法库函数sort，如果你要排序list，倒不如先将list的数据拷贝到vector进行排序，等排完序再将数据拷贝回list里面去，就算这样的排序的性能都是要比直接用list进行排序的性能要高不少 ---- 一定要release下进行对比，能差一倍！
测试代码：

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

#define N 100000

int main()
{
	list<int> lt1,lt2;
	vector<int> v;

	for (int i = 0; i < N; ++i)
	{
		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()); //调用算法库sort进行排序
	size_t i = 0;
	for (auto& e : lt1) //将数据拷贝回去
	{
		e = v[i++];
	}
	int end1 = clock();

	int begin2 = clock();
	lt2.sort();
	int end2 = clock();

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

算法库的sort底层用的是快速排序，为了key值选的合适，快排会进行三数取中，所以会进行迭代器的作差，而list的双向迭代器肯定不支持做差，所以调用算法库的sort就会报错。
如果想要排序链表，那就只能调用list类的成员函数sort来进行排序，list的sort底层用的是归并排序。

这里就要引出迭代器从功能上来说，可以分为三类：只能++的单向迭代器（单链表、哈希表），既能++也能 - - 的双向迭代器（list带头双向循环链表），既能++也能 - - 还能±某个具体的数的随机迭代器（string、vector）

resize用于调整链表的空间，如果是调整大一些，那就是一个一个的申请节点，尾插到链表上面去。如果是调整小一些，那也需要一个个的释放节点，相当于尾删节点。

// insert /erase 
void TestList4()
{
    int array1[] = { 1, 2, 3 };
    list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));

    // 获取链表中第二个节点
    auto pos = ++L.begin();
    cout << *pos << endl;

    // 在pos前插入值为4的元素
    L.insert(pos, 4);
    PrintList(L);

    // 在pos前插入5个值为5的元素
    L.insert(pos, 5, 5);
    PrintList(L);

    // 在pos前插入[v.begin(), v.end)区间中的元素
    vector<int> v{ 7, 8, 9 };
    L.insert(pos, v.begin(), v.end());
    PrintList(L);

    // 删除pos位置上的元素
    L.erase(pos);
    PrintList(L);

    // 删除list中[begin, end)区间中的元素，即删除list中的所有元素
    L.erase(L.begin(), L.end());
    PrintList(L);
}

// resize/swap/clear
void TestList5()
{
    // 用数组来构造list
    int array1[] = { 1, 2, 3 };
    list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
    PrintList(l1);

    // 交换l1和l2中的元素
    list<int> l2;
    l1.swap(l2);
    PrintList(l1);
    PrintList(l2);

    // 将l2中的元素清空
    l2.clear();
    cout << l2.size() << endl;
}

list的模拟实现

list的迭代器 — 精华部分

迭代器的价值是什么：
a.迭代器对底层的实现进行封装，不暴露底层实现的细节。
b.提供统一的访问方式，降低使用者的使用成本。

1. 实现list的迭代器，最底层其实就是一个链表节点结构体的指针，我们知道 迭代器： 要么就是原生指针，要么就是自定义类型对原生指针的封装，本质都是模拟指针的行为! 所以对list要实现迭代器的功能，我们对这个指针进行了封装，所以list的迭代器就是用一个自定义类型来封装 node* 。
2. 我们知道对于模板实例化，加上模板参数才是类型，否则就是类名。
   在实现const版本迭代器时最容易想到的一种方式就是重新构建一个类，类里面原有成员函数都不变，仅仅是将类名做出修改，然后我们把解引用函数的返回值修改成常引用，在使用const_iterator迭代器类型的时候，如果你解引用迭代器则直接调用__list_const_iterator类里面的返回常引用的重载函数。
3. == 这样显然是代码冗余的，大佬是怎么做的？其实是通过增加模板参数，在传参数时，根据参数类型的不同实例化出不同的类。==
   例如用const_iterator时，就是用第二个模板参数为const T&的类模板，等T类型确定时，就会实例化出具体的类，当用iterator时，我们就用第二个模板参数为T&的类模板，等T类型确定时，又会实例化出另一个不同的类。
4. 当list存的是结构体类型Pos时，直接打印解引用迭代器后的值就会出现问题，因为解引用迭代器后拿到的是Pos类的对象，所以如果想要打印对象的值，我们可以重载Pos类的流插入运算符来实现，如果Pos类的成员变量是私有的，我们也可以用友元函数来解决。
5. 如果是普通指针我们一般就用解引用，如果是结构指针，我们喜欢用→的访问方式。当迭代器指向的数据是一个结构体对象时，我们更偏向于用→来访问，当迭代器指向的数据是单个数据时，我们更偏向于用*来访问。
6. 所以下面→解引用的使用方式更舒服一些，因为迭代器it所指向的内容是Pos结构体的对象。但it不是一个结构体指针，不能用→这样的访问方式，这该如何解决呢？因为it是一个对象，我们可以利用运算符重载来解决。
7. 这里template<class T, class Ref, class Ptr>三个模板参数分别是提供 T& 、const T& 和提供解引用访问（→)

//迭代器 --- 自定义类型封装node*
	//分类：1.原生指针 2.用自定义类型对原生指针的封装，模拟指针的行为
	//即->迭代器： 要么就是原生指针，要么就是自定义类型对原生指针的封装，本质都是模拟指针的行为！

	template<class T, class Ref, class Ptr>  //通过增加模板参数，提供多版本迭代器
	struct _list_iterator
	{
		typedef list_node<T> node; //加上模板参数才是类型，否则只是类名
		typedef  _list_iterator<T, Ref, Ptr> self;  //方便后面返回值,做参数
		node* _node; //指针

		_list_iterator(node* n)  // 提供构造函数，遍历使用
			:_node(n)
		{}

		Ref operator* ()  //提供const版本迭代器
		{
			return _node->_data;
		}

		//const 迭代器和普通迭代器的区别是什么？   一个内容可修改 ，一个内容不可被修改

		Ptr operator->()  //->重载
		{
			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& s)
		{
			return _node != s._node;
		}

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

		}
	};

9. 那这个迭代器是浅拷贝可以吗？ 可以呀，因为这个是node的指针，浅拷贝后指针指向同一个node是可以的。那为什么没有报错呢？ 因为我们没有提供析构函数。 而且不释放当然是正确的，因为这里结点是属于链表的，释放结点的工作应该交给链表类而不是迭代器类。
   所以当内置类型涉及资源申请时，也并不一定就要写析构函数，还需要视情况而定。迭代器只是一个工具而已，释放也得由开辟空间的对象(list)来释放

10.对于迭代器的封装： 底层物理上都是指向这个对象的4个字节的指针。但语法的千差万别，主要还是运算符重载！

重点的两个接口 — insert 和 erase

1. 实现insert时可以看到所传参数是迭代器，实际就是链表结点的地址，也是一个结构体指针，只不过我们对这个结构体指针进行了封装，这个迭代器就变成了一个对象，在实现上和数据结构初阶实现的带头双向循环链表没什么区别，仅仅是多了一个类的封装。
2. 那insert这里迭代器会不会失效？ 不会，pos指向节点没有发生地址改变
3. erase这里迭代器失效吗 肯定失效。因为迭代器指向被干掉了。 所以我们可以加个断言啊---- 谁不可以erase？ — 哨兵位头节点
4. 迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
5. 实现erase时返回删除位置的下一个位置的迭代器，以便于使用者更新erase之后的迭代器，防止产生迭代器失效问题。

		//insert函数 pos前插入x
		//insert这里迭代器会不会失效？  不会，pos指向节点不会发生地址改变
		void insert(iterator pos, const T& x)
		{
			node* cur = pos._node; //指针
			node* prev = cur->_prev;

			node* new_node = new node(x); //堆区申请

			prev->_next = new_node;
			new_node->_prev = prev;
			new_node->_next = cur;
			cur->_prev = new_node;
		}

		//erase函数 删除pos位置
		void erase(iterator pos)
		{
			assert(pos != end());  //防止删除哨兵节点

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

			prev->_next = next;
			next->_prev = prev;
			delete pos._node;

		}

小问题

1. 在实现赋值重载函数时，为什么我们不能传引用？当然不能，因为这里是赋值，不是二者交换，所以应该传参调用其拷贝构造
   

//赋值重载
		list<T>& operator=(const list<T> l)
		{
			swap(l);
			return *this;
		}

2. list的反向迭代器：通过前面例子知道，反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

//反向迭代器
	// 适配器 -- 复用
	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;
		}
	};

3. 显示报错报错 没有合适的默认构造函数怎么办？ 提供缺省----缺省函数为什么用 T() :调用其默认构造
4. 这个是很多人的疑惑：const对象在定义时有没有const属性？ 答案是没有的！否则我们如何对数据进行初始化？所以这里是编译器的特殊处理罢了，站在语法的角度，就初始化后在赋予const属性

list模拟实现源码参考

list与vector的对比

vector

优点：
a.支持下标的随机访问
b.尾插尾删效率高
c.CPU高速缓存命中率高（局部性原理）
缺点：
a.前面部分插入删除数据效率低（插入和删除需要挪动数据，尤其是数据量大时效率较低）
b.扩容有消耗，还存在一定空间浪费（2倍扩容是比较合适的，开大了浪费空间，开小了需要频繁扩容）

list

优点：
a.按需申请释放空间，无需扩容
b.任意位置插入删除的时间复杂度是O(1)，不考虑find查找位置，只是单纯erase和insert。
缺点：
a.不支持下标的随机访问
b.CPU高速缓存命中率低（局部性原理）

1. vector的insert和erase之后迭代器都会失效，list在insert之后迭代器不会失效，erase之后迭代器会失效
2. 在需要高效存储，支持随机访问，不关心插入删除效率，我们倾向于使用vector
3. 大量插入和删除操作，不关心随机访问的情况，我们倾向于使用list，而且现实中项目中list用的蛮多的

少熬夜，早点休息！