Chapter 16. Templates and Generic Programming

Exercise 16.1

Define instantiation.

Class or function generated by the compiler from a template.

Exercise 16.2

Write and test your own versions of the compare functions.

Exercise 16.3

Call your compare function on two Sales_data objects to see how your compiler handles errors during instantiation.

error C2678: binary '<': no operator found which takes a left-hand operand of type 'const Sales_data' (or there is no acceptable conversion)

Exercise 16.4

Write a template that acts like the library find algorithm. The function will need two template type parameters, one to represent the function’s iterator parameters and the other for the type of the value. Use your function to find a given value in a vector<int> and in a list<string>.

Find

Exercise 16.5

Write a template version of the print function from 6.2.4 (p. 217) that takes a reference to an array and can handle arrays of any size and any element type.

Exercise 16.6

How do you think the library begin and end functions that take an array argument work? Define your own versions of these functions.

begin and end

Exercise 16.7

Write a constexpr template that returns the size of a given array.

SizeOfArray

Exercise 16.8

In the “Key Concept” box on page 108, we noted that as a matter of habit C++ programmers prefer using != to using <. Explain the rationale for this habit.

As we’ve seen, only a few library types, vector and string being among them, have the subscript operator. Similarly, all of the library containers have iterators that define the == and != operators. Most of those iterators do not have the < operator. By routinely using iterators and !=, we don’t have to worry about the precise type of container we’re processing.

Exercise 16.9

What is a function template? What is a class template?

function template: Definition from which specific functions can be instantiated.
class template: Definition from which specific classes can be instantiated.
differ: the compiler cannot deduce the template parameter type(s) like function templates for a class template. we should supply the list of template arguments to use in place of the template parameters inside angle brackets following the template's name.

Exercise 16.10

What happens when a class template is instantiated?

the compiler rewrites the class template, replacing each instance of the template parameter T by the given template argument.

Exercise 16.11

The following definition of List is incorrect. How would you fix it?

template <typename elemType> class ListItem;
template <typename elemType> class List {
public:
  List<elemType>();
  List<elemType>(const List<elemType> &);
  List<elemType>& operator=(const List<elemType> &);
  ~List();
  void insert(ListItem *ptr, elemType value);
private:
  ListItem *front, *end;
};

use of class template ListItem requires template arguments.

void insert(ListItem<elemType> *ptr, elemType value);
ListItem<elemType> *front, *end;

Exercise 16.12

Write your own version of the Blob and BlobPtr templates. including the various const members that were not shown in the text.

Blob, BlobPtr and ConstBlobPtr | Test

Exercise 16.13

Explain which kind of friendship you chose for the equality and relational operators for BlobPtr.

General friendship that each instantiation of BlobPtr grants access to the version of the equality and relational operators instantiated with the same type.

Exercise 16.14

Write a Screen class template that uses nontype parameters to define the height and width of the Screen.

Screen | Test

Exercise 16.15

Implement input and output operators for your Screen template. Which, if any, friends are necessary in class Screen to make the input and output operators work? Explain why each friend declaration, if any, was needed.

Screen | Test

same reason with Blob.

Exercise 16.16

Rewrite the StrVec class (§ 13.5, p. 526) as a template named Vec.

Vec | Test

Exercise 16.17

What, if any, are the differences between a type parameter that is declared as a typename and one that is declared as a class? When must typename be used?

When we want to inform the compiler that a name represents a type, we must use the keyword typename, not class.

Exercise 16.18

Explain each of the following function template declarations and identify whether any are illegal. Correct each error that you find.
(a) template <typename T, U, typename V> void f1(T, U, V);
(b) template <typename T> T f2(int &T);
(c) inline template <typename T> T foo(T, unsigned int*);
(d) template <typename T> f4(T, T);
(e) typedef char Ctype;
template <typename Ctype> Ctype f5(Ctype a);

Fixed:

(a) template <typename T, typename U, typename V> void f1(T, U, V); // identifier 'U'
(b) template <typename T> T f2(int &); // typename would be hidden
(c) template <typename T> inline T foo(T, unsigned int*); // inline must be after template
(d) template <typename T> void f4(T, T); // return type should be provided
(e) typedef char Ctype;
template <typename T> T f5(Ctype a); // the typename hides this typedef

Exercise 16.19

Write a function that takes a reference to a container and prints the elements in that container. Use the container’s size_type and size members to control the loop that prints the elements.

Exercise 16.20

Rewrite the function from the previous exercise to use iterators returned from begin and end to control the loop.

Exercise 16.21

Write your own version of DebugDelete.

DebugDelete|h | DebugDelete|cpp

Exercise 16.22

Revise your TextQuery programs from 12.3 (p. 484) so that the shared_ptr members use a DebugDelete as their deleter (12.1.4, p. 468).

Exercise 16.23

Predict when the call operator will be executed in your main query program. If your expectations and what happens differ, be sure you understand why.

when input the q to quit runQueries function. Exercise 16.22's output can check this.

Exercise 16.24

Add a constructor that takes two iterators to your Blob template.

Blob|h | Blob|test

Exercise 16.25

Explain the meaning of these declarations
extern template class vector<string>;
template class vector<Sales_data>;

vector<string> instantiation declaration here, it must be instantiated elsewhere in the program. vector<Sales_data> instantiates all members of the class template here.

Exercise 16.26

Assuming NoDefault is a class that does not have a default constructor, can we explicitly instantiate vector<NoDefault>? If not, why not?

see https://stackoverflow.com/questions/21525169/while-explicitly-instantiating-vectorsometype-what-is-the-sometype-default-co

Exercise 16.27

For each labeled statement explain what, if any, instantiations happen. If a template is instantiated, explain why; if not, explain why not.

template <typename T> class Stack { };

void f1(Stack<char>);                   // (a)
class Exercise {
   Stack<double> &rsd;                 // (b)
   Stack<int>    si;                   // (c)
};
int main() {
   Stack<char> *sc;                    // (d)
   f1(*sc);                            // (e)
   int iObj = sizeof(Stack< string >); // (f)
}

Solution:

(a) No instantiation, compiles, it got instantiated when called.
(b) No instantiation, compiles, references and pointers doesn't need instantiation
(c) Instantiation. Doesn't compile!
(d) No instantiation, compiles, references and pointers doesn't need instantiation
(e) Instantiation of Stack<char>. Doesn't compile!
(f) Instantiation of Stack<std::string>. Doesn't compileNo instantiation, compiles, references and pointers doesn't need instantiation!

Solution from How is a template instantiated? - Stack Overflow

Exercise 16.28

Write your own versions of shared_ptr and unique_ptr.

shared_ptr | unique_ptr | test

Exercise 16.29

Revise your Blob class to use your version of shared_ptr rather than the library version.

Blob with SharedPtr | test

Exercise 16.30

Rerun some of your programs to verify your shared_ptr and revised Blob classes. (Note: Implementing the weak_ptr type is beyond the scope of this Primer, so you will not be able to use the BlobPtr class with your revised Blob.)

check Exercise 16.28

Exercise 16.31

Explain how the compiler might inline the call to the deleter if we used DebugDelete with unique_ptr.

The compiler will set the default deleter type as DebugDelete, which will be executed is known at compile time.

Exercise 16.32

What happens during template argument deduction?

During template argument deduction, the compiler uses types of the arguments in the call to find the template arguments that generate a version of the function that best matches the given call.

Exercise 16.33

Name two type conversions allowed on function arguments involved in template argument deduction.

const conversions
Array- or function-to-pointer conversions

Exercise 16.34

Given only the following code, explain whether each of these calls is legal. If so, what is the type of T? If not, why not?
template <class T> int compare(const T&, const T&);
(a) compare("hi", "world");
(b) compare("bye", "dad");

(a): illegal, as two types are different, the first type being const char[3] ,second const char[6]
(b): legal, the type is const char(&)[4].

Exercise 16.35

Which, if any, of the following calls are errors? If the call is legal, what is the type of T? If the call is not legal, what is the problem?
template <typename T> T calc(T, int);
template <typename T> T fcn(T, T);
double d; float f; char c;
(a) calc(c, 'c');
(b) calc(d, f);
(c) fcn(c, 'c');
(d) fcn(d, f);

(a) legal, type is char.
(b) legal, type is double.
(c) legal, type is char.
(d) illegal, d is double, but f is float, they are totally different type.

Exercise 16.36

What happens in the following calls:

template <typename T> f1(T, T);
template <typename T1, typename T2) f2(T1, T2);
int i = 0, j = 42, *p1 = &i, *p2 = &j;
const int *cp1 = &i, *cp2 = &j;
(a) f1(p1, p2);
(b) f2(p1, p2);
(c) f1(cp1, cp2);
(d) f2(cp1, cp2);
(e) f1(p1, cp1);
(f) f2(p1, cp1);

At first, there are some error in function declarations.

f1, f2 should have return type, maybe void?
In f2, typename T2) should be typename T2>.

Then, the answers:

(a) T is int*
(b) T1 and T2 are both int*
(c) T is const int*
(d) T1 and T2 are both const int*
(e) error, p1 is int*, cp1 is const int*, they are different type
(f) T1 is int*, T2 is const int*

Exercise 16.37

The library max function has two function parameters and returns the larger of its arguments. This function has one template type parameter. Could you call max passing it an int and a double? If so, how? If not, why not?

Yes. Specify the parameter explicitly:

int a = 6; double b = 6.1231;
std::cout << std::max<long double>(a, b) << std::endl;
Normal conversions also apply for arguments whose template type parameter is explicitly specified.

Exercise 16.38

When we call make_shared (12.1.1, p. 451), we have to provide an explicit template argument. Explain why that argument is needed and how it is used.

Because when we call make_shared, it is allowed for no argument. Then, we have nothing to deduce the type of the return type.

Exercise 16.39

Use an explicit template argument to make it sensible to pass two string literals to the original version of compare from 16.1.1 (p.652).

std::cout << compare<std::string>("czwp", "czyz") << std::endl;
                    ^^^^^^^^^^^^^

Exercise 16.40

Is the following function legal? If not, why not? If it is legal, what, if any, are the restrictions on the argument type(s) that can be passed, and what is the return type?

template <typename It>
auto fcn3(It beg, It end) -> decltype(*beg + 0) {
    // process the range
    return *beg; // return a copy of an element from the range
}

legal. But only type that support this + 0 operation can be passed, and the return type depends on the what type the operator + return.

Exercise 16.41

Write a version of sum with a return type that is guaranteed to be large enough to hold the result of the addition.

template <typename T1, typename T2>
auto sum(T1 a, T2 b) -> decltype(a + b) {
    return a + b;
}

Exercise 16.42

Determine the type of T and of val in each of the following calls:
template <typename T> void g(T&& val);
int i = 0; const int ci = i;
(a) g(i);
(b) g(ci);
(c) g(i * ci);

(a) T: int& val: int& && -> int &
(b) T: const int& val: const int& && -> const int &
(c) T: int val: int &&

When we pass an lvalue int to a function parameter that is an rvalue reference to a template type parameter T&&, the compiler deduces the template type parameter as the argument’s lvalue reference type int &.

X& &, X& &&, and X&& & all collapse to type X&.

Exercise 16.43

Using the function defined in the previous exercise, what would the template parameter of g be if we called g(i = ci)?

int&

Exercise 16.44

Using the same three calls as in the first exercise, determine the types for T if g’s function parameter is declared as T (not T&&). What if g’s function parameter is const T&?

Whatever g's function parameter is declared as T or const T&, the T's type in this three case would always int.

Exercise 16.45

Given the following template, explain what happens if we call g on a literal value such as 42. What if we call g on a variable of type int?
template <typename T> void g(T&& val) { vector<T> v; }

If we call g on a literal value such as 42, T should be int, and we get a tempoary variable v, which type is vector<int>. If we call g on a variable of type int, then val should be a lvalue, T should be int&(because int& && ==> int&), then we would declared a v as vector<int&>. But the component type of vector must be assignable, the references are not assignable, thus, vector<int&> is not allowed, the compiler would complain about it.

Exercise 16.46

Explain this loop from StrVec::reallocate in 13.5 (p.530):
for (size_t i = 0; i != size(); ++i)
  alloc.construct(dest++, std::move(*elem++));

Since C++11, std::allocator::construct's second parameter is Args&&... args. *elem++ is a certain lvalue, and would be casted to a rvalue reference by std::move, then the construct would call the move constructor of std::string rather than copy constructor.

Exercise 16.47

Write your own version of the flip function and test it by calling functions that have lvalue and rvalue reference parameters.

flip and test

Exercise 16.49

Explain what happens in each of the following calls:

template <typename T> void f(T);                   //1
template <typename T> void f(const T*);            //2
template <typename T> void g(T);                   //3
template <typename T> void g(T*);                  //4
int i = 42, *p = &i;
const int ci = 0, *p2 = &ci;
g(42); g(p); g(ci); g(p2);
f(42); f(p); f(ci); f(p2);

Answer:

g(42);  // type: int(rvalue) call template 3  T: int          instantiation: void g(int)
g(p);   // type: int *       call template 4  T: int          instantiation: void g(int *)
g(ci);  // type: const int   call template 3  T: const int    instantiation: void g(const int)
g(p2);  // type: const int * call template 4  T: const int    instantiation: void g(const int *)
f(42);  // type: int(rvalue) call template 1  T: int          instantiation: void f(int)
f(p);   // type: int *       call template 1  T: int *        instantiation: void f(int *)
// f(int *) is an exact match for p(int *) while f(const int *) has a conversion from int * to const int *.
f(ci);  // type: const int   call template 1  T: const int    instantiation: void f(const int)
f(p2);  // type: const int * call template 2  T：int          instantiation: void f(const int *)

Exercise 16.50

Define the functions from the previous exercise so that they print an identifying message. Run the code from that exercise. If the calls behave differently from what you expected, make sure you understand why.

overload template

Exercise 16.51

Determine what sizeof...(Args) and sizeof...(rest) return for each call to foo in this section.

template <typename T, typename ... Args>
void foo(const T & t, const Args & ... rest);
int i = 0; double d = 3.14; string s = "how";
foo(i, s, 42, d);  // input in Args: string, int(rvalue), double  sizeof...(Args): 3  sizeof...(rest): 3
foo(s, 42, "hi");  // input in Args: int(rvalue), const char[3]   sizeof...(Args): 2  sizeof...(rest): 2
foo(d, s);         // input in Args: string                       sizeof...(Args): 1  sizeof...(rest): 1
foo("hi");         // input in Args: None                         sizeof...(Args): 0  sizeof...(rest): 0
foo(i, s, s, d);   // input in Args: string, string, double       sizeof...(Args): 3  sizeof...(rest): 3

Exercise 16.52

Write a program to check your answer to the previous question.

variadic template