C++ list

1. ​std::list 基本概念

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

2. ​构造函数

(1) ​默认构造函数

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

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

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

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

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

(4) ​拷贝构造函数

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

3. ​修改元素的成员函数

(1) ​push_back() 和 push_front()

在末尾或头部添加元素：

list<int> lst;
lst.push_back(10);   // 末尾添加10 → {10}
lst.push_front(5);   // 头部添加5 → {5, 10}

(2) ​insert()

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

• ​插入单个值：

  list<int> lst = {1, 3};
  list<int>::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<int>::iterator it = lst.begin();
  ++it;
  lst.erase(it);  // 删除位置1的元素 → {1, 3, 4, 4, 5, 6}

• ​删除范围元素：

  list<int>::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<int> lst1 = {1, 2};
  list<int> lst2 = {3, 4};
  lst1.splice(lst1.end(), lst2);  // lst1 → {1, 2, 3, 4}, lst2变为空

• ​移动单个元素：

  list<int> lst3 = {5, 6};
  list<int>::iterator it = lst3.begin();
  lst1.splice(lst1.begin(), lst3, it);  // lst1 → {5, 1, 2, 3, 4}, lst3 → {6}

• ​移动范围元素：

  list<int> lst4 = {7, 8, 9};
  list<int>::iterator first = lst4.begin();
  list<int>::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<int> lst = {1, 2, 3, 2, 4};
  lst.remove(2);  // 删除所有值为2的元素 → {1, 3, 4}

(3) ​sort() 和 merge()

排序和合并链表：

• ​sort()：

  list<int> lst = {3, 1, 4, 2};
  lst.sort();  // 默认升序 → {1, 2, 3, 4}

• ​merge()（要求两个链表已排序）：

  list<int> lst1 = {1, 3};
  list<int> lst2 = {2, 4};
  lst1.merge(lst2);  // lst1 → {1, 2, 3, 4}, lst2变为空

(4) ​unique()

删除连续重复元素（需先排序）：

list<int> lst = {1, 1, 2, 3, 3};
lst.unique();  // 删除连续重复 → {1, 2, 3}

(5) ​reverse()

反转链表元素顺序：

list<int> lst = {1, 2, 3};
lst.reverse();  // → {3, 2, 1}

7. ​迭代器操作

• ​begin() 和 end()：

  for (list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
      cout << *it << " ";
  }

• ​rbegin() 和 rend()（反向迭代器）​：

  for (list<int>::reverse_iterator rit = lst.rbegin(); rit != lst.rend(); ++rit) {
      cout << *rit << " ";
  }

8. ​注意事项

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