c++ - 前向迭代器上的 stable_partition

Question

1. 在当前的标准草案中，std::stable_partition 的规范 is :

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

我没有发现 Bi DirectionIterator 应该是双向迭代器的要求，但名称表明如此。(见下文)

2. 在SGI STL中，规范is :

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

Requirements on types: ForwardIterator is a model of Forward Iterator.

当前标准和 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 << ' ';
}

compiles and produces the correct output 。 Microsoft 的编译器无法编译此代码(没有 -- 运算符)。英特尔的成功。

我有两个相关问题:

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

编辑。

找到this clause :

If an algorithm's template parameter is named BidirectionalIterator, BidirectionalIterator1, or BidirectionalIterator2, the template argument shall meet the Cpp17BidirectionalIterator requirements.

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

Answer 1

首先，没有放弃支持，std::stable_partition 始终需要标准的 Bi DirectionIterator。这并不意味着不允许库的实现者对输入参数给予较少的限制(如果它继续遵守 ofc 标准的其他部分)。因此，Gcc、Clang 和 Intel 使用他们的权利，使代码变得更加通用。您可以将其视为标准库的编译器扩展。

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

编辑:

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