C++如何跟踪std::forward_list首元素完成指定插入删除操作

问题根源 #

std::forward_list是单向链表实现，before_begin()返回的首前迭代器本质指向链表内部的哨兵节点，该节点的next指针永远指向当前链表的首元素。调用emplace_front/push_front做头部插入时，只会修改哨兵节点的next指向新插入元素，因此提前保存的首前迭代器的后继会变成新插入的元素，erase_after(it)自然会删掉新插入的元素而非原首元素。

另外要明确：std::forward_list的插入操作不会使任何指向已存在元素的迭代器失效，只有被删除元素对应的迭代器才会失效，这是后续方案的核心实现依据。

可行方案 #

方案1：O(1) 插入删除，仅需一次迭代器更新 #

核心逻辑：原首元素的直接前驱节点，在完成第一次头部插入后就不会再因为头部插入改变next指向——所有后续头部插入的元素都会被放在哨兵节点和这个前驱节点之间，不会修改该前驱节点的next指针，因此该前驱节点的迭代器自增后永远指向原首元素。
操作步骤：

• 初始状态下，先给存储迭代器赋初始值：auto stored_it = fl.before_begin(); 此时自增stored_it刚好指向原首元素，兼容无头部插入的场景。
• 第一次执行头部插入（emplace_front/push_front/insert_after(fl.before_begin(), ...)）后，将stored_it更新为当前链表的首元素迭代器fl.begin()即可。
• 后续无论再做多少次头部插入，都不需要更新stored_it，它的自增结果永远是原首元素。
• 要删除原首元素时，直接调用fl.erase_after(stored_it)即可。

对应修改后的测试代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    forward_list<int> fl = { 20, 30, 40, 50 };
    auto stored_it = fl.before_begin(); // 初始值适配无插入场景
    fl.emplace_front(10);
    stored_it = fl.begin(); // 第一次头部插入后更新存储迭代器，指向新插入的10
    // 若后续继续头部插入，比如fl.emplace_front(5)，不需要更新stored_it
    fl.erase_after(stored_it);
    cout << "Element of the list are:" << endl;
    for (auto it = fl.begin(); it != fl.end(); ++it)
        cout << *it << " "; // 输出10 30 40 50，符合预期
    return 0;
}

如果插入操作不只是在头部，还可能在stored_it和原首元素之间插入元素，只需要在这类插入完成后，将stored_it更新为新插入元素的迭代器即可，依然保持O(1)效率。

方案2：插入无额外开销，删除时遍历找前驱 #

如果不想在插入阶段做任何迭代器维护，可以直接保存指向原首元素的迭代器，删除时再查找它的前驱：

• 初始时直接保存原首元素迭代器：auto original_first = fl.begin(); 这个迭代器永远指向原首元素，不会因为任何插入操作失效。
• 要删除原首元素时，从首前迭代器开始遍历，找到后继等于original_first的迭代器，调用erase_after删除即可。

示例代码片段：

// 初始保存原首元素
auto original_first = fl.begin();
// 执行任意插入操作，不需要维护迭代器
fl.emplace_front(10);
fl.emplace_front(5);
// 删除时遍历找前驱
auto prev = fl.before_begin();
while (next(prev) != original_first) {
    ++prev;
}
fl.erase_after(prev); // 成功删除原首元素20

这个方案的缺点是删除操作的时间复杂度和原首元素前的元素个数成正比，适合头部插入元素不多的场景。

内容的提问来源于stack exchange，提问作者wznmickey