C++ STL list 容器常用接口与拓展用法详解
C++ STL list 容器基于双向链表实现,元素非连续存储。本文介绍其核心特性(动态分配、O(1) 插入删除)、常用接口(构造、容量、迭代器、遍历、增删改查)及拓展接口(emplace_back、merge、unique、splice、sort)。通过示例代码演示了 list 在内存管理、排序及合并操作中的具体应用,帮助开发者高效使用标准库容器。

C++ STL list 容器基于双向链表实现,元素非连续存储。本文介绍其核心特性(动态分配、O(1) 插入删除)、常用接口(构造、容量、迭代器、遍历、增删改查)及拓展接口(emplace_back、merge、unique、splice、sort)。通过示例代码演示了 list 在内存管理、排序及合并操作中的具体应用,帮助开发者高效使用标准库容器。

在 C++ 标准库中,std::list 是一个双向链表容器。定义在头文件 <list> 中,它的元素在内存中不是连续存储的,而是通过节点之间的指针相互链接,这使得它在插入和删除操作上有独特的优势。
std::list 是一个双向链表容器,即其底层结构为双向链表(带头双向循环链表),需要注意,双向链表的头节点(哨兵位)只用来占位,而不存储有效数据。所以,双向链表的头插即是在 d1 节点之前插入节点;头删即删除 d1 节点;尾插即在 d3 节点之后插入节点;尾删即删除 d3 节点。
核心特性
实现 list 对象在定义的同时初始化。
| 构造函数(construct) | 功能 |
|---|---|
list() | 默认构造,构造空链表(即哨兵位) |
list(const list<value_type>& lt) | 拷贝构造,用已经存在的对象 lt 初始化 |
list(size_t n, const value_type& val=value_type()) | 填充构造函数,用 n 个 value_type 类型的值去初始化 |
list(InputIterator first,InputIterator last) | 迭代器区间构造,使用迭代器范围 [first, last) 内的元素来初始化 list 对象 |
list(std::initializer_list<value_type> ilist) | 初始化列表构造函数(C++11 引入) |
void test1() {
list<int> lt1; // 构造空链表
list<int> lt2(5, 1); // 使用 5 个 1 初始化 lt2
list<int> lt3(lt2); // 构造 lt3 对象,并用 lt2 初始化
list<int> lt4(lt2.begin(), lt2.end()); // 使用 lt2 的迭代器区间初始化 lt4
list<int> lt5({ 1,2,3,4,5 }); // 使用初始化列表初始化 lt5
}
| 函数 | 功能 |
|---|---|
size() | 获取双向链表的有效节点个数 |
empty() | 判断链表是否为空 |
void test2() {
list<int> lt({ 1,2,3,4,5 });
cout << lt.size() << endl;
if (lt.empty()) cout << "为空" << endl;
else cout << "非空" << endl;
}
此处,大家可暂时将迭代器理解成一个指针,该指针指向 list 中的某个节点。
| 函数 | 功能 |
|---|---|
lt.begin() | begin 获取头节点下一个节点的迭代器(地址) |
lt.end() | end 获取头节点的迭代器(地址) |
lt.rbegin() | rbegin() 返回的是反向迭代器,指向链表的头节点 |
lt.rend() | rend 获取头节点下一个节点的迭代器(地址) |
| 函数 | 功能 |
|---|---|
front | 获取第一个节点的值 |
back | 获取最后一个节点的值 |
push_front(const value_type x) | 在头部插入值为 x 的新节点 |
pop_front | 删除头部节点 |
push_back(const value_type x) | 在尾部插入一个值为 x 的新节点 |
pop_back | 删除尾部节点 |
insert(iterator pos, const value_type x) | 在 pos 指向的节点之前插入一个值为 x 的新节点 |
erase(iterator pos) | 删除 pos 指向的节点 |
swap | 交换两个对象的值 |
clear | 清理链表中的有效节点 |
由于 list 底层结构为双向链表,导致他的元素在内存中并不是连续存储的,所以我们不能用下标的方式来访问。
方法一:范围 for + auto
void test3() {
list<int> lt({ 1,2,3,4,5 });
for (auto e : lt) {
cout << e << " ";
}
}
方法二:迭代器
void test4() {
list<int> lt({ 1,2,3,4,5 });
list<int>::iterator it = lt.begin();
while (it != lt.end()) {
cout << *it << " ";
it++;
}
}
前面我们已经介绍了一个尾插的接口(push_back),那为什么 list 容器还要实现一个 emplace_back 尾插接口呢?
假设我们额外定义一个 AA 类,然后,将 AA 类型的数据分别使用 push_back 和 emplace_back 尾插到 lt 对象,看会发生什么?
struct AA {
AA(int a1 = 1, int a2 = 1) :_a1(a1) ,_a2(a2) {}
int _a1;
int _a2;
};
void test5() {
AA a1;
list<AA> lt;
lt.push_back(a1);
lt.push_back(AA(20, 20));
lt.push_back(30, 30); // 报错
}
这里有一种应用 emplace_back 特殊情景,此时只有 emplace_back 才能够实现。当我们想要直接将构造 a 对象的数据作为参数传给尾插函数时,push_back 就会报错,而 emplace_back 则支持这种操作。
// emplace_back
void test6() {
list<AA> lt;
lt.emplace_back(30, 30);
}
需要注意:merge 只能用来合并两个已经排好序的链表,同时,合并之后一个链表将会为空。
void test7() {
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 链表
first.merge(second);// (second is now empty)
for (auto e : first) cout << e << " ";
}
注意:只能连续的重复元素去掉,并只保留一个。
void test8() {
list<int> lt;
lt.push_back(1);
lt.push_back(5);
lt.push_back(5);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
for (auto e : lt) cout << e << " ";
cout << endl;
lt.unique(); // 去重
for (auto e : lt) cout << e << " ";
}
注意:移动之后一个链表将会为空。
void test9() {
std::list<int> mylist1, mylist2;
std::list<int>::iterator it;
for (int i = 1; i <= 4; ++i) mylist1.push_back(i);
for (int i = 1; i <= 3; ++i) mylist2.push_back(i * 10);
it = mylist1.begin();
++it;
mylist1.splice(it, mylist2); // 链表 mylist2 节点转移给链表 mylist1 的第二个节点之前
for (auto e : mylist1) {
cout << e << " ";
}
}
我们知道 C++ 在标准库中已经实现了排序算法,为什么 list 还要再自己实现呢?这就是因为迭代器的性质造成的。下面我们来介绍一下迭代器的类型。
根据前面对 string 和 vector 的学习,我们知道,根据迭代器的功能,将迭代器分为:
根据迭代器性质将迭代器分为:
#include<algorithm> // sort 的头文件
void test01() {
list<int> lt;
lt.push_back(6);
lt.push_back(3);
lt.push_back(5);
lt.push_back(2);
lt.push_back(1);
// sort :仅支持随机迭代器
//sort(lt.begin(), lt.end()); // list 类对象的迭代器为双向迭代器,所以报错
string st("ahdncxvjsvf");
sort(st.begin(), st.end()); // string 类对象的迭代器为随机迭代器
cout << st << endl;
// reverse : 支持双向迭代器(也兼容随机迭代器)
reverse(lt.begin(), lt.end());
reverse(st.begin(), st.end());
}
void test02() {
list<int> lt;
lt.push_back({6, 3, 5, 2, 1});
// list 容器中的 sort
lt.sort();
for (auto e : lt) cout << e << " ";
}
list 容器提供了丰富而且非常实用的接口,只要我们不断查文档,并不断应用,就一定能够掌握这些接口的用法。

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online