list的简单介绍
1. list的介绍及使用
1.1 list的介绍
1.2 list的使用
list的接口比较多，只需要掌握如何正确的使用，然后再去深入研究背后的原理，以达到可扩展的能力。以下为list的一些常见的重要接口。
1.2.1 list的构造
| 构造函数 | 接口说明 |
| list(sizt_type n,const value-type& val=value-type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list(const list& x) | 拷贝构造函数 |
| list(Inputlterator first,Inputlterator last) | 用[first,last]区间的元素构造list |
1.2.2 list iterator的使用
此处，可暂时将迭代器理解为一个指针，该指针指向list中的某个节点。
| 函数声明 | 接口说明 |
| begin+end | 返回第一个元素的迭代器+返回最后一个元素下一个位置都迭代器 |
| rbegin+rend | 返回第一个元素上一个位置的reverse_iterator,即end位置，返回最后一个元素的reverse_iterator，即begin位置 |
注意：
1.begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动。
2.rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
1.2.3 list capacity
| 函数声明 | 接口声明 |
| empty | 检测list是否为空，是返回true,否则返回false |
| size | 返回list中有效节点的个数 |
1.2.4 list element access
| 函数声明 | 接口说明 |
| front | 返回list的第一个节点中值的引用 |
| back | 返回list的最后一个节点中值的引用 |
1.2.5 list modifiers
| 函数声明 | 接口说明 |
push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list中最后一个元素 |
| push_back | 在list的尾部插入值为val的元素 |
| pop_back | 删除list中最后一个元素 |
| insert | 在list position位置插入值为val的元素 |
| erase | 删除list position位置的元素 |
| swap | 交换两个list中的元素 |
| clear | 清空list中的有效元素 |
1.2.6 list的迭代器失效
前面说过，此处大家可将迭代器暂时理解为类似于指针。迭代器失效即迭代器指向的节点的无效，即该节点别删除了。因为list的底层结构为带头节点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的是指向被删除节点的迭代器，其他迭代器并不会受影响。
#include<iostream>
#include<list>
using namespace std;void TestListIterator1()
{int array[] = { 1,2,3,4,5,6,7,8,9,0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){//erase（）函数执行后，it所指向的节点已被删除，因此it无效，// 在下一次使用it时，必须先给其赋值。l.erase(it);++it;}
}//改正
void TestListIterator2()
{int array[] = { 1,2,3,4,5,6,7,8,9,0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){//erase（）函数执行后，it所指向的节点已被删除，因此it无效，// 在下一次使用it时，必须先给其赋值。l.erase(it++);//it=l.erase(it);}
}int main()
{//TestListIterator1();TestListIterator2();return 0;
}2. list的模拟实现
2.1模拟实现list
2.2 list的反向迭代器
反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器。即：反向迭代器内部可以包含一个正向迭代器，会正向迭代器的接口进行包装即可。
//#include<iostream>
//using namespace std;
//
//template<class Iterator>
//class ReverseListTierator
//{
// //注意：此处typename的作用的明确告诉编译器，
// // Ref是Iterator类中的类型，而不是静态成员变量
// //否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
// //因为静态成员变量也是按照 类名::静态成员变量名的 方式访问
//public:
// typedef typename Iterator::Ref Ref; // 解引用返回类型
// typedef typename Iterator::Ptr Ptr; // 成员访问指针类型
// typedef ReverseListIterator<Iterator> Self; // 自身类型别名
//public:
// //构造
// ReverseListIterator(Iterator it):_it(it){} // 封装正向迭代器
//
// //具有指针类似行为
// Ref operator*()
// {
// Iterator temp(_it);
// --temp;// 后退到实际元素位置
// return *temp; // 返回元素引用
// }
//
// Ptr operator->()
// {
// return &(operator*());
// }
//
//
// //迭代器移动操作
// //前置++（反向迭代器前进=正向迭代器后退）
// Self& operator++()
// {
// --_it;// 正向迭代器后退
// return *this;
// }
//
// //后置++
// Self operator++(int)
// {
// Self temp(*this);// 保存当前状态
// --_it;// 正向迭代器后退
// return temp;// 返回旧状态
// }
//
// //前置--(反向迭代器后退 = 正向迭代器前进)
// Self& operator--()
// {
// ++_it;
// return *this;
// }
//
// //后置--
// Self operatoe--(int)
// {
// Self temp(*this); // 保存当前状态
// ++_it; // 正向迭代器前进
// return temp; // 返回旧状态
// }
//
// //比较操作
// bool operator==(const Self& rit) const
// {
// return _it == rit._it;
// }
//
// bool operator!=(const Self& rit) const
// {
// return _it != rit._it;
// }
//
//private:
// Iterator _it;//封装的底层正向迭代器
//};3. list与vector的对比
| vector | list | |
| 底层结构 | 动态顺序表，一段连续空间 | 带头节点的双向循环链表 |
| 随机访问 | 支持随机访问，访问某个元素效率O（1） | 不支持随机访问，访问某个元素效率O（N） |
| 插入和删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低。 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O（1） |
| 底层利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对原生态指针（节点指针）进行封装 |
| 迭代器失效 | 在插入元素时，要给所有的迭代器赋值，因为插入元素有可能导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值，否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使用场景 | 需要高效储存，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |
您对list有什么独特见解吗？欢迎在评论区留下思考轨迹，如果觉得这些内容有价值，不妨点亮小收藏🌟或分享给需要的人。下期我将带来关于stack和queue，让我们继续在思想的河流中相遇。
记住：最好的观点永远在碰撞中产生，我在留言区等你来创造思维的火花！