C++ Templates: 'Name Lookup', 'ADL' and 'Argument Deduction' (Sentinel)

Finally, we are at the final part of this series. Hope you enjoyed the reading till now. 
If you have not had the chance to go over the previous two articles, I will link you to those:

Part 1
Part 2


Template Argument Deduction

Just like other topics, I can only dream about knowing all the nooks and crooks of argument deduction in the template world. But, what I can put forth here is what every experienced C++ programmer must know about it.  

Most of the things I will be writing about is directly influenced by what is already explained in "C++ Templates: The Complete Guide" book. It is highly recommended for everyone who makes use of templates in their C++ code to read through it and always keep it at your hands distance.

Why Argument Deduction ?

A simple template code which one might have written to understand template would have looked like this:

#include <iostream>
#include <string>
#include <typeinfo>

template <typename T>
void func(T arg) {
   std::cout << "func called with arg " << typeid(T).name() << std::endl;
}

int main() {
    func<int>(5);
    func<char>('a');
    return 0;
}

Now, assume you have below function, which you need to call many times and at many places in your code:

template<typename T1, typename T2, typename T3>
void someCommonFunction(T1& a, T2 b, T3 c) {
....
}

...
someCommonFunction<std::string, char, int>(str, 'b', 5);

This is what you would be writing every where! Too much verbosity!!
This is where argument deduction comes in. It deduces the types auto-magically thereby relieving us from the burden of mentioning the intended template types everywhere.

Also, a very important point to remember is that, template type deduction works only for function templates and member function templates, it is not applicable at the class level.


Let's cover some basics...

Look at the below example:

template <typename T>
T max (const T& a, const T& b) {
    return a < b ? b : a;
}

int max_val = max(10, 11);

Lets now see how compiler might be thinking while deducing the types:
1. It encounters the first parameter as 10 and considers its data type as 'int'. So, the parameterized type 'T' of function template max is considered 'int'  as one of the option.

2. Now, it checks the data type of the second argument, which is also 'int'. This matches with the previous conclusion done in step #1 and also fits perfectly as the argument type of the function template based upon the paremeter type i.e both the arguments should be of same type.
Hence, in this case, type deduction succeeded.

3. Let's now consider the max call like below:

int max_val = max(10, 10.1);

4. For the above case, step #1 will tentatively deduce 'T' as 'int'. But, for the second argument, 'T' will be deduced as 'double'. This second deduction does not conform with the first deduction and also w.r.t the parameter type of the function template i.e. both argument needs to be of the same type.
Hence, for this case, argument deduction rightfully fails and the compiler looks for other overloaded function with the same name 'max' to match it with the actual call.


Type Deduction Scenarios

There are various scenarios depending upon the argument type of the function template on which deduction of type T is dependent. These are:
1. Argument type is either a pointer or reference.
2. Argument type is pass by value.
3. [C++11 specific] Argument type is a forwarding reference. (We will not be covering this now.)

NOTE: Examples in this section are influenced by what is provided in 'Effective Modern C++' by Scott Meyers.

Case 1. When argument type is either reference or pointer.
Remember that, if the argument type of the callee is a reference or a pointer, then, the pointer or the reference is ignored. 
For example:

template <typename T>
void func(T& param) {   // See that argument is a reference type
}

int x = 27;
const int cx = x;
const int& rx = x;

f(x);  // 'x' is int; 'T' is int; Argument type is 'int&'

f(cx); // 'cx' is 'const int'; 'T' is 'const int'; Arg type is 'const int&'

f(rx); // 'rx' is 'const int&'; 'T' is 'const int'; Arg type is 'const int&'

Following the comments, it should be pretty straightforward to grasp what is happening here.
The important point to remember here is that:

When we pass a const object to a reference parameter, the object remains as a const i.e. const-ness (also volatile) of the object becomes part of the type deduced for T.

Let's see the same example again with a small change to the argument type:

template <typename T>
void func(const T& param) {
}

int x = 27;
const int cx = x;
const int& rx = x;

f(x);  // x is int; T is int; Arg type is const int&

f(cx); // cx is const int; T is int; Arg type is const int&

f(rx); // rx is const int&; T is int; Arg type is const int&

If param was a pointer ( or a pointer to const ) instead of a reference, things would have been the same. The note above regarding the const-ness (also volatile) of the object also holds in case of the pointer.


Case 2. When argument is passed by value
When the parameter is passed by value, a completely new object is created at the target destination. This has some major changes in the rules regarding c-v (const - volatile) qualifier which we saw for reference/pointer types.

As before, if the callers expression type is a reference, ignore the reference part. If the callers expression type has c-v qualifiers, then they are stripped off.

Example:

template <typename T>
void func(T param) {
}

int x = 27;
const int cx = x;
const int& rx = x;

f(x); // x is int; T is int; Arg type is int

f(cx);// cx is const int; T and Arg type are int

f(rx);// rx is const int& ; T and Arg type are int

As can be seen from the above example that the c-v qualifiers are stripped off when passed by value.


Decaying

Case 1. Decaying of Array into a pointer
In many contexts, an array decays into a pointer to its first element. This is what we know right from C. But, this decaying also takes place in case of function templates accepting parameter by-value!

Example:

const char name[] = "Arun"; // Type of name is const char[5]

const char* pname = name; // array decays to a pointer

template <typename T>
void func(T param) {
}

f(name); // T is const char*, name is const char[5]

Now, the confusing part, if we modify the function template to accept argument by-reference instead of by-value, the deduced type for T is the actual type of the array i.e const char[5], and the type of func's parameter is const char (&) [5].



Use of type deduction

Have a look at boost source or STL implementation, they are every where. It is one of the very basic requirements to understand how template works after all.
It is used in type traits, boost function etc.

What I will be showing here is a pretty useless example, but will cover how in general type traits are written and also shows a peek into boost function traits . 

Beware, following code is only for those who can bend their mind :) 

#include <iostream>

// Type trait helper function
// Determines at compiler time whether type is signed integer or not
template <typename T> struct is_integer { enum {value = false}; };
template <> struct is_integer<int> { enum {value = true}; };

// Base structure of function trait
template <typename Func> struct function_traits {};

// Partially specialized function_trait
// to accept a function signature
template <typename R>
struct function_traits<R (void)> {
    typedef R result_type;
};

// Partially specialized function_trait 
// to accept a function pointer
template<typename R>
struct function_traits<R (*) (void)> {
    typedef R result_type;
};


int test_func() {
    std::cout << "This is a test function" << std::endl;
    return 42;
}

template <typename Fun>
typename function_traits<Fun>::result_type 
my_function(Fun& f) {
    return f();
}

int main() {
    if (is_integer<function_traits<float(void)>::result_type>::value == true) {
        std::cout << "Return type of function is integer" << std::endl;
    } else {
        std::cout << "Return type is not integer!!" << std::endl;
    }

    int (*fptr)() = test_func;

    if (is_integer<function_traits<int (*)(void)>::result_type>::value == true) {
        std::cout << "Return type of function is integer" << std::endl;
    } else {
        std::cout << "Return type of the function is not integer!!" << std::endl;
    }

    std::cout << my_function(test_func) << std::endl;

    return 0;
}

For those who reached at this point of the page in 5 seconds, have patience, it's not that difficult! Just go one line at a time and you will get it for sure.

Basically, we are just identifying the return type of the function based upon the signature, boost function traits does  a lot more than that.

Disabling Type Deduction

Yes, you can do that as well. With C++, getting things done is never an issue, the only ugly part that can be is the code itself. :)
Recently, I got bogged down by the question, why 'std::forward' cannot use type deduction ?
As always, I found the answer in THIS SO post. That's when the use of 'identity type trait' stuck me. So simple, yet so powerful. 
Lets dig in to an example right away...

#include <iostream>
#include <string>

template <typename T>
void func_deduct(T& val) {
    std::cout << "With deduction: " << val << std::endl;
}

// Identity type trait
template <typename T>
struct identity {
    typedef T type;
};

template <typename T>
void func_nodeduct(typename identity<T>::type& val) {
    std::cout << "No deduction: " << val << std::endl;
}

int main() {
    std::string str("Will it work?");
    //func_nodeduct(str);                // Uncomment this and face the wrath of compiler
    func_nodeduct<std::string>(str);

    return 0;
}

As to why deduction does not work, in short, it is because template type T in function 'func_nodeduct' appears in 'nondeduced' context.

From the Standard 14.8.2.4/4:

The nondeduced contexts are:

• The nested-name-specifier of a type that was specified using a qualified-id.

• A type that is a template-id in which one or more of the template-arguments is an expression that references a template-parameter.

When a type name is specified in a way that includes a nondeduced context, all of the types that comprise that type name are also nondeduced. However, a compound type can include both deduced and nondeduced types. [Example: If a type is specified as A<T>::B<T2>, both T and T2 are nondeduced. Likewise, if a type is specified as A<I+J>::X<T>, I, J, and T are nondeduced. If a type is specified as void f(typename A<T>::B, A<T>), the T in A<T>::B is nondeduced but the T in A<T> is deduced. ]

There are lots more to be discussed about argument deduction, but I will call it a day. One can lookup here to understand it in more detail.