automatic type deduction for templates

I have the following code:

#include<vector>
template<typename InputIterator>
inline typename std::iterator_traits<InputIterator>::difference_type
   distance(InputIterator first, InputIterator last)
{
    return last-first;
}

int main()
{
    std::vector<int> vec;
     distance(
    static_cast<std::vector<int>::const_iterator>(vec.begin()),
     vec.end());
}

I understand that for the instantiation to happen there should be an
exact match. Such mixing of iterators will cause compilation failure.
But this is just because of the fact that the algorithm is implemented
using templates. For pure functions, this wouldn't have had been a
problem. And the iterator would have had been a valid argument where a
const_iterator was being asked for.

My first question is - does the standard mandate that these algorithms
must be implemented as templates? [Well, I understand it can be quite
chaotic to implement so many non-template versions to handle all types
but just for the sake of clarity]. Can an implementation provide a non-
template solution? Why does the standard mandate usage of templates?

Second part of the question is, can the automatic type deduction not
happen at all in this case? What is so illegal about mixing the
iterators that it is flagged as an error? I understand that there
cannot be a template instantiation made with varying iterator types
for function template that takes just one type as a type parameter. A
work-around could be asking for an explicit instantiation, like this:

     distance<std::vector<int>::const_iterator>(
        static_cast<std::vector<int>::const_iterator>(vec.begin()),
        vec.end());

Can an instantiation not happen by automatic type deduction for the
"most restrictive argument type"? Would it be inappropriate to expect
an instantiation for const_itrerator so, that the construct becomes
valid even when the second argument is an iterator - with automatic
conversion to const_iterator supported?

Will this muddy the template argument deduction a lot?

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]