42 C++ STL模板库11-容器4-forward_list

STL模板库-容器4-forward_list

forward_list 是一个支持快速在容器中任意位置插入和删除元素的容器。它实现为单向链表。
不支持快速随机访问。与 std::list 相比，当不需要双向迭代时，该容器提供更节省空间的存储。

1. 构造函数

1.函数说明

函数签名	功能说明
forward_list()	创建空链表
forward_list(size_type n, const T& value)	创建包含 n 个相同元素的链表
forward_list(InputIt first, InputIt last)	用迭代器范围内的元素创建链表
forward_list(const forward_list& other)	拷贝构造函数
forward_list(forward_list&& other)	移动构造函数（C++11）

2. 用法示例

#include <forward_list>
#include <array>int main() {// 示例1：创建空链表std::forward_list<int> emptyList;  // 空链表：{}// 示例2：创建含5个100的链表 std::forward_list<int> filledList(5, 100);  // {100,100,100,100,100}// 示例3：用迭代器范围创建链表std::array<int, 5> arr = {1,3,5,7,9};std::forward_list<int> iterList(arr.begin(),  arr.end());   // {1,3,5,7,9}// 示例4：拷贝构造链表 std::forward_list<int> original = {2,4,6,8};std::forward_list<int> copiedList(original);  // {2,4,6,8}（深拷贝）// 示例5：移动构造链表（C++11）std::forward_list<int> movedList(std::move(original));  // 转移资源所有权 // 此时original变为空链表 return 0;
}

3. 详细说明

• 迭代器构造的灵活性

  // 支持原生数组初始化 
  int arr[] = {10,20,30};
  std::forward_list<int> arrList(arr, arr+3);// 支持部分范围构造 
  std::string words[] = {"A","B","C","D"};
  std::forward_list<std::string> partList(words+1, words+3);  // {"B","C"}
  

• 深拷贝与浅拷贝

  // 深拷贝验证
  auto listA = std::forward_list{1.1, 2.2};
  auto listB(listA);  // 深拷贝
  listB.front() = 3.3;  // 修改副本 
  // listA仍为{1.1,2.2}（独立内存）
  

2. 元素访问

1. 函数说明

函数签名	功能说明
T& front()	访问首元素（空链表调用会导致未定义行为）
const T& front() const	访问首元素（const 版本）

2. 用法示例

#include <forward_list>
#include <iostream>int main() {// 示例1：非const版本修改首元素std::forward_list<int> nums = {10, 20, 30};if (!nums.empty()) {int& first = nums.front();  // 获取首元素引用 first *= 2;                 // 直接修改元素值// 此时链表变为 {20,20,30}}// 示例2：const版本安全读取 const std::forward_list<std::string> words = {"Apple", "Banana"};if (!words.empty()) {const std::string& firstWord = words.front();  // 只读访问 std::cout << "首元素：" << firstWord;           // 安全输出 }// 示例3：避免未定义行为 std::forward_list<double> emptyList;// emptyList.front() = 3.14;  // ❌ 危险！空链表引发崩溃 return 0;
}

3. 详细说明

1. 引用返回的特性风险

   std::forward_list<int> data = {1,2,3};
   int& ref = data.front();  // 获取引用
   data.pop_front();         // 删除首元素
   // ref 成为悬空引用（危险！）
   

2. const版本的特殊用法

   void printFirst(const std::forward_list<std::string>& list) {if (!list.empty()) std::cout << list.front();  // 必须使用const版本 
   }
   

3. 结合现代C++特性

   // C++17结构化绑定
   if (auto [first, hasValue] = std::pair{&data.front(), !data.empty()}; hasValue) {*first = 100;  // 安全修改 
   }
   

4. 元素类型适配

   // 对大型对象使用const引用减少拷贝 
   struct BigData { /* ... */ };
   const std::forward_list<BigData> bigList;
   if (!bigList.empty()) {const auto& first = bigList.front();  // 零拷贝访问 
   }
   

3. 迭代器操作

1. 函数说明

函数签名	功能说明
iterator before_begin()	返回首元素前驱的迭代器
const_iterator before_begin() const	before_begin() 的 const 版本
const_iterator cbefore_begin() const	before_begin() 的 const 版本,显式请求版
iterator begin()	返回指向首元素的迭代器
iterator end()	返回尾后迭代器
const_iterator begin() const	begin() 的 const 版本
const_iterator end() const	end() 的 const 版本
const_iterator cbegin() const	begin() 的 const 版本
const_iterator cend() const	end() 的 const 版本

2. 用法示例

1. 特殊位置迭代器

   // 1. before_begin() 系列 - 获取首元素前驱位置
   std::forward_list<int> flist = {10, 20, 30};auto pre_it = flist.before_begin();      // 可修改的虚拟头节点迭代器 
   auto cpre_it = flist.cbefore_begin();    // 显式声明的const版本（C++11）// 在链表头部插入元素 
   flist.insert_after(pre_it, 5);   // 新链表: {5,10,20,30}// 安全读取操作（const对象）
   const auto& const_flist = flist;
   auto const_pre = const_flist.before_begin();  // 必须使用const版本
   

2. 首尾元素迭代器

   // 2. begin()/end() 系列 - 获取有效范围
   std::forward_list<std::string> words = {"Apple", "Banana"};// 非const版本遍历修改 
   for (auto it = words.begin(); it != words.end(); ++it) {it->append("!");  // 修改元素: Apple! → Banana!
   }// const版本安全遍历
   const auto& const_words = words;
   for (auto cit = const_words.cbegin(); cit != const_words.cend(); ++cit) {std::cout << *cit;  // 只读访问
   }// C++11范围for等价于 
   for (auto&& w : words) { /* 同begin()/end() */ }
   

3. 迭代器用法对比表

函数原型	典型应用场景	修改权限	空链表行为
before_begin()	insert_after插入头元素	读写	返回有效迭代器
before_begin() const	const对象头部插入操作	只读	返回有效迭代器
cbefore_begin() const	显式声明只读意图的头部操作	只读	返回有效迭代器
begin()	遍历修改元素/删除操作	读写	等于end()
begin() const	const对象遍历	只读	等于end()
cbegin() const	显式声明只读意图的遍历	只读	等于cend()
end()	遍历终止条件	-	始终有效
end() const	const对象遍历终止条件	-	始终有效
cend() const	显式声明只读遍历的终止条件	-	始终有效

4. 详细说明

• 首元素前驱： 首元素前的位置，不存储实际数据，仅作为操作锚点。

  //前驱迭代器特殊性
  // before_begin() 指向虚拟节点（不可解引用）
  auto pre = flist.before_begin();
  // *pre = 5;  // ❌ 禁止操作！未定义行为 auto it = flist.before_begin(); 
  // *it = 10;   // 错误！未定义行为（前驱位置无实际数据）//与前向迭代的关系
  auto it = flist.before_begin(); 
  it++;  // 现在指向首元素（等同于 flist.begin() ）
  

• const_iterator before_begin() const和const_iterator cbefore_begin() const

  • 这两个函数的返回值相同：均指向链表首元素前的逻辑位置（虚拟头节点）

  • 功能权限相同：均提供只读访问权限

  • 关键差异：

    使用场景	before_begin() const	cbefore_begin() const
    在非 const 对象调用	不可调用	可调用
    设计意图	为 const 对象提供只读锚点	明确强制表达提供只读锚点(即使对象非 const)

• 迭代器失效规则

  auto it = flist.begin();  // 指向10 
  flist.pop_front();        // 删除首元素 
  // it 已失效！不可继续使用
  

• const一致性原则

  const auto& const_list = flist;
  // auto it = const_list.begin();  // 返回const_iterator 
  // it->append("!");  // ❌ 禁止修改const对象 
  

​ 优先使用 cbegin()/cend() 和 cbefore_begin() 表达只读意图，避免意外修改数据。在C++14+中，非const对象的 begin()/end() 返回iterator，而const对象返回const_iterator，保持类型安全。

4. 容量查询

1. 函数说明

函数签名	功能说明
bool empty() const	检查链表是否为空
size_type max_size() const	返回可容纳的最大元素数量

2. 用法示例

#include <forward_list>
#include <iostream>int main() {// 示例1：empty() 检查链表状态std::forward_list<int> listA = {1, 2, 3};if (!listA.empty())  {  // 检查链表是否非空std::cout << "链表A有数据\n";}std::forward_list<std::string> listB;if (listB.empty())  {  // 检查链表是否为空 std::cout << "链表B为空\n";}// 示例2：max_size() 获取理论容量上限 std::cout << "int链表最大容量: " << listA.max_size()  << "\n";// 1152921504606846975std::cout << "string链表最大容量: " << listB.max_size()  << "\n";//461168601842738790return 0;
}

3. 详细说明

1. empty() 使用场景

   // 安全操作前置检查 
   void safe_pop(std::forward_list<T>& list) {if (!list.empty()) {list.pop_front();  // 防止未定义行为}
   }
   

2. max_size() 的误导性

   // 返回值是理论最大值
   // 实际受内存限制可能远小于此值 
   auto max_elements = list.max_size();
   // 尝试分配 max_size() 个元素通常导致崩溃
   

3. 无 size() 函数的替代方案

   // 必须遍历计数 
   size_t count = 0;
   for (auto it = list.cbegin(); it != list.cend(); ++it) {++count;
   }
   

5. 元素修改

1. 函数说明

函数签名	功能说明
void push_front(const T& value)	在链表头部插入元素（拷贝语义）
void emplace_front(Args&&... args)	在链表头部就地构造元素
void pop_front()	删除链表首元素
iterator insert_after(const_iterator pos, const T& value)	在指定位置后插入单个元素
iterator insert_after(const_iterator pos, size_type n, const T& value)	在指定位置后插入 n 个相同元素
iterator insert_after(const_iterator pos, InputIt first, InputIt last)	在指定位置后插入迭代器范围内的元素
iterator emplace_after(const_iterator pos, Args&&... args)	在指定位置后就地构造元素
iterator erase_after(const_iterator pos)	删除指定位置后的单个元素
iterator erase_after(const_iterator first, const_iterator last)	删除指定范围内的元素
void resize(size_type count)	调整链表大小（默认构造新元素）
void resize(size_type count, const value_type& value)	调整链表大小（指定值构造新元素）
void clear()	清空链表所有元素

2. 用法示例

1. 头部操作函数

   // 1. 头部插入（拷贝语义）
   std::forward_list<int> flist;
   flist.push_front(1);   
   flist.push_front(2);  // {2, 1}// 2. 头部就地构造（C++11）
   flist.emplace_front(3);  // {3 2 1} 直接构造(3) 这里是 int 时只能是一个参数// 3. 头部删除 
   flist.pop_front();   // 删除3
   if (!flist.empty())  flist.pop_front();   // 安全删除 2 
   

   • 对比特性：

     函数	参数传递方式	性能优势	适用场景
     push_front	值拷贝	低	已有对象插入
     emplace_front	参数包展开	高（免拷贝）	直接构造新对象

2. 插入操作函数

   // 1. 单元素插入 
   auto it = flist.insert_after(flist.before_begin(), 4); // {4 , 1}// 2. 批量插入（3个100）
   flist.insert_after(it, 3, 3);  // {4 3 3 3 1}// 3. 范围插入 
   std::array<int,3> ar{7,8,9};
   flist.insert_after(it, ar.begin(), ar.end());// {4 7 8 9 3 3 3 1}// 4. 就地构造插入（C++11）
   it = flist.emplace_after(it, 314);  // 直接构造int类型元素 {4 314 7 8 9 3 3 3 1}
   

3. 删除操作函数

   // 1. 删除单个后继元素 
   auto pos = flist.begin();
   flist.erase_after(pos);  // 删除pos的下一个节点 {4 7 8 9 3 3 3 1}// 2. 范围删除（左开右闭）
   auto first = flist.begin();      //指向 4 的位置
   auto last = std::next(first, 3); //指向 9 的位置
   flist.erase_after(first, last);  //删除first和last之间的元素（不包括first）//{4 9 3 3 3 1}
   // 3. 清空链表 
   flist.clear();  // 效果等价于 erase_after(before_begin(), end())
   

   • 删后不删前erase_after 的本质是 删除两个锚点之间的节点，而非数学意义上的区间操作。

   • 删除安全规范：

     // 错误示范 ❌ 
     auto risky_it = flist.begin();
     flist.erase_after(risky_it);  // 若risky_it是末元素则导致UB // 正确做法 ✅ 
     if (flist.begin() != flist.end()) flist.erase_after(risky_it);
     

4. 尺寸调整函数

   std::forward_list<int> nums{1,2,3};// 1. 扩容至5个元素（补0）
   nums.resize(5);        // {1,2,3,0,0}// 2. 缩容至3个元素 
   nums.resize(3);        // {1,2,3}// 3. 指定填充值扩容 
   nums.resize(5, 100);   // {1,2,3,100,100}
   

5. 性能优化建议

   1. 批量插入优化

      // 优先用范围插入代替循环插入 
      std::vector<int> bulkData(1000, 5);
      flist.insert_after(pos, bulkData.begin(), bulkData.end());
      

   2. 移动语义应用

      // 大对象使用移动构造 
      struct HeavyObj { /* ... */ };
      HeavyObj obj;
      flist.emplace_front(std::move(obj));  // 避免拷贝 
      

   3. 内存预判技巧

      // 通过resize预分配内存（forward_list无容量概念）
      flist.resize(flist.size() + 100);  // 提前创建节点 
      

6. 链表操作

1. 函数说明

函数签名	功能说明
void splice_after(const_iterator pos, forward_list& other)	将另一链表的所有元素转移到当前链表
void splice_after(const_iterator pos, forward_list&& other)	移动语义版本
void splice_after(const_iterator pos, forward_list& other, const_iterator it)	转移另一链表的单个元素
void splice_after(const_iterator pos, forward_list& other, const_iterator first, const_iterator last) 操作范围：(first, last)（左开右开区间）	转移另一链表的部分元素
void remove(const T& value)	删除所有等于指定值的元素
void remove_if(UnaryPredicate p)	删除所有满足条件的元素
void unique()	删除连续重复的元素
void unique(BinaryPredicate p)	使用自定义谓词删除连续重复元素
void merge(forward_list& other)	合并两个有序链表
void merge(forward_list&& other)	移动语义版本
void merge(forward_list& other, Compare comp)	使用自定义比较函数合并
void sort()	对链表进行升序排序
void sort(Compare comp)	使用自定义比较函数排序
void reverse()	反转链表顺序

2. 用法示例

1. 链表拼接操作

   // 1. 转移整个链表 
   std::forward_list<int> listA{1,2}, listB{3,4};
   listA.splice_after(listA.begin(), listB);  // listA: {1,3,4,2}, listB空 // 2. 移动语义版本（C++11）
   std::forward_list<int> listC{5,6};
   listA.splice_after(listA.begin(), std::move(listC));  // listA: {1,5,6,3,4,2}// 3. 转移单个元素 
   std::forward_list<int> listD{7,8};
   auto itD = listD.begin();  // 指向7 
   listA.splice_after(listA.begin(), listD, itD);  // 转移8 → listA: {1,8,5,6,3,4,2}// 4. 转移元素范围 
   std::forward_list<int> listE{9,10,11};
   auto firstE = listE.begin();        // 指向9 
   auto lastE = std::next(firstE, 2);  // 指向11 
   listA.splice_after(listA.begin(), listE, firstE, lastE);  // 转移10 → listA: {1,10,8,5,6,3,4,2}
   

2. 元素删除操作

   // 5. 删除特定值 
   listA.remove(5);  // 删除所有5 → {1,10,8,6,3,4,2}// 6. 条件删除 
   listA.remove_if([](int n){ return n % 2 == 0; });  // 删除偶数 → {1,3}// 7. 删除连续重复值 
   std::forward_list<int> dupList{1,1,2,2,3,3};
   dupList.unique();  // 结果 → {1,2,3}// 8. 自定义重复判定 
   dupList.unique([](int a, int b){ return abs(a-b) < 2; });  // 删除差值<2的相邻元素 
   

3. 合并与排序操作

   // 9. 合并有序链表 
   std::forward_list<int> sortedX{1,3,5}, sortedY{2,4,6};
   sortedX.merge(sortedY);  // sortedX: {1,2,3,4,5,6}, sortedY空 // 10. 移动语义合并 
   std::forward_list<int> sortedZ{7,8,9};
   sortedX.merge(std::move(sortedZ));  // sortedX: {1,2,3,4,5,6,7,8,9}// 11. 自定义比较合并 
   std::forward_list<int> descA{9,7,5}, descB{8,6,4};
   descA.merge(descB, [](int a, int b){ return a > b; });  // 降序合并 → {9,8,7,6,5,4}// 12. 升序排序 
   std::forward_list<int> unsorted{3,1,4,2};
   unsorted.sort();  // → {1,2,3,4}// 13. 自定义排序 
   unsorted.sort(std::greater<int>());  // 降序 → {4,3,2,1}
   

4. 链表反转

   // 14. 反转链表顺序 
   std::forward_list<int> original{1,2,3,4};
   original.reverse();  // → {4,3,2,1}
   

3. 详细说明

1. 关键操作特性对比

   操作类型	时间复杂度	迭代器有效性	特殊要求
   splice_after	O(n)	被转移迭代器失效	源/目标链表不同
   remove/remove_if	O(n)	被删元素迭代器失效	无
   unique	O(n)	被删元素迭代器失效	需先排序（非连续重复）
   merge	O(n+m)	源链表迭代器失效	输入链表已排序
   sort	O(n log n)	全部迭代器失效	无
   reverse	O(n)	全部迭代器失效	无

2. 注意事项

   • splice_after 操作后源链表元素被转移
   • merge 要求链表已按相应规则预排序
   • unique 仅处理相邻重复元素，非全局去重
   • sort 在链表较大时优先于 std::sort（因指针操作高效）
   • 自定义谓词需满足严格弱序关系（如 a < b 而非 a <= b）

3. 最佳用法建议：

   • 拼接操作后源链表变为空
   • 自定义排序时确保比较函数满足严格弱序关系（如 return a<b 而非 a<=b ）

7. 非成员函数

1. 函数说明

函数签名	功能说明
bool operator==(const forward_list& lhs, const forward_list& rhs)	相等比较运算符
bool operator!=(const forward_list& lhs, const forward_list& rhs)	不等比较运算符
bool operator<(const forward_list& lhs, const forward_list& rhs)	小于比较运算符
bool operator<=(const forward_list& lhs, const forward_list& rhs)	小于等于比较运算符
bool operator>(const forward_list& lhs, const forward_list& rhs)	大于比较运算符
bool operator>=(const forward_list& lhs, const forward_list& rhs)	大于等于比较运算符
void swap(forward_list& lhs, forward_list& rhs)	交换两个链表内容

2. 用法示例

1. 链表比较运算符

   std::forward_list<int> listA{1,2,3};
   std::forward_list<int> listB{1,2,3};
   std::forward_list<int> listC{1,3,5};// 1. 相等比较 
   bool eq = (listA == listB);  // true：元素数量相同且所有元素值相等 
   // 2. 不等比较 
   bool neq = (listA != listC);  // true：元素序列不同（2 vs 3）// 3. 小于比较 
   bool lt = (listA < listC);  // true：第二个元素不同元素2<3（字典序）// 4. 小于等于比较 
   bool le = (listA <= listB);  // true：两者完全相等 // 5. 大于比较 
   bool gt = (listC > listA);  // true：首个不同位置（第二个元素）3>2 // 6. 大于等于比较 
   bool ge = (listB >= listA);  // true：两者完全相等  

2. 链表交换操作

   // 7. 交换链表内容 
   std::forward_list<int> listX{10,20,30};
   std::forward_list<int> listY{40,50};swap(listX, listY);  
   // listX → {40,50}
   // listY → {10,20,30}
   

3. 详细说明

1. 元素类型要求
   比较运算符依赖元素类型的对应运算符（如 T::operator==）

2. 字典序规则

   {1,2} < {1,2,3}  // true（长度更短）
   {1,3} < {2,1}    // true（1<2决定结果）
   

3. 交换操作特性

   auto itX = listX.begin();  // 指向10 
   swap(listX, listY);
   // itX 仍有效 → 指向10（但已属于listY）
   

8. 关键特性总结

1. 单向链表：仅支持前向遍历，无反向迭代器
2. 高效插入/删除：任意位置插入/删除时间复杂度 O(1)
3. 无随机访问：不支持 operator[] 或 at() 等随机访问操作
4. 无 size()：计算元素数量需遍历整个链表（O(n) 复杂度）
5. 内存高效：每个节点仅需存储元素值和单个指针

使用建议：

• 优先使用 emplace_front() 和 emplace_after() 避免拷贝开销；
• 大数据量排序时使用成员函数 sort() 而非 std::sort() 算法。
• 在性能关键场景优先使用 front() 直接访问，但务必通过 empty() 前置检查防止崩溃。
• const版本是线程安全读取的基石。