前向迭代器上的 stable_partition

Question

1. 在目前的标准草案中，规范std::stable_partition 是：

template<class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(
    BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

我没有找到BidirectionalIterator应该是双向迭代器的要求，但名称表明是这样。（见下文）

2. 在SGI STL中，规范是：

template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(
    ForwardIterator first, ForwardIterator last, Predicate pred);

对类型的要求：ForwardIterator是前向迭代器的模型。

当前标准和 SGI 版本的复杂性规范是相同的：最多N log N交换，只有O(N)在有足够的额外内存和N谓词和投影的准确应用时才交换。

3. libstdc++和libc++ 中 的声明如下所示：

template<typename ForwardIterator, typename Predicate>
ForwardIterator stable_partition(
    ForwardIterator first, ForwardIterator last, Predicate pred);

在 GCC 和 Clang 中std::stable_partition确实可以使用前向迭代器。例如：

int main() {
    std::forward_list<int> list{1, 4, 5, 2, 3, 0};
    std::stable_partition(list.begin(), list.end(), [](int i) { return i < 3;});

    for (auto v : list)
        std::cout << v << ' ';
}

编译并产生正确的输出。Microsoft 的编译器无法编译此代码（无--运算符）。英特尔的一个成功了。

我有两个相关的问题：

• 标准是否std::stable_partition至少接受双向迭代器，或者名称BidirectionalIterator是否具有误导性？
• 如果它确实只接受双向迭代器，为什么放弃了对前向迭代器的支持？

编辑。

发现这个条款：

如果算法的模板参数名为BidirectionalIterator、BidirectionalIterator1、 或BidirectionalIterator2，则模板参数应满足Cpp17BidirectionalIterator要求。

所以，只剩下第二个问题了。

Answer 1

首先，没有任何支持被丢弃，std::stable_partition一直BidirectionalIterator是标准所要求的。这并不意味着库的实现者不允许对输入参数提供较少的限制（如果它继续遵守标准 ofc 的其他部分）。因此 Gcc、Clang 和 Intel 使用他们的权利并使代码更加通用。您可以将其视为标准库的编译器扩展。

话虽如此，人们可能会问为什么BidirectionalIterator这里需要标准。我想这是可能的，因为标准的作者没有看到没有这个要求就符合复杂性要求的方法。gcc 的作者可能找到了一种比标准预期的更好的方法。查看 gcc 源代码有点证实了这一点。https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1613

编辑：

我已经深入研究了 GCC 库的实现，我想我明白了。实施ForwardIterator，BidirectionalIterator并RandomAccessIterator针对不同的std::stable_partition。这是由于std::rotate分区算法使用了不同的实现。因此，对于前向迭代器，交换次数更大并且可以超过(last - first) * log(last - first)。看这里和这里。

Answer 2

这个问题似乎有历史原因，而不是数学原因。翻阅Alexander Stepanov的论文，我发现了这篇：“分区和相关函数”。

\n\n

其中包含以下段落：

\n\n

\n

备注：有趣的是，这个优秀的算法并不在需要双向迭代器进行分区的 C++ 标准中。自从 80 年代中期我第一次在 CACM 的 Bentley\xe2\x80\x99s 专栏中读到它以来，我已经了解、实现和教授这个算法很长一段时间了 \xe2\x80\x93 。但我最初的 STL 提案确实以某种方式为 和指定了双向迭代器。这两个问题都在 SGI STL 中得到了纠正，但大多数供应商仍然落后。这件小事已经困扰我十多年了；最麻烦的部分是遗漏的事实。它是怎么发生的？我怀疑这个解释非常简单：虽然在 90 年代初期，我已经理解了将每种算法减少到最低要求的想法，而且我也知道，当我们对数据了解更多时，可以使用更好的算法来实现相同的操作。当它们被应用时，我还没有完全意识到需要为最弱的情况提供一种算法（如果这样的算法可用）。又花了几年时间才理解 \xe2\x80\x9c 填充算法空间的重要性。\xe2\x80\x9dpartitionstable_partition

\n

\n\n

下面的简单算法

\n\n

template <typename I, // I models Forward Iterator\n          typename N, // N models Integer\n          typename P> // P models Unary Predicate\npair<I, I> stable_partition_inplace_n(I f, N n, P p)\n{\n    if (n == 0) return make_pair(f, f);\n    if (n == 1) {\n        I l = successor(f);\n        if (p(*f)) l = f;\n        return make_pair(f, l);\n    }\n    pair<I, I> i = stable_partition_inplace_n(f, n/2, p);\n    pair<I, I> j = stable_partition_inplace_n(i.second, n \xe2\x80\x93 n/2, p);\n    return make_pair(rotate(i.first, i.second, j.first), j.second);\n}\n

\n\n

该论文中给出了。它与前向迭代器一起使用，并O(N log N)在最坏的情况下执行交换。

\n