physicalattraction
physicalattraction

Reputation: 6858

How to let the compiler deduce the types of my template iterators?

I wrote a function that finds the most common element in any given container (see code below), where the input are two const_iterators for that container. If I call this function however with findMostFrequent(ivec.begin(), ivec.end()) where ivec is a vector<int>, the compiler cannot deduce the template arguments. Calling the function with findMostFrequent< vector<int> >(ivec.begin(), ivec.end()) works fine, but it seems cumbersome. Is there a way to let the compiler find out which template to instantiate?

template <typename T> typename T::value_type findMostFrequent(typename T::const_iterator beg, typename T::const_iterator end)
{
    // T is the type of container, T::value_type is the type which is stored in the container
    typename T::size_type current_streak = 0, max_streak = 0;
    T::value_type max_so_far;
    for (T::const_iterator iter = beg; iter != end; ++iter)
    {
        current_streak = count(beg, end, *iter);
        if ( current_streak > max_streak )
        {
            max_so_far = *iter;
            max_streak = current_streak;
        }
    }
    return max_so_far;
}

Upvotes: 3

Views: 870

Answers (3)

ltjax
ltjax

Reputation: 16007

The compiler can not deduce nested specifiers. "Find me a type that has a nested specifier that is equal to the type that I see as a parameter" is too complicated and often ambiguous to resolve it easily. Instead, try to deduce everything you need to know from the iterators directly:

template <typename IteratorType>
typename std::iterator_traits<IteratorType>::value_type
findMostFrequent(IteratorType beg, IteratorType end)
{
    typename std::iterator_traits<T>::difference_type current_streak = 0, max_streak = 0;
    typename std::iterator_traits<T>::value_type max_so_far;
    for (IteratorType  iter = beg; iter != end; ++iter)
    {
        current_streak = count(beg, end, *iter);
        if ( current_streak > max_streak )
        {
            max_so_far = *iter;
            max_streak = current_streak;
        }
    }
    return max_so_far;
}

The reason why you should use std::iterator_traits<T>::value_type instead of T::value_type is that it enables you to also have these "iterator specifications" for types that do not naturally define them, such as pointers. For example, T* is actually a valid iterator for this snippet, but it does not contain a value_type typedef/type.

Upvotes: 10

Ilya Lavrenov
Ilya Lavrenov

Reputation: 367

Because as a template parameter you must use an iterator type. The code below works well

#include <iostream>
#include <vector>

template <typename IterType> 
typename IterType::value_type findMostFrequent(IterType beg, IterType end)
{
    // T is the type of container, T::value_type is the type which is stored in the container
    unsigned int current_streak = 0, max_streak = 0;
    typename IterType::value_type max_so_far;
    for (IterType iter = beg; iter != end; ++iter)
    {
        current_streak = count(beg, end, *iter);
        if ( current_streak > max_streak )
        {
            max_so_far = *iter;
            max_streak = current_streak;
        }
    }
    return max_so_far;
}

int main()
{
    std::vector<int> v;
    for (unsigned int i = 0; i < 10; ++i)
        v.push_back(i);

    findMostFrequent(v.begin(), v.end());

    return 0;
}

In your code an iterator type don't have any relations to vector and as a result compiler couldn't deduce a template parameter

Upvotes: 2

orlp
orlp

Reputation: 118006

Yes, by making the function accept an Iter template argument and deducing T from that using iterator traits (<iterator>) - basically the other way around.

Upvotes: 3

Related Questions