构算法度·list容器 – 将去未还的随笔

一、list容器的背景与优势

1.引入

前面的vector容器以及deque容器都提供了高效的随机访问，但是你是否遇见过一下情景：

// 在中间频繁插入删除的场景
vector<int> vec = {1, 2, 3, 4, 5};
// 在位置2插入元素99 - 需要移动后面所有元素
vec.insert(vec.begin() + 2, 99); // 效率O(n)

一次插入时间复杂度是O(n)，一旦要求我们插入操作m次，那么此时时间复杂度就会来到O(m*n)，这显然不是我们所希望的效果。

这时候list容器就派上用场了，模板类list是一个容器，list是由双向链表来实现的，每个节点存储1个元素。list支持前后两种移动方向，并且在任意位置插入删除都是O(1)时间复杂度，如果我们使用list容器那么m次插入时间复杂度就会被优化为O(m)，显著缩短了时间量级。

2.优势对比

list容器与vector容器和deque容器的对比如下表所示：

特性	vector	deque	list
底层结构	动态数组	分块数组	双向链表
随机访问	O(1)	O(1)	O(n)
头部插入	O(n)	O(1)	O(1)
中间插入	O(n)	O(n)	O(1)
内存布局	连续	分块连续	非连续
迭代器类型	随机访问	随机访问	双向

二、list容器的使用操作

1.list创建与初始化

// 多种初始化方式
std::list<int> lst1;                    // 空列表
std::list<int> lst2(5, 100);            // 5个元素，每个都是100
std::list<int> lst3 = {1, 2, 3, 4, 5};  // 初始化列表
std::list<int> lst4(lst3.begin(), lst3.end());  // 范围构造
std::list<int> lst5(lst3);              // 拷贝构造
// C++11起支持移动构造
std::list<int> lst6(std::move(lst5));

2.元素访问

std::list<int> lst = {10, 20, 30, 40, 50};

// 错误：不支持operator[]和at()
// lst[2] = 100;  // 编译错误！
// lst.at(2) = 100; // 编译错误！

// 正确的访问方式：
std::cout << "第一个元素: " << lst.front() << std::endl;  // 10
std::cout << "最后一个元素: " << lst.back() << std::endl;  // 50

// 只能通过迭代器顺序访问
std::list<int>::iterator it = lst.begin();
std::advance(it, 2);  // 移动迭代器到第三个元素
std::cout << "第三个元素: " << *it << std::endl;  // 30

3.插入删除操作

std::list<int> lst = {1, 2, 3, 4};

// 两端操作
lst.push_front(0);    // 头部插入: {0, 1, 2, 3, 4}
lst.push_back(5);     // 尾部插入: {0, 1, 2, 3, 4, 5}
lst.pop_front();      // 头部删除: {1, 2, 3, 4, 5}
lst.pop_back();       // 尾部删除: {1, 2, 3, 4}

// 任意位置插入
auto it = lst.begin();
std::advance(it, 2);      // 指向第3个元素
lst.insert(it, 99);       // 在位置2插入99: {1, 2, 99, 3, 4}

// 范围插入
std::vector<int> vec = {100, 101};
lst.insert(it, vec.begin(), vec.end());  // 在迭代器位置插入范围

// 删除指定值
lst.remove(3);           // 删除所有值为3的元素

// 条件删除
lst.remove_if([](int n) { 
    return n % 2 == 0;   // 删除所有偶数
});

// 删除迭代器指向的元素
it = lst.begin();
std::advance(it, 1);
lst.erase(it);           // 删除第二个元素

// 范围删除
auto first = lst.begin();
auto last = lst.begin();
std::advance(last, 2);
lst.erase(first, last);  // 删除前两个元素

4.splice() – 链表拼接

// 场景1：整个链表拼接
std::list<int> list1 = {1, 2, 3};
std::list<int> list2 = {4, 5, 6};

list1.splice(list1.end(), list2);  // list1: {1, 2, 3, 4, 5, 6}
// list2现在为空！元素被移动，而非拷贝

// 场景2：单个元素拼接
std::list<int> list3 = {1, 2, 3, 4, 5};
std::list<int> list4 = {10, 20, 30};

auto it = list4.begin();
std::advance(it, 1);  // 指向20

// 将list4中的20移动到list3的末尾
list3.splice(list3.end(), list4, it);  
// list3: {1, 2, 3, 4, 5, 20}, list4: {10, 30}

// 场景3：范围拼接
std::list<int> list5 = {1, 2, 3, 4, 5};
std::list<int> list6 = {10, 20, 30, 40};

auto first = list6.begin();  // 指向10
auto last = first;
std::advance(last, 2);       // 指向30（注意：last是开区间）

// 将[first, last)范围的元素移动到list5开始位置
list5.splice(list5.begin(), list6, first, last);
// list5: {10, 20, 1, 2, 3, 4, 5}, list6: {30, 40}

5.merge() – 有序链表合并

// merge要求两个链表都已经排序！
std::list<int> list1 = {1, 3, 5, 7};
std::list<int> list2 = {2, 4, 6, 8};

list1.merge(list2);  // list1: {1, 2, 3, 4, 5, 6, 7, 8}
// list2现在为空

// 自定义排序规则的merge
std::list<int> list3 = {7, 5, 3, 1};
std::list<int> list4 = {8, 6, 4, 2};

// 降序合并
list3.merge(list4, std::greater<int>());
// list3: {8, 7, 6, 5, 4, 3, 2, 1}

6.sort() – 链表排序

// list有自己的sort成员函数，比std::sort更高效
std::list<int> lst = {5, 3, 8, 1, 9, 2};

lst.sort();  // 升序排序: {1, 2, 3, 5, 8, 9}

// 自定义排序
lst.sort(std::greater<int>());  // 降序排序: {9, 8, 5, 3, 2, 1}

// 为什么list有自己的sort？
// 因为std::sort需要随机访问迭代器，而list只有双向迭代器

7. unique() – 删除连续重复元素

std::list<int> lst = {1, 1, 2, 3, 3, 3, 2, 2, 4};

lst.unique();  // 删除连续重复，结果: {1, 2, 3, 2, 4}

// 自定义唯一性条件
std::list<int> lst2 = {1, 2, 3, 4, 5, 6};
lst2.unique([](int a, int b) {
    return (a % 2) == (b % 2);  // 删除奇偶性相同的连续元素
});

8. reverse() – 反转链表

std::list<int> lst = {1, 2, 3, 4, 5};
lst.reverse();  // 结果: {5, 4, 3, 2, 1}
// 时间复杂度O(n)，比vector的reverse高效

三、常见问题

1.迭代器失效问题

std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
std::advance(it, 2);  // 指向3

// list插入删除不会使其他迭代器失效！
lst.insert(it, 99);    // it仍然有效，指向3
lst.erase(it);         // 删除3，it现在失效

// 对比vector：中间插入会使后面所有迭代器失效！
std::vector<int> vec = {1, 2, 3, 4, 5};
auto vit = vec.begin() + 2;  // 指向3
vec.insert(vit, 99);         // vit和之后的所有迭代器都失效！

2.错误使用案例

std::list<int> lst = {5, 3, 1, 4, 2};

// 错误：std::sort需要随机访问迭代器
// std::sort(lst.begin(), lst.end());  // 编译错误！

// 正确：使用list自己的sort成员函数
lst.sort();  // 正确

// 错误：二分查找需要随机访问
// std::binary_search(lst.begin(), lst.end(), 3);  // 虽然编译通过，但性能O(n)而非O(log n)

// 正确：先排序，再用list的迭代器顺序查找
lst.sort();
auto it = std::find(lst.begin(), lst.end(), 3);

3.认知误区

// 虽然list插入是O(1)，但实际性能可能不如vector
std::list<int> lst;
std::vector<int> vec;

// 连续插入100万个元素
for (int i = 0; i < 1000000; ++i) {
    lst.push_back(i);   // 每次分配内存，可能比vector慢
    vec.push_back(i);   // 偶尔需要扩容，但内存连续，缓存友好
}

// 遍历：vector的缓存局部性使其更快
int sum1 = 0;
for (int n : lst) sum1 += n;  // 慢：指针跳跃，缓存不友好

int sum2 = 0;
for (int n : vec) sum2 += n;  // 快：内存连续，缓存友好

对于list容器，相较于vector容器和deque容器并没有那么常用，作为一种补充让大家能理解链表，同时对遇见引入中的问题超时后作为一种备用思路，之后我会尽快敲完迭代器的使用方案，届时大家可以学习完迭代器后再次重温几遍容器部分。当然，学习不是一蹴而就的，我也会努力完善文章结构，补充其他容器类知识点如map，set等，祝你有美好的一天。