Re: automatic type deduction for templates
On Sun, 6 May 2007, Abhishek Padmanabh wrote:
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.
The problem is not that an exact match is lacking. The problem is the
ambiguity: both arguments are T. You pass const_iterator for one, iterator
for the other. Which one should the compiler use for the deduction?
Let's take a simpler example:
template <typename T>
T min(T a, T b);
....
int i = 1636943928;
float f = 24153.322f;
double d = min(i, f);
What should T be deduced as? int and float are implicitly convertible to
each other - as such there is not necessarily a "better" way: both numbers
are (probably) not exactly representable in the other type.
int and float are both valid deductions for T, but there is only one T.
As such, the call is ambigous and a compile error.
Your example is exactly the same, except that there is a "better" type:
iterator is convertible to const_iterator, but not the other way round.
However, such deduction is not specified in the standard, probably because
a) it only applies in a limited number of cases and
b) it would make the deduction a lot more complex. For example, it would
require the compiler to look into the definition of the involved types to
do the deduction.
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?
The standard mandates that templates are used, yes. Why? Because any other
way is impossible: the algorithm must work for user-defined types just as
well as library-defined types. The library cannot provide overloads for
types it doesn't know about - only templates can do that.
I think I answered the other question above.
Sebastian Redl
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]