Answers for chapter 16

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.

header source

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

In file included from unit_test.cc:8:
ex_16_2.h: In instantiation of ‘int compare(const T&, const T&) [with T = Sales_data]’:
unit_test.cc:17:29:   required from here
ex_16_2.h:25:8: error: no match for ‘operator<’ (operand types are ‘const Sales_data’ and ‘const Sales_data’)
   25 |  if(v1 < v2) return 1;
      |     ~~~^~~~
ex_16_2.h:26:8: error: no match for ‘operator<’ (operand types are ‘const Sales_data’ and ‘const Sales_data’)
   26 |  if(v2 < v1) return -1;
      |     ~~~^~~~

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>.

header test

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.

header test

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.

header test

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

test

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.

When implementing functions with templates, we should attempt to minimize the number of requirements placed on the argument types. From this perspective, we should see how we can benefit from using the “!=” operator instead of “<“.

For instance, when dealing with most of the containers, we rely on iterators to operate them over a subscription. The reason for this is that only a few containers support subscript operations, while most support iterator dereferencing. Since iterators are definitely helpful to operate the containers at this point, we need to use equality operators instead of relational operators between them since most of the iterators do not define the relational operators. In this way, we can avoid to worry about the precise type of container we are processing, to a large extent.

Exercise 16.9: What is a function template? What is a class template?

• function template：A function template is a formula from which we can generate type-specific versions of that function.
• class template：A class template is a blueprint for generating classes.

Important distinct：class templates differ from function templates in that the compiler cannot deduce the template parameter type(s) for a class template.

Exercise 16.10: What happens when a class template is instantiated?

When the compiler instantiates a class from our class template, it rewrites the class template, replacing each instance of the template parameter 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;
};

void insert(ListItem *ptr, elemType value);

private:
    ListItem *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.h BlobPtr.h test

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

I chose the one-to-one friend relationship in my case, since both operators deal with the instantiated BlobPtr object.

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

header 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.

header test

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

header 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?

Generally, there is no difference between using the typename and class keywords. However, 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.

//illegal, template parameter must be preceded by the keyword typename
a) template <typename T, U, typename V> void f1(T, U, V);

//illegal, The template parameter "T" cannot be used as a variable name.
b) template <typename T> T f2(int &T);

//illegal, the inline keyword must follow the template parameter list.
c) inline template <typename T> T foo(T, unsigned int*);

//illegal, the "f4" function does not have a return value or be a void function.
d) template <typename T> f4(T, T);

//legal, but the char alias "Ctype" was hidden by template parameter "Ctype"
e) typedef char Ctype;
    template <typename Ctype> Ctype f5(Ctype a);

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.

source

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

source

Exercise 16.21: Write your own version of DebugDelete.

source

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).

header source

ex_12_22.h and data.txt are in the same directory.

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.

In the TextQuery Progream, we applied our custom deleter to three shared pointers.

• The first shared-pointer manages the lineData member, which stores the texts that correspond to every word. This shared pointer will keep the text data available until the program ends. Our deleter will run once on this shared-pointer.

• The second shared-pointer manages the lineNumSet member, which stores the line location of each word in the whole segment. Since every word needs its own lineNumSet, our deleter will run as many times as the non-repeating word counts.

• The third shared-pointer handles the noData member, which is an empty set representing a query that fails to find a match (no matched lines). Since this member is a static member, it will be allocated at the beginning of the query operation and will remain until the program ends. The deleter can only be invoked once when there is a query operation, and it will not run if the program is exited right after the data map has just been created.

Blob.h BlobPtr.h test.cc

Exercise 16.25: Explain the meaning of these declarations:

1. extern template class vector<string>;
2. template class vector<Sales_data>;

• vector<string> is a declaration of a class template that is supposed to be instantiated explicitly.
• It cannot be define in the current header.
• It should be define where it needs to be instantiated.
• The compiler will not instantiate vector<string> (generally, vector<string> will be instantiated when vector<T> is used in more than two files) until it sees that the vector<string> is defined in the other files.

For statement 2：

• vector<Sales_data> is an ordinary class template instantiation definition.
• Both its declaration and definition need to be put into the header file.
• If there is no using for the class template, it won't be instantiated.
• Any use of it in more than two other files will result in its instantiation for every single file.

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?

No.

• The explicit instantiation will instantiate all its members.
• The default constructor of the element will be used for initializing the vector.

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) no instantiation
class Exercise {
    Stack<double> &rsd;                 // (b) no instantiation
    Stack<int>    si;                   // (c) instantiation
};
int main() {
    Stack<char> *sc;                    // (d) no instantiation
    f1(*sc);                            // (e) instantiation
    int iObj = sizeof(Stack< string >); // (f) instantiation
}

• a doesn't create an object
  • b,d are indirect type which not require instantiation (no actual day are allocated).
  • c is an member definition
  • e is using d, thus allocating happens here.
  • f creates an new object

Refs：

• What happens in memory when a C++ class is instantiated
• How is a template instantiated?

Exercise 16.28: Write your own versions of shared_ptr and unique_ptr.

Header:
shared_ptr unique_ptr
Test:
shared_ptr test unique_ptr test
Deleter:
Deleter

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

Header

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.)

Test

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

The custom deleter DebugDelete will be passed to the constructor of unique_ptr, and it will be stored on the member with which it corresponds during compiling-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.

* Conversion to const for a reference parameter

• Array- or function to pointer conversions

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"); // illegal
(b) compare("bye", "dad"); // legal

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'); // legal. T is char.
b) calc(d, f);   // legal. T is double
c) fcn(c, 'c');  // legal. 'c' is const char but passed to the parameter in the copy way. Thus T is char type. 
d) fcn(d, f);    // illegal. the arguments to T must have essentially the same type. d, f are different types and there is no conversion between them.

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);  //T is int*
b) f2(p1, p2);  //T1, T2 both are int*
c) f1(cp1, cp2);  //T is pointer to const int
d) f2(cp1, cp2);  //T1, T2 both are pointer to const int

//won't compile, need version f1(int*&, const int*&) . 
//deduced conflicting types for parameter ‘T’
e) f1(cp1, p1); 

f) f2(p1, cp1); //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 we can. We can specify the type we want to compare explicitly (int or double, or any other convertible type). Because explicit arguments follow the normal conversion rule, the parameter that doesn't match the specified type will be converted to it via the arithmetic conversion.

int i = 1;
double d = 1.0;
auto ret = std::max<int>(i, d); //max(int, int)

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.

The explicit argument that is passed to the make_shared function specifies the type of user-specific instants, that is, the type of the object that is allocated and the type of the smart pointer that is returned.

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::string is an good option
//const char* works, but need to define the less operation
compare<std::string>("11111", "1111");

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, however:

• The element to which beg refers must support + 0 operation
• The operation (*beg + 0) yields an rvalue, decltype will return its type. Thus the return type is the type of the result of the operation.

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 x, T2 y) ->decltype(x + y)
{
    return x + y;
}

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); // int&, lvalue -> T& -> T& && -> T&
b) g(ci); // const int&, const lvalue -> const T& -> const T& && -> const T&
c) g(i * ci); // int&&,  no collapsing here

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)?

i; // lvalue int
cil; //const lvalue int
i = ci; // lvalue int. top const is ignored
g(i=ci); // lvaue int to T&& -> T& -> 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&?

/* T */
a) g(i); // int
b) g(ci); // int, top const is ignored
c) g(i * ci); // int, top const is ignored

/* const T& */
a) g(i); // int
b) g(ci); // int, const is already a part of function parameter type.
c) g(i * ci); // int, int&& to const 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; }

int i = 0;
g(42); // v is vector<int>, rvalue to T&& -> int -> vector<int>
g(i); // v is vector<int&>, lvalue to T&& -> int& -> vector<int&>

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++));

• Overall, the loop constructed n of the objects that managed by elem in specified dynamic memory
• Code break down（assume template parameter type is T）
  1. *elem generally returns an reference to the object, which is T&, then moves to the next element position
  2. std::move takes the argument returned by *elem, deduct the template type as T&
  3. The move template instantiated as <T&>, as well as remove_reference template
  4. remove_reference<&T>::type is T
  5. after static_cast<typename remove_reference<T>::type&&>, the final return type will be T&&
  6. allocator::construct takes an position pointer dest and a rvaule reference to construct the current object
  7. move dest to the next construct position, get ready for the next construction

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

Source

Exercise 16.48: Write your own versions of the debug_rep functions.

Source

Exercise 16.49: Explain what happens in each of the following calls:

template <typename T> void f(T);
template <typename T> void f(const T*);
template <typename T> void g(T);
template <typename T> void g(T*);
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);

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.

Source

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

foo(i, s, 42, d);    // 3 in Args, const (string&, int&, double& | 3 in rest: (s, 42, d)
foo(s, 42, "hi");    // 2 in Args, const (int&, char(&)[3] | 2 in rest: (42, "hi")
foo(d, s);           // 1 in Args, const (string&) | 1 in rest: s
foo("hi");           // empty & empty

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

Source

Exercise 16.53: Write your own version of the print functions and test them by printing one, two, and five arguments, each of which should have different types.

Source

Exercise 16.54: What happens if we call print on a type that doesn’t have an « operator?

The program won't compile. Compiler couldn't find a matching operator « for template instantiating.

ex_16_53.cc:19:12: error: no match for ‘operator<<’ (operand types are ‘std::ostream’ {aka ‘std::basic_ostream<char>’} and ‘const std::basic_istream<char>’)
   19 |  return os << t << "\n"
      |         ~~~^~~~

Exercise 16.55: Explain how the variadic version of print would execute if we declared the nonvariadic version of print after the definition of the variadic version.

the program won't compile:

ex_16_53.cc:20:14: error: no matching function for call to ‘print(std::ostream&)’

An example from C++ template book might helpful to explain:

template<typename T, typename… Types>
void print (T firstArg, Types… args)
{
  std::cout << firstArg << ’\n’;
  if (sizeof…(args) > 0) {      //error if sizeof…(args)==0
    print(args…);               // and no print() for no arguments declared
  }
}

Exercise 16.56: Write and test a variadic version of errorMsg.

Header Source

Exercise 16.57: Compare your variadic version of errorMsg to the error_msg function in § 6.2.6 (p. 220). What are the advantages and disadvantages of each approach?

The variadic version can handle multiple types at a time.

Exercise 16.58: Write the emplace_back function for your StrVec class and for the Vec class that you wrote for the exercises in § 16.1.2 (p. 668).

Header Source test

Exercise 16.59: Assuming s is a string, explain svec.emplace_back(s).

1. s will be packed with rvalue pattern && in template parameter list and parameter list of emplace_back().
2. s will be passed to alloc.construct as a pack. The pack will be dealed with std::forward to ensure alloc.construct can get an string&& type to create a new element.

Exercise 16.60: Explain how make_shared (§ 12.1.1, p. 451) works.

• make_shared() accepts a pack of arguments matching the type of shared_ptr.
• The pack will be passed to the allocator object for construction; each element will be constructed independently.
• Once the construction is complete, make_shared() returns a shared_ptr that points to the allocated memory.

Exercise 16.61: Define your own version of make_shared.

Source

Exercise 16.62: Define your own version of hash<Sales_data> and define an unordered_multiset of Sales_data objects. Put several transactions into the container and print its contents.

Header soruce Test

Exercise 16.63: Define a function template to count the number of occurrences of a given value in a vector. Test your program by passing it a vector of doubles, a vector of ints, and a vector of strings.

Source

See 16.63.

Exercise 16.65: In § 16.3 (p. 698) we defined overloaded two versions of debug_rep one had a const char* and the other a char* parameter. Rewrite these functions as specializations.

Source

Exercise 16.66: What are the advantages and disadvantages of overloading these debug_rep functions as compared to defining specializations?

Specializations are limited by the form of the “mother template”. It is relatively more special, but it is also constrained by the template it derives from. Overloading, on the other hand, is the most dedicated way to deal with a particular problem. Overloading functions can handle any kind of problem, but do not offer any flexibility, while template specializations can still hold some.

Hence, it depends on how generality can be abstracted from the problem we are trying to solve. In cases where there aren't too many things in common, overloading may be a good strategy. Otherwise, spending some time on the template is definitely worth it.

Exercise 16.67: Would defining these specializations affect function matching for debug_rep? If so, how? If not, why not?

Specializations instantiate a template; they do not overload it. As a result, specializations do not affect function matching.