Overloaded Sum Function, Confusing List/Vector with Map

Question

I'm still working on overloading a Sum function that can work with either vectors/lists or maps. My vector/list version of the sum function works fine, and I think my code for the map version is pretty decent, but when I test it, the compiler seems to think I'm trying to call the list/vector version of the function, and throws some compiler errors. Relevant code is as follows:

template <typename T>
const double Sum(typename T start_iter, typename T end_iter)
{// code...
}

template <typename T>
const double Sum(map<typename T, double> start_iter, map<typename T, double> end_iter)
{// different code...
}

int main()
{

map<string, double> test_map; // construct empty map

test_map["Line1"] = 10; // add some data
test_map["Line2"] = 15; 

Sum(test_map.begin(),test_map.end()) // this tries to call the list/vector version of sum
}

How am I confusing these functions? Thanks!

First, you're missing two `::iterator`s in the second declaration. The `typename` in `map` is also unnecessary. Second, in `map::iterator`, `T` is in a non-deducible context, so you're out of luck. You can try to overload based on whether `std::iterator::value_type` is a `pair` or not. — avakar, Oct 01 '12 at 09:01
So, it should be more like this? `const double Sum>(map::iterator start_iter, map::iterator end_iter)` — ch-pub, Oct 01 '12 at 09:08
@Clark: yes, but also pay attention to what avakar said about deducing T. If you call your function as `Sum(test_map.begin(),test_map.end())`, the compiler cannot work out by template argument deduction that `T` is supposed to be `string`. You could call it as `Sum(test_map.begin(),test_map.end())`. — Steve Jessop, Oct 01 '12 at 09:12
Regardless of how you write it, it won't work, because the compiler will not be able to deduce that `T` is a `string` by matching `map::iterator` against `map::iterator`. That's what is meant by non-deducible context. — avakar, Oct 01 '12 at 09:13
The reason, btw, is that there's nothing in the standard to say whether `map::iterator` is the same type as `something_else::iterator`. `iterator` is just a typedef in a class, it's a *name* for a type. Template argument deduction works on the types passed, not on the names for them. "Appears as a typedef in some class" is not a property of a type that the standard pays any attention to. — Steve Jessop, Oct 01 '12 at 09:15
If `Sum` only uses the values, then see http://stackoverflow.com/questions/259240/iterator-adapter-to-iterate-just-the-values-in-a-map. You can make it the caller's problem to pass the right values to `Sum`, rather than `Sum`'s problem to anticipate every container that exists or will exist in future, and know how to get out of it the "right" value to add. You're only special-casing `map` at the moment, but what about `unordered_map`, `multimap` and `unordered_multimap`? — Steve Jessop, Oct 01 '12 at 09:24

score 2 · Accepted Answer · answered Oct 01 '12 at 09:15

A slight alternative to what is being discussed in the comments:

template <typename Vt>
struct getter
{
  Vt operator()(const Vt& v)
  {
    return v;
  }
};

template <typename F, typename G>
struct getter<std::pair<F, G> >
{
  G operator()(const std::pair<F, G>& v)
  {
    return v.second;
  }
};


template <typename Iterator>
int sum(Iterator it, Iterator end)
{
  int r = 0;
  for(; it != end; ++it)
    r += getter<typename Iterator::value_type>()(*it);
  return r;
}

Now the sum function doesn't care what it is iterating over, simply rely on the appropriate getter to get the values...

For example:

  std::map<int, int> f;
  f[1] = 3;
  f[2] = 6;
  f[3] = 12;
  f[4] = 24;

  std::vector<int> g;
  g.push_back(4);
  g.push_back(8);
  g.push_back(16);
  g.push_back(32);

  std::cout << sum(f.begin(), f.end()) << std::endl;
  std::cout << sum(g.begin(), g.end()) << std::endl;

+1, nice solution that doesn't involve `enable_if` (which is what I'd use :) ). — avakar, Oct 01 '12 at 09:16
Although beware that calling `sum` using iterators to a `vector>` now adds up all the second elements. In the questioner's original code it presumably doesn't compile (because the body of `Sum` will try to add elements), and that might be desirable. — Steve Jessop, Oct 01 '12 at 09:17

score 0 · Answer 2 · answered Oct 02 '12 at 08:34

Well, as explained in the previous remarks, the compiler cannot deduce the container type of the iterator given as the parameter of Sum.

However, it is possible to use the fact that std::map<X,Y>::iterator::value_type is a pair of values std::pair<XX, YY>. Of course, this would not limit the desired specializing of Sum to std::map iterators, but to any container iterator returning a pair of element (eg. std::vector< std::pair<std::string, double> >.)

If this does not bother you, or if sthg like std::vector< std::pair<std::string, double> > should use the same specialization, then the following code seems to give the desired results in your case:

#include <map>
#include <string>
#include <iostream>
#include <cassert>
#include <boost/utility/enable_if.hpp>
#include <boost/type_traits/remove_reference.hpp>


// a small structure to 
template <class U>
struct is_a_key_pair_it
{
  typedef boost::false_type type;
};

template <class A, class B>
struct is_a_key_pair_it< std::pair<A, B> >
{
  typedef boost::true_type type;
};

// using boost::disable_if to avoid the following code to be instanciated 
// for iterators returning a std::pair
template <typename T>
const double Sum(T start_iter, T end_iter, 
  typename boost::disable_if<
    typename is_a_key_pair_it<
      typename boost::remove_reference<typename T::value_type>::type 
    >::type >::type * dummy = 0)
{
  // code...
  std::cout << "non specialized" << std::endl;
  return 0;
}

// using boost::enable_if to limit the following specializing of Sum
// to iterators returning a std::pair
template <typename T>
const double Sum(T start_iter, T end_iter, 
  typename boost::enable_if<
    typename is_a_key_pair_it<
      typename boost::remove_reference<typename T::value_type>::type 
    >::type >::type * dummy = 0)
{
  // different code...
  std::cout << "specialized" << std::endl;
  return 1;
}




int main()
{
  typedef std::map<std::string, double> map_t;

  // check
  assert(is_a_key_pair_it<map_t::iterator::value_type>::type::value);
  // works also for const_iterators
  assert(is_a_key_pair_it<map_t::const_iterator::value_type>::type::value);

  map_t test_map;
  test_map["Line1"] = 10; // add some data
  test_map["Line2"] = 15; 

  double ret = Sum(test_map.begin(),test_map.end()); 
}

Overloaded Sum Function, Confusing List/Vector with Map

2 Answers2