1.list介绍
1.1 list概述
1.概述：list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. 底层实现：list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list区别：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. list的优势：与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. list的缺陷：与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
我们用代码来体会一下list的缺点：
void test_op1()
{
srand(time(0));
const int N = 1000000;//一百万数据
//两个链表
list<int> lt1;
list<int> lt2;
//一个顺序表
vector<int> v;
//生成随机数据，尾插到链表1和顺序表v中去
for (int i = 0; i < N; ++i)
{
auto e = rand()+i;//加上这个i主要是为了减少重复数字概率
lt1.push_back(e);
v.push_back(e);
}
//vector排序
int begin1 = clock();
sort(v.begin(), v.end());
int end1 = clock();
//list排序
int begin2 = clock();
lt1.sort();
int end2 = clock();
//打印比较两者用时
printf("vector sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}
void test_op2()
{
srand(time(0));
const int N = 1000000;
list<int> lt1;
list<int> lt2;
for (int i = 0; i < N; ++i)
{
auto e = rand();
lt1.push_back(e);
lt2.push_back(e);
}
// 拷贝vector
int begin1 = clock();
vector<int> v(lt2.begin(), lt2.end());
// 排序
sort(v.begin(), v.end());
// 拷贝回lt2
lt2.assign(v.begin(), v.end());
int end1 = clock();
//lt1排序
int begin2 = clock();
lt1.sort();
int end2 = clock();
//打印
printf("list copy vector sort copy list sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}
1.2相关接口的介绍
2.简化模拟实现
通过去查看stl中list.h的源码我们可以知道，list是通过一个_head的Node*指针进行维护的，而其中广泛使用迭代器进行传值和访问数据。下面对其先直接摆代码，然后对其中细节进行详细介绍。
#pragma once
#include<assert.h>
#include<iostream>
namespace zzg
{
template<typename T>
struct ListNode
{
ListNode<T>* _next;//这个地方为什么类型不是T*？？？答：因为我们指针是需要指向一个ListNode<T>*类型的，而非T类型。
ListNode<T>* _prev;
T _data;
//ListNode有参构造
ListNode(const T& x = T())
:_next(nullptr)
,_prev(nullptr)
, _data(x)
{}
};
template<class T, class Ref, class Ptr>
class list_iterator
{
typedef struct ListNode<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
public:
Node* _node;
public:
//带参构造
list_iterator(Node* node)//这个地方用值拷贝，用引用会有bug
:_node(node)
{}
//++
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)//后置++
{
Self temp = *this;//拷贝构造一份，这时候会调用编译器自动生成的拷贝构造，为浅拷贝，但是需求满足了。
_node = _node->_next;
return temp;//这个地方得返回值了，因为现在的Self已经变了
}
//--
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)//后置--
{
Self temp = *this;//拷贝构造一份，这时候会调用编译器自动生成的拷贝构造，为浅拷贝，但是需求满足了。
_node = _node->_prev;
return temp;//这个地方得返回值了，因为现在的Self已经变了
}
//*it
Ref operator*()
{
return _node->_data;
}
//!=
bool operator!=(const Self& it)
{
return _node != it._node;
}
//==
bool operator==(const Self& it)
{
return _node == it._node;
}
//->重载
Ptr operator->()
{
return &_node->_data;
}
};
//template<typename T>
//class list_const_iterator
//{
// typedef struct ListNode<T> Node;
// typedef list_const_iterator<T> Self;
//public:
// Node* _node;
//public:
// //带参构造
// list_const_iterator(Node* node)//这个地方用值拷贝，用引用会有bug
// :_node(node)
// {}
// //++
// Self& operator++()
// {
// _node = _node->_next;
// return *this;
// }
// Self operator++(int)//后置++
// {
// Self temp = *this;//拷贝构造一份，这时候会调用编译器自动生成的拷贝构造，为浅拷贝，但是需求满足了。
// _node = _node->_next;
// return temp;//这个地方得返回值了，因为现在的Self已经变了
// }
// //--
// Self& operator--()
// {
// _node = _node->_prev;
// return *this;
// }
// Self operator--(int)//后置--
// {
// Self temp = *this;//拷贝构造一份，这时候会调用编译器自动生成的拷贝构造，为浅拷贝，但是需求满足了。
// _node = _node->_prev;
// return temp;//这个地方得返回值了，因为现在的Self已经变了
// }
// //*it
// const T& operator*()
// {
// return _node->_data;
// }
// //!=
// bool operator!=(const Self& it)
// {
// return _node != it._node;
// }
// //==
// bool operator==(const Self& it)
// {
// return _node == it._node;
// }
// //->重载
// const T* operator->()
// {
// return &_node->_data;
// }
//};
template<typename T>
class list
{
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
typedef struct ListNode<T> Node;
private:
Node* _head;//头节点
public:
//无参构造函数
list()
{
empty_init();
}
//拷贝构造
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
// lt1 = lt3
list<T>& operator=(list<T> lt)//先调用拷贝构造，构造出一个lt来
{
swap(lt);//然后交换这个局部变量与this，原this中是其他的东西
return *this;//返回this本身
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
//清理函数
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
//析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
iterator begin()
{
return _head->_next;//隐式类型转换
//return iterator(_head->_next);
}
iterator end()
{
return _head;//隐式类型转换
//return iterator(_head);
}
//const + 迭代器 --> 迭代器本身不可修改
//我们需要的：迭代器指向的内容不可修改 const T*类型 而不是 T* const类型
//如果我们直接在一般迭代器前面+const,即const iterator --> 该迭代器不可修改，因为这是一个自定义类
//解决，直接再单独一个自定义const迭代器类出来
const_iterator begin() const
{
return _head->_next;//return iterator(_head->_next);
}
const_iterator end() const
{
return _head;//return iterator(_head);
}
//尾插
void push_back(const T& x)
{
insert(end(), x);
}
//头插
void push_front(const T& x)
{
insert(begin(), x);
}
//void push_back(const T& x)
//{
// Node* newnode = new Node(x);
// //找到尾巴
// Node* tail = _head->_prev;
// tail->_next = newnode;//链接临近两点
// newnode->_prev = tail;
// newnode->_next = _head;
// _head->_prev = newnode;
//}
//任意插入
void insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
}
//任意删除
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
//尾删
void pop_back()
{
erase(--end());
}
//头删
void pop_front()
{
erase(begin());
}
};
struct A
{
public:
int _a;
int _b;
A(int a = 0, int b = 0)
{
_a = a;
_b = b;
}
};
//测试函数
void test_list1()
{
/*list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
lt.pop_back();
lt.pop_back();
lt.pop_back();
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
std::cout << *it << " ";
it++;
}
std::cout << std::endl;*/
list<A> Al;
Al.push_back({ 1,1 });
Al.push_back({ 2,2 });
Al.push_back({ 3,3 });
Al.push_back({ 4,4 });
Al.push_back({ 5,5 });
Al.push_back({ 6,6 });
list<A>::iterator it = Al.begin();
while (it != Al.end())
{
//std::cout << (*it)._a << '/' << (*it)._b << std::endl;
std::cout << it->_a << '/' << it->_b << std::endl;//it->_a ---> it->->_a == it.operator->()->_a;
it++;
}
std::cout << std::endl;
}
}
3.各部分的细节详述
主要包含三个部分，一是整体的链表类，二是链表中的每个元素结点类，还有就是用来访问修改结点的迭代器类。
下面分开进行细节介绍。
3.1结点
每个结点我们很熟悉，无非是两个指针和一个数据，一个指针指向它前面的结点，另一个指向其后面的结点，数据中放具体元素的值。
下面是基本结构框架：
template<typename T>
struct ListNode
{
ListNode<T>* _next;//这个地方为什么类型不是T*？？？答：因为我们指针是需要指向一个ListNode<T>*类型的，而非T类型。
ListNode<T>* _prev;
T _data;
//ListNode有参构造
ListNode(const T& x = T())
:_next(nullptr)
,_prev(nullptr)
, _data(x)
{}
};
细节：
- 使用struct，标注为公有属性，方便外部调用
- list是带头双向循环链表，因而每个结点要有两个指针
- 提供全缺省的默认构造函数
思考：每个结点的两个指针为什么是ListNode*类型而不是T*类型呢？
答：因为我们每个结点的指针指向的是一个结点，T仅仅是一个结点中的数据而已。
3.2迭代器
template<class T, class Ref, class Ptr>
class list_iterator
{
typedef struct ListNode<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;
public:
Node* _node;
public:
//带参构造
list_iterator(Node* node)//这个地方用值拷贝，用引用会有bug
:_node(node)
{}
}
细节1：迭代器用原生指针还是专门设计为类的问题
思考：list迭代器为什么要专门设置一个类？？？
答：
这是由于list的每个节点物理空间不连续，导致迭代器不能像之前string\vector那样简单的设计为原生指针，而是设计为一个类，以此来扩大我们对迭代器行为控制权限，重新设计*，->,++等操作。
vector，string原生指针充当迭代器：
像之前string，vector这种容器，其原生指针T*就是天然的迭代器，因为++就会自动指向到下一个数据，*引用也是拿到的我们想要的数据。
但是在list中，我们++T*，很明显由于地址不连续的缘故，压根不知道会指向的是什么(大概率会是随机值)。
但是需要重点注意的是，我们所设计的迭代器类是模拟的string/vector中T*的动作。
细节2：迭代器++、–行为重载的返回类型问题
//++
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self operator++(int)//后置++
{
Self temp = *this;//拷贝构造一份，这时候会调用编译器自动生成的拷贝构造，为浅拷贝，但是需求满足了。
_node = _node->_next;
return temp;//这个地方得返回值了，因为现在的Self已经变了
}
//--
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)//后置--
{
Self temp = *this;//拷贝构造一份，这时候会调用编译器自动生成的拷贝构造，为浅拷贝，但是需求满足了。
_node = _node->_prev;
return temp;//这个地方得返回值了，因为现在的Self已经变了
}
思考：为什么前置++返回的是类对象引用，而后置++返回类型是一般类型？
答：这要结合函数设计来看，在前置++中，我们返回的是类本身；而后置++，我们返回的是一个局部的类对象，局部类对象在出函数后会自动销毁。
细节3：迭代器解引用返回类型
//*it
Ref operator*()
{
return _node->_data;
}
注：
//iterator:
typedef list_iterator<T, Ref, Ptr> Self;
//list:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
返回Ref，用来区分const_iterator 和 iterator。
思考：为什么不重载const iterator?
答：const + 类 --> 表示该指针不可修改，并非我们所期望的指针指向内容不可修改。
思考：iterator 与 const_iterator 是同一个类吗？
答：不是。是利用同一份类模板生成的完全不同两份类。
细节4：迭代器operator->重载
//->重载
Ptr operator->()
{
return &_node->_data;
}
注：
//iterator:
typedef list_iterator<T, Ref, Ptr> Self;
//list:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
struct A
{
public:
int _a;
int _b;
A(int a = 0, int b = 0)
{
_a = a;
_b = b;
}
};
main:
list<A> Al;
Al.push_back({ 1,1 });
Al.push_back({ 2,2 });
Al.push_back({ 3,3 });
Al.push_back({ 4,4 });
Al.push_back({ 5,5 });
Al.push_back({ 6,6 });
list<A>::iterator it = Al.begin();
while (it != Al.end())
{
//std::cout << (*it)._a << '/' << (*it)._b << std::endl;
std::cout << it->_a << '/' << it->_b << std::endl;//it->_a ---> it->->_a == it.operator->()->_a;
it++;
}
std::cout << std::endl;
为了可读性，编译器把it->->_a优化为了it->_a
思考：上述代码的it->->_a代表了什么？
答：it->_a —> it->->_a == it.operator->()->_a;，这里在编译器写法上理论上应该写两个箭头的，一个用于运算符重载函数的调用，另一个是为了进入到指针里面访问数据，这里编译器为了可读性将其优化为了一个箭头。
3.3链表
链表类主要结构如下：
template<typename T>
class list
{
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
typedef struct ListNode<T> Node;
//无参构造函数
list()
{
empty_init();
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
private:
Node* _head;//头节点
}
细节1：list中提供begin和end函数的理由和返回类型？
iterator begin()
{
return _head->_next;//隐式类型转换
//return iterator(_head->_next);
}
iterator end()
{
return _head;//隐式类型转换
//return iterator(_head);
}
//const + 迭代器 --> 迭代器本身不可修改
//我们需要的：迭代器指向的内容不可修改 const T*类型 而不是 T* const类型
//如果我们直接在一般迭代器前面+const,即const iterator --> 该迭代器不可修改，因为这是一个自定义类
//解决，直接再单独一个自定义const迭代器类出来
const_iterator begin() const
{
return _head->_next;//return iterator(_head->_next);
}
const_iterator end() const
{
return _head;//return iterator(_head);
}
思考：list提供begin和end的原因：
答：
1._head是私有的。
2.更加方便的使用迭代器，在上面代码我们可以发现，返回的都是迭代器类型。
返回迭代器类型的原因：
与后面使用迭代器相兼容。
细节2：插入元素代码
//尾插
void push_back(const T& x)
{
insert(end(), x);
}
//头插
void push_front(const T& x)
{
insert(begin(), x);
}
//void push_back(const T& x)
//{
// Node* newnode = new Node(x);
// //找到尾巴
// Node* tail = _head->_prev;
// tail->_next = newnode;//链接临近两点
// newnode->_prev = tail;
// newnode->_next = _head;
// _head->_prev = newnode;
//}
//任意插入
void insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
}
细节3：删除元素代码
//任意删除
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
//尾删
void pop_back()
{
erase(--end());
}
//头删
void pop_front()
{
erase(begin());
}
思考：为什么erase()要返回迭代器类型？？？
答：因为要及时对外更新迭代器指针，防止迭代器失效。
思考：为什么pop_back()没有返回迭代器类型？
答：因为pop_back()不会对外接收迭代器，不存在对外更新迭代器问题。但是erase是接收迭代器的，因而要及时更新。
思考：–end()是否会影响到_head，为什么？
答：会影响到，但是影响到的是_head的值拷贝，没有影响到“母体”。
细节4：clear()函数和析构函数
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
//清理函数
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
//析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
细节5：拷贝构造函数与赋值运算符重载
//拷贝构造
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
// lt1 = lt3
list<T>& operator=(list<T> lt)//先调用拷贝构造，构造出一个lt来
{
swap(lt);//然后交换这个局部变量与this，原this中是其他的东西
return *this;//返回this本身
}
思考：为什么赋值运算符重载函数参数用list lt而不是引用呢？
答：复用拷贝构造函数，是为现代写法。
细节6：insert返回为void？
//任意插入
void insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
}
在string中insert我们返回的是迭代器，但是这里为什么返回值是void呢？
答：因为string是连续空间，插入数据会挪动数据，造成迭代器失效。但是链表是由结点链接而成，插入数据不会挪动数据，不会造成迭代器失效问题。
在vector中 insert/erase因为增删都会牵扯到数据挪动问题，两个函数肯定都要去返回迭代器来更新外部迭代器。
但是对于list，insert不会挪动数据因而不会失效，但是erase时候，原结点被删除，会造成迭代器失效。
4.总结
list模拟实现核心就是一个类迭代器的实现，相比之前string、vector，list迭代器更值得细细思考与总结。
list模拟实现还一个难点在于使用类模板，应注意类模板问题。
EOF
