The algorithms for_each and transform are often understood as very similar in that they apply an operation (supplied as a function object) to each element in an input range. The difference is that for_each discards the operation's return value, while transform copies the return value to an element in the output range. This kind of understanding is a fairly common oversimplification. According to the Standard, however, the difference between both algorithms is more fundamental. Our goal in this installment of our column is to explain the conceptual difference between the algorithms and to point out the potential portability trap that the naïve understanding of the algorithms opens.
 
 

Reading the Standard

FOR_EACH . The for_each algorithm is specified in the Standard in the section of non-modifying sequence operations.
 
 

template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);

Effects: Applies f to the result of dereferencing every iterator in the range [first, last) , starting from first and proceeding to last - 1 .
• Returns: f
• Complexity: Applies f exactly last - first times.
• Notes:If f returns a result, the result is ignored.

template<class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform(InputIterator first, InputIterator last,
                         OutputIterator result, UnaryOperation op);

• Effects: Assigns through every iterator i in the range [result, result + (last - first)) a new corresponding value equal to op(*(first + (i - result)) .
• Requires: op shall not have any side effects [2] .
• Returns: result + (last - first)
• Complexity: Exactly last - first applications of op .
• Notes: result may be equal to first .

• for_each is a non-modifying algorithm; transform is a mutating algorithm.
• for_each ignores the operation's return value; transform assigns the return value to successive elements in the output range.
• for_each returns a copy of the function object; transform returns an iterator to the end of the output range.
• for_each applies the operation in a definite order, namely starting at the beginning and proceeding to the end of the input range; no such guarantee is given for transform .
• The operation supplied to transform must not have any side effects; no such restriction is imposed on the operation supplied to for_each .

The Intent

RETURN VALUES . Typical return values produced by algorithms are a Boolean value (see includes ), a count (see count_if ), an iterator pointing to a particular element in the input sequence (see find_if ), an iterator pointing to the end of a produced output sequence (see copy ), or a pair of iterators denoting an iterator range (see equal_range ). Most algorithms produce a return value, only a few do not (i.e., fill , replace , sort , and swap ).
 
 

Regarding modification of sequence elements, the Standard distinguishes between mutating (or modifying) and inspecting (or non-modifying) algorithms.

MUTATORS. Algorithms such as remove , replace , copy , or sort actively produce side effects, namely modification of elements in a sequence. Typically they do so by assigning values through dereferenced iterators. copy , for instance, assigns elements from the input range to elements in the output range. If the modified sequence is the input sequence, then the Standard talks of an in-place algorithm ; if the modification affects the output range, then it talks of a copy algorithm . For instance, replace_if is an in-place algorithm, while replace_copy_if is a copy algorithm.
 
 

INSPECTORS. The non-modifying algorithms, in contrast, do not assign to any sequence elements. Examples of non-modifying algorithms are find_if , count_if , and search . The actual purpose of an inspecting algorithm is not modification of any sequence element, but production of a return value.

In this sense, transform is a modifying copy algorithm since it modifies sequence elements by assigning the result of the function object to an element in the output range, whereas for_each is a non-modifying algorithm because it does not assign to any sequence elements.

As stated before, the sole purpose of a non-modifying algorithm is production of a return value. for_each is a non-modifying algorithm, and it returns the function object that was supplied to it. One might wonder: what is the point in applying for_each to a sequence of elements if it does not modify any elements and returns what it received? Does for_each have an effect at all? Indeed, for_each does not actively produce any side effect at all. The actual purpose of invoking for_each lies in the effects that the function object that is supplied to for_each produces when it is invoked for each element in the input sequence. More precisely: the function object may produce an effect by modifying the input sequence, and it can produce a useful result by mutating itself in the course of its invocations.

For this reason, the operation supplied to for_each is not restricted regarding side effects; invocation of for_each with a side-effect-free function object is utterly pointless. This is radically different for the operation supplied to transform , which according to the Standard must not have any side effects at all. And here we see the fundamental difference between for_each and transform . for_each depends on the side effect produced by the function object, while transform produces effects by itself and prohibits any side effects that the function object might produce.
 
 

In this sense, transform is a modifying copy algorithm since it modifies sequence elements by assigning the result of the function object to an element in the output range, and for_each is a non-modifying algorithm because it does not assign to any sequence elements.

The sole purpose of a non-modifying algorithm is production of a return value. for_each returns the function object that was supplied to it. Strictly speaking, for_each does not actively produce any side effect at all. The point of invoking for_each is the effects produced by the function object supplied to for_each . The function object may produce an effect by modify the input sequence, and it can produce a result by mutating itself in the course of its invocations.
 
 

For this reason, the operation supplied to for_each is not restricted regarding side effects; this is different from the operation supplied to transform , which according to the Standard must not have any side effects at all. This is the a fundamental difference between for_each and transform . for_each depends on the side effect produced by the function object, while transform produces effects by itself and prohibits any side effects that the function object might produce.
 
 

This difference explains why for_each gives a guarantee regarding order and number of invocations of the function object. When an operation produces side effects, we need to know how often and in which order the operation is invoked, because it might be sensitive to the number or order of invocations. transform , on the other hand, forbids any side effects of its function object and only guarantees the number of invocations as a sort of a complexity guarantee, but does not say anything about the order of invocation.
 
 

The Consequences

Side Effects

Side effects of a function object can be as harmless as writing output to a stream for debugging purposes or modifying its own data members, none of which would interfere with the side effects that the algorithm produces itself. Still, such a function object must not be supplied to transform because it violates the standard requirements.

On the other hand, it is common sense that a function object is not free to have any kind of side effect whatsoever. The side effects produced by a function object must not interfere with the activities performed by the algorithm. For instance, invalidating the iterators or the sequences that the algorithm works with is disastrous in any case. Even the function object supplied to for_each must obey this common-sense rule, even if the Standard does not say so.

Order of Invocation

Why would this matter in practice? Well, let's study an example.
 
 

A Concrete Example

The first idea might be to use the algorithms remove_if and remove_copy_if : remove an entry from the map if its name is contained in the file (and copy the entry to another map ). This of course does not work because remove_if and remove_copy_if are mutating algorithms, which try to assign values to elements in the input sequence through dereferenced iterators. The map container, however, does not allow assignment to its contained elements; its elements are pairs of a const key and an associated value, and the const key cannot be changed. For this reason, an attempted application of remove_if or remove_copy_if to the map container would not compile. Instead of using remove_if and remove_copy_if , elements in a map are better removed via the map 's erase member function

Using for_each

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));

So far, so good. Now, imagine the situation changes slightly: instead of removing entries from the directory, we must now split the directory; that is, we must move the entries corresponding to the names in the file from the existing directory into a separate directory. How do we solve the new problem?

Using transform

We slightly modify the original function object so that we can use it with transform . The main difference compared to the original function object is that the modified function object returns the value of the removed sequence element so that transform can store the value in the output sequence. All necessary modifications are marked in the implementation shown below:
 
 

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); }

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

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

The situation is surprisingly different with transform . The effect of supplying the modified function object to transform is neither predictable nor portable, because the Standard only allows side-effect-free function objects in conjunction with transform , and our function object has a side effect, namely removal of an element from the map that its data member points to.
 
 

Here we see the fundamental difference between for_each and transform . It's misleading to describe the two algorithms as very similar with the sole difference being that for_each ignores the return value of the function object while transform does not. Instead, the two algorithms work with entirely different categories of function objects: one is side-effect-producing; the other is side-effect-free.
 
 

Theory vs. Practice

One conceivable optimization would be execution of the transformation in parallel threads. A function object that is side-effect free is in particular thread-safe; since it cannot cause any change in the so-called execution environment, there cannot be any potential conflict if the function object is invoked from several threads in parallel. Such an optimized implementation of the transform algorithm would clearly break the code in our example.

The transformator in our example might erase an element from a map, which is not an atomic operation. One thread might be in the process of erasing an element while the other checks for the end of the map, which an instant later will be invalidated by the first thread, and as a result the second thread will crash. This is the prototypical race condition, and it stems from the fact that our transformator violates the requirement that it must not have side effects.

In practice, you will find that supplying a function object with side effects to the transform algorithm works just fine and yields predictable and reliable results with most implementations of the standard library. In fact, no library implementation that we know of takes advantage of the latitude that the Standard gives them for optimizing the algorithm. Still, keep in mind: strictly speaking it is not portable to use side-effect-producing transformators.

So, what can we do in a portable program instead of using transform ? Off-hand we see two potential solutions: implement a relaxed version of transform and use that instead of the standard transform algorithm, or use for_each instead of transform .

Implement Your Own Version of 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;
}

template<class InputIterator, class OutputIterator, class Transformator >
OutputIterator relaxed_transform(InputIterator first, InputIterator last,
                                 OutputIterator result, Transformator trans);

• Effects: Applies trans to the result of dereferencing every iterator in the range [first, last) starting from first and proceeding to last - 1 and assigns through every iterator i in the range [result, result + (last - first)) the return value of trans(*(first + (i - result)) .
• Requires: trans shall not have any side effects that invalidate any iterator in the range [first, last) and [result, result + (last - first)) .
• Returns: result + (last - first)
• Complexity: Exactly last - first applications of trans and exactly last - fir st assignments.
• Notes: result may be equal to first .

The purpose and benefit of the user-defined relaxed_transform algorithm is that it eases implementation of portable applications. The downside is that potential performance optimizations that a library implementation might provide for the standard transform algorithm taking advantage of the requirements imposed on the function object of transform are not available in this relaxed, user-defined version of the algorithm.
 
 

Use for_each in Case of Doubt

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));

Summary

In fact, for_each is an exception among the algorithms in the standard library: it is the only algorithm that gives exact guarantees regarding order and number of invocations of the function object and permits side effects including modification of elements from the input sequence. In detail:

• for_each is the one of the few algorithms in the standard library that gives a guarantee regarding the order in which it invokes the function object [3] . This allows application of order-sensitive functionality through a function object. Supplying order-sensitive function objects to any other algorithm is downright nonsensical since the result is unpredictable.
• for_each is the only algorithm that returns the function object. This allows application of function objects that accumulate in their data members' information, which can be retrieved after execution of the algorithm. Supplying such a function object to any other algorithm requires instantiation of those algorithms for a reference to the function object, which is kind of inconvenient since it involves explicit function argument specification, plus you will by struggling with library deficiencies [4] .
• for_each is one of the few algorithms that does not restrict the function object regarding side effects [5] .This gives users an enormous amount of flexibility regarding the implementation of function objects. All other algorithms impose requirements of varying degrees of severity on the function objects they use.

Notes and References

[2] The Standard defines a side effect as follows: Accessing an object designated by a volatile lvalue , modifying an object, calling a library I/O function, or calling a function that does any of those operations are all side effects , which are changes in the state of the execution environment.

[3] The other algorithms that give a guarantee regarding the order of invocation are the generalized numeric operations accumulate , inner_product , partial_sum , and adjacent_difference defined in header file <numerics> . These algorithms, different from for_each , require side-effect-free function objects.

[4] Klaus Kreft and Angelika Langer. "Effective Standard C++ Library: Explicit Function Template Argument Specification and the STL," C++Experts Forum .

[5]The other algorithm that does not restrict the side effects of its function object is generate .
 
 
 

If you are interested to hear more about this and related topics you might want to check out the following seminar:

Seminar   Effective STL Programming - The Standard Template Library in Depth 4-day seminar (open enrollment and on-site) IOStreams and Locales - Standard C++ IOStreams and Locales in Depth 5-day seminar (open enrollment and on-site)