mardi 2 février 2016

Time complexity of `std::partition()`

According to cppreference:

Complexity
Exactly std::distance(first,last) applications of the predicate and at most std::distance(first,last) swaps. If ForwardIt meets the requirements of BidirectionalIterator at most std::distance(first,last)/2 swaps 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