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

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.