Skip to main content

Avoiding intermediate copies in std::accumulate

std::accumulate makes a ton of copies internally. In fact it's 2x the size of the number of elements in the iterator range. To fix, use std::ref and std::reference_wrapper for the initial state. std::shared_ptr is also a possibility if the accumulated state must be dynamically allocated for some reason. Live code on wandbox.

Update: Please see alternative solutions in the comments section.

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <functional>

struct Vector : public std::vector<int> {
  Vector(std::initializer_list<int> il) : std::vector<int>(il){
    std::cout << "Vector(std::initializer_list)\n";
  }
  Vector() {
    std::cout << "Vector()\n";
  }
  Vector(const Vector &v) : std::vector<int>(v) {
    std::cout << "Vector(const Vector &)\n";
  }
  Vector & operator = (const Vector &v) {
    if (this != &v) {
      std::vector<int>::operator=(v);
      std::cout << "Vector& Vector::operator=(const Vector &)\n";
    }
    return *this;
  }
  Vector & operator = (Vector && v) {
    if (this != &v) {
      std::vector<int>::operator=(std::move(v));
      std::cout << "Vector& Vector::operator=(Vector&&)\n";
    }
    return *this;
  }
  Vector(Vector&& v) : std::vector<int>(std::move(v)) {
     std::cout << "Vector(Vector&&)\n";
  }
};

void copy_accumulate(Vector &v) {
    Vector v2 = std::accumulate(v.begin(), v.end(), Vector(), 
                    [](Vector & v, int i) {
                      v.push_back(i);
                      return v;
                    });
    std::cout << "size of v2 = " << v2.size() << "\n";
}

void nocopy_accumulate(Vector &v) {
    Vector init;
    Vector v2 = std::accumulate(v.begin(), v.end(), std::ref(init), 
                    [](std::reference_wrapper<Vector> v, int i) {
                      v.get().push_back(i);
                      return v;
                    });
    std::cout << "size of v2 = " << v2.size() << "\n";
}

int main()
{
    Vector v { 1, 2, 3, 4 };
    copy_accumulate(v);
    std::cout << "=============\n";
    nocopy_accumulate(v);
}

Comments

MR said…
try this one
void copy_accumulate(Vector &v) {

Vector v2 = std::accumulate(v.begin(), v.end(), Vector(),
[](Vector & v, int i)->Vector& {
v.push_back(i);
return v;
});
std::cout << "size of v2 = " << v2.size() << "\n";
}
Anonymous said…
Because std::accumulate is intended for numeric accumulators, so copy worth nothing with them.
Anonymous said…
void copy_accumulate(Vector& v) {
Vector v2 = std::accumulate(v.begin(), v.end(), Vector(),
[] (Vector& v, int i) {
v.push_back(i);
return std::ref(v);
});
std::cout << "size of v2 = " << v2.size() << "\n";
}
Sumant Tambe said…
Good alternative solutions. Thanks folks!

Popular posts from this blog

Understanding Fold Expressions

C++17 has an interesting new feature called fold expressions. Fold expressions offer a compact syntax to apply a binary operation to the elements of a parameter pack. Here’s an example. template <typename... Args> auto addall(Args... args) { return (... + args); } addall(1,2,3,4,5); // returns 15. This particular example is a unary left fold. It's equivalent to ((((1+2)+3)+4)+5). It reduces/folds the parameter pack of integers into a single integer by applying the binary operator successively. It's unary because it does not explicitly specify an init (a.k.a. identity) argument. So, let add it. template <typename... Args> auto addall(Args... args) { return (0 + ... + args); } addall(1,2,3,4,5); // returns 15. This version of addall is a binary left fold. The init argument is 0 and it's redundant (in this case). That's because this fold expression is equivalent to (((((0+1)+2)+3)+4)+5). Explicit identity elements will come in handy a little la…

Multi-dimensional arrays in C++11

What new can be said about multi-dimensional arrays in C++? As it turns out, quite a bit! With the advent of C++11, we get new standard library class std::array. We also get new language features, such as template aliases and variadic templates. So I'll talk about interesting ways in which they come together.

It all started with a simple question of how to define a multi-dimensional std::array. It is a great example of deceptively simple things. Are the following the two arrays identical except that one is native and the other one is std::array?

int native[3][4];
std::array<std::array<int, 3>, 4> arr;

No! They are not. In fact, arr is more like an int[4][3]. Note the difference in the array subscripts. The native array is an array of 3 elements where every element is itself an array of 4 integers. 3 rows and 4 columns. If you want a std::array with the same layout, what you really need is:

std::array<std::array<int, 4>, 3> arr;

That's quite annoying for two r…

Folding Monadic Functions

In the previous two blog posts (Understanding Fold Expressions and Folding Functions) we looked at the basic usage of C++17 fold expressions and how simple functions can be folded to create a composite one. We’ll continue our stride and see how "embellished" functions may be composed in fold expressions.

First, let me define what I mean by embellished functions. Instead of just returning a simple value, these functions are going to return a generic container of the desired value. The choice of container is very broad but not arbitrary. There are some constraints on the container and once you select a generic container, all functions must return values of the same container. Let's begin with std::vector.
// Hide the allocator template argument of std::vector. // It causes problems and is irrelevant here. template <class T> struct Vector : std::vector<T> {}; struct Continent { }; struct Country { }; struct State { }; struct City { }; auto get_countries…