c++ - `std::partition()` 的时间复杂度

Question

根据 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.

我查看了底部的示例实现:

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;
}

我认为它最多执行 std::distance(first,last)/2 交换而不是 std::distance(first,last)。没有？

Answer 1

这似乎是非双向迭代器的实现，仅向前发展。仅通过一系列 n 项向前移动，至少需要 n-1 次交换才能将单个非 p 项从头移动到尾。使用双向迭代器，可以从两端向内工作。