41 C++ STL模板库10-容器3-list

C++ STL模板库10-容器3-list

list是 双向链表，是一种内存不连续的数据结构。

一、构造函数与赋值操作

1. 函数说明

操作类型	函数	功能描述	时间复杂度
默认构造	list<T> lst;	创建空链表	O(1)
填充构造	list<T> lst(n, val);	创建含n个val元素的链表	O(n)
迭代器构造	list<T> lst(iter1, iter2);	用迭代器区间[iter1, iter2)初始化	O(n)
填充赋值	lst.assign(n, val)	分配n个val元素	O(n)
区间赋值	lst.assign(iter1, iter2)	用迭代器区间赋值	O(n)
拷贝赋值	lst = other_list	拷贝赋值 复制另一个链表的内容	O(n)
初始化列表赋值	lst = initializer_list	初始化列表赋值（如lst = {1,2,3};）	O(n)

2. 用法示例

1. 构造函数
   默认构造

   #include <list>
   std::list<int> lst1;  // 创建空链表
   // lst1: {}
   

   填充构造

   std::list<int> lst2(3, 100); // 创建含3个100的链表 
   // lst2: {100, 100, 100}
   

   迭代器区间构造

   int arr[] = {10, 20, 30};
   std::list<int> lst3(arr, arr+3);  // 用数组区间初始化 
   // lst3: {10, 20, 30}
   

   拷贝构造

   std::list<int> lst4(lst3);  // 复制lst3的内容 
   // lst4: {10, 20, 30}
   

   初始化列表构造 (C++11)

   std::list<int> lst5 = {8, 6, 7};  
   // lst5: {8, 6, 7}
   

2. 赋值操作
   operator= 赋值

   std::list<int> lstA = {1, 2};
   std::list<int> lstB;
   lstB = lstA;  // 复制lstA内容
   // lstB: {1, 2}lstB = {9, 8, 7};  // 直接赋初始化列表 
   // lstB: {9, 8, 7}
   

   assign() 区间赋值

   std::list<int> lstC;
   std::vector<int> vec = {5, 6};
   lstC.assign(vec.begin(), vec.end());  // 用vector迭代器区间 
   // lstC: {5, 6}
   

   assign() 填充赋值

   lstC.assign(4, 88);  // 替换为4个88 
   // lstC: {88, 88, 88, 88}
   

链表的插入/删除操作时间复杂度为 O(1)，适合频繁修改场景。

二、元素访问

1. 函数说明

函数	功能描述	异常安全
lst.front()	返回首元素引用（空链表未定义）	无异常（需非空链表）
lst.back()	返回尾元素引用（空链表未定义）	无异常（需非空链表）

⚠️ 注意,由于内存不连续，不支持随机访问（如operator[], std::sort()）

2. 用法示例

#include <iostream>
#include <list>int main (void) {std::list<int> nums = {10, 20, 30, 40};//1. 首尾元素直接访问std::cout << "Front: " << nums.front();  // 输出 Front: 10 std::cout << "Back: " << nums.back();    // 输出 Back: 40 std::cout << std::endl;//2. 迭代器顺序访问for(auto it = nums.begin();  it != nums.end();  ++it)std::cout << *it << " ";  // 输出 10 20 30 40 std::cout << std::endl;//3. 反向迭代器逆序访问for(auto rit = nums.rbegin();  rit != nums.rend();  ++rit) std::cout << *rit << " ";  // 输出 40 30 20 10 std::cout << std::endl;//4. 范围for循环简化访问for(const auto& num : nums) std::cout << num << " ";  // 输出 10 20 30 40 std::cout << std::endl;//5. 安全访问模式if(!nums.empty())  std::cout << "First : " << nums.front(); // 输出 First : 10std::cout << std::endl;return 0;
}

3. 特殊场景注意事项⚠️

场景	处理方式	示例
空链表访问	先检查empty()	if(!lst.empty()) lst.front()
需要中间元素	迭代器步进	std::next(lst.begin(), 2)

三、迭代器操作

1. 函数说明

类型	函数	方向	示例
正向迭代器	lst.begin()	→	auto it = lst.begin();
	lst.end()	→
常量正向迭代器	lst.cbegin()	→	auto cit = lst.cbegin();
	lst.cend()	→
反向迭代器	lst.rbegin()	←	auto rit = lst.rbegin();
	lst.rend()	←
常量反向迭代器	lst.crbegin()	←
	lst.crend()	←

2. 用法示例

1. 基础遍历（正向迭代器）🔄

   std::list<int> data = {10, 20, 30};
   for (auto it = data.begin(); it != data.end(); ++it) {std::cout << *it << " ";  // 输出: 10 20 30 
   }
   

   ✅ 特性：begin()指向首元素，end()指向尾后位置

2. 反向遍历（反向迭代器）🔙

   for (auto rit = data.rbegin(); rit != data.rend(); ++rit) {std::cout << *rit << " ";  // 输出: 30 20 10 
   }
   

   ✅ 特性：rbegin()指向尾元素，rend()指向首前位置

3. 迭代器修改元素✏️

   auto it = data.begin();
   std::advance(it, 1);  // 移动至第2个元素 
   -it = 99;             // 修改值 
   // data: {10, 99, 30}
   

   ⚠️ 注意：需用std::advance移动迭代器（链表不支持it+2）

4. 迭代器插入元素➕

   auto pos = data.begin();
   data.insert(pos, 5);    // 在头部插入 
   // data: {5, 10, 99, 30}std::advance(pos, 2);   // 移动迭代器 
   data.insert(pos, 3, 8); // 插入3个8 
   // data: {5, 10, 8, 8, 8, 99, 30}
   

   ✅ 特性：插入操作不失效其他迭代器

5. 迭代器删除元素✂️

   auto del_it = data.begin();
   std::advance(del_it, 3);  // 指向第4个元素 
   del_it = data.erase(del_it);  // 删除元素，返回下一位置 
   // data: {5, 10, 8, 8, 99, 30}data.erase(data.begin(), del_it); // 删除区间[begin, del_it)
   // data: {8, 99, 30}
   

   ⚠️ 关键：被删元素的迭代器失效，其他迭代器保持有效

6. 常量迭代器（安全访问）🔄

   const std::list<int> cdata = {1, 2, 3};
   for (auto cit = cdata.cbegin(); cit != cdata.cend(); ++cit) {// *cit = 5;  // 错误！禁止修改 std::cout << *cit;  // 安全读取 
   }
   

   ✅ 用途：防止意外修改容器内容

四、容量管理

1. 函数说明

函数	功能描述	时间复杂度
lst.empty()	判断链表是否为空	O(1)
lst.size()	返回元素数量（C++11起O(1)）	O(1)
lst.max_size()	返回可容纳最大元素数	O(1)
lst.resize(n)	调整链表大小为n（多余删除）	O(
lst.resize(n, val)	调整大小并用val填充新增位置	O(

2. 用法示例

1. 空状态检查（empty）📏

   std::list<std::string> tasks;
   if (tasks.empty()) {  // 检查链表是否为空 std::cout << "任务列表为空，请添加新任务！";
   }
   // 输出：任务列表为空，请添加新任务！
   

2. 元素计数（size）🔢

   std::list<int> prime = {2, 3, 5, 7};
   std::cout << "找到 " << prime.size() << " 个质数";
   // 输出：找到 4 个质数 
   

3. 动态扩容（resize）📐
   扩展链表（默认填充0）

   std::list<int> scores = {85, 90};
   scores.resize(4);  // 扩展到4个元素 
   // scores: {85, 90, 0, 0}
   

   扩展链表（指定填充值）

   scores.resize(6, -1);  // 扩展到6个元素，用-1填充 
   // scores: {85, 90, 0, 0, -1, -1}
   

   收缩链表

   scores.resize(3);  // 收缩到3个元素 
   // scores: {85, 90, 0}
   

4. 容量上限（max_size）🚧

   std::list<double> bigData;
   std::cout << "系统支持的最大元素数: " << bigData.max_size();  // 输出理论最大值（如768614336404564）
   

5. 清空链表（clear）🧹

   std::list<char> letters = {'A','B','C'};
   std::cout << "清理前: " << letters.size() << " 字母";  // 输出：3 
   letters.clear();  // 清空所有元素 
   std::cout << "清理后: " << letters.size();  // 输出：0 
   

五、修改操作🔧

1. 函数说明

• 插入/删除
  | 函数 | 功能描述 | 复杂度 |
  |------------------------------|-----------------------------------------|---------------|
  | lst.push_front(val) | 头部插入val | O(1) |
  | lst.push_back(val) | 尾部插入val | O(1) |
  | lst.pop_front() | 删除头部元素（空链表未定义） | O(1) |
  | lst.pop_back() | 删除尾部元素（空链表未定义） | O(1) |
  | lst.insert(iter, val) | 在iter前插入val | O(1) |
  | lst.insert(iter, n, val) | 在iter前插入n个val | O(n) |
  | lst.erase(iter) | 删除iter指向的元素 | O(1) |
  | lst.erase(iter1, iter2) | 删除区间[iter1, iter2)元素 | O(距离) |
  | lst.clear() | 清空所有元素 | O(n) |

• 拼接/交换
  | 函数 | 功能描述 |
  |------------------------------|-----------------------------------------|
  | lst.splice(iter, other_lst) | 将other_lst所有元素移动到iter前 |
  | lst.splice(iter, other_lst, it) | 移动other_lst中it指向的元素到iter前 |
  | lst.swap(other_lst) | 交换两个链表内容 |

2. 用法示例

1. 头尾增删操作（O(1)复杂度）

   std::list<int> nums = {10, 20};// 头部操作 
   nums.push_front(5);  // 头部插入 → {5,10,20}
   nums.pop_front();    // 头部删除 → {10,20}// 尾部操作
   nums.push_back(30);  // 尾部插入 → {10,20,30}
   nums.pop_back();     // 尾部删除 → {10,20}
   

   ✅ 特性：

   • 无需移动元素，直接修改指针
   • 空链表调用pop_*会触发未定义行为

2. 定点插入/删除（迭代器操作）

   auto it = nums.begin();
   std::advance(it, 1);  // 指向第2个元素(20)// 单点插入
   it = nums.insert(it, 15);  // 在20前插入 → {10,15,20}// 批量插入 
   nums.insert(it, 2, 18);    // 插入2个18 → {10,18,18,15,20}// 删除元素 ,删除元素后返回的是下一个元素的位置
   it = nums.erase(it);       // 删除当前元素(15) → {10,18,18,20}
   nums.erase(nums.begin(), it); //it指向的是20位置，删除的区间是 [10,20),所以元素只剩下： 20
   

   ⚠️ 注意：

   • 插入后返回新元素迭代器
   • 删除后返回下一元素迭代器
   • 被删元素的迭代器失效
   • 删除的是左闭右开区间 [iter1, iter2)

3. 链表拼接（splice）

   std::list<int> part1 = {1,2};
   std::list<int> part2 = {3,4};
   auto pos = part1.begin();// 整链表移动
   part1.splice(pos, part2);  // part2所有元素插入pos前 
   // part1: {3,4,1,2}, part2变为空// 单元素移动 第一步操作后 pos 仍指向原元素 1（非首元素）
   part2.splice(part2.begin(), part1, pos);  // 移动pos指向的元素（1）
   // part1: {3,4,2}, part2: {1}
   

   💡 优势：

   • 零拷贝：仅修改指针，效率极高
   • 操作后源链表迭代器保持有效

4. 链表交换lst.swap(other_lst)

   • 仅交换内部指针,不涉及元素复制或移动

   1. 基础交换（高效指针操作）

      std::list<int> teamA = {1,2};
      std::list<int> teamB = {3,4};teamA.swap(teamB);   // 交换链表内容
      // 结果：
      // teamA → {3,4}
      // teamB → {1,2}
      

   2. 迭代器稳定性验证

      • 交换后迭代器保持关联原元素不变
      • 仅容器归属关系变化（原teamA的迭代器现在关联teamB的元素）

      std::list<std::string> teamA = {"Alice", "Bob"};
      std::list<std::string> teamB = {"Charlie", "Diana"};auto itA = teamA.begin();   // 指向"Alice"
      auto itB = teamB.begin();   // 指向"Charlie"teamA.swap(teamB); std::cout << *itA;  // 仍输出"Alice"（但此时属于teamB）
      std::cout << *itB;  // 仍输出"Charlie"（但此时属于teamA）
      

💎 操作特性对比表

操作类型	核心函数	时间复杂度	迭代器安全性
头尾操作	push/pop_front/back	O(1)	操作点外的迭代器保持有效
定点操作	insert/erase	O(1)	仅被删元素迭代器失效
链表拼接	splice	O(1)	所有迭代器保持有效（含其他链表）
链表交换	lst.swap(other_lst)	O(1)	仅交换指针，比赋值操作高效

六、链表专属操作

1. 函数说明

函数	功能描述	复杂度
lst.sort()	升序排序（可自定义比较器）	O(n log n)
lst.unique()	删除连续重复值（可传入二元谓词）	O(n)
lst.merge(other_lst)	合并有序链表（other_lst被清空）	O(n)
lst.reverse()	反转链表元素顺序	O(n)
lst.remove(val)	删除所有值为val的元素	O(n)
lst.remove_if(pred)	删除满足谓词pred的元素	O(n)

2. 用法示例

1. 排序 lst.sort()

   std::list<int> nums = {3, 1, 4, 2};  
   nums.sort();  // 默认升序 → {1, 2, 3, 4}  // 自定义排序（降序）  
   nums.sort([](int a, int b){ return a > b; });  
   // → {4, 3, 2, 1}  
   

   特性：

   • 时间复杂度 O(n log n)（稳定排序）

2. 去重 lst.unique()

   std::list<int> data = {1,1,2,3,3,3,2};  
   data.sort();          // 预排序 → {1,1,2,2,3,3,3}  
   data.unique();        // 去重 → {1,2,3}  data = {1,3,5,4};
   // 条件去重（差>1才视为重复）  
   data.unique([](int a, int b){ return abs(a-b) <=1; });  
   // 原数据{1,3,5} → 删除4（因5-4<=1）
   

   特性：

   • 仅处理相邻重复，需先排序才能完全去重
   • 时间复杂度 O(n)

3. 合并 lst.merge(other_lst)

   std::list<int> list1 = {2, 5};  
   std::list<int> list2 = {1, 3, 4};  
   list1.merge(list2);  // 合并后 list1→{1,2,3,4,5}, list2空  
   

   规则：

   • 必须预先排序（否则结果无序）
   • 合并后other_lst被清空
   • 时间复杂度 O(n + m)（n、m为两链表长度）

4. 反转 lst.reverse()

   std::list<char> letters = {'A','B','C'};  
   letters.reverse();  // → {'C','B','A'}  
   

   特性：

   • 时间复杂度 O(n)（仅调整指针）
   • 不影响迭代器有效性

5. 条件 lst.remove(val)

   std::list<int> scores = {85, 90, 85, 70};  
   scores.remove(85);  // 删除所有85 → {90,70}  
   

   性能：

   • 时间复杂度 O(n)（全链表扫描）
   • 比循环+erase更高效

6. 条件删除 lst.remove_if(pred)

   // 删除偶数  
   scores.remove_if([](int x){ return x%2 ==0; });  
   // 原数据{90,70,95} → 删除后{95}  
   

   扩展应用：

   • 支持复杂谓词（如正则匹配、对象属性判断）

7. 结构修改（merge/reverse/unique）

   std::list<int> list1 = {1,5};
   std::list<int> list2 = {2,3};// 合并有序链表（需预先排序）
   list1.sort(); list2.sort();     // {1,5} {2,3}
   list1.merge(list2);             // {1,2,3,5}, list2清空 // 反转链表
   list1.reverse();                // {5,3,2,1}list1 = {5,3,5,5,5,5,2,1,5,5,};
   // 去重（需连续重复）
   list1.unique();                 // {5,3,5,2,1,5}
   list1.push_back(5);             // {5,3,5,2,1,5,5}
   list1.unique();                 // → {5,3,5,2,1,5}
   

   🚀 专属特性：

   • merge()要求链表预先有序
   • unique()仅处理相邻重复元素

💎操作与选择对比

操作类型	典型场景	时间复杂度	关键优势
sort	需要有序遍历	O(n log n)	稳定排序
unique	数据清洗（如日志去重）	O(n)	减少冗余数据
merge	合并有序数据集	O(n + m)	零拷贝高效合并
reverse	逆向处理（如历史记录展示）	O(n)	快速结构调整
remove*	过滤特定元素	O(n)	条件删除一步到位

七、完整示例

1. 示例1：

#include <iostream>
#include <list>
#include <string>using namespace std;template<class T>
void print (const list<T>& l) {using CIT = typename list<T>::const_iterator ;for (CIT it = l.begin (); it != l.end (); it++)cout << *it << ' ';cout << endl;
}int main (void) {list<int> ln;ln.push_back (20);ln.push_back (30);ln.push_front (10);print (ln);        // 10 20 30list<string> ls;ls.push_front ("北京");ls.push_front ("上海");ls.push_back ("重庆");list<string>::iterator it = ls.begin ();it++;ls.insert (it, "天津");print (ls);        // 上海 天津 北京 重庆ls.push_back ("上海");print (ls);        //上海 天津 北京 重庆 上海ls.remove ("上海"); // 删除所有匹配的元素print (ls);        //天津 北京 重庆ln.push_back (20);ln.push_back (20);ln.push_back (30);print (ln);        // 10 20 30 20 20 30ln.sort ();print (ln);        // 10 20 20 20 30 30ln.unique (); // 对连续重复出现的元素唯一化print (ln);        // 10 20 30ln.push_back (40);ln.push_back (50);print (ln);        // 10 20 30 40 50list<int> l2;l2.push_back (100);l2.push_back (200);print (l2);        // 100 200list<int>::iterator it0 = l2.begin (),it1 = ln.begin (), it2 = ln.end ();it0++; // -> 200it1++; // -> 20it2--; // -> 50// 将ln中从it1到it2之前的元素剪切至l2的it0处l2.splice (it0, ln, it1, it2);print (ln);        // 10 50print (l2);        // 100 20 30 40 200l2.sort ();print (l2);        // 20 30 40 100 200// 将有序的ln中的元素剪切到有序的l2中，仍然保持 l2 有序l2.merge (ln);print (ln);        // print (l2);        // 10 20 30 40 50 100 200}

示例2：

#include <iostream>
#include <list>
#include <algorithm>struct Product {std::string name;int quantity;/*  1：添加相等运算符 */bool operator==(const Product& other) const {return name == other.name  && quantity == other.quantity; }/* 关 2：添加小于运算符（用于排序）*/bool operator<(const Product& other) const {return quantity < other.quantity;   // 按数量排序}Product(std::string n, int q) : name(n), quantity(q) {}friend std::ostream& operator<<(std::ostream& os, const Product& p) {return os << p.name  << "×" << p.quantity;  }
};int main() {// ▶ 1. 初始化std::list<Product> cart;std::list<Product> promo(3, {"牙刷", 1});std::list<Product> backup = {{"牛奶",2}, {"面包",3}};auto expired = backup;// ▶ 2. 容量与访问 std::cout << "促销品数量: " << promo.size()  << "\n";std::cout << "首件商品: " << promo.front()  << "\n";// ▶ 3. 增删元素cart.push_front({" 苹果", 5});cart.push_back({" 鸡蛋", 10});cart.pop_front(); // ▶ 4. 定点操作auto it = cart.begin();  it = cart.insert(it,   {"大米", 1});it = cart.erase(it); // ▶ 5. 批量操作 cart.splice(cart.end(),  promo);cart.remove_if([](auto&  p){ return p.name  == "牙刷"; });// ▶ 6. 排序重组 backup.sort([](auto&  a, auto& b){ return a.quantity  > b.quantity;  });// 修复点：确保expired也排序（merge要求）expired.sort([](auto&  a, auto& b){ return a.quantity  > b.quantity;  });// ▶ 7. 合并去重 backup.merge(expired); backup.unique();   //  // ▶ 8. 反转与删除 backup.reverse(); backup.remove({" 牛奶", 2});  // 需要operator== // ▶ 9. 算法库交互 auto found = std::find_if(backup.begin(),  backup.end(),  [](auto& p){ return p.name  == "面包"; });if (found != backup.end())  found->quantity = 5;// ▶ 10. 内存优化std::list<Product>().swap(expired);cart.emplace_back(" 矿泉水", 6);
}

八、 关键特性总结

1. 双向结构：支持高效头尾插入/删除（O(1)），不支持随机访问。
   • 链表的插入/删除操作时间复杂度为 O(1)，适合频繁修改场景。
2. 迭代器稳定性：增删元素时，非被删元素的迭代器/引用始终保持有效。
3. 专属算法：提供sort(), merge(), unique()等高效成员函数（优于通用算法）。
4. 内存布局：元素非连续存储，无容量（capacity）概念。因此不会发生容量预留，每次增删都是精确内存操作。
5. 应用场景：适合频繁在任意位置插入/删除、无需随机访问的场景。需随机访问时优先选vector或deque。