c++ - std::equal_range 是否需要严格的弱排序？

Question

我看到一些旧的、非标准的 equal_range 文档明确调用了严格的弱排序(旧的 SGI 文档)和一些更新的、标准的 equal_range 没有(cppreference、libstdc++ 文档)。

函数是否更改为过去需要严格的弱排序，现在需要...某种没有专有名称的分区？

Answer 1

std::equal_range要求被检查的序列必须被表达式分割 pr(value, N)和 pr(N, value)其中 pr是谓词，value是您要为其找到相等范围的值，N是序列的一个元素。

对于序列，这是一个比要求序列必须按严格的弱顺序排序更弱的条件。它只需要有一个分区点P，其中pr(N, value)返回 true对于 P 之前序列中的所有元素 N，pr(value, N)返回 false对于 P 或之后序列中的所有元素.例如，序列 [2, 1, 5, 4] 按 < 划分和值 3 , 分割点在值为 5 的元素处。

对于谓词本身，equal_range需要关于 value 的不对称性, 即 pr(N, value)暗示 ! pr(value, N)对于序列的所有 N。特别是，这意味着 pr(X, X)可以回true ，这不是严格的弱排序的情况。严格弱排序的要求/属性是:

• 不对称性:pr(x, y)暗示 ! pr(y, x)
• 非自反性:pr(x, x) == false
• 传递性:pr(x, y) && pr(y, z)暗示 pr(x, z)
• ! pr(x, y) && ! pr(y, z)暗示 ! pr(x, z) (在编程基础中，这是通过一个额外的等价关系来说明的)

请注意，这些点适用于序列的所有元素 x、y。关于pr的要求在 equal_range然而，这不是对谓词的一般要求，而是对谓词和特定值的特定要求。