Используйте more_equal в adjing_find, чтобы найти эквивалентные элементы в отсортированной последовательности - PullRequest
Новая
       64

Используйте more_equal в adjing_find, чтобы найти эквивалентные элементы в отсортированной последовательности

1 голос
/ 12 апреля 2019

Использует ли UB алгоритм std::greater_equal в std::adjacent_find, чтобы найти эквивалентные (в противоположность равным) элементы в отсортированном диапазоне?

Ответ может быть «нет», если порядок пред. и следующие элементы в 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));

Ответы [ 4 ]

3 голосов
/ 12 апреля 2019

std::adjacent_find ищет два последовательных элемента, где предикат возвращает true. Стандарт C ++ документирует поведение как находящее:

  • *i == *(i + 1) для перегрузок без параметра pred
  • pred(*i, *(i + 1)) != false для перегрузок с параметром pred

Второй маркер указывает порядок, в котором элементы передаются в предикат.

В этом примере реализации ( скопировано с 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;
}
0 голосов
/ 12 апреля 2019

У вас нет UB, но вы не хотите std::less, так как 1 < 2, он вернет итератор к 1.

Вам нужно: 

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;
0 голосов
/ 12 апреля 2019

Вы смотрите на этот шаблон: 

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

Здесь p равно

p - двоичный предикат, который возвращает true, если элементы должны рассматриваться как равные.

Здесь нет UB, если выполнены требования алгоритма. Если для вашей проблемы вы должны рассматривать less как equal, то это совершенно справедливо.

0 голосов
/ 12 апреля 2019

Это UB, чтобы использовать std :: less в алгоритме std ::acent_find, чтобы найти эквивалентные (как противоположные равные) элементы в отсортированном диапазоне?

Это никогда не неопределенное поведение, единственными ограничениями для предиката, передаваемого в std::adjacent_find, является правильный тип и отсутствие модификации его аргументов.

...