According to cppreference:
Complexity
Exactlystd::distance(first,last)applications of the predicate and at moststd::distance(first,last)swaps. If ForwardIt meets the requirements of BidirectionalIterator at moststd::distance(first,last)/2swaps are done.
I looked at the sample implementation at the bottom:
template<class ForwardIt, class UnaryPredicate>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
if (first == last) return first;
ForwardIt part(first++);
if (first == last) return p(*part) ? first : part;
while (first != last) {
if (p(*part))
++part;
else if (p(*first)) {
iter_swap(part, first);
++part;
}
++first;
}
return part;
}
I think it performs at most std::distance(first,last)/2 swaps instead of std::distance(first,last). No?
Aucun commentaire:
Enregistrer un commentaire