Система Orphus

 

Поиск по сайту

 

Статьи » Различия между алгоритмами for_each and transform в STL

Различия между алгоритмами for_each и transform

The Difference between for_each and transform

Журнал C/C++ Users, февраль 2001 г.

© Клаус Крэфт и Анжелика Лангер

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

Читаем стандарт

Перед началом обсуждений давайте посмотрим, что говорит стандарт.

FOR_EACH. Алгоритм for_each указан в стандарте в разделе операций, не модифицирующих последовательности.

template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);
  • Эффект: f применяется к результату разыменования каждого итератора в диапазоне [first, last), начиная с first и продолжая до last - 1.
  • Возвращаемое значение: f
  • Сложность: f применяется ровно last - first раз.
  • Примечание: если f возвращает результат, то он игнорируется.

TRANSFORM. Алгоритм transform указывается в стандарте в разделе операций, изменяющих последовательности. Имеет два варианта, один вариант (унарный transform) работает с одной входной последовательностью, другая версия (бинарный transform) принимает две входных последовательности. Так как мы хотим сравнить for_each и transform, мы будем рассматривать только унарный вариант.

template<class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform(InputIterator first, InputIterator last,
                         OutputIterator result, UnaryOperation op);
  • Эффект: через каждый итератор i в диапазоне [result, result + (last - first)) назначает новое соответствующее значение, равное op(*(first + (i - result)).
  • Требования: op не имеет никаких побочных эффектов.
  • Возвращаемое значение: result + (last - first).
  • Сложность: ровно last - first применений op.
  • Примечание: результат может быть равным first.

Действительно, как унарный алгоритм transform, так и алгоритм for_each применяются как унарные операции для каждого элемента в диапазоне входных итераторов ровно один раз. В остальном они имеют мало общего. Различия включают в себя:

  • for_each является не модифицирующим алгоритмом; transform – модифицирующий алгоритм.
  • for_each игнорирует возвращаемое значение операции; transform присваивает возвращаемое значение последовательным элементам в выходном диапазоне.
  • for_each возвращает копию объекта функции; transform возвращает итератор на конец выходного диапазона.
  • for_each применяет операцию в определенном порядке, а именно, начиная с начала и переходя к концу входного диапазона; для transform такой гарантии не дается.
  • Операция, предоставляемая для transform не должна иметь никаких побочных эффектов; операция, предоставляемая для for_each, таких ограничений не имеет.

Давайте посмотрим, что означают эти различия, и почему они существуют.

Назначение

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

Возвращаемые значения. Типичными значениями, возвращаемыми алгоритмами являются: логическое значение (см. includes), счетчик (см. count_if), итератор, указывающий на конкретный элемент входной последовательности (см. find_if), итератор, указывающий на конец сформированной выходной последовательности (см. copy), или пара итераторов, обозначающих итераторный диапазон (см. equal_range). Большинство алгоритмов возвращают значения и лишь немногие - нет (то есть, fill, replace, sort и swap).

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

Модифицирующие алгоритмы. Алгоритмы, такие как remove, replace, copy или sort активно производят побочные эффекты, а именно изменяют элементы последовательности. Обычно они делают это путем присваивания значений через разыменованные итераторы. copy, например, присваивает элементы входного диапазона элементам выходного диапазона. Если модифицированной последовательностью является входная последовательность, то стандарт говорит об изменяющем на месте алгоритме; если изменения влияют на выходной диапазон, то он говорит о копирующих алгоритмах. Например, replace_if является изменяющим на месте алгоритме, в то время как replace_copy_if является копирующим алгоритмом.

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

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

Как отмечалось ранее, единственной целью не модифицирующего алгоритма является генерация возвращаемого значения. for_each не является модифицирующим алгоритмом и он возвращает функциональный объект, который был ему передан. Можно задаться вопросом, какой смысл в использовании for_each для последовательности элементов, если он не изменяет никаких элементов и возвращает то, что получил? Вообще использование for_each дает хоть какой-нибудь эффект? Действительно, for_each активно не производит никаких побочных эффектов. Фактическая цель вызова for_each заключается в эффекте, производимым функциональным объектом – этот объект передается в for_each и вызывается для каждого элемента входной последовательности. Более точно, функциональный объект может производить эффект, изменяя входную последовательность, а также модифицируя себя в процессе своих вызовов.

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

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

Последствия

Рассмотрим последствия спецификаций for_each и transform, определяемых стандартом. Оказывается, что такая простая формулировка "очень похожие алгоритмы, которые различаются в использовании возвращаемого значения вызываемого ими объекта функций" часто вводит в заблуждение.

Побочные эффекты

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

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

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

Порядок вызовов

Объект функции, чувствительный к порядку вызовов может передаваться в for_each, но не в transform. Стандарт ничего не говорит о порядке, в котором алгоритм transform вызывает объекты функций. По этой причине, результат передачи чувствительной к порядку вызовов операции непредсказуем для transform и хорошо определен для for_each.

Почему бы не рассмотреть эти вопросы на практике? Давайте изучим примеры.

Конкретный пример

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

Первая идея может строиться на основе алгоритмов remove_if и remove_copy_if: удалить запись из map, если ее имя содержится в файле (и копировать запись в другой контейнер map). Однако эта идея не работает, так как remove_if и remove_copy_if являются модифицирующими алгоритмами, которые пытаются присвоить значения элементам входной последовательности через разыменованные итераторы. Контейнер map не позволяет присваивание содержащихся в нем элементов; его элементы являются парами “константный ключ и связанное значение”, и константный ключ не может быть изменен. По этой причине такой код не будет компилироваться. Вместо использования remove_if и remove_copy_if, элементы контейнера map лучше удалить с помощью функции-члена erase.

Использование for_each

Используем другой подход на основе for_each: для каждого имени в файле, применим функцию, удаляющую соответствующую запись в map. Функциональный объект может выглядеть следующим образом:

template <class MapT>
class eraseFct {
public:
  eraseFct(MapT* m) : theMap(m) {}
  void operator() (string nam)
  { typename MapT::iterator iter = theMap->find(nam);
    if (iter == theMap->end()) 
        throw invalid_argument(nam);
    theMap->erase(iter);
  }
private:
  MapT* theMap;
};

template <class MapT>
eraseFct<MapT> eraser(MapT* m) 
{ return eraseFct<MapT>(m); }

Этот функтор может использоваться следующим образом:

map<string,info> directory_1;
// ... populate directory_1 ...
ifstream infile("toBeErased.txt");
for_each(istream_iterator<string>(infile),istream_iterator<string>(),
         eraser(&directory_1));

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

Итак, пока все хорошо. Теперь немного изменим задачу: теперь вместо удаления записей из каталога, мы должны разделить каталог, то есть, мы должны переместить записи, соответствующие именам в файле из существующего каталога в отдельный каталог. Как решить такую задачу?

Использование transform

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

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

template <class MapT>
class eraseFct {
public:
  eraseFct(MapT* m) : theMap(m) {}
  
  typename MapT::value_type
  operator() (string nam)
  { typename MapT::iterator iter = theMap->find(nam); // !
    if (iter == theMap->end()) 
        throw invalid_argument(nam);
    
    typename MapT::value_type res = *iter; // !

    theMap->erase(iter);
    
    return res; // !

  }
private:
  MapT* theMap;
};

template <class MapT>
eraseFct<MapT> eraser(MapT* m) 
{ return eraseFct<MapT>(m); }

Этот объект функции будет использоваться с transform для разделения каталога:

map<string,info> directory_2;
transform(istream_iterator<string>(infile),istream_iterator<string>(), 
          inserter(directory_2,directory_2.end()),
          eraser(&directory_1));

Мы могли бы также использовать его вместо исходного объекта функции с for_each для решения исходной задачи, а именно удаления записей:

map<string,info> directory_1;
// ... populate directory_1 ...
ifstream infile("toBeErased.txt");
for_each(istream_iterator<string>(infile),istream_iterator<string>(),
         eraser(&directory_1));

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

C transform ситуация на удивление другая. Эффект от передачи модифицированного объекта функции в transform не является ни предсказуемым, ни переносимым, так как стандарт позволяет использовать с transform только объекты функций без побочных эффектов, а наш функтор имеет побочный эффект, а именно удаляет элементы из контейнера map, на который указывает его член данных.

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

Теория против практики

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

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

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

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

Итак, что мы можем сделать в  переносимых  программах вместо использования transform? Мы видим два возможных решения: реализовать свою версию transform и использовать ее вместо стандартного алгоритма; или использовать for_each вместо transform.

Реализуйте собственную версию transform

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

template <class InputIterator, class OutputIterator, class Transformator>
OutputIterator relaxed_transform(InputIterator first, InputIterator last,
                         OutputIterator result, Transformator trans) {
  for ( ; first != last; ++first, ++result)
    *result = trans(*first);
  return result;
}

Эту реализацию вы найдете в большинстве реализаций transform стандартной библиотеки, однако, так или иначе, безопаснее использовать свою собственную версию, так как она является переносимым решением. Алгоритм выше может быть объявлен так:

template<class InputIterator, class OutputIterator, class Transformator>
OutputIterator relaxed_transform(InputIterator first, InputIterator last,
                             OutputIterator result, Transformator trans);
  • Эффект: trans применяется к результату разыменования каждого итератора в диапазоне [first, last), начиная с first и продолжая до last – 1 и присваивает через каждый итератор i в диапазоне [result, result + (last - first)) возвращаемое значение trans(*(first + (i - result)).
  • Требования: trans не должен иметь побочных эффектов, которые делают недействительным любой итератор в области [first, last) и [result, result + (last - first))
  • Возвращаемое значение: result + (last - first)
  • Сложность: last - first применений trans и last – first присваиваний.
  • Примечание: result может быть равным first.

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

Применение пользовательских версий алгоритма transform делает приложения переносимыми. Однако имеются и недостатки - таким версиям недоступен весь потенциал для оптимизации производительности.

Используйте for_each в случае сомнений

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

template <class MapT>
class moveFct {
public:
  moveFct (MapT* m1, MapT* m2) : theMap1(m1), theMap2(m2) {}
  void operator() (string nam)
  { typename MapT::iterator iter = theMap1->find(nam);
    if (iter == theMap1->end()) 
        throw invalid_argument(nam);
    theMap2->insert(*iter);
    theMap1->erase(iter);
  }
private:
  MapT* theMap1;
  MapT* theMap2;
};

template <class MapT>
moveFct<MapT> mover(MapT* m1,MapT* m2) 
{ return moveFct<MapT>(m1,m2); }

Этот функциональный объект может использоваться следующим образом:

map<string,info> directory_1;
// ... populate directory_1 ...
ifstream infile("toBeErased.txt");
for_each(istream_iterator<string>(infile),istream_iterator<string>(),
         eraser(&directory_1));

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

Резюме

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

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

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

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

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

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

Источник: http://www.angelikalanger.com/Articles/Cuj/03.ForeachTransform/ForEachTransform.html