Унарные предикаты (unary predicates) в STL

Сначала давайте посмотрим, как стандарт определяет унарные предикаты (стандарт именует их просто предикатами).

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

Основные свойства

1. Унарный предикат должен быть "вызываемым".
2. Унарный предикат должен принимать один аргумент и возвращать логическое значение или значение, которое можно преобразовать в логическое.
3. Унарный предикат не обязан быть копируемыми.

Свойства, имеющие побочные эффекты

4. Унарный предикат не должен изменять свой аргумент.
5. Унарный предикат не должен делать недействительными свои итераторы или последовательности, с которыми работает алгоритм.
6. Унарный предикат может производить любые побочные эффекты, кроме 4 и 5.

Другие свойства

7. Унарный предикат должен быть независимым от порядка его вызовов, то есть, результаты его работы не должны зависеть от порядка вызовов.
8. Унарный предикат необязательно дает одинаковый результату для разных вызовов с тем же аргументом.

Давайте рассмотрим подробно, почему предикат обладает именно этими свойствами.

Основные свойства 1, 2 и 3

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

Эти свойства являются более или менее очевидным, когда мы рассмотрим, как стандарт определяет использование унарных предикатов алгоритмами , а именно, предикат "должен работать правильно в конструкции if(pred(*first)){...}". Вот типичная реализация алгоритма, демонстрирующего использование унарного предиката:

template <class InputIterator, class Predicate> 
  typename iterator_traits<InputIterator>::difference_type
count_if( InputIterator first, InputIterator last, Predicate pred ) {
  typename iterator_traits<InputIterator>::difference_type n = 0;
  for ( ; first != last; ++first)    
    if (pred(*first))
      ++n;
  return n;
}

Другими словами, унарный предикат вызывается также как и функция. Требованию "вызываемости" соответствует не только указатель на функцию, но и объект некоторого типа (или ссылка на этот объект), у которого определен оператор вызова функции operator() (так называемый функтор). При вызове предикату передается единственный аргумент. Аргументом является результат разыменования итератора, то есть, ссылка на элемент последовательности. Возвращаемое значение используется в условном выражении и должно преобразовываться в тип bool. И это в полной мере описывает цель унарного предиката: он вызывается для получения логического результата для элементов последовательности.

В частности, не существует никаких требований к семантике копирования унарного предиката. Он даже необязательно должен быть копируемым. Основное правило состоит в том, что при использовании объектов алгоритм не должен полагаться на свойства этих объектов, которые от них не требуются. Это подразумевает, что алгоритм не должен копировать предикат, потому что пользователь не обязан предоставлять разумное внутреннее копирование своего предиката. Это просто замечательно, если мы объявляем конструктор копирования и оператор копирующего присваивания как private члены нашего предиката типа и передаем предикатные объекты по ссылке, если это имеет смысл. Работа любого алгоритма не должна быть нарушена. На практике, вы найдете библиотеки, которые предполагают копирование предикатов, хотя они и не должны делать этого. Одно из удивительных последствий при использовании таких реализаций стандартной библиотеки были рассмотрены в статье, опубликованной в C++ Report. В то же время некоторые реализации устранили это ограничение, и теперь ведут себя, как ожидается, например, Metrowerks CodeWarrior 6.0. Принимая во внимание различные библиотечные реализации, мы рекомендуем избегать унарных предикатов с необычной или некопирующей семантикой.

На практике большинство предикатов имеют нормальную семантику копирования. Это потому, что обычно мы вызываем алгоритм таким образом, что предикат передается по значению. Для этого предикат должна быть копируемым. Некопируемые предикаты могут быть полезны, но они необычны, потому что они должны передаваться по ссылке, что требует повышенной осторожности. Теперь перейдем к рассмотрению вопросов о побочных эффектах от использования унарных предикатов.

Свойства 4, 5 и 6, имеющие побочные эффекты

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

Стандарт запрещает определенные побочные эффекты, но позволяет другие. Почему? Чтобы это понять, рассмотрим, что происходит внутри алгоритма, который использует унарный предикат. Существует две сущности, производящие побочные эффекты: сам алгоритм и унарный предикат. Алгоритм перебирает последовательность входных элементов, проверяет элементы, подставляет их в качестве аргумента предиката, изменяет и копирует их, а также может производить другие побочные эффекты. Унарный предикат получает ссылку на элемент входной последовательности и может также просматривать и изменять элемент и производить другие побочные эффекты. Естественно, что эти действия могут конфликтовать. По этой причине, будем классифицировать побочные эффекты, создаваемые унарным предикатом по степени конфликтности как опасные, потенциально опасные и безопасные побочные эффекты.

Опасные побочные эффекты

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

Примером ”опасного” предиката является предикат, который хранит указатель или ссылку на последовательность, с которой работает алгоритм и использует эту ссылку для удаления элементов последовательности. Удаление элементов может сделать недействительными итераторы, которые используются алгоритмом для получения входных и выходных последовательностей, и в этом случае работа алгоритма может привести к аварийному завершению программы.

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

В любом случае, следует избегать предикатов с опасными побочными эффектами при любых обстоятельствах. Никогда не используйте функциональные объекты, которые приводят к недействительности итератора или последовательности, с которой работает алгоритм.

Потенциально опасные побочные эффекты

Эта категория побочных эффектов намеренно запрещена стандартом. Все унарные предикаты, которые используют неконстантную функциональность по отношению к своим аргументам, попадают в эту категорию, потому что модифицируют элементы последовательности. Будем называть такие предикаты модифицирующими. (Обратите внимание на различие между "изменением последовательности" (опасные) и "изменением элементов последовательности" (только потенциально опасные): "изменение последовательности" означает, что элементы вставляются, удаляются или переставляются так, что некоторые итераторы или итераторные диапазоны становятся недействительными. "Изменение последовательности элементов" означает, что при доступе к элементам последовательности их содержание изменяется, но итераторы по прежнему остаются действительными).

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

Когда случаются такие коллизии? Не все алгоритмы изменяют элементы входной последовательности, но некоторые из них это действительно делают. Алгоритмы делятся на несколько категорий: немодифицирующие и модифицирующие алгоритмы. В свою очередь модифицирующие алгоритмы могут производить изменения как "на месте", так и в копии. Немодифицирующие алгоритмы (например, count_if) только проверяют элементы последовательности, но они ничего не меняют. Модифицирующие копию алгоритмы (например, replace_copy_if) не изменяют элементы входной последовательности, копируют их в выходную последовательность и изменяют элементы в выходной последовательности. Модифицирующие на месте алгоритмов (например, replace_if) изменяют элементы "на месте", что означает, что они изменяют элементы входной последовательности, что является критичным. Таким образом, потенциальный конфликт между предикатом и алгоритмом имеет место для модифицирующих на месте алгоритмов в сочетании с модифицирующим унарным предикатом.

При использовании двойной модификации одного и того же элемента последовательности возникает несколько вопросов, таких как: какая модификация выполняется в первую очередь и, возможна ли ее замена второй? Это результат вообще предсказуемый? Для того чтобы избежать таких конфликтов между алгоритмом и предикатом, стандарт требует, чтобы унарный предикат не изменял элементы входной последовательности, которые он получает в качестве аргументов. Обратите внимание, что модифицирующий побочный эффект запрещен для всех унарных предикатов, а не только для модифицирующих на месте алгоритмов.

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

Безопасные побочные эффекты

И последнее, но не менее важное - предикат может обладать безопасными побочными эффектами. Все немодифицируюшие предикаты попадают в эту категорию. Предикат может использовать константную функциональность к своим аргументам, то есть, он может проверять элементы последовательности, но он не должен изменять их. Кроме того, унарный предикат может изменять объекты, отличные от своих аргументов. Он может, например, иметь члены данных и изменять их значения. Или он может ссылаться на не связанные элементы последовательности и изменять их. Это безопасно до тех пор, пока последовательности, которые были изменены предикатом, не используются одновременно в алгоритмах.

Почему нужно быть внимательным

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

Это зависит от обстоятельств. Если вы посмотрите на типичные примеры предикатов в учебниках по C++, то вы обнаружите, что унарные предикаты, такие как isEven определяется как bool isEven(int elem) { return elem %2 == 0; } или выражения, например, bind2nd(greater<int>(),4), которое является унарным предикатом, создаваемым из предопределенного бинарного предиката с помощью так называемого связывателя (binder). Даже если вы изучите унарные предикаты, которые реализуются на основе функторов (т. е. классов с перегруженным оператором вызова функции), они редко имеют члены данных или что-нибудь сложное, и поэтому они никогда не создают побочных эффектов.

На практике все немного по-другому. Например, если мы заботимся об эффективности. Очевидно, что быстрее выполнять несколько вещей за один проход по последовательности вместо того, что бы делать повторяющиеся пошаговые вычисления над элементами большой последовательности. Рассмотрим несколько примеров.

Пусть имеется контейнер, представляющий базу данных о покупателях. Нам необходимо определить всех наиболее частых покупателей. Мы хотим создать список рассылки для оправки рекламных материалов по почте именно таким частым покупателям. Однако список рассылки не должен содержать превышать 5000 адресатов. Это задача. Как мы можем ее решить? Одним возможным вариантом может быть решение на основе унарного предиката, который возвращает true для частых покупателей и накапливает информацию для списка рассылки. Алгоритм count_if при использовании такого предиката будет вычислять желаемое количество и наращивать список рассылки в качестве побочного эффекта. Такой унарный предикат строго соответствует правилам. Он принимает элемент последовательности, проверяет его и производит безопасный побочный эффект, а именно, список рассылки.

Рассмотрим другой похожий пример. Пусть нам нужно удалить всех нечастых покупателей из нашей клиентской базы и обновить записи по оставшимся частым покупателям для предоставления скидок. Опять же, мы стараемся заботиться об эффективности и хотим сделать это на одном проходе по клиентской базе. По аналогии с предыдущим подходом, мы могли бы реализовать унарный предикат для алгоритма remove_if, который возвращал бы true для редких покупателей (так чтобы алгоритм удалял их) и добавлял информацию о скидках для оставшихся покупателей. В отличие от предыдущего примера, это неправильно, так как добавление информации к элементам входной последовательности является запрещенным побочным эффектом. Помните: предикат не должен изменять свой аргумент. Но это именно то, что нам нужно: мы хотим обновить остальные элементы в последовательности. Итак, что же нам делать в этом случае?

Здесь мы мало, что можем сделать. Тщательное изучение раздела “алгоритмы” стандарта показывает, что алгоритм for_each - единственный алгоритм, который принимает объект функции и позволяет ему изменять свои аргументы. По этой причине, мы ограничены в выборе алгоритмов для решения конкретной задачи, если эта задача включает в себя модификацию элементов входной последовательности; for_each является единственным выбором.

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

Альтернативы:

• Функциональный объект для использования в for_each, который удаляет и изменяет элементы (повторяя, таким образом, функциональность remove_if)
• Пользовательская версия алгоритма remove_if, которая позволяет модифицировать элементы входной последовательности
• Ручное кодирование алгоритма (без использования стандартных алгоритмов)

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

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

Свойство 7

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

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

Число вызовов точно указываются: алгоритмы, такие как count_if или remove_if используют унарный предикат только один раз для каждого элемента входной последовательности. Порядок же вызовов имеет другой характер: ни один из алгоритмов, в которых используются унарные предикаты, не определяет порядок, в котором он поставляет элементы последовательности в предикат. Как следствие, унарные предикаты должны быть независимы от порядка вызова. Если мы используем предикат, который зависит от порядка вызовов, то результат будет непредсказуемым.

Вот пример: (зависимый от порядка) предикат, который возвращает true для каждого n-ого элемента последовательности:

class Nth {
public:
  Nth(int n) : theN(n), theCnt(0) {}
  bool operator()(int) 
  { return (++theCnt)%theN; }
private:
  const int theN;
  int theCnt;
};

Если мы предоставляем предикат, такой как Nth(3) для алгоритма, например, remove_copy_if, то можно ожидать, что каждый третий элемент входной последовательности переместиться в выходную последовательность. Но это не гарантируется, так как элементы последовательности не обязательно поставляются в определенном порядке. Мы можем рассчитывать лишь на то, что треть всех элементов будут перемещены из входной последовательности в выходную.

Почему стандарт не дает гарантии относительно порядка вызова унарных предикатов? Потому, что некоторые алгоритмы могут быть оптимизированы для определенных типов итераторов. Например, алгоритм может последовательно обходить все элементы последовательности от начала до конца для итераторов ввода, а может также “перешагивать ” сразу несколько элементов для итераторов произвольного доступа. Поскольку стандарт не хочет ограничивать потенциал для такой оптимизации, поэтому он не дает никаких гарантий относительно порядка вызовов унарных предикатов.

Последствием для пользователей STL является то, что все унарные предикаты не должны зависеть от того, в какой последовательности элементы поставляются с ним. Если мы хотим использовать зависимые от порядка предикаты, то мы должны сами реализовать наши пользовательские алгоритмы так, чтобы они давали нам нужные гарантии относительно порядка вызовов унарных предикатов.

С порядком и количеством вызовов унарного предиката связано последнее свойство.

Свойство 8

Унарный предикат необязательно дает одинаковый результату для разных вызовов с тем же аргументом.

Это свойство может показаться немного надуманным. Мы включили его в список свойств, потому что мы заметили следующее: иногда предполагают, что предикаты демонстрируют ”стабильное” поведение в том смысле, что они дают тот же результат каждый раз, когда они вызываются с тем же или ”равным” аргументом. Это предположение не оправдано, стандарт не определяет никаких требований по этому поводу.

Почему же тогда иногда предполагается ”стабильное” поведение от унарного предиката? Потому, что это дает достаточную свободу для его реализации. При "стабильном" поведении не имеет значения, как часто предикат вызывается для одного и того же элемента последовательности, так как результат всегда будет одинаковым. При этом не имеет значения, используется ли ссылка на элемент последовательности или его временная копия.

Однако для унарных предикатов в STL не существует требования “стабильного“ поведения. Поэтому имеет смысл рассмотреть "нестабильный" предикат. Примером может служить предикат, который дает true для всех элементов с определенным свойством предела максимального числа элементов. Он может использоваться для копирования максимального количества элементов с заданным свойством из входной последовательности в выходную, используя remove_copy_if.

Резюме

Следующие алгоритмы стандартной библиотеки используют унарные предикаты: replace_if, remove_if, partition, stable_partition, replace_copy_if, remove_copy_if, count_if и find_if.

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

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