Re: std::transform
On 2011-07-01 08:11, Andy Johnson wrote:
Hi
I'm trying to implement the scan operator in terms of std::transform
as follows:
#include<iostream>
#include<algorithm>
#include<functional>
Your program misses to include header <vector>.
using namespace std;
template<typename T>
vector<T> scan(vector<T> v, function<int (int, int)> f)
{
vector<T> res(v.size()+1, 0);
transform(v.begin(), v.end(), res.begin(), res.begin()+1, f);
return res;
}
int main()
{
vector<int> input = {1, 2, 3, 4};
vector<int> res = scan(input, [](int a, int prev) {return a +
prev;});
for(auto i : res)
cout<< i<< ", ";
cout<< endl;
}
Which outputs 0, 1, 3, 6, 10,
This is to be expected, because you are using std::transform in the form
with two input sequences and one output sequences. The two original
input sequences are (in order):
{1, 2, 3, 4}
{0, 0, 0, 0, 0}
In your example the output sequence is identical to the second input
sequence, but starting at the second element (This combination is
allowed). Thus when doing the first iteration step within std::transform
the result sequence is supposed to have the following first two entries
(The * represents elements of res that we have not yet reached via
std::transform):
{0, 1, *, *, *}
The '1' being the result of summing v[0] to res[0], the initial '0'
follows because of your offset in res.
In the next step the algorithm adds v[1] == 2 to res[1] == 1 ending in
{0, 1, 3, *, *}
we proceed with v[2] == 3 and res[2] == 3 ending in
{0, 1, 3, 6, *}
and finally adding v[3] == 4 and res[3] == 6 ending in
{0, 1, 3, 6, 10}
2 questions:
1. If I create res to be equal in size to v and pass v.begin() as the
4th argument to std::transform I get 1, 2, 3, 4. Why?
Now your input sequences are
{1, 2, 3, 4}
{0, 0, 0, 0}
and the result sequence is now the start of the first input vector. If
we do a step-by-step iteration as specified by the standard we get get
in the first iteration in v
{1, *, *, *}
as the result of summing v[0] == 1 to res[0] == 0. We proceed with the
2nd step with v[1] == 2 added to res[1] == 0 written into v[1]:
{1, 2, *, *}
etc. until
{1, 2, 3, 4}
because in each step we just replace the corresponding input element of
the first sequence with the summation result.
2. Can the std::function parameter be rewritten to use the template
parameter?
You could, but then you would be required to convert the lambda
expression *explicitly* to std::function<int(int,int)>, which is no
improvement of the situation. There are two solutions out of this problem:
a) Make the second argument a non-deduced context. The signature would
now be changed to
template<typename T>
vector<T> scan(vector<T> v,
typename common_type<function<T (T, T)>>::type f);
I'm using std::common_type here as a replacement for an identity
mapping. This helps, because the compiler can already deduce T from the
first argument.
b) Instead of requiring a std::function object you could simply accept
*every* function object type. The signature of scan would now be changed to
template<typename T, typename F>
vector<T> scan(vector<T> v, F f);
HTH & Greetings from Bremen,
Daniel Kr?gler
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]