如何正确使用splice_after为C++11 forward_list实现stable_partition

你的思路完全正确——利用forward_list的splice_after可以在O(n)时间、无额外内存分配/拷贝的情况下实现stable_partition，但你的代码在迭代器管理和splice_after的用法上踩了两个关键坑，我来帮你修正并解释清楚。

你的代码核心问题 #

1. splice_after的用法误解：splice_after(pos, list, iter)的作用是把iter后面的元素移动到pos的后面，而不是iter指向的元素。你本来想移动*iter，结果实际移动的是iter的下一个元素，这就是插入错误的根源。
2. 迭代器失效与遍历混乱：当你把元素从原列表移到positives后，iter指向的元素已经不在原列表里了，继续++iter会遍历positives的节点，完全偏离了原列表的遍历逻辑。

正确实现方案 #

解决问题的关键是用前驱迭代器操作——因为forward_list是单链表，所有修改操作都需要通过目标节点的前驱来完成，这样才能保证迭代器始终有效，并且正确移动目标元素。

template <typename T, typename UnaryPredicate>
void stable_partition(std::forward_list<T>& list, UnaryPredicate p) {
    std::forward_list<T> positives;
    auto prev_pos = positives.before_begin(); // 指向positives末尾元素的前驱
    auto prev_list = list.before_begin();     // 指向原列表当前元素的前驱

    // 遍历原列表：通过prev_list的下一个节点来检查元素
    while (std::next(prev_list) != list.end()) {
        auto current = std::next(prev_list); // 当前要检查的元素
        if (p(*current)) {
            // 把current指向的元素移动到positives的末尾
            // splice_after参数：目标前驱，源列表，源节点的前驱
            positives.splice_after(prev_pos, list, prev_list);
            // 更新positives的前驱到刚插入的元素位置，以便下次追加
            prev_pos = std::next(prev_pos);
            // 原列表的prev_list不需要移动：因为current被移走后，prev_list的下一个自动变成原current的下一个
        } else {
            // 元素不满足条件，原列表的前驱后移
            prev_list = current;
        }
    }

    // 把所有符合条件的元素拼接到原列表的开头
    list.splice_after(list.before_begin(), positives);
}

关键细节解释 #

• 前驱迭代器的必要性：forward_list没有反向迭代器，所有节点的修改（包括移动）都必须通过其前驱节点完成。splice_after(prev_target, source, prev_source)的语义是：将prev_source后面的节点移动到prev_target后面，这正好匹配我们移动current节点的需求（prev_list就是current的前驱）。
• 迭代器安全：prev_list始终指向原列表中存在的节点，移动元素后，原列表的链表结构自动调整，prev_list的下一个直接指向原current的下一个节点，不会出现迭代器失效的问题。
• 稳定性保证：我们按原列表的顺序逐个移动符合条件的元素到positives的末尾，最后拼接到原列表开头，完全保留了元素的原始相对顺序，符合stable_partition的要求。
• 复杂度：每个元素被检查一次，所有splice_after操作都是O(1)时间，整体复杂度O(n)，无内存分配和元素拷贝，完全符合你的设计目标。

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