为什么c++标准需要std::分区来满足不同类型迭代器的不同复杂性

Question

c++标准要求std::partition在ForwardIterator和BidirectionalIterator之间具有不同数量的谓词应用。对于ForwardIterator版本，谓词应用数为<= N，其中N = std::distance(first, last);对于BidirectionalIterator版本，谓词应用数为<= N/2。显然，两个版本都有时间复杂度O(N)。

我的问题是，为什么要为不同类型的迭代器提供不同的要求呢?这样的要求迫使很多编译器?

e。g: MSVC，用两种方式实现std::partition函数来满足这样的要求，这看起来不是很优雅

进一步的问题:是否存在依赖于该系数的算法，使得当N/2变成N时，其渐近复杂度会有所不同?根据我的理解，如果我们考虑Master's Theorem，对于T(n) = aT(n/b) + f(n)中的形式，f(n)中的系数并不重要。

出口。MSVC分区的等价实现:

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 1

谓词pred在两种情况下都精确执行N次-每个元素必须测试一次。ForwardIterator和BidirectionalIterator的区别在于交换的数量。

BidirectionalIterator最多做N/2交换，因为它同时从前面和后面扫描范围，一旦它从左边到达不满足谓词的值和从右边到达满足谓词的值，它就交换它们。所以在最坏的情况下它可以在N/2交换中完成它的工作。

ForwardIterator没有这个优势，在最坏的情况下可能会对每个元素进行交换。

标准要求这两个不同的限制，因为它们都是一个人能得到的最好的限制。所以程序员可以相信每个标准库的实现都是这样的。

Answer 2

没错，时间复杂度还是一样的。

重要的是要注意互换实际上是相当昂贵的。特别是对于大的物体。大多数情况下，它们涉及三个移动操作。在这种情况下，我们应该将互换的数量减少到最低限度。通过使用双向迭代器，我们在效率方面得到了显著的提高，尽管时间复杂度是相同的。

请记住，在实际环境中，快速执行简单操作可能是至关重要的。只要有可能这样做，就应该这样做。当处理复杂的算法(通常是np完全问题的变体)需要花费大量时间来计算时，在一半的时间内执行操作可能是至关重要的。您更喜欢0.2秒到0.1秒的延迟吗?时间复杂性是一堆很好的理论，但现实世界并没有那么美好，每一秒的一小部分都很重要。