Zhiqing Xiao - 4 months ago 18

C++ Question

The C++ standard requires

`std::partition`

`ForwardIterator`

`BidirectionalIterator`

`ForwardIterator`

`std::distance(first, last)`

`BidirectionalIterator`

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

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

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.