How do I use other values in a vector in a std::transform?

Viewed 257

Given the code below which just adds 1 to each element of a vector:

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    // Create vector 1 - print it out
    std::vector<int> v1 {1,2,3,4,5,6,7,8,9};
    for (auto val : v1)
    {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Create vector 2 by a transform of vector 1 + 1
    std::vector<int> v2(v1.size());
    std::transform(v1.begin(), v1.end(), v2.begin(),
        [](int val){ return val + 1; });

    // Print out vector 2
    for (auto val : v2)
    {
        std::cout << val << " ";
    }
    std::cout << std::endl;        
}


Instead of just adding 1 to each value I want to add the value of the previous element so that:

v[0] = v[0] (no previous value)
v[1] = v[1] + v[0]
v[2] = v[2] + v[1]
 etc...

So that I end up with:

1     = 1
2 + 1 = 3
3 + 2 = 5
4 + 3 = 7
etc...

Its a silly example - its not a maths puzzle or anything like that, I am just trying to figure out if I can use other values in my vector other then the one passed into the lambda function?

I am missing two bits of data in the lambda:

    std::transform(v1.begin(), v1.end(), v2.begin(), [](int val){
            // What is the index of val?
            // What is the size of the vector v1?
            // How would I express this:
            if (INDEX_OF(val) > 0)
                return val + INDEX_OF(val - 1);
            else
                return val;
        });

I can pass v1 in by capture and use that to do some calculations, but not quite what I want since I don't know the index.

    std::transform(v1.begin(), v1.end(), v2.begin(),
        [&v1](int val){ return val + v1.size() - v1[0]; });

Maybe transform is not the tool for this job and I need to resort to iterator loop?:

    std::vector<int> v2(v1.size());
    auto it2 = v2.begin();
    for (auto it1 = v1.begin(); it1 != v1.end(); it1++, it2++)
    {
        std::distance(v1.begin(), it1) == 0 ? *it2 = *it1 : *it2 = *it1 + *(it1 - 1);
    }

This works, but the point of my question is to know if it can be done with std::transform, or maybe some other algorithm?

4 Answers

You can add lambda capture to store the previous element's value.

E.g.

std::vector<int> v2(v1.size());
std::transform(v1.begin(), v1.end(), v2.begin(),
    [pv = 0](int val) mutable { int nv = pv + val; pv = val; return nv; });

LIVE

PS: Captures with initializer was supported since C++14.

@songyuanyao answers the question. This is similar solution to show how you can add a generic amount of memory for the previous values in your container.

#include <memory>

template<typename It1, typename It2>
void slide_transform(It1 first, It1 last, It2 write, size_t n = 1) {

    // a memory bank to store the previous values
    auto mem = std::make_unique<typename std::iterator_traits<It1>::value_type[]>(n);

    size_t rw = 0; // current position in memory

    std::transform(first, last, write,
        [&](const auto& val) {
            auto nv = val + mem[rw];
            mem[rw] = val;
            rw = (rw + 1) % n;
            return nv; 
        }
    );
}

// ...

// change 1 to a bigger value below to add earlier elements
slide_transform(v1.begin(), v1.end(), v2.begin(), 1);

For this to be really useful one would probably want to be able to provide a user defined functor taking the previous value as a parameter and in that case I'd skip using std::tranform and do something like this:

#include <memory>

template<typename It1, typename It2, typename Func>
void slide_transform(It1 first, It1 last, It2 write, size_t n, Func func) {
    auto mem = std::make_unique<typename std::iterator_traits<It1>::value_type[]>(n);
    size_t rw = 0;
    for(;first != last; std::advance(first, 1)) {
        auto copy = *first;
        *write = func(mem[rw], *first);
        std::advance(write, 1);
        mem[rw] = copy;
        rw = (rw + 1) % n;
    }
}
// ...

slide_transform(v1.begin(), v1.end(), v2.begin(), 1, [](auto prev_val, auto val) {
    return prev_val + val;
});

You've already gotten a couple of answers pointing out the ability to use a capture to temporarily store the previous value for the next iteration.

For the job at hand, however, I'd personally take a slightly different approach. The overload of std::transform you're using takes one input range, applies an operation to each element, and pushes each result to an output range.

There is, however, another overload that takes two input ranges, applies an operation to combine them, and push the result to an output. That fits your requirement much better--it just happens that in your particular case the two input ranges overlap each other.

This does have a difficulty deal with the first element, that you want copied intact. We could create a proxy that yielded a phantom first element of 0, but for a first attempt, it's probably easier to just copy the first element, then use the algorithm for the remaining items.

If you honestly cared solely about the problem as you've posed it, capturing a reference and using that to temporarily store the value from one invocation to the next would probably be the more obvious choice.

The advantage of this is that it's easy to apply when (for example) you want to add each element to the element that was, say, 4 or 5 elements previous rather than the one immediately previous. For that more general form of the problem, I'd probably write code on this general order:

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>

int main() { 
    std::vector<int> v1 { 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::vector<int> v2;

    int offset = 1;

    // copy the first N elements intact
    std::copy(v1.begin(), v1.begin() + offset, std::back_inserter(v2));

    // each remaining element gets added to the one N previous:
    std::transform(v1.begin()+offset, v1.end(), 
        v1.begin(), 
        std::back_inserter(v2), 
        [](auto a, auto b){ return a + b; });

    // show the result:
    std::copy(v2.begin(), v2.end(), std::ostream_iterator<int>(std::cout, "\t"));
    std::cout << "\n";
}

As it stands right now, this sets offset to 1, which matches the question as you posed it. But if, for example, you wanted the first three items copied across and the remaining items each added to the element 3 before it in the input, you'd change offset to 3 (and leave the rest of the code intact).

Instead of just adding 1 to each value I want to add the value of the previous element.

You exactly describe the partial_sum function from the standard library. You can pass as parameters user defined functions too. To know more about it click here.

Related