为 forward_list 实施 stable_partition

Question

我想实现类似于 std::stable_partition 的东西，但是对于 c++11 的 forward_list。 stl 版本需要双向迭代器，但是通过使用特定于容器的方法，我相信我可以有效地获得相同的结果。

示例声明：

template <typename T, typename UnaryPredicate>
void stable_partition(std::forward_list<T>& list, UnaryPredicate p);

（虽然可以添加开始和结束迭代器，但为了简洁起见，我省略了它们。返回分区点也是如此）

我已经在我自己的列表类型上制定了算法来完成这个，但是我在 stl 中实现它时遇到了麻烦。

关键方法似乎是splice_after。其他方法需要内存分配和复制元素。

算法草图：

创建一个新的空列表。它将保持所有元素 p returns 为真。
遍历目标列表，根据调用p将项目添加到真实列表。
将真实列表连接到目标列表的开头。

通过适当的编码，这应该是线性时间（循环内的所有操作都可以在常数时间内完成）并且没有额外的内存分配或复制。

我正在尝试使用 splice_after 实现第二步，但我最终要么连接了错误的元素，要么使我的迭代器无效。

问题：

splice_after的正确用法是什么，让我避免在列表之间混合迭代器并插入正确的元素？

第一次尝试（我希望它成功）：

template <typename T, typename UnaryPredicate>
void stable_partition(std::forward_list<T>& list, UnaryPredicate p)
{
    std::forward_list<T> positives;
    auto positives_iter = positives.before_begin();

    for (auto iter = list.begin(); iter != list.end(); ++iter)
    {
        if (p(*iter))
            positives.splice_after(positives_iter, list, iter);
    }

    list.splice_after(list.before_begin(), positives);
}

不幸的是，这至少有一个重大缺陷：splice_after 在 iter 之后插入，插入了错误的元素。

此外，当元素移动到另一个列表时，递增 iter 现在会遍历错误的列表。

Answer 1

必须为 std::forward_list::splice_after 维护前面的迭代器使它有点棘手，但仍然很短：

template<class T, class UnaryPredicate>
std::array<std::forward_list<T>, 2>
stable_partition(std::forward_list<T>& list, UnaryPredicate p) {
    std::array<std::forward_list<T>, 2>  r;
    decltype(r[0].before_begin()) pos[2] = {r[0].before_begin(), r[1].before_begin()};
    for(auto i = list.before_begin(), ni = i, e = list.end(); ++ni != e; ni = i) {
        bool idx = p(*ni);
        auto& p = pos[idx];
        r[idx].splice_after(p, list, i);
        ++p;
    }
    return r;
}

用法示例：

template<class T>
void print(std::forward_list<T> const& list) {
    for(auto const& e : list)
        std::cout << e << ' ';
    std::cout << '\n';
}

int main() {
    std::forward_list<int> l{0,1,2,3,4,5,6};
    print(l);
    // Partition into even and odd elements.
    auto p = stable_partition(l, [](auto e) { return e % 2; });
    print(p[0]); // Even elements.
    print(p[1]); // Odd elements.
}

为 forward_list 实施 stable_partition

Implementing stable_partition for forward_list

c++

stl

singly-linked-list