英文:
incorrect behavior of upper_bound
问题
这段代码的第一部分输出为 24576，第二部分输出为 2。
为什么呢？
在第一部分的代码中，vector v 包含了四个元素 {0, 1, 3, 2}。然后，upper_bound 函数在 v 的反向迭代器范围内查找大于 1 的第一个元素，它找到了数字 2（在 v 中是最后一个元素）。因此，x 指向数字 2，然后输出 (*x)，所以结果是 2。
在第二部分的代码中，v 包含了五个元素 {0, 1, 3, 2, 2}。upper_bound 函数在反向迭代器范围内查找大于 1 的第一个元素，它仍然找到了数字 2，但这次是在第一个数字 2 处停止。因此，x 仍然指向数字 2，然后输出 (*x)，所以结果仍然是 2。
英文:
vector<int> v = {0,1,3,2};
auto x = upper_bound(v.rbegin(), v.rend(), 1);
cout<<(*x);
This block of code gives output 24576
vector<int> v = {0,1,3,2,2};
auto x = upper_bound(v.rbegin(), v.rend(), 1);
cout<<(*x);
This block gives output 2.
Why?
答案1
得分: 1
std::upper_bound 有一个前提条件。引用 cppreference 的说法，而非标准：
范围
[first, last)必须根据表达式!(value < element)或!comp(value, element)进行分区，也就是说，表达式为true的所有元素必须在表达式为false的所有元素之前。
这是由你作为调用者来确保满足的前提条件，如果未能满足这一条件，你的程序将具有未定义行为。
由于你传递了反向迭代器，算法的序列对于第一个示例是 2, 3, 1, 0。（第二个示例也有完全相同的问题。）表达式 !(1 < element) 在这个序列上的评估结果为 false, false, true, true，这意味着 true 值不在 false 值之前，即前提条件被违反了。你的程序具有未定义行为，而确切的结果值是不可预测和无关紧要的。
英文:
std::upper_bound has a precondition. Quoting cppreference here, not the standard:
> The range [first, last) must be partitioned with respect to the expression !(value < element) or !comp(value, element), i.e., all elements for which the expression is true must precede all elements for which the expression is false.
It is up to you, the caller, to make sure this precondition is satisfied, and your program has undefined behavior if you fail to do so.
Since you pass reverse iterators, the sequence for the algorithm is 2, 3, 1, 0 for the first example. (The second has exactly the same issue.) The expression !(1 < element) evaluates for this sequence to false, false, true, true, which means the true values don't precede the false values, i.e. the precondition is violated. Your program has undefined behavior, and the exact resulting values are unpredictable and irrelevant.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论