为什么C++标准要求std :: partition满足不同类型迭代器的不同复杂性？

Question

C++标准要求std::partition在ForwardIterator和之间有不同数量的谓词应用程序BidirectionalIterator.对于ForwardIterator版本,谓词应用程序的数量应为<= N,其中N = std::distance(first, last),但对于BidirectionalIterator版本,谓词应用程序的数量应为<= N/2.显然,两个版本都具有时间复杂度O(N).

我的问题是,为什么要为不同类型的迭代器提供不同的要求呢？这样的要求迫使很多编译器？

例如:MSVC,std::partition以两种方式实现功能以满足这样的要求,这似乎不是很优雅.

还有一个问题:是否有任何算法依赖于这个系数,这样当N/2变为N时,渐近复杂度会有所不同？根据我的理解,如果我们考虑到Master's Theorem,对于形式T(n) = aT(n/b) + f(n),系数in f(n)并不重要.

Cf MSVC分区的等效实现:

template<class BidirIt, class UnaryPred>
BidirIt partition(BidirIt first, BidirIt last, UnaryPred pred, std::bidirectional_iterator_tag)
{
    while (true)
    {
        while ((first != last) && pred(*first))
        {
            ++first;
        }
        if (first == last)
        {
            break;
        }
        --last;
        while ((first != last) && !pred(*last))
        {
            --last;
        }
        if (first == last)
        {
            break;
        }
        std::iter_swap(first, last);
        ++first;
    }
    return first;
}
template<class ForwardIt, class UnaryPred> 
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred pred, std::forward_iterator_tag)
{
    first = std::find_if_not(first, last, pred);
    if (first == last)
    {
        return first;
    }

    for (ForwardIt src = std::next(first); src != last; ++src)
    {
        if (pred(*src))
        {
            std::iter_swap(first, src);
            ++src;
        }
    }
    return first;
}
template<class ForwardIt, class UnaryPred>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred pred)
{
    return partition(first, last, pred, typename std::iterator_traits<ForwardIt>::iterator_category());
}

Answer 1

在这两种情况下，谓词pred都执行了N次——每个元素都必须测试一次。ForwardIterator和之间的区别在于BidirectionalIterator掉期数量。

BidirectionalIterator最多进行N/2 次交换，因为它一次从前面和后面扫描范围，一旦它从左边到达不满足谓词的值和从右边来满足它的值，它就会交换它们。所以在最坏的情况下，它可以在N/2交换中完成它的工作。

ForwardIterator 没有那个优势，在最坏的情况下可能会对每个元素进行交换。

该标准需要这两种不同的限制，因为它们都是可以得到的最好的限制。因此，程序员可以相信每个标准库实现都会以这种方式运行。