lost(c++)

一、list 概述

  • 来自头文件：#include <list>
  • 类型：双向链表容器
  • 特点：
    • 插入/删除操作高效（尤其是中间插入/删除）
    • 不支持随机访问（不能使用 []）
    • 支持迭代器（双向迭代器）
    • 可存储任意类型元素（包括自定义类型）

二、创建与初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <list>
using namespace std;

// 空 list
list<int> a;

// 指定大小（值为默认0）
list<int> b(5);

// 指定大小与初始值
list<int> c(3, 10); // [10, 10, 10]

// 初始化列表
list<int> d = {1, 2, 3, 4};

// 拷贝构造
list<int> e(d);

三、常用成员函数与方法分类总览

1️⃣ 访问元素

函数说明
front()获取第一个元素
back()获取最后一个元素
1
2
3
list<int> l = {1, 2, 3};
cout << l.front();  // 1
cout << l.back();   // 3

2️⃣ 插入与删除

函数说明
push_back(val)在末尾添加元素
push_front(val)在头部添加元素
pop_back()删除最后一个元素
pop_front()删除第一个元素
insert(pos, val)在指定位置插入元素
erase(pos)删除指定位置元素
remove(val)删除所有等于 val 的元素
clear()清空 list 中所有元素
1
2
3
4
5
6
7
8
9
10
11
12
list<int> l = {1, 2, 3};
l.push_back(4);       // 1 2 3 4
l.push_front(0);      // 0 1 2 3 4
l.pop_back();         // 0 1 2 3
l.pop_front();        // 1 2 3

auto it = l.begin();
advance(it, 1);       // 指向 2
l.insert(it, 10);     // 插入 10 到 2 前面 -> 1 10 2 3

l.erase(it);          // 删除 2
l.remove(10);         // 删除所有 10

3️⃣ 遍历 list

1
2
3
4
5
6
7
8
9
10
11
list<int> l = {10, 20, 30};

// 1. 普通迭代器
for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
    cout << *it << " ";
}

// 2. C++11 范围 for 循环
for (int x : l) {
    cout << x << " ";
}

4️⃣ 排序、去重与逆序

函数说明
sort()排序（默认升序）
reverse()倒序
unique()删除连续重复元素
1
2
3
4
list<int> l = {3, 2, 1, 2, 2, 3};
l.sort();         // 1 2 2 2 3 3
l.unique();       // 1 2 3
l.reverse();      // 3 2 1

5️⃣ 大小与容量

函数说明
size()返回元素数量
empty()判断是否为空
clear()清空 list
1
2
3
cout << l.size();   // 返回大小
cout << l.empty();  // 是否为空
l.clear();          // 清空

6️⃣ 合并与交换

函数说明
merge(lst)合并另一个已排序 list
swap(lst)与另一个 list 交换内容
1
2
3
4
5
6
7
list<int> l1 = {1, 3, 5};
list<int> l2 = {2, 4, 6};
l1.sort();
l2.sort();
l1.merge(l2);       // l2 变为空

l1.swap(l2);        // 交换内容

7️⃣ 自定义排序（struct）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Student {
    string name;
    int score;
};

bool cmp(const Student& a, const Student& b) {
    return a.score > b.score;
}

list<Student> students = {
    {"Tom", 90}, {"Lucy", 95}, {"Jim", 88}
};

// 自定义排序：C++11 后写法
students.sort([](const Student& a, const Student& b) {
    return a.score > b.score;
});

8️⃣ assign() 赋值操作

1
2
3
4
list<int> l;
l.assign(5, 100);     // 五个100
list<int> l2 = {1,2,3};
l.assign(l2.begin(), l2.end());  // 拷贝l2

9️⃣ emplace / emplace_back（C++11）

  • 比 push_* 更高效，直接构造元素
1
2
3
list<string> l;
l.emplace_back("hello");
l.emplace_front("world");

四、完整示例：功能演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

int main() {
    list<int> l = {3, 1, 4, 1, 5, 9, 2};

    l.push_back(6);
    l.push_front(0);

    cout << "原始 list: ";
    for (int x : l) cout << x << " ";
    cout << endl;

    l.sort();       // 排序
    l.unique();     // 去重
    l.reverse();    // 逆序

    cout << "处理后 list: ";
    for (auto it = l.begin(); it != l.end(); ++it)
        cout << *it << " ";
    cout << endl;

    l.remove(4);    // 删除指定值
    cout << "删除4后: ";
    for (int x : l) cout << x << " ";
    cout << endl;

    return 0;
}

五、与 vector 的区别

特性listvector
底层结构双向链表动态数组
访问方式只能通过迭代器支持随机访问 ([])
插入/删除效率中间插入/删除高效末尾插入/删除高效
内存使用相对高相对低
使用场景频繁插入删除频繁读写、索引访问