前向迭代器上的 stable_partition [英] stable_partition on forward iterators

问题描述

1.在当前的标准草案中 std::stable_partition 是:

<块引用>

template双向迭代器 stable_partition(先是双向迭代器，最后是双向迭代器，谓词 pred)；

我没有发现 BidirectionalIterator 应该是双向迭代器的要求，但名字暗示是这样.(见下文)

2.在 SGI STL 中，规范是:

<块引用>

template ForwardIterator stable_partition(ForwardIterator 首先，ForwardIterator 最后，Predicate pred);

对类型的要求:ForwardIterator 是 Forward Iterator 的模型.

当前标准和 SGI 版本的复杂性规范相同:最多 N log N 次交换，如果有，则只有 O(N) 次交换足够的额外内存和谓词和投影的N 个应用程序.

3.libstdc++ 和 libc++ 看起来像:

templateForwardIterator stable_partition(ForwardIterator 首先，ForwardIterator 最后，Predicate pred);

在 GCC 和 Clang 中 std::stable_partition 确实适用于前向迭代器.例如:

int main() {std::forward_list列表{1, 4, 5, 2, 3, 0};std::stable_partition(list.begin(), list.end(), [](int i) { return i <3;});对于(自动 v:列表)std::cout <<v<<' ';}

编译并产生正确的输出.Microsoft 的编译器无法编译此代码(没有 -- 运算符).英特尔的一个成功了.

我有两个相关的问题:

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

编辑.

发现此条款:

<块引用>

如果算法的模板参数被命名为BidirectionalIterator、BidirectionalIterator1或BidirectionalIterator2，则模板参数应满足Cpp17BidirectionalIterator代码>要求.

那么，只剩下第二个问题了.

解决方案

首先，没有放弃支持，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).查看这里 和 这里.

1. In the current standard draft the specification of std::stable_partition is:

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

I didn't find the requirement that BidirectionalIterator should be a bidirectional iterator, but the name suggests so. (See below)

2. In the SGI STL, the specification 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.

The specification of complexity is the same for both, current standard and SGI, versions: at most N log N swaps, only O(N) swaps if there is enough extra memory and exactly N applications of the predicate and projection.

3. The declaration in libstdc++ and libc++ looks like:

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

In GCC and Clang std::stable_partition indeed works with forward iterators. For example:

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's compiler fails to compile this code (no -- operator). Intel's one succeeds.

I have two related questions:

• Does std::stable_partition accepts at least bidirectional iterators by the standard or the name BidirectionalIterator is misleading?
• If it indeed accepts only bidirectional iterators, why the support of forward iterators has been dropped?

Edit.

Found this clause:

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

So, only the second question remains.

解决方案

First of all, no support has been dropped, std::stable_partition has always required BidirectionalIterator by the standard. Which does not mean that the implementors of the library are disallowed to give less restrictions on input arguments (if it continues to comply with other parts of the standard ofc). And so Gcc, Clang and Intel use their rights and made the code even more generic. You can think of it as a compiler extension of standard library.

Having said that one may ask why standard requires BidirectionalIterator here. I suppose it is possible because the authors of the standard didn't see a way to comply with the complexity requirements without this requirement. It is possible that the authors of gcc found a way to do it better than anticipated by the standard. Looking at the gcc source code kinda confirms this. https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1613

EDIT:

I have dug through GCC library implementation and I think I get it. Implementation for ForwardIterator, BidirectionalIterator and RandomAccessIterator are different for std::stable_partition. This is due to different implementations of std::rotate which is used by the partitioning algorithm. And so, for forward iterator number of swaps is greater and can exceed (last - first) * log(last - first). Look here and here.

这篇关于前向迭代器上的 stable_partition的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！