Lecture 14.md

Lecture 14

Template

1. Please state the original intention (意图) of bringing in template mechanism.

• Template allows same operations on different types of data.Avoid code repetition due to different data type.

2. Please write down the general form of function template definition.

template<class T1, class T2, ...>
ReturnType FunctionName(ParameterList) {
	// FunctionBody
}

Where ParameterList must include all the template arguments.

3. Please state all the data types that can be template arguments.

• All the data types that can be instantiated can be template arguments, including all the build-in types, pointers, non-abstract classes, structs, etc.

4. What is template specialization (模板特化)? Please write down the general form of it.

• When we want to use template but we'd like to introduce a specific version of one specific type, the template specialization is needed. The general form state as follow:

    template <class T> class pair;
    template <> class pair <int>;
    // template <> class class_name <type>
  

5. Please implement (实现) the following code such that we can get Fibonacci sequence value of 100 within O(1) runtime.

int main ()
{
    Fib<100> f;
    cout << f.value << endl;
    return 0;
}

template<int n>
class Fib
{
public:
  float value;

Fib() {
    value = 1.0 / sqrt(5) * (pow((1 + sqrt(5)) / 2, n));
  }
};

6. What is implicit call instantiation of template? When does it work?

• The implicit call instantiation of template is that sometimes we don’t specify the type of template arguments and the compiler will determine the type by the arguments.
• It work when the type cannot determined by programmers, then we use implicit call instantiation to let compiler finish the job.Implicit call (instantiation) of template works when a template function is directly called with arguments in certain types.

7. Can a template parameter appear twice or more in the argument list? Can a template argument never appear in the template function/class body?

• Repeated declaration is prohibited.
• Argument can never appear.

8. Please write down the general form of class template.

template <class T1, class T2, …>
class ClassName {
//Class body
};

9. Why are the definitions of template functions and template classes supposed to be placed in header files?

• A template is not a class or a function. A template is a “pattern” that the compiler uses to generate a family of classes or functions.
• In order for the compiler to generate the code, it must see both the template definition (not just declaration) and the specific types/whatever used to “fill in” the template.
• Your compiler probably doesn’t remember the details of one .cpp file while it is compiling another .cpp file.

10. What should you do to use default value for template parameters? What should you do to use constant values in template? What should you do to inherit from a template class? Please illustrate them with certain examples.

• Default value for template parameters:

    template<class T = int>
  

• Consntant value in template:

    template<class T, int max>
  

• Inherit from a template class:

    template<class T>
    class InheritedClass : public BaseClass<T> {
    	// Declaration body.
    };
  

11. Please plot the UML class diagram for the iterator design pattern.

12. Plese implement a general “count_if” algorithm using template along with the iterator design pattern.

template <typename InputIterator, class Pred>
int Count_If(InputIterator begin, InputIterator end, Pred pred) {
    int count = 0;
    for (; begin != end; ++begin) 
        if (pred(*begin))
            count++;

    return count;
}

13. Please give an example to illustrate how the function object (函数对象) is used in STL.

Priority_queue<int, vector<int>, greater<int> > Q;

其中greater就是stl中自定义的函数对象，内置了括号运算符来比较两个int的大小。上述代码建立了一个小根堆（默认是less的大根堆）