Why C++ standard requires std::partition to meet different complexities for different types of iterator?

Question

The C++ standard requires std::partition to have different numbers of predicate applications between ForwardIterator and BidirectionalIterator. For the ForwardIterator version, the number of predicate applications shall be <= N, where N = std::distance(first, last), but for the BidirectionalIterator version, the number of predicate applications shall be <= N/2. Obviously, both versions have time complexity O(N).

My question is, why does it bother to provide different requirements for different type of iterators? Such requirement forces a lot of compilers?

e.g: MSVC, implement the function std::partition in two ways to meet such requirement, which does not seem to be very elegant.

A further question: Are there any algorithm that relies on this coefficient, such that when N/2 becomes N, the asymptotic complexity will be different? For my understanding, if we consider the Master's Theorem, for the form in T(n) = aT(n/b) + f(n), the coefficient in f(n) does not matter much.

C.f. An equivalent implementation of MSVC's partition:

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

The predicate pred is executed exactly N times in both cases - every element must be tested once. The difference between ForwardIterator and BidirectionalIterator is in the amount of swaps.

BidirectionalIterator does at most N/2 swaps, because it scans the range from the front and from the back at once, once it reaches value from the left that doesn't fulfill the predicate and value from right that does fulfill it, it swaps them. So in worst case it can do it's job in N/2 swaps.

ForwardIterator doesn't have that advantage and in worst case may do a swap for every element.

The standard requires those two different limitations, because they are both the best one can get. So programmers can rely that every standard library implementation will behave that way.