个人主页: 起名字真南的CSDN博客
个人专栏:
- 【数据结构初阶】 📘 基础数据结构
- 【C语言】 💻 C语言编程技巧
- 【C++】 🚀 进阶C++
- 【OJ题解】 📝 题解精讲
目录
📌 1 引言
在C++的表中模板库(STL)中，list容器提供了一个
双向链表的实现，他能高效的在任意位置进行插入和删除元素，非常适合需要频繁修改数据的场景。与vector不同，list是一个双向链表结构，并不支持快速随机访问。本文将详细介绍list容器的特点，使用场景，以及其主要成员函数的用法。
📌2 list容器
✨2.1 list容器简介
list 容器简介list 是一个双向链表数据结构，具有以下特点：
- 高效插入和删除：在已知位置插入或删除元素的时间复杂度为 O(1)，远高于
vector的 O(n)。 - 不支持随机访问：与数组不同，
list不支持通过下标访问，因此需要通过迭代器进行遍历。 - 双向链表：支持从头部和尾部同时遍历，方便实现一些特定算法。
✨2.2 list容器结构
std::list 使用双向链表实现，每一个节点都包含了两个指针和一个数据字段
- 数据字段 ：用于储存数据
- 前驱指针 ：指向当前节点的前一个节点
- 后继指针：指向当前接的后一个指针
在这种结构下，list容器还有一个头节点，它的前一个指针对应着尾节点，后一个指针对应着头节点。
- 头指针 ：指向链表中的第一个节点
- 尾指针 ：指向链表的最后一个节点
📌3 list中主要成员函数
✨ 3.1 构造函数初始化list
| 构造函数 | 接口说明 |
|---|---|
list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
list() | 构造空的list |
list (const list& x) | 拷贝构造函数 |
list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
#include<iostream>
#include<list>
using namespace std;
int main()
{
list<int> l1;
list<int> l2(6, 6);
list<int> l3(l2);
int arr[] = { 1,2,3,4,5, };
list<int> l4(arr, arr + sizeof(arr) / sizeof(arr[0]));
return 0;
}
调试结果：
✨ 3.2 迭代器遍历list容器
| 函数声明 | 接口说明 |
|---|---|
begin + end | 返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器 |
rbegin + rend | 返回第一个元素的 reverse_iterator，即 end 位置，返回最后一个元素下一个位置的 reverse_iterator，即 begin 位置 |
list<int>l1(8, 8);
//使用l1的迭代器构造l2
list<int>l2(l1.begin(), l1.end());
//列表格式初始化C++11
list<int>l3{ 1,2,3,4,5,6,7,8,9 };
//使用迭代器的方式来遍历打印数组
int main()
{
list<int>::iterator it = l1.begin();
while (it != l1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto au : l3)
{
cout << au << " ";
}
cout << endl;
auto l = l3.rbegin();
while (l != l3.rend())
{
cout << *l << " ";
l++;
}
cout << endl;
return 0;
}
输出结果：
注意 ：
- 不管是使用正向迭代器还是反向迭代器，我们遍历的方法一直都是++控制。
✨ 3.3 对list的空间进行操作
| 函数声明 | 接口说明 |
|---|---|
| empty | 检测 list 是否为空，是返回 true，否则返回 false |
| size | 返回 list 中有效节点的个数 |
void test3()
{
list<int> l1;
list<int> l2(8,8);
if (l1.empty())
{
cout << "l1 为空" << endl;
}
else
{
cout << "l1 不为空" << endl;
}
if (!(l2.empty()))
{
cout << "l2 不为空" << endl;
cout << "l2.size() : " << l2.size() << endl;
}
}
输出结果：
注意 ：
- 在这串代码中
empty()的函数返回值是bool，如果为空则返回true，不为空返回false。
✨ 3.4 对list的元素进行访问
| 函数声明 | 接口说明 |
|---|---|
| front | 返回 list 的第一个节点中值的引用 |
| back | 返回 list 的最后一个节点中值的引用 |
void test4()
{
list<int> l1{ 1,2,3,4,5,6,7,8,9,10 };
cout << "l1.front(): " << l1.front() << endl;
cout << "l1.back(): " << l1.back() << endl;
}
输出结果：
注意 ：
- 在list中不能随机访问链表中的元素，只能通过front和back来获取头结点的数据和尾节点的数据
✨ 3.5 对list的元素进行修改
| 函数声明 | 接口说明 |
|---|---|
| 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 中的有效元素 |
🚀3.5.1 push and pop
在容器的开始位置插入元素
来list容器的开始位置插入一个新的元素，在它当前的第一个元素之前将val的值移到第一个元素中。
增加一个容量。
在容器的末尾位置插入元素
来list容器的开始位置插入一个新的元素，在它当前的第一个元素之前将val的值移到第一个元素中。
增加一个容量。
void test5()
{
list<int> l1{ 1,2,3,4,5,6,7,8,9 };
l1.push_front(0);
l1.push_back(10);
for (auto it : l1)
{
cout << it << " ";
}
cout << endl;
}
输出结果：
将list中第一个元素删除，减少一个容量。
将list中末尾元素删除，减少一个容量。
void test5()
{
list<int> l1{ 1,2,3,4,5,6,7,8,9 };
l1.push_front(0);
l1.push_back(10);
for (auto it : l1)
{
cout << it << " ";
}
cout << endl;
l1.pop_back();
l1.pop_front();
for (auto it : l1)
{
cout << it << " ";
}
cout << endl;
}
输出结果：
🚀3.5.2 insert and erase
insert 在pos位置的数据前面插入一个数据
从图中我们可以看到传的参数可以是迭代器位置，也可以是一个迭代器区间
void test6()
{
list<int> l1{0,1,2,3,5,6,7,8,9 };
for (auto it : l1)
{
cout << it << " ";
}
cout << endl;
l1.insert(l1.begin(), 18);
for (auto it : l1)
{
cout << it << " ";
}
cout << endl;
}
输出结果：
erase 将pos位置的数据删除
从图中可以看到参数可以是一个迭代器区间也可以是一个位置
void test6()
{
list<int> l1{0,1,2,3,5,6,7,8,9 };
for (auto it : l1)
{
cout << it << " ";
}
cout << endl;
l1.erase(--l1.end());
for (auto it : l1)
{
cout << it << " ";
}
cout << endl;
}
输出结果：
注意 ：
- 在我们erase的时候需要注意关于迭代器失效的问题，在我们调用erase是必须保证他指向了一个有效的位置，如果代码中使用
l1.erase(l1.end())在我们删除最后一个元素的时候他指向了最后一个数据的尾巴所以会造成迭代器失效
🚀 3.5.3 swap and clear
交换两个相同类型容器的元素
for (auto it : l1)
{
cout << it << " ";
}
cout << endl;
list<int> l2(6, 6);
for (auto it : l2)
{
cout << it << " ";
}
cout << endl;
swap(l1, l2);
for (auto it : l1)
{
cout << it << " ";
}
cout << endl;
for (auto it : l2)
{
cout << it << " ";
}
输出结果：
清空list中所有有效元素
l1.clear();
l2.clear();
调试结果：
4 📌 参考文件
传送门： C++Reference
