c++ - 在 adjacent_find 中使用 greater_equal 来查找排序序列中的等价元素

Question

使用std::greater_equal是UB吗？在 std::adjacent_find在排序范围内找到等效(与相等相反)元素的算法？

如果 std::greater_equal<>{}(*prev, *next) 中 prev 和 next 元素的顺序，答案可能是“否”算法的内部实现没有严格规定。

std::container<int> c{1, 2, 3, 3, 4, 5};
assert(std::is_sorted(std::cbegin(c), std::cend(c));
assert(std::adjacent_find(std::cbegin(c), std::cend(c), std::greater_equal<int>{}) != std::cend(c));

Answer 1

std::adjacent_find 搜索谓词返回 true 的两个连续元素。 C++ standard将行为记录为发现:

• *i == *(i + 1) 用于没有参数的重载 pred
• pred(*i, *(i + 1)) != false 用于带有参数的重载 pred

第二个项目符号指定元素传递给谓词的顺序。

这个示例实现 ( copied from cppreference.com ) 应该更清楚这一点。

template<class ForwardIt, class BinaryPredicate>
ForwardIt adjacent_find(ForwardIt first, ForwardIt last, BinaryPredicate p)
{
    if (first == last) {
        return last;
    }
    ForwardIt next = first;
    ++next;
    for (; next != last; ++next, ++first) {
        if (p(*first, *next)) { // <- predicate called here
            return first;
        }
    }
    return last;
}