accumulate the sum of elements in map, using value

Question

Say I have a

struct SMyStruct 
{
   int MULT;
   int VAL;

};


std::map<std::string, SMyStuct*> _idToMyStructMap;

Now I want to calculate total of all SMyStuct, where total is defined as MULT1 *VAL1 + MULT2 *VAL2 for each elements in the idToMyStructMap.

Seems like accumulate function is a natural choice. Please suggest. thanks

No Boost please.... just an 'ld fashion stl

Aw, bb beat me to the answer, so I'm going to be a bit pedantic instead: You know leading underscores are generally a bad idea, right? (reserved to the implementation in most cases) And the S prefix on a struct is completely pointless noise. :) — jalf, Apr 06 '09 at 15:14
argh, ok ... Well we always prefix structs with S and classes with C; our coding standard mandates. Insofar as "_", I agree but since it wasn't part of anything, I left it as such. I typically use m_ for members g_ for globals and s_ for static. Thanks for pointing it out. — , Apr 06 '09 at 15:23
The _ *might* technically be ok. The rules are something like "Double leading _ OR leading _ followed by capital letter is reserved to the implementation. Leading _ followed by anything else is reserved in the global namespace". Easiest to just avoid leading _'s altogether ;) — jalf, Apr 06 '09 at 15:29
This has a nice summary of various forms of names reserved in C/C++: http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier/228797#228797 — Michael Burr, Apr 06 '09 at 16:42
although it could be done using `std::accumulate` but I am not sure if that is worth the efforts and compromise of readability, as the complexity of operation remains unchanged. — sabertooth1990, Sep 07 '15 at 09:59

score 13 · Accepted Answer · answered Apr 06 '09 at 15:09

13

typedef std::map< std::string, SMyStruct* > string_to_struct_t;

int add_to_totals( int total, const string_to_struct_t::value_type& data )
{
    return total + data.second->MULT * data.second->VAL; 
}

const int total = std::accumulate(
                         _idToMyStructMap.begin(),
                         _idToMyStructMap.end(),
                         0, 
                         add_to_totals );

answered Apr 06 '09 at 15:09

bayda

13,365
8
39
48

1

Would be more efficient to write add_to_totals as an object with an operator(). Otherwise, good solution. – pauljwilliams Apr 06 '09 at 15:15
2

@bb: Because if it's a struct, the compiler can deduce which function is called, and trivially inline it. If it is a function pointer, it has to do some fairly complex interprocedural analysis to determine which function is called. So you generally can't count on it inlining the call. – jalf Apr 06 '09 at 15:18
2

That is, if it had been a struct, then the type to call would be add_to_totals::operator(), which is one static function. With a function pointer, the type is merely "int(*)(int, const string_to_struct_t::value_type&)", so the actual function is unknown. – jalf Apr 06 '09 at 15:20
Read this post about underscores in identifiers: http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier – Martin York Apr 06 '09 at 15:33
@Martin: Wow, great post. Wonder why I hadn't seen that one before. Good to know. :) – jalf Apr 06 '09 at 16:17
@jalf: really interest comment, I'm never thought on this. @Martin: Thank you, I know just about begining underscore and double underscores. – bayda Apr 06 '09 at 20:51

score 6 · Answer 2 · edited Apr 06 '09 at 17:05

6

A variation on the theme would be to define operator+ for your struct, and then just use std::accumulate in its default mode.

int & operator+ (const int &lhs, const SMyStruct &rhs){
    return lhs + (rhs.MULT * rhs.VALUE);
}

Then:

std::accumulate(_idToMyStructMap.begin(), _idToMyStructMap.end(), 0);

Of course, if operator+ makes sense in general for your struct, then you'd want to add overloads for using SMyStruct on the left as well, and/or make them templates so that you get functions for int, float, double, long, etc. all in one shot. As jalf mentioned in comments, if operator+ (or this version of it) doesn't make sense in general for your struct, then the other solution is better.

edited Apr 06 '09 at 17:05

Svante

50,694
11
78
122

answered Apr 06 '09 at 15:11

Harper Shelby

16,475
2
44
51

The problem with that is that you now have an operator+ which is visible throughout your codebase, but only makes sense in this specific context. May be confusing to anyone reading (or maintaining) the code. – jalf Apr 06 '09 at 15:16
@jalf - perhaps, but perhaps not. It may actually make sense in more places, I don't know. If it doesn't, then it's a legitimate reason not to choose this path. – Harper Shelby Apr 06 '09 at 15:55
It will not work. You should write operator+(...) for std::map::value_type – bayda Apr 06 '09 at 16:13
I agree with @jaff about the code quality; bb's solution is cleaner for this problem. Thx – Apr 06 '09 at 18:29
on top of that, bb's right: accumulate will try to find operator+( pair&, pair ) when map.begin() and map.end() are taken as iterators. The essential problem is dereferencing something wrapped inside the pair. – xtofl Apr 06 '09 at 18:47
Yeah, I see that - just don't have time to fix it just now. – Harper Shelby Apr 06 '09 at 21:00

score 1 · Answer 3 · answered Apr 06 '09 at 19:55

You can also separate the 'take second of pair' functionality from 'calculate MULT*VAL' and 'add something to an accumulator'.

Though you don't need boost to do this, they already created a great deal of a 'functional' programming framework. If you can't use boost, you need some template magic of your own. Not too complicated, though.

#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iostream>

Now I deem it better to put the multiplication inside the class.

struct SMyStruct 
{
   int MULT;
   int VAL;
   long f() const { return MULT*VAL; }
};

Create a generic functor for 'take second of pair':

// a 'take-second' functor
template< typename at_pair >
struct to_second_t : public std::unary_function< at_pair, typename at_pair::second_type > {
  const typename at_pair::second_type& operator()( const at_pair & p ) const {
    return p.second;
  }
};

This looks tricky, but is merely a generic way of saying: 'first do this, then do that with the result':

// compose two functors (simplified)
template< typename at_F, typename at_G >
struct compose_t : public std::unary_function< typename at_F::argument_type, typename at_G::result_type >{
    at_F f;
    at_G g;
    compose_t( at_F& f, at_G& g ): f( f ), g(g) {}

    typename at_G::result_type operator()( const typename at_F::argument_type& v ) const {
        return g( f( v ) );
    }
};

template< typename at_F, typename at_G >
compose_t<at_F, at_G> compose( at_F& f, at_G& g ) { return compose_t<at_F,at_G>( f, g ); }



// compose two functors (a unary one, and a binary one)
//
template< typename at_F, typename at_G >
struct compose2_t : public std::binary_function< typename at_F::first_argument_type, typename at_G::argument_type, typename at_G::result_type >{
    at_F f;
    at_G g;
    compose2_t( at_F& f, at_G& g ): f( f ), g(g) {}

    typename at_G::result_type operator()( const typename at_F::first_argument_type& a1, const typename at_G::argument_type& v ) const {
        return f( a1, g( v ) );
    }
};

template< typename at_F, typename at_G >
compose2_t<at_F, at_G> compose2( at_F& f, at_G& g ) { return compose2_t<at_F,at_G>( f, g ); }

And finally, putting it all in practice:

int main()
{
  typedef std::map<int, SMyStruct > tMap; 
  tMap m;
  SMyStruct s = {1,2};
  m[1].VAL = 1; m[1].MULT = 3;
  m[2].VAL = 2; m[2].MULT = 10;
  m[3].VAL = 3; m[3].MULT = 2;

  // mind, this is not LISP (yet)
  long total = std::accumulate( m.begin(), m.end(), 0, 
    compose2( 
      std::plus<int>(),  
      compose( 
        to_second_t<tMap::value_type>(), 
        std::mem_fun_ref( &SMyStruct::f ) ) )
    );

  std::cout << "total: " << total <<std::endl;
  return 0;
}

accumulate the sum of elements in map, using value

3 Answers3