为什么C标准要求std :: partition满足不同类型迭代器的不同复杂性？

概述C标准要求std :: partition在ForwardIterator和BidirectionalIterator之间具有不同数量的谓词应用程序.对于Forw​​ardIterator版本,谓词应用程序的数量应为< = N,其中N = std :: distance(first,last),但对于BidirectionalIterator版本,谓词应用程序的数量应为< = N / 2.显然,两 C标准要求std :: partition在ForwardIterator和BIDirectionaliterator之间具有不同数量的谓词应用程序.对于Forw​​ardIterator版本,谓词应用程序的数量应为< = N,其中N = std :: distance(first,last),但对于BIDirectionaliterator版本,谓词应用程序的数量应为< = N / 2.显然,两个版本都具有时间复杂度O(N). 我的问题是,为什么要为不同类型的迭代器提供不同的要求呢？这样的要求迫使很多编译器？ 例如：MSVC,以两种方式实现函数std :: partition来满足这样的要求,这似乎不是很优雅. 还有一个问题：是否有任何算法依赖于这个系数,这样当N / 2变为N时,渐近复杂度会有所不同？根据我的理解,如果我们考虑Master的定理,对于T(n)= aT(n / b)f(n)中的形式,f(n)中的系数并不重要. C.F. 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,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,UnaryPred pred){    return partition(first,pred,typename std::iterator_traits<ForwardIt>::iterator_category());}

解决方法 在两种情况下,谓词pred都执行N次 – 每个元素必须测试一次. ForwardIterator和BIDirectionaliterator之间的区别在于交换量.

BIDirectionaliterator最多可以进行N / 2次交换,因为它一次从前面和后面扫描范围,一旦它从左边达到不满足谓词的值,并且从右边开始实现它,它会交换它们.因此,在最坏的情况下,它可以在N / 2交换中完成它的工作.

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

该标准要求这两个不同的限制,因为它们都是最好的限制.因此程序员可以依赖每个标准库实现都会这样做.

总结

以上是内存溢出为你收集整理的为什么C标准要求std :: partition满足不同类型迭代器的不同复杂性？全部内容，希望文章能够帮你解决为什么C标准要求std :: partition满足不同类型迭代器的不同复杂性？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。