是否定义为C++标准算法提供空范围?

Lig*_*ica 3 c++ std language-lawyer c++11

继我之前的问题之后,我们能否证明该标准允许我们将空范围传递给标准算法?

第24.1/7段将"空范围"定义为范围[i,i)(在哪里i有效),并且i看起来是"可到达"的,但我不确定这是否有资格证明.

特别是,在查看排序功能时会遇到麻烦.例如,std::sort:

复杂性:( O(N log(N))其中N== last- first)比较

由于log(0)通常被认为是未定义的,我不知道是什么0*undefined,这里可能有问题吗?


(是的,好吧,我有点迂腐.当然,没有自尊的stdlib实现会导致传递空范围的实际问题std::sort.但是我想知道标准措辞中是否存在潜在漏洞.)

bdo*_*lan 10

Big-O表示法是根据函数的限制来定义的.具有实际运行时间的算法g(N)是O(f(N)),且当且是否lim N?? g(N)/f(N)为非负实数时, 对于大于某个常数的所有值,g(N)/f(N)小于某个正实数(精确值为和非物质;您必须能够找到任何并且,使这个真).(谢谢你的纠正,杰西!)CNkCk Ck

您会注意到元素的实际数量与big-O分析无关.Big-O分析没有说明算法对少量元素的行为; 因此,如果f(N)定义为,则无关紧要N=0.更重要的是,实际的运行时行为由不同的函数控制g(N),N=0即使f(0)未定义,也可以定义.


Jer*_*fin 7

我似乎没有太大的问题空间.在§24.1/ 6中,我们被告知:

迭代器j被称为可以从迭代器i到达,当且仅当存在表达式++ i的有限序列的应用程序时才使i == j.

以$ 24.1/7:

当且仅当j可从i到达时,Range [i,j]才有效.

由于0是有限的,[i, i)是一个有效的范围.§24.1/ 7继续说:

将库中的函数应用于无效范围的结果是未定义的.

这并不是说有效范围保证定义的结果(合理的,因为还有其他要求,例如比较函数),但当然似乎暗示一个范围为空的范围本身不应该导致UB或类似的东西.然而,特别是,该标准使空范围只是另一个有效范围; 空的和非空的有效范围之间没有真正的区别,因此适用于非空有效范围的情况同样适用于空的有效范围.