C++ – From goto to std::transform

[exDM69]

What I find painful about writing pseudo-functional C++ using <algorithm> and other tricks is that you have to allocate storage for intermediate values. This makes C++ algorithms a lot less composable than similar things in other languages.

So if I wanted to do something like (in Haskell):

    sumOfOddSquares xs = sum . map (^2) . filter odd $ xs

In C++, I would need to allocate temporary storage for the intermediate values.

    std::vector odd_numbers;
    std::copy_if(xs.begin(), xs.end(), back_inserter(odd_numbers), isOdd);
    std::transform(odd_numbers.begin(), odd_numbers.end(), odd_numbers.begin(), square);
    std::accumulate(odd_numbers.begin(), odd_numbers.end(), 0, plus);

This becomes quite painful very quickly. You can use solutions like boost::filter_iterator, but soon you're knee deep in C++ templates and the long compile times and awful error messages that follow.

The example above is a bit contrived since it can be easily be done with a single accumulate, but you get the idea...

    std::accumulate(xs.begin(), xs.end(), 0,
        [](int sum, int i) { return sum + ((i&1) ? i*i : 0); });

So while you can have lots of fun with <algorithm>, it's quite limited in what it can do.

[humanrebar]

On the other hand, C++ has more flexibility. Since C++ allows you to specify your allocation scheme, you can guarantee a piece of code will never trigger an allocation, allocate in a special way to ensure cache coherence, etc.

For example, you could have written equivalent logic that allocates odd_numbers on the stack or from a special memory pool.

Sure, application developers shouldn't care about that kind of fine-grained control. However, they should care about having fast, small, safe, and high-quality libraries available. For library authors and developers in special domains (high-performance, safety-critical, etc.), these tools are essential.

[nhaehnle]

This is indeed painful. However, with C++11's move semantics, I suspect libraries will over time develop in ways that make this less painful. See nly's comment for an example.

[nly]

<algorithm> is so 90s. In C++14 you'll be able to do this:

    auto square_copy = [](auto v) {
       for (auto& e: v) { e *= e; }
       return v;
    };

Another option:

    auto square = [](auto& v) { v *= v; };

    auto map = [](auto range, auto fun) {
        transform (begin(range), end(range), fun); 
        return range;
    };

    vector<int> vec = {1,2,3,4,5,6};
    auto squared = map (vec, square);

Note that, in both of these cases, if you use std::move() to gift a container to these functions, they will not actually allocate any memory and will effectively operate in-place.

[stormbrew]

Am I missing something? I don't see anything beyond C++11 in here.

[ajtulloch]

Using Facebook's `folly::gen` library [1], you can get it down to:

    vector<int> squareVec3(const vector<int>& v) {
      return from(v) | mapped([](int i){ return i * i; }) | as<vector>();
    }

which is pretty slick. There are a bunch of the usual LINQ/functional operators in `folly::gen` that are quite nice. As an example, to filter out the odd elements of `v`, you can do

    vector<int> squareVecFiltered(const vector<int>& v) {
      return from(v) 
           | filter([](int i){ return i % 2 == 0; })
           | mapped([](int i){ return i * i; })  
           | as<vector>();
    }

https://github.com/facebook/folly/tree/master/folly/gen

[pfultz2]

Or using [Linq](https://github.com/pfultz2/Linq):

    vector<int> squareVec(const vector<int>& v)
    {
        return LINQ(from(i, v) select(i*i)) | linq::to_container;
    }

And also filtering out odd elements:

    vector<int> squareVecFiltered(const vector<int>& v)
    {
        return LINQ(from(i, v) where(i % 2 == 0) select(i*i)) | linq::to_container;
    }

[humanrebar]

That's cool, but I'd rather not bitwise-or my functional operators together. Something like this would be better:

    vector<int> squareVecFiltered(const vector<int>& v) {
      return from(v
           filter([](int i){ return i % 2 == 0; }),
           mapped([](int i){ return i * i; }),
           as<vector>());
    }

[stormbrew]

C++ is evolving at a kind of breakneck pace lately, and it's already a lot different from the language it used to be. Auto, range loops, and lambdas are making it much more pleasant to work in while still maintaining a lot of performance advantages.

I know it's pretty popular to hate on C++, but I'm pretty excited about where it's going, personally.

[spoiler]

I've recently started working in C++ (I've had some prior knowledge, but mostly basics) and whenever I try to Google stuff up, a few of the results are Don't use C++ because of X

I read a few of them out of curiosity, and realised that they are mostly religious reasons to hate C++, hardly any of them are proper, factual, or empirical reasons. So, my hypothesis is the following: They were unable to learn C++, and because of immaturity, decided it was stupid[0][1].

[0]: I'm no saint to this. I said on numerous occasions Erlang is shit because I couldn't wrap my head around the syntax.

[1]: I believe it's a phenomenon associated with Psychological Projection, but I might've confused it with something else.

[jeorgun]

I'm not really sure why references are being used here, if you're just making a copy straight-away.

    vector<int> square(vector<int> vcopy)
    {
        for (int &i : vcopy)
            i *= i;
        return vcopy;
    }

is shorter, (IMO) much more readable, and on my tests, measurably faster than the reference version. If you really want the std::accumulate version,

    vector<int> square(vector<int> vcopy)
    {
        accumulate(begin(vcopy), end(vcopy), begin(vcopy),
                   [](int i) { return i * i; });
        return vcopy;
    }

works just as well.

Still, I guess it's beside the point.

[Dobiasd]

Awesome! It is more readable and makes it faster. Thank you very much. I changed my article accordingly.

[humanrebar]

I like your version better, but I suspect it would be significantly slower for many compilers that you are not testing.

[pathikrit]

After coding in languages in like Scala/Python for a while, it took me a while to parse this. Scala equivalent: `def square(a: List[Int]) = a map {i => i*i}`

[douglasheriot]

After in coding in languages like C/C++/ObjC for a while, it took me a while to parse your Scale equivalent.

Personally I find the C++ much clearer – I don’t see either as that much better/worse.

[Jare]

Convenience overloads for common use cases (iterating over the full vector, accumulating on a default-constructed accumulator, etc) would be great to have as standard. Are there and I have missed them? If not, what's the rationale? (this goes for the STL in general, not specifically these high order algos)

[Negitivefrags]

Here is a blog post on this very issue:

http://herbsutter.com/2011/10/07/why-no-container-based-algo...

[crawshaw]

Readability improved from squareVec1 to squareVec4, then went downhill. Hiding loops behind new names doesn't make programming better.

[nly]

At Going Native last year Sean Parent, from Adobe, gave a superb talk called 'C++ Seasoning' where his number one pro-tip for C++ was: no raw loops.

He made a good case that anywhere you have a non-trivial loop in C++, you're almost always going to be better off folding the problem in to a composition of algorithms. The code got more readable, more performant, and redundant code can often be removed.

Please take an hour to watch it here in glorious high quality:

http://channel9.msdn.com/Events/GoingNative/2013/Cpp-Seasoni...

[rootlocus]

It does if you're familiar with the common high-order functions used in functional programming.

[notacoward]

My thoughts exactly. It's simply not true that "everybody knows without thinking" what the std::accumulate version will do. It's specific not only to a particular pattern but to the expression of that pattern in a particular language. People new to C++ won't be able to parse "[](vector<int> acc" right away, and it's key to understanding the whole. By contrast, the range-based for loop is obvious even to a C++ novice and easily guessable even by those who don't know C++.

If you want something that's both concise and readable, try the Python list-comprehension version. That is an elegant solution. The C++ accumulate/transform solutions are the very opposite of elegant. In a code review, I would flag them as obfuscatory.

[vinkelhake]

Just as a side note: if you're looking to write a convenience wrapper like the author's transformVec, do not have it take the function as `const function<T(T)>&`. Instead, do something like:

    template <typename T, typename F>
    vector<T> transformVec(const vector<T>& v, F op)

Using std::function in a case where you just want something callable just makes the optimizer's job a lot harder. Using std::function is a good idea if you actually need type erasure (for example if you want to pass something callable to a function that is not a template).

[Dobiasd]

Wow, awesome tip, thanks. This makes the wrapped version as fast as the others. I updated my article accordingly.

[Marat_Dukhan]

The author probably thinks that all versions are equally fast, but in fact they are just equally slow. Neither gcc 4.8 nor icc 14 can use vectorization for this loop (likely because of aliasing).

[pbsd]

It's not because of aliasing, it's because of the push_back call inside the inner loop, which may potentially have to allocate (in this case we know it doesn't, but the compiler does not). If you replace squareVec6 with

    vector<int> squareVec6(const vector<int>& v)
    {
        vector<int> result(v.size()); // preallocate
        // result.reserve(v.size());
        transform(begin(v), end(v), begin(result), [](int i)
        {
            return i*i;
        });
        return result;
    }

the compiler will be happy to vectorize the loop.

[heliumcraft]

  def square(vector)
    vector.collect { |i| i**2 }
  end

[adamnemecek]

Cool, it will also be probably 30x slower.

[milliams]

I like the Python version of:

  def square(vector):
    return [v**2 for v in vector]

[spoiler]

Y not map.

[u124556]

`result = [i * i for i in v]` looks much more readable to me.

What if you need to square every other element? copy_if and transform then don't look so pretty anymore. `result = [i * i for i in v if i % 2 == 0]` is still more readable.

What if you need to do something else and you don't know if there is a transform like function for it?

[alecbenzer]

> What if you need to do something else and you don't know if there is a transform like function for it?

What about the same thing in python? As far as I know the two examples you gave exhausted list comprehensions' functionality.

[geocar]

It seems like it's the loop itself that is redundant. Why couldn't I just do:

    squaredVec = vec * vec

or

    squaredVec = vec ^ 2

[bstamour]

You can, but not with vector. Use valarray if you need to perform those kinds of computations.

[ww2]

The example is too trivial. you could have 100 ways to write "hello world", but it does not matter.

[GFK_of_xmaspast]

Why were all the examples using iterators, and not square bracket indexing?

[mytummyhertz]

am i the only one who thinks the std::transform version is LESS readable than the for loop?

[shultays]

  but you still have to read the whole line

Oh the pain!