【C++】——list 容器的解析与极致实现
https://i-blog.csdnimg.cn/direct/511c68e52cb04cc4bb7c19de8168dfe1.gif人的一切痛苦，本质上都是对自己的无能的愤怒。
—— 王小波
目次
1、list 介绍
2、list的使用
2.1 list 的构造
2.2 iterator 的使用
2.3 list 的修改
2.4一些特殊接口
2.5 迭代器失效题目
3、实现list
3.1底层结构
结点类
list类
迭代器类
3.2功能接口
迭代器接口
插入删除
拷贝赋值析构函数
4、list与vector 区别对比
1、list 介绍
List是C++标准模板库(STL)中的一个成员，其本质为带头双向循环链表。差别于连续的、精密排列的数组容器Vector，List容器的内部是由双向链表构成的，使得它在插入和删除操作上，就如同行云流水一样平常顺畅，不需移动其它元素。
List的结构示意图如下：环状链表的尾是一个空节点，符合“左闭右开”区间。
https://i-blog.csdnimg.cn/direct/e5cfa4ceaa58483cba1212fe2940e568.png
List得当的场景是那些需要频繁进行插入和删除操作的场所。
例如，如果你正在管理一个动态变化的列表，如使命调度、职员列队等场景，List的特性将大放异彩。但是如果你的应用场景更多地需要随机访问元素，那么Vector或者数组可能是更佳的选择。因为List的顺序访问性能相比之下会显得有些力有未逮。
[*]以是如果需要频繁随机的访问数据，那么选择vector容器
[*]如果需要频繁插入删除数据，那么选择list容器
[*]排序不要选择list ！！！可以先拷贝给vector排序后再拷贝回来
迭代器的介绍
迭代器可以按照功能、性质两大模块分类
https://i-blog.csdnimg.cn/direct/6dbb09d6d88a482bb2180c8df41b261e.png
迭代器的一些性质（重载的运算符）决定着算法库里对算法的调用
https://i-blog.csdnimg.cn/direct/8e4b8c44e03a42339ac1699e88adfc8c.png
而这些迭代器是子类与父类的继承关系
https://i-blog.csdnimg.cn/direct/69821698101341f9a14adbb70fda04db.png
2、list的使用
list 中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的本领。以下为list中一些常见的重要接口。
2.1 list 的构造
https://i-blog.csdnimg.cn/direct/9e78a76f3c78498b9cf5b89ee6c666c4.png
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 };
list<int> l7 = { 1,2,4,5,6,7,8 };
// 用迭代器方式打印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;
} 2.2 iterator 的使用
关于 list 的迭代器可以姑且理解为指针，本质是通过运算符重载模拟指针的行为
https://i-blog.csdnimg.cn/direct/547d3e99ff2745d3b28ccd7f427c4cfd.png
https://i-blog.csdnimg.cn/direct/8e727526815c4f95ae5a61a338031f0c.png
【TIP】
[*] begin 与 end 为正向迭代器，对迭代器实行++操作，迭代器向后移动
[*]rbegin(end) 与 rend(begin) 为反向迭代器，对迭代器实行++操作，迭代器向前移动
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, };
list<int> l(array, array + sizeof(array) / sizeof(array));
// 使用正向迭代器正向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 迭代器是双向 不支持 + -
/*l.insert(l.begin() + 3);*/
//想要实现第三个位置后插入一个数可以通过下面代码
it = l.begin();
int k = 3;
while (k--)
{
it++;//支持++
}
l.insert(it, 40);
PrintList(l);
} 2.3 list 的修改
https://i-blog.csdnimg.cn/direct/bb1830719dd54161a9880a6aa7675021.png
struct A {
public:
A(int a1 = 1, int a2 = 1)
:_a1(a1)
, _a2(a2)
{
cout << "A(int a1=1,int a2=1)" << endl;
}
A(const A& aa)
:_a1(aa._a1)
, _a2(aa._a2)
{
cout << "A(const A& aa)" << endl;
}
private:
int _a1;
int _a2;
};
void TestList3()
{
int array[] = { 1, 2, 3 };
list<int> L(array, array + sizeof(array) / sizeof(array));
// 在list的尾部插入4，头部插入0
L.push_back(4);
L.push_front(0);
PrintList(L);
// 删除list尾部节点和头部节点
L.pop_back();
L.pop_front();
PrintList(L);
list<A>lt;
A aa1(1, 1);
lt.push_back(aa1);//有名对象尾插
lt.push_back(A(2, 2));//匿名对象尾插
//lt.push_back(3, 3);//不支持 push back只支持一个参数
lt.emplace_back(aa1);
lt.emplace_back(A(2, 2));
cout << endl;
// 前面的插入都是 构造+拷贝构造
// (3,3)的插入 并没有拷贝构造 性能上来说优于 push back
lt.emplace_back(3, 3);//支持 本质支持直接传构造A对象的参数
} https://i-blog.csdnimg.cn/direct/fb277466152d4aeda162f76b0c5c9ac5.png
可以看到 emplace_back 可以支持直接传构造A的参数 省去了临时变量的拷贝构造
插入与删除
https://i-blog.csdnimg.cn/direct/f89473e9c45f46e595c7df38b17c83cf.png
// insert /erase
void TestList4()
{
int array1[] = { 1, 2, 3 };
list<int> L(array1, array1 + sizeof(array1) / sizeof(array1));
// 获取链表中第二个节点
auto pos = ++L.begin(); //pos 可以理解为下标
cout << *pos << endl;
// 在pos前插入值为4的元素
L.insert(pos, 4);
PrintList(L);
// 在pos前插入6个值为5的元素
L.insert(pos, 6, 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);
}
https://i-blog.csdnimg.cn/direct/707463e007e54ec2a95f2111cb2a3628.png
// resize/swap/clear
void TestList5()
{
// 用数组来构造list
int array1[] = { 1, 2, 3 };
list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1));
PrintList(l1);
// 交换l1和l2中的元素
list<int> l2;
l1.swap(l2);
PrintList(l1);
PrintList(l2);
// 将l2中的元素清空
l2.clear();
cout << l2.size() << endl;
}
https://i-blog.csdnimg.cn/direct/7956e77d08b943cc8d6291199588ccc2.png
2.4一些特殊接口
https://i-blog.csdnimg.cn/direct/0df30accae854d1b9dc477c18522eb56.png
reverse 逆置链表 sort 排序 （算法库里没有list的排序（迭代器不匹配））
https://i-blog.csdnimg.cn/direct/a4190277b973492b8d8a9dc82f5a7441.png
void test_list4()//容器的 逆置与排序
{
list<int>lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
print_list(lt);
lt.reverse();
print_list(lt);
reverse(lt.begin(), lt.end());
print_list(lt);
reverse(++lt.begin(), --lt.end());
print_list(lt);
//算法库里的排序和容器的排序都是默认升序
lt.sort();
print_list(lt);
//想要降序 则需要 仿函数
//less<int>ls;//升序
//greater<int>gt;//降序
//还可以结合匿名对象使用
lt.sort(greater<int>());
print_list(lt);
} https://i-blog.csdnimg.cn/direct/12c0a4093db242f699efd071954fd98c.png
merge 归并 与 unique 去重（条件均有序链表）
void test_list5() // merge有序list合并unique 有序list去除重复数据
{
std::list<double> first, second;
first.push_back(3.1);
first.push_back(2.2);
first.push_back(2.9);
second.push_back(3.7);
second.push_back(7.1);
second.push_back(1.4);
first.sort();
second.sort();
//将 second和first合并 second置为空 前提两list有序
first.merge(second);
print_list(first);
print_list(second);
list<int>lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(2);
lt.push_back(3);
lt.push_back(3);
lt.push_back(4);
lt.push_back(1);
lt.push_back(1);
print_list(lt);
lt.sort();
//有序的数据去掉重复的数据
lt.unique();
print_list(lt);
}
https://i-blog.csdnimg.cn/direct/03228499a6db412099b47d036d12927b.png
剪切拼接 splice 的妙用
void test_list6()
{
//把一个链表结点转移给另一个链表
std::list<int> mylist1, mylist2;
std::list<int>::iterator it;
// set some initial values:
for (int i = 1; i <= 4; ++i)
mylist1.push_back(i); // mylist1: 1 2 3 4
for (int i = 1; i <= 3; ++i)
mylist2.push_back(i * 10); // mylist2: 10 20 30
it = mylist1.begin();
++it; // points to 2
mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
// mylist2 (empty)
// "it" still points to 2 (the 5th element)
print_list(mylist1);
print_list(mylist2);// splice 剪切功能
//splice 还可以调整当前list的顺序
list<int>lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
print_list(lt);
int x = 0;
cin >> x;
it = find(lt.begin(), lt.end(), x);
if (it != lt.end())
{
// 调整当前链表的元素顺序将 it指向元素 调整到 begin
lt.splice(lt.begin(), lt, it);
// //迭代器区间
//lt.splice(lt.begin(), lt, it,lt.end());
}
print_list(lt);
} https://i-blog.csdnimg.cn/direct/c46c9bf0dc1a4588876ebb402941e53e.png
https://i-blog.csdnimg.cn/direct/c2f938ef921b476fab7184a15c4e2a19.png
2.5 迭代器失效题目
前面说过，此处可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。
因为list的底层结构为带头结点的双向循环链表，因此在 list 中进行插入时是不会导致 list 的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
这在 vector 是不创建的，因为 vector 的插入操作有元素移动可能导致重新设置空间，导致原有的迭代器全部失效。
void TestListIterator1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array));
auto it = l.begin();
while (it != l.end())
{
// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
l.erase(it);
++it;
}
} VS2022 对于迭代器失效有着严格的监控机制直接报错https://i-blog.csdnimg.cn/direct/94a8e4e3322e41c0b9ca3a4d7ac63c5a.png
// 改正
void TestListIterator()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array + sizeof(array) / sizeof(array));
auto it = l.begin();
while (it != l.end())
{
l.erase(it++); //it = l.erase(it); erase 返回下一个位置的迭代器
}
} 这里的 erase 会返回下一个结点的位置https://i-blog.csdnimg.cn/direct/b9a872f10b354a5da8a7fca793355398.png
https://i-blog.csdnimg.cn/direct/bb59e32ca42d497ba7c9f6bbde9592c6.png
https://i-blog.csdnimg.cn/direct/96803d1b2c0c4ca5aa51e572055f4f6d.png
对于 erase(it++); 可以理解为 先it++了再实行erase 代码块里的内容
3、实现list
list 容器的底层是一个带头双向循环链表
[*] 双向链表的意思是：每个节点不仅存储着数据，还包罗两个指针，分别指向前一个节点和后一个节点。这使得 list 可以在常数时间内进行双向遍历和插入、删除操作。
[*] 库里的节点结构大致如下：
[*] https://i-blog.csdnimg.cn/direct/3bbd2c7680064d10a9b90766ae381d88.png
[*] 头节点和尾节点会分别指向 nullptr ，这表明链表的边界。
这种双向链表的结构给予了 list 灵动的特性：它可以或许轻松地在恣意位置增长或移除元素，而这种操作险些是与容器大小无关的，体现了时间复杂度上的优势。但这种优势的代价是，与数组相比，List在访问元素时的速度会较慢，因为它需要从头开始遍历。这也决定了list的更得当频繁插入的动态数据。
3.1底层结构
根据对链表的理解，我们需要封装一个结点类，为了兼容迭代器的使用，我们需要对结点指针封装一下即迭代器，最后就是实现功能函数的list 类了，我们可以加入一个头结点方便插入删除和兼容容器的左闭右开。
结点类
// 结点结构体
template<class T>
struct list_node //默认公有 struct
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
list_node(const T& data=T())
:_data(data)
,_prev(nullptr)
,_next(nullptr)
{}
~list_node()
{
_next = nullptr;
_prev = nullptr;
}
}; 结点类的结构还是很简单的 结构体里包罗着数据和前后指针即可，因为要多次访问结点以是设置为 struct 较符合
list类
构造函数需要创建一个头结点，因为我们要创建双向循环链表，以是头尾都要指向头结点本身。 _size统计元素个数。
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
void empty_init()
{
//_head = new Node;//这里写了 Node 带参数构造 所以报错 需要匿名参数
_head = new Node(T());
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
list(initializer_list<T>il)
{
empty_init();
for (auto& e : il)
{
push_back(e);
}
_size = il.size();
}
private:
Node* _head;
size_t _size;
}; 这里的 list(initializer_list<T>il) 是C++11出现的语法，就可以像数组一样进行初始化了
迭代器类
list的迭代器显然不是指针！！ 链表的物理地址并不是连续存储的，指针的++ -- 操作是没有意义的，以是我们需要实现一个用结点指针封装的迭代器类，通过运算符重载去模拟指针的行为
https://i-blog.csdnimg.cn/direct/cdd11c52435a41baa6bd03e84929af71.png
可以看到库里所实现的迭代器类与我们所预想的一致！
如何实现++ 到下一个结点呢？？https://i-blog.csdnimg.cn/direct/dcca874b2535496ea2d10a6fe6c387d2.png
通过 重载 ++运算符 获取地址返回下一个结点即可
迭代器实现：
由于STL list是一个双向链表，迭代器必须具备迁移，后移的本领，以是 list 提供的是 Birdirectional Iterator（双向）
List 的迭代器
迭代器有两种实现方式，具体应根据容器底层数据结构实现：
1. 原生态指针，比如：vector
2. 将原生态指针进行封装，因迭代器使用形式与指针完全雷同，因此在自定义的类中必须实现以下方法：
（1）指针可以解引用，迭代器的类中必须重载 operator*()
（2）指针可以通过->访问其所指空间成员，迭代器类中必须重载 oprator->()
（3）指针可以++向后移动，迭代器类中必须重载 operator++() 与 operator++(int)
至于 operator--() / operator--(int) 是否需要重载，根据具体的结构来抉择，双向链表可以向前移动，以是需要重载，如果是forward_list（单向）就不需要重载--
（4）迭代器需要进行是否相称的比较，因此还需要重载 operator==() 与 operator!=()
template<class T>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T> Self;
Node* _node;//指针成员变量
list_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &(_node->_data);
}
//操作符重载 前置++ 与 后置++的区别是参数是否带（int）
// ++it
Self& operator++()
{
_node = _node->_next;
return *this;
}
// it++
Self& operator++(int x)
{
Self tmp(*this);//浅拷贝
_node = _node->_next;
return tmp;
}
//--it
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//it--
Self& operator--(int x)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& s)const { return _node != s._node; }
bool operator==(const Self& s)const { return _node == s._node; }
}; 有须要注意的是 重载 -> 是为了适配T为自定义类型的环境
list<AA>lta;
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
auto ita = lta.begin();
while (ita != lta.end())
{
//cout << *ita << ' '; //编译不通过 结构体并没有重载流插入
//cout << (*ita)._a1 << ' ';
//cout << ita->_a1 << ' '; //为了可读性省去了一个箭头
cout << ita.operator->()->_a1 << ' ';
++ita;
} https://i-blog.csdnimg.cn/direct/19bec4d05200464986ee21451874cdeb.png
调用了 operator ->后 AA* 结构体指针再用->调用了_a1
如许迭代器大致实现了应该有的功能，我们还需要实现一个const 迭代器，如何封装const 迭代器呢？不能修改内容，只需要重载的 * 和 -> 返回类型加上const 修饰即可https://i-blog.csdnimg.cn/direct/01967bab04284455a7f201b79cd40e2a.png
但是注意到其他重载的运算符都是一样的，如果重新定义一个const 迭代器是否过于冗余呢？
观察一下STL库里是如何实现的
https://i-blog.csdnimg.cn/direct/913315ac3bd846ecaefa441ee9cf0078.png
显然并不是冗余的复制一份迭代器，而是同一个类模板实现的，实例化两个差别的类，本质上与冗余的写法是一个道理
https://i-blog.csdnimg.cn/direct/e6e17738ec9e49978be225ee50d1f0e7.png
那么我们开始优化一下迭代器
将类模板修改一下
//reference 引用pointer 指针
template<class T , class Ref ,class Ptr> 有差异的返回值也改变一下
Ref operator*() //现在返回const类型还是普通类型是通过编译器推导的
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
} 那么类实例化的时候传入对应参数编译器就会推导出对应的类：
typedef list_iterator<T,T&,T*> iterator;
typedef list_iterator<T,const T&,const T*> const_iterator; 测试一下
https://i-blog.csdnimg.cn/direct/c1f187a7dc7a4558aaa2b99cde14813e.png
那么就实现乐成迭代器类模板
3.2功能接口
迭代器接口
iterator begin()//第一个结点指针
{
//iterator it(_head->_next);//构造函数
//return it; 优化一下
return _head->_next; //走的隐式类型转换
}
// const 修饰begin 可以兼容拷贝构造 否则出现权限放大 这是不允许的
const_iterator begin()const //前面的const 迭代器是指向元素或引用不可以改变内容 后面的const是修饰this 对象不可以改变
{ //隐含的this指针由 list * const this 变为 const list* const this 前者是指针不可以更改指向
return _head->_next;
}
const_iterator cbegin()const
{
return _head->_next;
}
iterator end()
{
return _head; // 头节点 左闭右开
}
const_iterator end()const
{
return _head;
}
const_iterator cend()const
{
return _head;
} const 修饰begin 是为了防止权限放大的错误出现
https://i-blog.csdnimg.cn/direct/62322bc344a94257944b15e66f597409.png
因为拷贝构造中参数是 const 对象
插入删除
由于双向循环，插入删除相对比较简单，就是注意链接的顺序性即可
void push_back(const T& x)
{
//Node* newnode = new Node(x); //没有写Node 构造报错
//_head->_prev->_next = newnode;
//newnode->_next = _head;
//newnode->_prev = _head->_prev;
//_head->_prev = newnode;
//++_size;
insert(end(), x);//复用 insert
}
void push_front(const T& x)
{
insert(begin(), x);
}
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
// prev newnode cur
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
++_size;
return newnode;
} 实现了 insert 我们可以根据迭代器复用 insert 实现尾插和头插
TIp：新节点将位于插入点的前一个位置这是STL对于“插入操作”的标准规范。
删除操作，与 insert 一样使用指针操作，来达到删除的效果。注意要对删除的节点进行释放空间操作（delete），不然会发生内存泄漏！！！
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
iterator erase(iterator pos) //防止迭代器失效问题
{
assert(pos != end());//不可以删除头结点
Node* prev = pos._node->_prev;;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
--_size;
return next;
}
需要注意的是，恣意位置删除因为使用了迭代器，删除后会造成迭代器失效，以是需要更新迭代器，返回被删除节点的下一个节点的迭代器即可。
拷贝赋值析构函数
//lt1(lt)
list( const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
//lt1=lt3
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
auto it = begin();
while (it!=end())
{
//erase(it++);//可以这样写 可以理解为 先进行了 it++后再 执行 erase 代码块里的内容
it=erase(it);
}
_size = 0;
} 拷贝构造我们只需要范围 for 遍历依次尾插即可，这里空初始化是为了创捷头结点，赋值重载只需要互换头节点就可以
4、list与vector 区别对比
vector 与 list 都是STL中非常重要的序列式容器，由于两个容器的底层结构差别，导致其特性以及应用场景差别，其主要差别如下：
https://i-blog.csdnimg.cn/direct/5db4bdf09b134804bea74e9ab2f20940.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]