C++ forward_list 教程

forward_list 是 C++ 标准库中的单链表容器,它支持从容器的任何位置快速插入和删除元素,但只能单向遍历。以下是关于 forward_list 的详细教程:

1. 头文件与基本概念

使用 forward_list 前需要包含头文件:

#include <forward_list>

forward_list 的特点:

  • 单向链表,每个节点只指向下一个节点
  • 不支持随机访问(无法通过下标直接访问元素)
  • 插入和删除操作效率高(O(1) 时间复杂度)
  • 相比 list(双向链表)节省空间,因为每个节点只需维护一个指针

2. 创建与初始化

#include <iostream>
#include <forward_list>

int main() {
    // 1. 默认构造函数 - 创建空链表
    std::forward_list<int> flist1;

    // 2. 初始化列表构造函数
    std::forward_list<int> flist2 = {10, 20, 30, 40};

    // 3. 指定大小和初始值
    std::forward_list<int> flist3(5, 100); // 5个元素,每个都是100

    // 4. 从另一个容器复制
    std::forward_list<int> flist4(flist2);

    // 5. 使用迭代器范围初始化
    std::forward_list<int> flist5(++flist2.begin(), flist2.end()); // 从第二个元素到末尾
}

3. 基本操作

插入元素
#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> flist = {10, 20, 30};

    // 在链表前插入元素
    flist.push_front(5);  // 链表现在是: 5 -> 10 -> 20 -> 30

    // 在指定位置后插入元素
    auto it = flist.begin();  // 指向5
    flist.insert_after(it, 7);  // 在5后插入7,链表变为: 5 -> 7 -> 10 -> 20 -> 30

    // 插入多个元素
    flist.insert_after(++it, {8, 9});  // 在7后插入8和9

    // emplace系列函数更高效
    flist.emplace_front(3);  // 在头部构造元素3
    flist.emplace_after(it, 6);  // 在迭代器it后构造元素6
}
删除元素
#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> flist = {3, 5, 7, 8, 9, 10, 20, 30};

    // 删除头部元素
    flist.pop_front();  // 移除3,链表现在是: 5 -> 7 -> 8 -> 9 -> 10 -> 20 -> 30

    // 删除指定位置后的元素
    auto it = flist.begin();  // 指向5
    flist.erase_after(it);  // 删除7,链表变为: 5 -> 8 -> 9 -> 10 -> 20 -> 30

    // 删除范围内的元素
    auto start = ++flist.begin();  // 指向8
    auto end = flist.end();
    flist.erase_after(start, end);  // 删除从8到末尾的所有元素,链表现在是: 5

    // 删除所有值为特定值的元素
    flist.remove(5);  // 链表现在为空
}
访问元素
#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> flist = {10, 20, 30, 40};

    // 访问第一个元素
    std::cout << "第一个元素: " << flist.front() << std::endl;  // 输出10

    // 遍历链表 - 使用迭代器
    for (auto it = flist.begin(); it != flist.end(); ++it) {
        std::cout << *it << " ";  // 输出: 10 20 30 40
    }

    // C++11 范围for循环更简洁
    for (int num : flist) {
        std::cout << num << " ";
    }
}

4. 常用方法

方法名 描述
empty() 判断链表是否为空
size() 不支持(单链表无法高效获取大小,需遍历整个链表)
max_size() 返回链表可能容纳的最大元素数
front() 返回第一个元素的引用
assign() 分配新内容替换链表中的元素
push_front() 在链表头部插入元素
pop_front() 删除链表头部元素
insert_after() 在指定位置后插入元素
erase_after() 删除指定位置后的元素
remove() 删除所有值等于给定值的元素
remove_if() 删除满足特定条件的元素
reverse() 反转链表中元素的顺序
sort() 对链表中的元素进行排序(升序)
merge() 合并两个已排序的链表
unique() 删除连续重复的元素,只保留一个
splice_after() 将另一个链表的元素插入到当前链表的指定位置后

5. 示例:使用 forward_list 实现简单的学生管理系统

#include <iostream>
#include <forward_list>
#include <string>

struct Student {
    std::string name;
    int age;
    double score;

    // 构造函数
    Student(const std::string& n, int a, double s) 
        : name(n), age(a), score(s) {}
};

int main() {
    std::forward_list<Student> students;

    // 添加学生
    students.emplace_front("Alice", 20, 95.5);
    students.emplace_front("Bob", 21, 88.0);
    students.emplace_front("Charlie", 19, 92.3);

    // 打印所有学生信息
    std::cout << "学生列表:" << std::endl;
    for (const auto& student : students) {
        std::cout << "姓名: " << student.name 
                  << ", 年龄: " << student.age 
                  << ", 分数: " << student.score << std::endl;
    }

    // 查找并修改学生信息
    for (auto& student : students) {
        if (student.name == "Bob") {
            student.score = 90.0;  // 更新Bob的分数
            std::cout << "Bob的新分数: " << student.score << std::endl;
            break;
        }
    }

    // 删除年龄小于20的学生
    students.remove_if([](const Student& s) {
        return s.age < 20;
    });

    std::cout << "更新后的学生列表:" << std::endl;
    for (const auto& student : students) {
        std::cout << "姓名: " << student.name 
                  << ", 年龄: " << student.age 
                  << ", 分数: " << student.score << std::endl;
    }
}

6. 注意事项

  1. 迭代器失效:在插入或删除元素后,指向被修改节点的迭代器会失效。

  2. 性能考虑

    • 插入/删除操作在已知位置时是 O(1)
    • 查找操作是 O(n)
    • 不支持随机访问(如 []at()
  3. 适用场景

    • 需要频繁在中间插入/删除元素
    • 不需要双向遍历
    • 内存使用效率很重要

通过本教程,你应该能够理解 forward_list 的基本概念、操作和适用场景。在实际编程中,根据需求选择合适的容器类型非常重要。

2 条评论

  • @ 2025-6-9 22:47:48

    C++ forward_list 链表

    🌟 什么是 forward_list

    在 C++ 中,forward_list单向链表(Singly Linked List)的实现。它属于标准模板库(STL)的一部分,定义在头文件 <forward_list> 中。

    ✅ 特点:

    • 每个节点只包含一个指向下一个节点的指针。
    • 不支持随机访问(不能用下标操作)。
    • 插入和删除效率高,适合频繁修改的场景。
    • 相比 list(双向链表),占用内存更少。

    📦 包含头文件

    #include <iostream>
    #include <forward_list>  // 使用 forward_list 所需头文件
    using namespace std;
    

    🧱 基本使用示例

    1. 定义并初始化 forward_list

    int main() {
        // 创建一个整型 forward_list 并初始化
        forward_list<int> flist = {1, 2, 3, 4};
    
        // 或者创建空链表再添加元素
        forward_list<int> emptyList;
    
        return 0;
    }
    

    2. 遍历 forward_list

    由于 forward_list 不支持 [] 下标访问,我们需要使用迭代器来遍历:

    cout << "Forward list elements: ";
    for (auto it = flist.begin(); it != flist.end(); ++it) {
        cout << *it << " ";  // 输出当前节点值
    }
    cout << endl;
    

    或者使用范围 for 循环(C++11 及以上):

    for (int val : flist) {
        cout << val << " ";
    }
    cout << endl;
    

    ✨ 插入元素

    forward_list 提供了多种插入方式,常见的是在头部或某个位置之后插入。

    在开头插入(push_front)

    flist.push_front(0);  // 在最前面插入 0
    

    在某个节点后插入(insert_after)

    auto it = flist.insert_after(flist.before_begin(), 5);
    // 在链表最前面插入 5,并返回插入后的迭代器
    

    也可以连续插入:

    it = flist.insert_after(it, 6);  // 在刚刚插入的 5 后面插入 6
    it = flist.insert_after(it, 7);
    

    此时链表为:5 6 7 0 1 2 3 4


    ❌ 删除元素

    删除开头元素(pop_front)

    flist.pop_front();  // 删除第一个元素
    

    删除某个位置后的元素(erase_after)

    flist.erase_after(flist.before_begin());  // 删除第一个元素
    

    也可以传入一个迭代器来删除指定位置后面的元素:

    auto it = flist.begin();
    ++it;  // 移动到第二个元素
    flist.erase_after(it);  // 删除第三个元素
    

    🔍 查找与修改元素

    虽然 forward_list 没有直接提供查找函数,但我们可以手动查找:

    bool found = false;
    for (auto it = flist.begin(); it != flist.end(); ++it) {
        if (*it == 3) {
            cout << "Found value 3" << endl;
            found = true;
            break;
        }
    }
    if (!found) {
        cout << "Value 3 not found" << endl;
    }
    

    🔄 修改元素值

    for (auto it = flist.begin(); it != flist.end(); ++it) {
        if (*it == 2) {
            *it = 20;  // 将值为 2 的元素改为 20
        }
    }
    

    📐 其他常用操作

    判断是否为空

    if (flist.empty()) {
        cout << "List is empty!" << endl;
    } else {
        cout << "List is not empty!" << endl;
    }
    

    获取链表长度(线性时间 O(n))

    int size = distance(flist.begin(), flist.end());
    cout << "Size of forward_list: " << size << endl;
    

    ⚠️ 注意:不像 vectorforward_list 没有 .size() 方法,获取长度是线性复杂度。


    📝 综合示例代码

    #include <iostream>
    #include <forward_list>
    using namespace std;
    
    int main() {
        // 创建 forward_list
        forward_list<int> flist = {1, 2, 3, 4};
    
        // 插入元素
        flist.push_front(0);  // 头部插入
        flist.insert_after(flist.before_begin(), 5);  // 最前面插入
    
        // 遍历输出
        cout << "Current list: ";
        for (int val : flist) {
            cout << val << " ";
        }
        cout << endl;
    
        // 查找并修改
        for (auto it = flist.begin(); it != flist.end(); ++it) {
            if (*it == 3) {
                *it = 30;
            }
        }
    
        // 删除元素
        flist.pop_front();  // 删除头部
        flist.erase_after(flist.begin());  // 删除第二个元素
    
        // 再次输出
        cout << "After modifications: ";
        for (int val : flist) {
            cout << val << " ";
        }
        cout << endl;
    
        return 0;
    }
    

    🧠 总结

    操作 方法
    创建链表 forward_list<int> flist = {1,2,3};
    插入头部 flist.push_front(0);
    插入任意位置后 flist.insert_after(it, value);
    删除头部 flist.pop_front();
    删除某位置后 flist.erase_after(it);
    遍历 使用 begin()end() 迭代器
    是否为空 flist.empty()

    📘 适用场景

    • 需要频繁插入/删除中间节点时;
    • 对内存要求严格(比 list 轻量);
    • 不需要随机访问的场合。

    如果你想要一个 双向链表,可以使用 std::list,功能更强大但也更占内存。

    如需进一步讲解 splice_after、合并排序等高级操作,也可以继续问我 😄

    • @ 2025-6-9 22:47:17

      C++ forward_list 教程

      forward_list 是 C++ 标准库中的单链表容器,它支持从容器的任何位置快速插入和删除元素,但只能单向遍历。以下是关于 forward_list 的详细教程:

      1. 头文件与基本概念

      使用 forward_list 前需要包含头文件:

      #include <forward_list>
      

      forward_list 的特点:

      • 单向链表,每个节点只指向下一个节点
      • 不支持随机访问(无法通过下标直接访问元素)
      • 插入和删除操作效率高(O(1) 时间复杂度)
      • 相比 list(双向链表)节省空间,因为每个节点只需维护一个指针

      2. 创建与初始化

      #include <iostream>
      #include <forward_list>
      
      int main() {
          // 1. 默认构造函数 - 创建空链表
          std::forward_list<int> flist1;
      
          // 2. 初始化列表构造函数
          std::forward_list<int> flist2 = {10, 20, 30, 40};
      
          // 3. 指定大小和初始值
          std::forward_list<int> flist3(5, 100); // 5个元素,每个都是100
      
          // 4. 从另一个容器复制
          std::forward_list<int> flist4(flist2);
      
          // 5. 使用迭代器范围初始化
          std::forward_list<int> flist5(++flist2.begin(), flist2.end()); // 从第二个元素到末尾
      }
      

      3. 基本操作

      插入元素
      #include <iostream>
      #include <forward_list>
      
      int main() {
          std::forward_list<int> flist = {10, 20, 30};
      
          // 在链表前插入元素
          flist.push_front(5);  // 链表现在是: 5 -> 10 -> 20 -> 30
      
          // 在指定位置后插入元素
          auto it = flist.begin();  // 指向5
          flist.insert_after(it, 7);  // 在5后插入7,链表变为: 5 -> 7 -> 10 -> 20 -> 30
      
          // 插入多个元素
          flist.insert_after(++it, {8, 9});  // 在7后插入8和9
      
          // emplace系列函数更高效
          flist.emplace_front(3);  // 在头部构造元素3
          flist.emplace_after(it, 6);  // 在迭代器it后构造元素6
      }
      
      删除元素
      #include <iostream>
      #include <forward_list>
      
      int main() {
          std::forward_list<int> flist = {3, 5, 7, 8, 9, 10, 20, 30};
      
          // 删除头部元素
          flist.pop_front();  // 移除3,链表现在是: 5 -> 7 -> 8 -> 9 -> 10 -> 20 -> 30
      
          // 删除指定位置后的元素
          auto it = flist.begin();  // 指向5
          flist.erase_after(it);  // 删除7,链表变为: 5 -> 8 -> 9 -> 10 -> 20 -> 30
      
          // 删除范围内的元素
          auto start = ++flist.begin();  // 指向8
          auto end = flist.end();
          flist.erase_after(start, end);  // 删除从8到末尾的所有元素,链表现在是: 5
      
          // 删除所有值为特定值的元素
          flist.remove(5);  // 链表现在为空
      }
      
      访问元素
      #include <iostream>
      #include <forward_list>
      
      int main() {
          std::forward_list<int> flist = {10, 20, 30, 40};
      
          // 访问第一个元素
          std::cout << "第一个元素: " << flist.front() << std::endl;  // 输出10
      
          // 遍历链表 - 使用迭代器
          for (auto it = flist.begin(); it != flist.end(); ++it) {
              std::cout << *it << " ";  // 输出: 10 20 30 40
          }
      
          // C++11 范围for循环更简洁
          for (int num : flist) {
              std::cout << num << " ";
          }
      }
      

      4. 常用方法

      方法名 描述
      empty() 判断链表是否为空
      size() 不支持(单链表无法高效获取大小,需遍历整个链表)
      max_size() 返回链表可能容纳的最大元素数
      front() 返回第一个元素的引用
      assign() 分配新内容替换链表中的元素
      push_front() 在链表头部插入元素
      pop_front() 删除链表头部元素
      insert_after() 在指定位置后插入元素
      erase_after() 删除指定位置后的元素
      remove() 删除所有值等于给定值的元素
      remove_if() 删除满足特定条件的元素
      reverse() 反转链表中元素的顺序
      sort() 对链表中的元素进行排序(升序)
      merge() 合并两个已排序的链表
      unique() 删除连续重复的元素,只保留一个
      splice_after() 将另一个链表的元素插入到当前链表的指定位置后

      5. 示例:使用 forward_list 实现简单的学生管理系统

      #include <iostream>
      #include <forward_list>
      #include <string>
      
      struct Student {
          std::string name;
          int age;
          double score;
      
          // 构造函数
          Student(const std::string& n, int a, double s) 
              : name(n), age(a), score(s) {}
      };
      
      int main() {
          std::forward_list<Student> students;
      
          // 添加学生
          students.emplace_front("Alice", 20, 95.5);
          students.emplace_front("Bob", 21, 88.0);
          students.emplace_front("Charlie", 19, 92.3);
      
          // 打印所有学生信息
          std::cout << "学生列表:" << std::endl;
          for (const auto& student : students) {
              std::cout << "姓名: " << student.name 
                        << ", 年龄: " << student.age 
                        << ", 分数: " << student.score << std::endl;
          }
      
          // 查找并修改学生信息
          for (auto& student : students) {
              if (student.name == "Bob") {
                  student.score = 90.0;  // 更新Bob的分数
                  std::cout << "Bob的新分数: " << student.score << std::endl;
                  break;
              }
          }
      
          // 删除年龄小于20的学生
          students.remove_if([](const Student& s) {
              return s.age < 20;
          });
      
          std::cout << "更新后的学生列表:" << std::endl;
          for (const auto& student : students) {
              std::cout << "姓名: " << student.name 
                        << ", 年龄: " << student.age 
                        << ", 分数: " << student.score << std::endl;
          }
      }
      

      6. 注意事项

      1. 迭代器失效:在插入或删除元素后,指向被修改节点的迭代器会失效。

      2. 性能考虑

        • 插入/删除操作在已知位置时是 O(1)
        • 查找操作是 O(n)
        • 不支持随机访问(如 []at()
      3. 适用场景

        • 需要频繁在中间插入/删除元素
        • 不需要双向遍历
        • 内存使用效率很重要

      通过本教程,你应该能够理解 forward_list 的基本概念、操作和适用场景。在实际编程中,根据需求选择合适的容器类型非常重要。

      • 1