在 adjacent_find 中使用 greater_equal 查找排序序列中的等效元素

Question

在 std::adjacent_find 算法中使用 std::greater_equal 来查找排序范围内的等价（与相等相反）元素是不是 UB？

答案可以是 "no" 如果 prev 和 next 元素在 std::greater_equal<>{}(*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

Is it UB to use std::less in std::adjacent_find algorithm to find equivalent (as opposite to equal) elements in sorted range?

这绝不是未定义的行为，传递给 std::adjacent_find 的谓词的唯一限制是正确的类型而不是修改其参数。

Answer 2

您正在查看此模板：

template< class ForwardIt, class BinaryPredicate>
ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPredicate p );

这里p是

p - binary predicate which returns true if the elements should be treated as equal.

这里没有UB只要满足算法要求即可。如果您的问题必须将 less 视为 equal 那么它是完全有效的。

Answer 3

std::adjacent_find 搜索谓词 returns 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;
}

Answer 4

您没有 UB，但它不是您想要的 std::less，因为 1 < 2，它会 return 到 1.[=14 的迭代器=]

你需要：

std::vector<int> c{1, 2, 3, 3, 4, 5};
assert(std::is_sorted(std::cbegin(c), std::cend(c));
auto it = std::adjacent_find(std::cbegin(c), std::cend(c),
                             [](auto lhs, auto rhs){
                                 // For unsorted container, you would need
                                 // return !(lhs < rhs) && !(rhs < lhs);
                                 // but as container is sorted,
                                 // we already have (lhs < rhs) || !(rhs < lhs)
                                 return !(lhs < rhs);

                             });
// *it == 3; *(it+1) == 3;

在 adjacent_find 中使用 greater_equal 查找排序序列中的等效元素

Use greater_equal in adjacent_find to find equivalent elements in sorted sequence

c++

algorithm

c++17

c++20