C++学习笔记（三十三）——forward_list

一、std::forward_list

(1) forward_list与其适用场景

std::forward_list 是 C++的STL中的单向链表（Singly Linked List），它相比 std::list（双向链表）更轻量，适用于仅需要单向遍历的场景。

主要特点：

• 单向链表：只能向前遍历，不支持双向迭代。
• 低内存开销：比 std::list 占用更少的内存（少一个指针）。
• 适合频繁插入和删除：由于其链表结构，插入和删除操作比 std::vector 高效（避免了数据移动）。
• 不支持随机访问：不像 std::vector，无法使用 operator[] 或 at() 访问元素。

适用场景：

• 仅需单向遍历的数据结构
• 频繁头部插入/删除的场景（push_front()、pop_front() 高效），如队列、哈希链表、日志存储等。
• 内存敏感的应用（比 std::list 更节省空间）

头文件：

#include <forward_list>

（2） forward_list vs list

二、forward_list 的常用函数

注意：
std::forward_list不提供返回其大小的函数。

三、forward_list的基本使用

(1) 创建 forward_list

示例：

#include <iostream>
using namespace std;
#include <forward_list>

int main() {
    forward_list<int> fl1 = { 1, 2, 3, 4, 5 };  // 列表初始化
    forward_list<int> fl2(5, 10);  // 5 个 10

    for (int num : fl1)
    {
        cout << num << " ";
    } 
    cout << endl;

    for (int num : fl2)
    {
        cout << num << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}

(2) 插入元素

示例：

#include <iostream>
using namespace std;
#include <forward_list>

int main() {
    forward_list<int> fl = { 10, 20, 30 };

    fl.push_front(5);  // 在头部插入 5

    auto it = fl.begin();
    fl.insert_after(it, 15);  // 在 10 之后插入 15

    cout << "After insertions: ";
    for (int num : fl)
    {
        cout << num << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}

注意：

• push_front()（在链表头部插入元素）
• emplace_front()（在头部插入元素，构造效率更高）
• insert_after()（在指定位置后插入）
• emplace_after()（在指定位置后插入）

(3) 删除元素

示例：

#include <iostream>
using namespace std;
#include <forward_list>

int main() {
    forward_list<int> fl = {10, 20, 30, 40, 50};

    fl.pop_front();  // 删除头部元素 10
    fl.remove(30);   // 删除所有值等于 30 的元素

    cout << "After deletions: ";
    for (int num : fl)
    {
        cout << num << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}

(4) 反转、排序

示例：

#include <iostream>
using namespace std;
#include <forward_list>

int main() {
    forward_list<int> fl = { 50, 10, 40, 30, 20 };

    fl.sort();  // 排序
    fl.reverse();  // 反转

    cout << "Sorted and Reversed List: ";
    for (int num : fl)
    {
        cout << num << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}

注意：

• sort() 默认为升序排列，再执行reverse()后为逆序排列；

四、forward_list 的应用

（1）维护一个日志记录系统

要求：

• 每次新的日志添加到前面（头部插入）。
• 只保留最近 N 条日志。

示例：

#include <iostream>
using namespace std;
#include <forward_list>
#include <string>

#define MAX_LOGS 5  // 最大日志条数

class LogSystem {
    forward_list<string> logs;
    int size = 0;

public:
    void addLog(const string& log) 
    {
        logs.push_front(log);  // 头部插入最新日志
        if (++size > MAX_LOGS)
        {
            pop_back();  // 超过最大数量时删除最后一条
            --size;
        }
    }

    void pop_back() 
    {
        if (logs.empty()) 
            return;

        auto it = logs.begin();
        auto prev = logs.before_begin();

        while (std::next(it) != logs.end()) // 找到倒数第二个元素
        { 
            prev = it;
            ++it;
        }

        logs.erase_after(prev);  // 删除最后一个元素
    }

    void showLogs() 
    {
        cout << "Recent Logs:" << endl;
        for (const auto& log : logs)
        {
            cout << log << endl;
        }
    }
};

int main() {
    LogSystem logSys;
    logSys.addLog("Log 1");
    logSys.addLog("Log 2");
    logSys.addLog("Log 3");
    logSys.addLog("Log 4");
    logSys.addLog("Log 5");
    logSys.addLog("Log 6");  // 触发删除最早的 Log 1
    logSys.showLogs();

    system("pause");
    return 0;
}

注意：
std::forward_list不提供pop_back()函数，使用则需要自己编写相应的函数。