Что значит "Предикаты не должны изменять свое состояние из-за вызова функции"?

Ответ 1

Давайте рассмотрим алгоритм std::count_if в качестве примера. Он пересекает диапазон и считает, как часто данный предикат оценивается как истинный. Далее предположим, что мы хотим проверить, сколько элементов в контейнере меньше заданного числа, например, 5 или 15.

Предикатом может быть много вещей. Это просто должно быть вызвано. Это может быть функтор:

struct check_if_smaller {
    int x;
    bool operator()(int y) { return y < x; }
};

Вы можете создавать разные экземпляры этого предиката, например, эти два

check_if_smaller a{5};
check_if_smaller b{15};

можно использовать для проверки того, что числа меньше, чем 5 или 15 соответственно:

bool test1 = a(3);  // true because 3 < 5
bool test2 = b(20); // false because 20 is not < 15

Элемент x является состоянием предиката. Обычно это не должно меняться при применении предиката (вызывая его operator()).

Из Википедии:

В математической логике предикат обычно понимается как Булевозначная функция P: X → {true, false}, называемая предикатом на X. Однако предикаты имеют много разных применений и интерпретаций в математика и логика и их точное определение, значение и использование будет варьироваться от теории к теории.

Небрежно говоря, предикат - это функция, отображающая что-то в логическое значение. Тот факт, что мы используем функтор, который является не просто функцией, а функциональным объектом с состоянием, может рассматриваться как деталь реализации, и повторная оценка одного и того же предиката для одного и того же ввода обычно дает тот же результат. Кроме того, алгоритмы делают это предположение, и ничто действительно не мешает им копировать предикат, который вы передаете. Если оценка предиката изменит его внутреннее состояние, алгоритм может работать не так, как ожидалось.

Ответ 2

С точки зрения непрофессионалов, состояние в предикате является членом данных. Изменение состояния предикатом означает, что член изменяется во время выполнения алгоритма, и это изменение повлияет на поведение предиката.

Причиной этого является тот факт, что алгоритмы не обязаны хранить единственный экземпляр предиката. Их можно легко скопировать, а состояние, измененное в одной копии, не будет передано состоянию в другой копии. В результате программа будет вести себя неожиданно (для того, кто ожидает изменения состояния).

Ответ 3

По существу, то, что стандарт говорит, что предикат должен действовать как чистая функция (в математических терминах), то есть его возвращаемое значение должно зависеть только от ввода.

Упоминание о состоянии, потому что предикаты могут быть скопированы или могут быть вызваны в разных потоках, что зависит от реализации и поведения платформы. Для лямбды и других вызываемых объектов, которые не являются функциями, это может означать неупорядоченный доступ к хранилищу, захваченный по ссылке, или доступ к другим значениям, если они были захвачены по значению. Для функции это означает, что любые побочные эффекты (включая изменение статических переменных) могут привести к проблемам.

Если предикат для сортировки возвращает разные результаты для одной и той же пары, то некоторые алгоритмы сортировки становятся недействительными.

Ответ 4

В дополнение к другим ответам, многие из алгоритмов, которые принимают предикаты, не обещают какого-либо определенного порядка обхода (перегрузки ExecutionPolicy допускают чередующийся обход). Вы можете получить разные ответы на один и тот же вопрос.

Если есть несколько потоков, вызывающих ¹ предикат, и он меняет некое общее значение, то это гонка данных, то есть неопределенное поведение.

1. или один поток чередует вызовы