C标准要求std :: partition在ForwardIterator和BidirectionalIterator之间具有不同数量的谓词应用程序.对于Forw​​ardIterator版本,谓词应用程序的数量应为< = N,其中N = std :: distance(first,last),但对于BidirectionalIterator版本,谓词应用程序的数量应为< = N / 2.显然,两个版本都具有时间复杂度O(N). 我的问题是,为什么要为不同类型的迭代器提供不同的要求呢？这样的要求迫使很多编译器？ 例如：MSVC,以两种方式实现函数std :: partition来满足这样的要求,这似乎不是很优雅. 还有一个问题：是否有任何算法依赖于这个系数,这样当N / 2变为N时,渐近复杂度会有所不同？根据我的理解,如果我们考虑Master的定理,对于T(n)= aT(n / b)f(n)中的形式,f(n)中的系数并不重要. C.F. 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,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,UnaryPred pred)
{
    return partition(first,pred,typename std::iterator_traits<ForwardIt>::iterator_category());
}