是否定义为向 C++ 提供空范围？标准算法？
继我之前的问题，我们能否证明标准允许我们将空范围传递给标准算法？
第 24.1/7 段将“空范围”定义为范围[i,i) （其中 i 有效），并且 i 似乎可以从自身“访问”，但我不是确保这有资格作为证据。
特别是，我们在查看排序函数时遇到了麻烦。例如，std::sort：
复杂度：
O(N log(N))（其中N==last-first）比较
比较code>log(0)一般认为是undefined，我不知道0*undefined是什么，会不会这里有问题？
（是的，好吧，我有点迂腐。当然，没有自尊的 stdlib 实现会导致将空范围传递给 std::sort<但我想知道这里的标准措辞是否存在潜在的漏洞。）
Following on from my previous question, can we prove that the standard allows us to pass an empty range to a standard algorithm?
Paragraph 24.1/7 defines an "empty range" as the range [i,i) (where i is valid), and i would appear to be "reachable" from itself, but I'm not sure that this qualifies as a proof.
In particular, we run into trouble when looking at the sorting functions. For example, std::sort:
Complexity:
O(N log(N))(whereN==last-first) comparisons
Since log(0) is generally considered to be undefined, and I don't know what 0*undefined is, could there be a problem here?
(Yes, ok, I'm being a bit pedantic. Of course no self-respecting stdlib implementation would cause a practical problem with an empty range passed to std::sort. But I'm wondering whether there's a potential hole in the standard wording here.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Big-O 表示法是根据函数的极限来定义的。具有实际运行时间
g(N)的算法是O(f(N))当且仅当lim N→∞ g(N)/f(N)是一个非负实数g(N)/f(N)小于某个正实数C表示所有值N大于某个值常量k（C和k的确切值并不重要；您只需能够找到任何C和k使这一点成为事实）。 （感谢杰西的更正！）您会注意到元素的实际数量与大O分析无关。 Big-O 分析没有提及算法对于少量元素的行为；因此，
f(N)是否定义在N=0并不重要。更重要的是，实际运行时行为由不同函数g(N)控制，该函数很可能定义在N= 0即使f(0)未定义。Big-O notation is defined in terms of the limit of the function. An algorithm with actual running time
g(N)isO(f(N))if and only iflim N→∞ g(N)/f(N)is a non-negative real numberg(N)/f(N)is less than some positive real numberCfor all valuesNgreater than some constantk(the exact values ofCandkare immaterial; you just have to be able to find anyCandkthat makes this true). (thanks for the correction, Jesse!)You'll note that the actual number of elements is not relevant in big-O analysis. Big-O analysis says nothing about the behavior of the algorithm for small numbers of elements; therefore, it does not matter if
f(N)is defined atN=0. More importantly, the actual runtime behavior is controlled by a different functiong(N), which may well be defined atN=0even iff(0)is undefined.我似乎没有太多提问的余地。在 §24.1/6 中我们被告知：
24.1 美元/7 美元：
由于
0是有限的，因此[i, i)是有效范围。 §24.1/7 继续说道：这并没有说有效范围保证定义的结果（合理，因为还有其他要求，例如比较函数），但肯定似乎意味着范围本身不应该为空导致 UB 或类似的东西。然而，特别是，该标准使空范围成为另一个有效范围；空有效范围和非空有效范围之间没有真正的区别，因此适用于非空有效范围的内容同样适用于空有效范围。
I don't seem much room for question. In §24.1/6 we're told:
and in $24.1/7:
Since
0is finite,[i, i)is a valid range. §24.1/7 goes on to say:That doesn't go quite so far as to say that a valid range guarantees defined results (reasonable, since there are other requirements, such as on the comparison function) but certainly seems to imply that a range being empty, in itself, should not lead to UB or anything like that. In particular, however, the standard makes an empty range just another valid range; there's no real differentiation between empty and non-empty valid ranges, so what applies to a non-empty valid range applies equally well to an empty valid range.
除了 @bdonlan 给出的相关答案之外，还要注意
f(n) = n * log(n)确实有一个明确定义的限制，因为n趋于零，即0。这是因为对数的发散速度比任何多项式都慢，特别是比n慢。所以一切都很好:-)Apart from the relevant answer given by @bdonlan, note also that
f(n) = n * log(n)does have a well-defined limit asngoes to zero, namely0. This is because the logarithm diverges more slowly than any polynomial, in particular, slower thann. So all is well :-)