what does [] const_iterator::value_type in std::transform mean

Question

specifically here is the code. What is line 15 doing (call to transform)?

Can someone please explain why this outputs 01234? On the other hand if I change cb to ++cb in line 15, it outputs 01110. What is the return value on line 15 doing?

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>

int main()
{
    typedef std::list<int> L;
    L l(5);

    typedef L::const_iterator CI;
    CI cb = l.begin(), ce = l.end();
    typedef L::iterator I;
    I b = l.begin();
    std::transform(cb, --ce, ++b, [] (CI::value_type n) { return ++n; });
    std::copy(l.begin(), l.end(), std::ostream_iterator<CI::value_type>(std::cout));
    std::cout << std::endl;

    return 0;
}

Answer 1

The expression [](CI:value_type n) { return ++n; } is a lambda function. The empty brackets mean that it does not access any members of the current scope.

transform basically applies this function to each element of the input sequence (l) and writes it to the output sequence (also l). It stops when the element before the last one has been reached because of the --ce.

The code takes one element of l after the other and increments it into the next element of l (because of the ++b). Therefore you get 0, 1, 2, 3, 4.

If you change cb to ++cb, you get 0, 1, 1, 1, 0 because then, you start at the element with index 1 and just increment each one until the before last one.

Find some information about lambdas here.

Explanation of std::transform

Answer 2

In this statement

L l(5);

there is created a list of 5 elements each of which is initialized by 0.

In this call

std::transform(cb, --ce, ++b, [] (CI::value_type n) { return ++n; });

cb points to the first element of the list. --ce after evaluation the decrement operator points to the last element of the list. Thus cb and --ce set range of elements of the list

[cb, --ce)

where the parenthesis means that --ce is not included in the range.

++b after evaluation of the increment points to the second element of the list. So you have

  b 
  | 
 0 0 0 0 0
^       ^
|       |
cb      ce

The value pointed to by cb that is the value of the first element of the list is increased in the lambda expression

[] (CI::value_type n) { return ++n; }

and is written in the second element of the list pointed to by iterator b. After that cb and b are incremented within the body of transform.

So after the first iteration the list looks like

    b 
    | 
 0 1 0 0 0
  ^     ^
  |     |
  cb    ce

Now cb points to the second element of the list. Its value is incremented in the lambda expression and is written in the third element pointed to by iterator b.

      b 
      | 
 0 1 2 0 0
    ^   ^
    |   |
    cb  ce

As a result you will get that list will have values 0, 1, 2, 3, 4.

If you will write the call of the algorithm like

std::transform(++cb, --ce, ++b, [] (CI::value_type n) { return ++n; });

that is using ++cb then cb and b will point to the same element and the algorithm simply will rewrite each element with its incremented value starting from the second element of the list because there was used iterator ++cb. The result will be 0, 1, 1, 1, 0

Answer 3

First, you need to get through the syntax: square brackets indicate that your lambda function is not capturing anything from its surrounding context. Basically, this is a succinct way of plugging in a piece of logic into the call of std::transform: you tell the function that transforming a value means adding one to it.

To further understand what is going on, and also to explain the 01110 output, let's see what std::transform does: it takes items from cb (the initial element) up to --ce (the second element from the back), inclusive, calls the lambda function, and places the result it returns into cells starting at ++b, i.e. at indexes 1, 2, 3, and so on.

The first iteration takes zero from L[0], adds one, and writes 1 into L[1]. The second iteration picks up the 1 from before, adds one, and writes 2 into L[2]. The iteration continues until std::transform writes 4 into L[4].

When you replace cb with ++cb, however, the writing is performed into the same cell from which the data was read, i.e. L[1] gets assigned 0+1, then L[2] gets assigned 0+1, then L[3] gets assigned 0+1, and then the loop reaches --ce, and stops.

Note that ++n is unnecessary, because the side effect of incrementing n disappears as soon as the lambda call is over. You can replace it with n+1 expression, which has no side effect:

std::transform(cb, --ce, ++b, [] (CI::value_type n) { return n+1; });