目录前言一、定义及初始化1.定义 forward_list 对象2.初始化方式二、向 forward_list 对象中添加元素1.在头部添加元素2.在指定位置之后添加元素三、forward_list 常用迭代器四、forward_list 常用运算符五、forward_list 常用成员函数1.empty 成员函数2.front 成员函数3.push_front 成员函数4.pop_front 成员函数5.insert_after 成员函数6.erase_after 成员函数六、forward_list 特有成员函数1.merge 特有成员函数2.remove 特有成员函数3.remove_if 特有成员函数4.reverse 特有成员函数5.sort 特有成员函数6.unique 特有成员函数七、综合练习练习 1forward_list 基本操作练习 2使用 forward_list 特有成员函数练习 3使用 forward_list 实现一个简单的队列前言forward_list是 C11 引入的标准库容器定义在forward_list头文件中位于std命名空间内。它是一种单向链表单链表只支持从前往后遍历不支持随机访问但在链表头部的插入和删除操作非常高效。一、定义及初始化使用forward list必须包含头文件forward_list#include forward_list1.定义 forward_list 对象#include forward_list // 定义一个存储 int 类型的 forward_list std::forward_listint flist; // 定义一个存储 std::string 类型的 forward_list std::forward_liststd::string strFlist;2.初始化方式默认初始化创建一个空 forward_liststd::forward_listint flist; // 空 forward_list列表初始化std::forward_listint flist {1, 2, 3, 4, 5}; std::forward_listint flist2{1, 2, 3, 4, 5}; // 与上面等价使用另一个 forward_list 初始化std::forward_listint flist1 {1, 2, 3, 4, 5}; std::forward_listint flist2 flist1; // 拷贝初始化 std::forward_listint flist3(flist1); // 拷贝构造使用迭代器范围初始化std::forward_listint flist1 {1, 2, 3, 4, 5}; std::forward_listint flist2(flist1.begin(), flist1.end()); // 包含 flist1 的所有元素 // 从其他容器初始化 std::vectorint vec {6, 7, 8, 9, 10}; std::forward_listint flist3(vec.begin(), vec.end()); // 包含 vec 的所有元素使用填充构造函数// 注意forward_list 没有接受元素个数和初始值的构造函数 // 可以使用生成器或循环来填充 std::forward_listint flist; for (int i 0; i 5; i) { flist.push_front(10); } // 此时 flist 包含 {10, 10, 10, 10, 10}但顺序是反的 // 可以使用 reverse() 来反转 flist.reverse(); // 现在 flist 包含 {10, 10, 10, 10, 10}二、向 forward_list 对象中添加元素forward_list是单向链表因此只能在头部或指定位置之后添加元素。1.在头部添加元素push_front 成员函数功能在 forward_list 头部添加一个元素参数要添加的元素值返回值无std::forward_listint flist {2, 3, 4}; flist.push_front(1); // flist 现在包含 {1, 2, 3, 4}emplace_front 成员函数C11功能在 forward_list 头部直接构造一个元素参数构造元素所需的参数返回值无优点避免了额外的拷贝或移动操作比 push_front 更高效std::forward_liststd::pairint, std::string flist; flist.emplace_front(1, one); // 直接在头部构造 pair 对象 flist.push_front({2, two}); // 先构造临时 pair 对象再移动到头部2.在指定位置之后添加元素insert_after 成员函数功能在指定迭代器位置之后插入元素参数版本 1pos, value- 在迭代器 pos 之后插入 value版本 2pos, count, value- 在迭代器 pos 之后插入 count 个 value版本 3pos, first, last- 在迭代器 pos 之后插入迭代器范围 [first, last) 中的元素返回值指向新插入的第一个元素的迭代器std::forward_listint flist {1, 3, 4, 5}; // 在第一个元素之后插入元素 2 auto it flist.begin(); // 指向第一个元素 1 flist.insert_after(it, 2); // flist 现在包含 {1, 2, 3, 4, 5} // 在头部之后插入 2 个 0 it flist.begin(); // 指向第一个元素 1 flist.insert_after(it, 2, 0); // flist 现在包含 {1, 0, 0, 2, 3, 4, 5} // 在指定位置之后插入另一个 forward_list 的元素 std::forward_listint flist2 {6, 7, 8}; it flist.end(); // 注意forward_list 的 end() 返回的是尾后迭代器不能用于 insert_after // 应该找到最后一个元素 it flist.begin(); while (std::next(it) ! flist.end()) { it; } flist.insert_after(it, flist2.begin(), flist2.end()); // flist 现在包含 {1, 0, 0, 2, 3, 4, 5, 6, 7, 8}emplace_after 成员函数C11功能在指定迭代器位置之后直接构造一个元素参数pos- 插入位置之前的迭代器构造元素所需的参数返回值指向新构造元素的迭代器优点避免了额外的拷贝或移动操作std::forward_liststd::pairint, std::string flist; auto it flist.before_begin(); // 使用 before_begin() 获取首前迭代器 flist.emplace_after(it, 1, one); // 在头部之后构造 pair 对象三、forward_list 常用迭代器forward_list容器提供了多种迭代器类型用于遍历容器中的元素。需要注意的是forward_list的迭代器是前向迭代器只支持操作不支持--操作。前向迭代器begin()返回指向第一个元素的迭代器end()返回指向最后一个元素之后位置的迭代器before_begin()返回指向第一个元素之前位置的迭代器首前迭代器cbefore_begin()返回指向第一个元素之前位置的常量首前迭代器常量迭代器cbegin()返回指向第一个元素的常量前向迭代器cend()返回指向最后一个元素之后位置的常量前向迭代器使用示例std::forward_listint flist {1, 2, 3, 4, 5}; // 使用前向迭代器遍历 for (auto it flist.begin(); it ! flist.end(); it) { std::cout *it ; // 输出: 1 2 3 4 5 } std::cout std::endl; // 使用常量迭代器遍历不能修改元素 for (auto it flist.cbegin(); it ! flist.cend(); it) { std::cout *it ; // 输出: 1 2 3 4 5 // *it 10; // 错误常量迭代器不能修改元素 } std::cout std::endl; // 使用首前迭代器 auto before_first flist.before_begin(); // 在首前迭代器之后插入元素相当于在头部插入 flist.insert_after(before_first, 0); // flist 现在包含 {0, 1, 2, 3, 4, 5}四、forward_list 常用运算符forward_list类重载了多种运算符方便容器操作赋值运算符将一个 forward_list 赋值给另一个 forward_liststd::forward_listint flist1 {1, 2, 3}; std::forward_listint flist2; flist2 flist1; // flist2 现在包含 {1, 2, 3}比较运算符判断两个 forward_list 是否相等!判断两个 forward_list 是否不相等判断一个 forward_list 是否小于另一个 forward_list字典序判断一个 forward_list 是否小于或等于另一个 forward_list判断一个 forward_list 是否大于另一个 forward_list判断一个 forward_list 是否大于或等于另一个 forward_liststd::forward_listint flist1 {1, 2, 3}; std::forward_listint flist2 {1, 2, 4}; bool b1 (flist1 flist2); // false bool b2 (flist1 flist2); // true第三个元素 3 4五、forward_list 常用成员函数forward list l的成员函数含义l.empty()判断是否为空l.front()返回第一个元素的引用l.push_front()头插l.pop_front()头删l.insert_after()插入一个或多个元素,这个效率为常数l.erase_after()删除一个或多个元素l.swap()交换两个list的值l.clear()清空数据1.empty 成员函数功能判断 forward_list 是否为空参数无返回值如果 forward_list 为空返回true否则返回falsestd::forward_listint flist1; std::forward_listint flist2 {1, 2, 3}; std::cout flist1.empty(); // 输出: 1 (true) std::cout flist2.empty(); // 输出: 0 (false)2.front 成员函数功能返回 forward_list 中第一个元素的引用参数无返回值第一个元素的引用说明如果 forward_list 为空行为未定义std::forward_listint flist {1, 2, 3}; std::cout flist.front(); // 输出: 1 flist.front() 10; // flist 现在包含 {10, 2, 3}3.push_front 成员函数功能在 forward_list 头部添加一个元素参数要添加的元素值返回值无std::forward_listint flist {2, 3, 4}; flist.push_front(1); // flist 现在包含 {1, 2, 3, 4}4.pop_front 成员函数功能删除 forward_list 头部的一个元素参数无返回值无说明如果 forward_list 为空行为未定义std::forward_listint flist {1, 2, 3, 4}; flist.pop_front(); // flist 现在包含 {2, 3, 4} flist.pop_front(); // flist 现在包含 {3, 4}5.insert_after 成员函数功能在指定迭代器位置之后插入元素参数版本 1pos, value- 在迭代器 pos 之后插入 value版本 2pos, count, value- 在迭代器 pos 之后插入 count 个 value版本 3pos, first, last- 在迭代器 pos 之后插入迭代器范围 [first, last) 中的元素返回值指向新插入的第一个元素的迭代器std::forward_listint flist {1, 3, 4, 5}; // 在第一个元素之后插入元素 2 auto it flist.begin(); // 指向第一个元素 1 flist.insert_after(it, 2); // flist 现在包含 {1, 2, 3, 4, 5}6.erase_after 成员函数功能删除指定迭代器位置之后的元素参数版本 1pos- 删除迭代器 pos 之后的元素版本 2first, last- 删除从 first 之后到 last 之前的元素返回值指向被删除元素之后位置的迭代器std::forward_listint flist {1, 2, 3, 4, 5}; // 删除第一个元素之后的元素即第二个元素 auto it flist.begin(); // 指向第一个元素 1 flist.erase_after(it); // flist 现在包含 {1, 3, 4, 5} // 删除从第一个元素之后到第四个元素之前的元素 it flist.begin(); // 指向第一个元素 1 auto end_it flist.begin(); std::advance(end_it, 3); // 移动到第四个元素 5 之前的位置 flist.erase_after(it, end_it); // flist 现在包含 {1, 5}六、forward_list 特有成员函数orward list l特有成员函数含义l.merge()链表合并l.remove(val)删除所有和val相同元素l.remove_if()删除符合条件的元素l.reverse()反转链表中的元素l.sort()排序(默认为升序)l.splice_after()链表连结l.unique()删除重复元素1.merge 特有成员函数功能合并两个已排序的 forward_list参数other- 另一个已排序的 forward_list返回值无说明合并后other 变为空std::forward_listint flist1 {1, 3, 5}; std::forward_listint flist2 {2, 4, 6}; flist1.merge(flist2); // flist1 现在包含 {1, 2, 3, 4, 5, 6}flist2 为空2.remove 特有成员函数功能删除所有值等于指定值的元素参数要删除的值返回值无std::forward_listint flist {1, 2, 3, 2, 4, 2, 5}; flist.remove(2); // flist 现在包含 {1, 3, 4, 5}3.remove_if 特有成员函数功能删除所有满足指定条件的元素参数一个返回 bool 的函数对象或 lambda 表达式返回值无std::forward_listint flist {1, 2, 3, 4, 5, 6}; // 删除所有偶数 flist.remove_if([](int n) { return n % 2 0; }); // flist 现在包含 {1, 3, 5}4.reverse 特有成员函数功能反转 forward_list 中元素的顺序参数无返回值无std::forward_listint flist {1, 2, 3, 4, 5}; flist.reverse(); // flist 现在包含 {5, 4, 3, 2, 1}5.sort 特有成员函数功能对 forward_list 中的元素进行排序参数可选的比较函数返回值无std::forward_listint flist {5, 2, 8, 1, 9}; flist.sort(); // flist 现在包含 {1, 2, 5, 8, 9} // 使用自定义比较函数降序 flist.sort(std::greaterint()); // flist 现在包含 {9, 8, 5, 2, 1}6.unique 特有成员函数功能删除连续的重复元素只保留一个参数可选的比较函数返回值无std::forward_listint flist {1, 1, 2, 2, 2, 3, 4, 4, 5}; flist.unique(); // flist 现在包含 {1, 2, 3, 4, 5}七、综合练习练习 1forward_list 基本操作#include iostream #include forward_list int main() { // 创建并初始化 forward_list std::forward_listint flist {3, 4, 5}; // 在头部添加元素 flist.push_front(2); flist.push_front(1); // 输出当前 forward_list std::cout Current forward_list: ; for (int x : flist) { std::cout x ; } std::cout std::endl; // 访问元素 std::cout Front: flist.front() std::endl; // 删除头部元素 flist.pop_front(); // 输出修改后的 forward_list std::cout After pop_front: ; for (int x : flist) { std::cout x ; } std::cout std::endl; // 在指定位置之后插入元素 auto it flist.begin(); // 指向第一个元素 2 flist.insert_after(it, 10); // 输出插入后的 forward_list std::cout After insert_after: ; for (int x : flist) { std::cout x ; } std::cout std::endl; // 删除指定位置之后的元素 it flist.begin(); // 指向第一个元素 2 flist.erase_after(it); // 输出删除后的 forward_list std::cout After erase_after: ; for (int x : flist) { std::cout x ; } std::cout std::endl; // 检查 forward_list 状态 std::cout Empty: (flist.empty() ? Yes : No) std::endl; return 0; }练习 2使用 forward_list 特有成员函数#include iostream #include forward_list int main() { // 创建并初始化 forward_list std::forward_listint flist {5, 2, 8, 1, 9, 3, 7, 4, 6}; // 排序 flist.sort(); std::cout After sort: ; for (int x : flist) { std::cout x ; } std::cout std::endl; // 反转 flist.reverse(); std::cout After reverse: ; for (int x : flist) { std::cout x ; } std::cout std::endl; // 创建另一个 forward_list 并合并 std::forward_listint flist2 {10, 11, 12}; flist2.sort(); // 合并前需要排序 flist.sort(); // 合并前需要排序 flist.merge(flist2); std::cout After merge: ; for (int x : flist) { std::cout x ; } std::cout std::endl; std::cout flist2 size: std::distance(flist2.begin(), flist2.end()) std::endl; // 应该为 0 // 添加重复元素并去重 flist.push_front(5); flist.push_front(5); flist.push_front(7); std::cout Before unique: ; for (int x : flist) { std::cout x ; } std::cout std::endl; flist.sort(); // 去重前最好先排序确保重复元素连续 flist.unique(); std::cout After unique: ; for (int x : flist) { std::cout x ; } std::cout std::endl; // 删除特定元素 flist.remove(5); std::cout After remove 5: ; for (int x : flist) { std::cout x ; } std::cout std::endl; // 删除满足条件的元素 flist.remove_if([](int n) { return n 8; }); std::cout After remove_if (8): ; for (int x : flist) { std::cout x ; } std::cout std::endl; return 0; }练习 3使用 forward_list 实现一个简单的队列#include iostream #include forward_list class Queue { private: std::forward_listint flist; // 用于跟踪尾部位置 std::forward_listint::iterator tail; // 更新尾部迭代器 void updateTail() { if (flist.empty()) { tail flist.before_begin(); } else { tail flist.begin(); while (std::next(tail) ! flist.end()) { tail; } } } public: Queue() : tail(flist.before_begin()) {} // 入队 void enqueue(int value) { if (flist.empty()) { flist.push_front(value); } else { // 如果 tail 无效更新它 if (tail flist.end() || std::next(tail) ! flist.end()) { updateTail(); } flist.insert_after(tail, value); tail; // 更新 tail 到新添加的元素 } } // 出队 void dequeue() { if (!flist.empty()) { flist.pop_front(); updateTail(); // 更新 tail } } // 获取队首元素 int front() { if (!flist.empty()) { return flist.front(); } return -1; // 表示队列为空 } // 检查是否为空 bool empty() { return flist.empty(); } // 获取队列大小 size_t size() { return std::distance(flist.begin(), flist.end()); } // 打印队列 void print() { std::cout Queue: ; for (int x : flist) { std::cout x ; } std::cout std::endl; } }; int main() { Queue q; // 入队 q.enqueue(1); q.enqueue(2); q.enqueue(3); q.enqueue(4); q.enqueue(5); q.print(); // 输出: Queue: 1 2 3 4 5 // 出队 q.dequeue(); q.dequeue(); q.print(); // 输出: Queue: 3 4 5 // 获取队首元素 std::cout Front: q.front() std::endl; // 输出: Front: 3 // 检查队列状态 std::cout Size: q.size() std::endl; // 输出: Size: 3 std::cout Is empty: (q.empty() ? Yes : No) std::endl; // 输出: Is empty: No return 0; }