Pass Templated iterator for STL Container

Question

For an exercise for my C++ class (which hasn't covered Boost yet), I am having trouble writing a templated method to accept two iterators for summing numeric values in an STL container.
Consider the following example:

#include <iostream>
#include <iterator>
#include <vector>

template<typename T>
double Sum(const T & c) {
    return 42.0;    // implementation stubbed
}

// need help writing this method signature to accept two iterators
template<typename T>
double Sum(const typename T::const_iterator & begin,
           const typename T::const_iterator & end) {
    return 43.0;    // another implementation stub
}

int main() {
    std::vector<double> v;
    v.push_back(3.14);
    v.push_back(2.71);
    v.push_back(1.61);    // sums to 7.46

    std::cout << Sum(v) << ' '              // line 23
              << Sum(v.begin(), v.end())    // line 24
              << '\n';
}

I expect this code to output 42 43, but it fails to compile.
The error g++ gives me is:

test_exercise2.cpp: In function ‘int main()’:
test_exercise2.cpp:24: error: no matching function for call to ‘Sum(__gnu_cxx::__normal_iterator<double*, std::vector<double, std::allocator<double> > >, __gnu_cxx::__normal_iterator<double*, std::vector<double, std::allocator<double> > >)’

If I comment out line 24, I get 42 as the output, as expected.
I get the same error message whether or not the second templated method is present or not, so for some reason, it's not able to resolve the call on line 24 to the second method I wrote.

What signature must I have for the method that accepts two iterators?

---

The reason why I'm stuck on this is because I need to support summing over the second element of std::map<K, V>. This will require two more overloads to call ->second instead of dereferencing the iterator:
1. template<typename K, typename V> double Sum(const std::map<K, V> & m); (I'm okay with this one)
2. and another one involving iterators over the map.

I feel like I'll be able to write the methods for std::map if I can figure out how to specify the passing of iterators for std::list and std::map. I'm okay with solutions that use template-templates.

---

EDIT: The precise wording of problem (omitting non-contributory sentences).
The containers from "the previous exercise" were std::vector<double>, std::list<double>, std::map<std::string, double>.

Create a template function called Sum() that accepts the template argument T as input and returns a double. The template argument will be a container.

• In the implementation get an iterator (T::const_iterator) for the end. Then create a loop that iterates the container T and adds all values. Finally return the sum.
• In the main program, call the Sum() function for the different container from the previous exercise.

The Sum() function created calculates the sum of the complete container. Also create a Sum() function that calculates the sum between two iterators. The function then uses the template argument for the iterator type and accepts two iterators, the start and end iterator.

Answer 1

The distinguishing feature when contrasting iterators from e.g. std::list with iterators from std::map is that the latter have a pair type as their value_type. That is to say, given std::map<K, V> then both std::map<K, V>::value_type and std::iterator_traits<std::map<K, V>::iterator>::value_type are std::pair<const K, V>.

Hence I suggest your Sum template accept any iterator, but that it operates not on elements given from the iterator (i.e. *it) and instead on a 'view': element(*it). Now you can take care to make sure that element 'does the right thing' when faced with a pair.

As a hint, you could declare Sum as the following (with a bit of metaprogramming for getting the return type correctly):

namespace result_of {

// Second template parameter is an implementation detail
template<
    typename Iterator
    , typename ValueType = typename std::iterator_traits<Iterator>::value_type
>
struct Sum {
    // general case: sum over the value type directly
    typedef ValueType type;
};

// If an iterator admits an std::pair as its value_type then we end up here
template<typename Iterator, typename Key, typename Value>
struct Sum<Iterator, std::pair<Key, Value> > {
    // special case: sum over the second type of the value
    typedef Value type;
};

} // result_of

template<typename Iterator>
typename result_of::Sum<Iterator>::type Sum(Iterator begin, Iterator end);

Answer 2

You're overcomplicating this. You want a pair of iterators of any type? Well, that's just as simple as .. two arguments, of any type.

template<typename Iterator>
double Sum(const Iterator& begin,
           const Iterator& end) {
    return 43.0;    // another implementation stub
}

Problem solved.

By the way, take a hint from the C++ Standard lib: If you can't de-reference the iterator, make the user provide a function to get the value from the iterator. Don't special-case std::map because tomorrow there's std::unordered_map and the day after that boost::multimap and all sorts of fun. And what if I wanted you to sum the keys from the std::map, not the values?

Your hardcoded case is a little more complex. A pair of iterators that have to come from std::map? Not even sure if possible without explicit template arguments.

template<typename K, typename V, typename Comp, typename Alloc>
double Sum(
    const std::map<K, V, Comp, Alloc>& map
) { ... }

Notice that I specifically said it had to be a std::map instantiation. This allows the compiler to deduce the parameters. From here, you can access the iterators.

Answer 3

As DeadMG said, the simple way is to template on the type of the iterator. The common convention is, on the other hand, to pass iterators by value:

template <typename Iterator>
double Sum( Iterator begin, Iterator end );

As to why the original code was not working, the problem is that the type of the container is not deducible:

template <typename T>
double Sum( T::const_iterator begin, T::const_iterator end );
Sum( v.begin(), v.end() );        // [*] Assume v == const std::vector<double>&

When the compiler tries to infer the type of the arguments to Sum it only sees the type returned by v.begin() and v.end(), which are the iterator. From that type, it cannot guess the type of the container. To be able to determine what the type T is, it would have to test all non template types, and generate all infinite possible instantiations of template types to look whether they have a nested type const_iterator that matches the type of v.begin() and v.end(). Because that would be impossible, to achieve, the language forbids it in the first place.

Beyond that, and related to the comment ^[*], even if the type would be deducible, overload resolution is performed on the arguments to the function, and not how the expression is later use. In your program, the argument to .begin() is a std::vector<double> non-const lvalue. Because it is not const, the overload selected will yield a non-const iterator (even if in the function you want to call, there is no need to read it).