C++STL系列-04. list和forward_list
核心区别
| 特性 | list | forward_list |
|---|---|---|
| 实现方式 | 双向链表 | 单向链表 |
| 内存开销 | 每个节点有两个指针（前向和后向） | 每个节点只有一个指针（前向） |
| 迭代器类型 | 双向迭代器 | 前向迭代器 |
| 大小查询 | 有 size() 方法 | 无 size() 方法（需要遍历计算） |
| 反向遍历 | 支持（有 rbegin(), rend()） | 不支持 |
| 性能 | 插入删除操作常数时间，但内存开销大 | 内存效率更高，但功能受限 |
list
#include<iostream>
#include<list>
using namespace std;
void printList(list<int> l) {
for (int i : l) {
cout << i << " ";
}
cout << endl;
}
int main() {
list<int>alvin(5,3); //包含5个值为3的元素
list<int>alvin1 = {1,2,3,4,5}; //初始化列表
alvin1.assign(3,6); //分配 3 个 值为 6 的元素， 前面的1，2，3，4，5会消失
alvin1.push_front(1); //头部添加元素
alvin1.push_back(7); //尾部添加元素
auto it = alvin1.begin();
alvin1.insert(it,5); //指定位置插入元素
alvin1.pop_front(); //删除首元素
alvin1.pop_back(); //删除尾元素
alvin1.erase(it); //删除指定位置元素
alvin1 = {1,2,3,4,5,5,5,6,7,8,9}; //重新填充
alvin1.remove(5); //删除所有等于值的元素. 打印结果 1,2,3,6,7,8,9
alvin1.remove_if([](int n) { return n % 2 == 0; }); // 删除满足条件的值，比如所有偶数，打印结果 1，3，7，9
alvin1 = {7,7,8,8,9,2,1,9,3,5,4,5,6,6};
alvin1.unique(); //删除连续重复的数 打印结果 7 8 9 2 1 9 3 5 4 5 6
alvin1.sort(); //排序 1,2,3,4,5,5,6,7,8,9,9
alvin1.merge(alvin); //合并并且排序
alvin1.reverse(); //反转
alvin = {55,99,88};
alvin1.swap(alvin); //交换
printList(alvin1);
return 0;
}
forward_list 常用函数
push_front() - 在首部添加元素
pop_front() - 删除首部元素
insert_after() - 在指定位置后插入元素
erase_after() - 删除指定位置后的元素
before_begin() - 返回第一个元素之前的位置
sort() - 排序
merge() - 合并两个有序链表
splice_after() - 移动元素从一个链表到另一个
reverse() - 反转链表
双链表代码原理单链表代码原理