C++ list

1 ​std::list 基本概念

• ​定义 ：std::list 是 C++ 标准库提供的带头（哨兵位）双向循环链表容器，支持高效的元素插入和删除。
• ​头文件 ：`#include

`

2 ​构造函数

(1) ​默认构造函数

list list1; // 创建一个空list，size=0

(2) ​指定初始大小和默认值

list list2(5); // 5个元素，默认初始化（int为0） list list3(5, 3.14); // 5个元素，每个值为3.14

(3) ​通过迭代器范围构造

int arr[] = {1, 2, 3}; list list4(arr, arr + 3); // 复制数组的[arr, arr+3)范围元素

(4) ​拷贝构造函数

list list5(list4); // 深拷贝list4的内容

3 ​修改元素的成员函数

(1) ​push_back() 和 push_front()

在末尾或头部添加元素： list lst; lst.push_back(10); // 末尾添加10 → {10} lst.push_front(5); // 头部添加5 → {5, 10}

(2) ​insert()

插入元素到指定位置，支持以下重载：

• ​插入单个值 ： list lst = {1, 3}; list::iterator it = lst.begin(); ++it; lst.insert(it, 2); // 在位置1插入2 → {1, 2, 3}
• ​插入多个相同值 ： lst.insert(lst.end(), 2, 4); // 在末尾插入2个4 → {1, 2, 3, 4, 4}
• ​通过迭代器范围插入 ： int arr[] = {5, 6}; lst.insert(lst.end(), arr, arr + 2); // 插入数组内容 → {1, 2, 3, 4, 4, 5, 6}

(3) ​erase()

删除指定位置或范围的元素：

• ​删除单个元素 ： list::iterator it = lst.begin(); ++it; lst.erase(it); // 删除位置1的元素 → {1, 3, 4, 4, 5, 6}
• ​删除范围元素 ： list::iterator first = lst.begin(); advance(first, 3); // 移动到位置3 lst.erase(first, lst.end()); // 删除位置3到末尾 → {1, 3, 4}

(4) ​clear()

清空所有元素： lst.clear(); // size=0

(5) ​assign()

重新分配元素（覆盖原有内容）：

• ​指定数量和值 ： lst.assign(3, 10); // 3个10 → {10, 10, 10}
• ​通过迭代器范围 ： int arr[] = {20, 30, 40}; lst.assign(arr, arr + 2); // 复制前2个元素 → {20, 30}

4 ​访问元素的成员函数

(1) ​front() 和 back()

访问首尾元素： int first = lst.front(); // 第一个元素 int last = lst.back(); // 最后一个元素

5 ​容量管理的成员函数

(1) ​size()

获取元素数量： size_t s = lst.size(); // 当前元素数量

(2) ​resize()

调整元素数量： lst.resize(5); // 调整size=5，多出的元素默认初始化（int为0） lst.resize(3, 100); // 调整size=3，若需要新增元素则初始化为100

6 ​链表特有操作

(1) ​splice()

将另一个链表的元素移动（拼接）到当前链表，支持以下重载：

• ​移动整个链表 ： list lst1 = {1, 2}; list lst2 = {3, 4}; lst1.splice(lst1.end(), lst2); // lst1 → {1, 2, 3, 4}, lst2变为空
• ​移动单个元素 ： list lst3 = {5, 6}; list::iterator it = lst3.begin(); lst1.splice(lst1.begin(), lst3, it); // lst1 → {5, 1, 2, 3, 4}, lst3 → {6}
• ​移动范围元素 ： list lst4 = {7, 8, 9}; list::iterator first = lst4.begin(); list::iterator last = lst4.end(); –last; lst1.splice(lst1.end(), lst4, first, last); // lst1 → {5, 1, 2, 3, 4, 7, 8}, lst4 → {9}

(2) ​remove()

删除特定元素：

• ​remove()： list lst = {1, 2, 3, 2, 4}; lst.remove(2); // 删除所有值为2的元素 → {1, 3, 4}

(3) ​sort() 和 merge()

排序和合并链表：

• ​sort()： list lst = {3, 1, 4, 2}; lst.sort(); // 默认升序 → {1, 2, 3, 4}
• ​merge()（要求两个链表已排序）： list lst1 = {1, 3}; list lst2 = {2, 4}; lst1.merge(lst2); // lst1 → {1, 2, 3, 4}, lst2变为空

(4) ​unique()

删除连续重复元素（需先排序）： list lst = {1, 1, 2, 3, 3}; lst.unique(); // 删除连续重复 → {1, 2, 3}

(5) ​reverse()

反转链表元素顺序： list lst = {1, 2, 3}; lst.reverse(); // → {3, 2, 1}

7 ​迭代器操作

• ​begin() 和 end()： for (list::iterator it = lst.begin(); it != lst.end(); ++it) { cout « *it « " “; }
• ​rbegin() 和 rend()（反向迭代器）​： for (list::reverse_iterator rit = lst.rbegin(); rit != lst.rend(); ++rit) { cout « *rit « " “; }

8 ​注意事项

• ​迭代器失效 ：删除操作仅使被删除元素的迭代器失效，其他迭代器仍然有效（后面我会专门整理这个问题）。
• ​性能特点 ：插入和删除操作高效，但随机访问效率低（需遍历链表）。
• ​排序与合并 ：sort() 和 merge() 是成员函数，不同于 `` 中的全局函数。