Zhiqing Xiao -4 years ago 125
C++ Question

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

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());
}
``````

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.