How to apply std::accumulate algorithm for associative containers?

Question

For a map like std::map, how do I accumulate it's values' sum?
Actually, I made it with a functor and std::for_each algorithm. But I'd also like to make this using std::accumulate algorithm.
I have no idea how to apply it to std::map.
Is this even possible?

struct Accumurator
    : std::unary_function<std::pair<int, int>, void>
{
    Accumurator()
        : totalValue_(0)
    {
    } 

    void operator()(const std::pair<int, int>& p)
    {
        totalValue_ += p.second;
    }

    int result() const
    {
        return totalValue_;
    }

    int totalValue_; 
};

int _tmain(int argc, _TCHAR* argv[])
{
    std::map<int, int> m;
    m.insert(make_pair(1, 10));
    m.insert(make_pair(2, 10));
    m.insert(make_pair(3, 10));
    m.insert(make_pair(4, 10));
    m.insert(make_pair(5, 10));
    m.insert(make_pair(6, 10));

    int totalSum = std::for_each(m.begin(), m.end(), Accumurator()).result();

    // How can I apply accumulate algorithm for associative containers.
    // int totalSum = accumulate(m.begin(), m.end(), ???);

    return 0;
}

score 6 · Accepted Answer · answered Aug 04 '11 at 01:32

6

Almost. The functor must be a binary operator taking the return value type as the first and the range type as the second argument:

x = Functor(init, *it++);
x = Functor(x, *it++);
x = Functor(x, *it++);
// ... until it == end

So you don't need a stateful functor at all, a simple function will do:

int map_acc(int lhs, const std::pair<int, int> & rhs)
{
  return lhs + rhs.second;
}

const int sum = std::accumulate(m.begin(), m.end(), 0, map_acc);

answered Aug 04 '11 at 01:32

Kerrek SB

464,522
92
875
1,084

1

Aha, **_Fn2** type means binary function/functor? Helpful. I haven't noted about that. – Benjamin Aug 04 '11 at 02:25

score 2 · Answer 2 · answered Aug 04 '11 at 01:32

std::accumulate requires an init argument and a binary operation to perform. Your binary operation needs to accept a pair as the second argument and int as the first argument and return int.

struct pair_add {
  int operator()(int i, const std::pair<int, int>& x) {
    return i + x.second;
  }
};
//use as
int totalSum = accumulate(m.begin(), m.end(), 0, pair_add());

The real problem is to get the functor as generic as possible.

How to apply std::accumulate algorithm for associative containers?

2 Answers2

Linked