std::lower_bound等三个C++算法的前置条件及文档歧义解析

核心前置条件：
这三个算法的核心要求是目标范围 [first, last) 必须基于特定的比较规则形成分区，具体对应：

• 对于 std::lower_bound（默认用 < 比较）：所有满足 elem < val 的元素必须出现在不满足该条件的元素之前。简单说就是“小于val的元素全在前，其余在后”。
• 对于 std::upper_bound（默认用 < 比较）：所有不满足 val < elem 的元素（即 elem <= val）必须出现在满足该条件的元素之前。也就是“不大于val的元素全在前，其余在后”。
• 对于 std::equal_range：范围需要同时满足上述两个条件——此时等于val的元素会形成一个连续的区间，等价于范围是按 < 严格弱序排序的。

关于“相对于val分区”的澄清：
你提到的文档里的“相对于val分区”表述容易混淆，原因在于它和std::partition的通用一元谓词分区不同：
这里的“分区”特指绑定了val的特定一元谓词：

• 对应lower_bound的谓词是 [&val](const auto& elem) { return elem < val; }
• 对应upper_bound的谓词是 [&val](const auto& elem) { return !(val < elem); }

范围只要满足被这个特定谓词分区（即谓词返回true的元素全部集中在左侧，false的在右侧），就符合前置条件——不需要整个范围完全排序，只要满足这个分区规则即可。当然，如果范围是严格弱序排序好的，必然满足这个分区要求，这也是我们最常用的场景。

额外说明：
如果使用自定义比较函数（比如std::greater<T>），上述逻辑需要对应调整：比如用std::greater时，lower_bound要求所有大于val的元素在前，其余在后，以此类推。

内容的提问来源于stack exchange，提问作者Dr. Gut