You Can Program In C++ (2006) [eng]

C H A P T E R 7

Generic Functions

C++ provides some very useful mechanisms for writing code that is independent of the data types used. We have already been using them when, for example, we created vectors to contain a specified type. std::vector<int>, std::vector<long>, std::vector<std::string>, and even std::vector<std::vector<int>> are all examples of using the general C++ concept of a vector container as a sequence of objects of a specified type.

The fundamental mechanism is the C++ template. In this chapter, I am going to focus on C++ function templates. We most commonly simply use functions generated from function templates provided by libraries (either the Standard C++ Library or third-party ones). However, this chapter will also cover writing simple function templates. The primary intention is to help you understand the template concept.

Some readers may wish to delay learning the details of writing function templates. If you are one of them, please at least skim this chapter so that you will know what they are and how to use them. You can come back later to study writing them in more detail.

Language Note: Much of this chapter may seem surprising if your previous programming experience has been with a dynamically typed language such as Python. C++ is a statically typed language. That means that the types of objects and expressions must be determined at compile time. We will see later that C++ also supports a limited amount of dynamic typing, but only for names; objects must have a static type, i.e. a type that the compiler can identify.

Which Is Larger

Choosing the larger of two values is a common problem – so common that you probably want to make it a function. The following short function returns the larger of two int values supplied to it as arguments:

int max(int first, int second){

return first > second ? first : second;

}

That function is so simple – it is just a wrapper for using the conditional operator – that you may wonder why we should make it into a function. One reason is that good programming not only avoids ‘magic numbers’ but also avoids ‘magic expressions’; we try to name things to help the human reader follow what our code is doing. In general, self-expressive code is worth the risk of a possible slight degradation in performance, because it saves a great deal of maintenance time. C++ also provides tools to tackle the issue of efficiency when it matters.

120

CHAPTER 7

T R Y T H I S

Here is a small program that uses the above function to select the largest of a set of integer values input via the console (i.e. keyboard):

1 #include <iostream>

2 #include <vector>

3

4 int max(int first, int second){

5 return first > second ? first : second;

6 }

7

8 int main( ){

9try{

10std::vector<int> data;

11std::cout << "Type in some integers. End input with -9999.\n\n";

12int value(0);

13do{

14std::cin >> value;

15data.push_back(value);

16} while(value != -9999);

17int maximum(-9999);

18for(size_t i(0); i != data.size( ); ++i){

19maximum = max(maximum, data[i]);

20}

21std::cout << "The largest input value was " << maximum << ".\n";

22}

23catch(...){ std::cerr << "\n***An exception was thrown***\n";}

24}

Create a project, type in the program, and try it.

W A L K T H R O U G H

Most of the above code should be familiar to you by now. Lines 10 to 16 create a container called data, which is a sequence of int values, stored in a std::vector<int> object. Data provided by the keyboard is stored in it. Note that we have to define value outside the data-capture loop because it is used in the while-clause that checks to see if input has finished. (Try moving the definition of value inside the do–while loop to see that the compiler then rejects the code.) Storing the terminating value gives us a small benefit in that it ensures that there will always be at least one value stored in data.

The design also assumes that only valid data will be supplied – it does not check for input failure. We will deal with that problem later in this chapter.

Line 18 uses the Standard-defined name, size t, for the unsigned integer type used to measure the size of objects in C++. Which unsigned integer type is used for size t is implementation-defined (i.e. the compiler implementer must document which choice was made from the available unsigned types).

GENERIC FUNCTIONS

121

Line 19 uses the function max( ) to go through the supplied data to find the largest value. If no data was provided, apart from the terminating value, the original value of maximum (-9999 in the above code) will be used.

Getting the Largest

Suppose that we now want to select the largest value from a sequence of values of type double. If you look at the above code you will realize that very little has to change in main( ). We will need to change all the instances of int in the body of main( ) to double. We will also need to change the end of data test – remember that it is unsafe to compare floating-point values for equality. We might change the test to check that the input value is greater than -9999.0.

T R Y T H I S

Try making those changes. Be careful that you do not change the definition of max( ). Also make sure that you did not change the return type of main( ); that must always be int.

When you come to compile the result you will get a number of warnings. Ignore them for now; build and execute the program. You should notice that the program gets the answers slightly wrong if the largest value is not an exact integer value. Think about why that should be.

The problem is that the values are being converted (rounded) to int values on the way into max( ). To avoid that, we need to add a new version of max( ), one that takes two doubles. In the short term we might just edit our current version of max( ) by replacing int by double throughout its declaration and definition, including its return type.

The short-term measure of replacing int max(int, int) with double max(double, double) only works if we do not want to use both versions within a single program.

Getting the Largest Using a typedef

In practice, there are many different types of values for which we may want to choose the bigger of two (or the one that comes second when the values are arranged in order). Here is a way that works as long as there is only a single relevant type in the program. It uses the C++ device (inherited from C) for giving an existing type a new name. The mechanism is a typedef declaration. This works like any other declaration of a name, but the name becomes a synonym for a type rather than a variable or function name. The following code demonstrates its use for providing some support for writing generic (type-independent) code:

1 #include <iostream>

2 #include <vector>

3 typedef int value_t;

4 value_t max(value_t first, value_t second){ 5 return first > second ? first : second; 6 } 7

122

CHAPTER 7

8 int main( ){

9try{

10std::vector<value_t> data;

11std::cout << "Type in some integers. End input with -9999\n\n";

12value_t value;

13do{

14std::cin >> value;

15data.push_back(value);

16} while(value > -9999);

17value_t maximum(-9999);

18for(size_t i(0); i != data.size( ); ++i){

19maximum = max(maximum, data[i]);

20}

21std::cout << "The largest input value was " << maximum << ".\n";

22}

23catch(...){ std::cerr << "\n***An exception was thrown***\n"; }

24}

Yes, that is the code from the previous program with two changes: line 3 now contains a typedef declaration that makes value t a synonym for int, and all the relevant uses of int have been changed to value t. Notice how our code now distinguishes between the uses of int to represent the kind of data we wish to process and other uses of int such as the return from main( ). This is another example of removing ‘magic’ from our code.

Before you try it, it is time to remove those magic uses of -9999. You will appreciate why in a few moments. Change line 7 to:

value_t const limit(-9999);

Now modify line 11 so that it outputs the message but uses limit instead of -9999. You will have to reorganize the statement because you cannot use variables, even const qualified ones, inside quotation marks.

Finally replace the other two uses of -9999 with limit.

T R Y T H I S

The resulting program should work exactly as the earlier one did. However, we now have the ability to reuse main( ) for other types, by making a couple of simple changes to the source code.

Try changing the typedef so that value t is a synonym for double, and change limit’s initializer to -9999.0. Now build and execute the program. How well the message at line 11 fits with the new version depends on how general you managed to make it. You could have pulled the message into a std::string and placed that out front along with the other pieces that need changing for different types. However, I am sure you get the idea: write code so that is easily adjusted from a general case to a specific one.

Now for a final demonstration of the power of writing code this way. Try changing line 3 to

typedef std::string value_t;

and line 7 to:

value_t limit("@");

GENERIC FUNCTIONS

123

You will need to add #include <string> so that the compiler can find the declarations relating to the std::string type. You will probably also need to tweak the message asking for data input.

Build and execute the resulting program. Note that ‘largest’ in this context will mean the word, or string of characters, that would be last when the data is sorted into lexical (alphabetical) order.

EXERCISES

1.Tidy up the above program by declaring a suitable std::string const prompt and modifying line 11 to use it. Arrange the code so that the three things that need modifying for different types are declared/defined as three consecutive statements.

2.Change the output so that it also lists the input values a comma-separated list. The output should be something like the ‘The largest value in (. . .) was . . .’ with the dots replaced by the correct data.

3.Write a program that outputs the second-largest value from a sequence of values. You must not modify the order of the sequence, so using std::sort( ) and then selecting the second from the end is not a valid solution to this problem.

Getting the Largest Using a Template

Choosing the greater of two values uses exactly the same basic code for any type for which the > operator can be used. The only thing we need to change is the type of the data. The C++ function-template mechanism is designed to deal with this. It allows us to create type parameters to which we can pass type arguments. Here is a function template for creating max( ) functions:

template <typename value_type>

value_type max(value_type first, value_type second){ return first > second ? first : second;

}

Let us focus on the first line of that code. The template keyword tells the compiler that what follows is generic code. The code between the angle brackets tells the compiler the generic parameters. These are provided as a list (comma-separated if there is more than one parameter). There are three kinds of generic parameter: type, value, and template. For the time being I am going to deal only with type parameters – the other two are expert territory and best left alone until you have more substantial experience of writing C++. Type parameters are identified by the keyword typename (class can also be used, but I prefer to use the more descriptive option), followed by a parameter name. As you can see above, the parameter name behaves in a similar fashion to a typedef name as far as the function-template code is concerned.

The big difference is in the way we use a function template. I can explicitly provide the relevant type argument(s) at the point where I want to call a function generated from the function template. I can rewrite my example program as:

1 #include <iostream>

2 #include <vector>

124	CHAPTER 7
3	#include <string>
4
5	template <typename value_type>
6	value_type max(value_type first, value_type second){
7	return first > second ? first : second;
8	}
9	typedef int value_t;
10	value_t limit(-9999);
11	std::string type("integers");
12

13int main( ){

14try{

15std::vector<value_t> data;

16std::cout << "Type in some " << type <<

17". End input with " << limit << ".\n\n";

18int value;

19do{

20std::cin >> value;

21data.push_back(value);

22} while(value > -9999);

23value_t maximum(-9999);

24for(size_t i(0); i != data.size( ); ++i){

25maximum = max<value_t>(maximum, data[i]);

26}

27std::cout << "The largest input value was " << maximum << ".\n";

28}

29catch(...){std::cerr << "\n***An exception was thrown***\n";}

30}

I have tidied up the code but the critical change is at line 25: max<value t> specifies that the version of max( ) generated for the type of value t must be used. value t is the type argument passed to the function template parameter, value type. Your first reaction may be that we seem to have gained very little over just using a typedef. If we were only interested in this single program, you would be right. Indeed if you try this code with value t being some type from the Standard C++ Library such as std::string it will no longer compile. Put that to one side for now because I will deal with that issue later in this chapter.

The advantage of using a template is a longer-term one: we can use the function template for max( ) whenever we want to select the larger of two values. There are two conditions required for using a function template. The first is that the compiler must see the actual definition of the template function (though a new mechanism – using the keyword export – for allowing the compiler to go ahead with only a declaration of the template function is beginning to become available in some compilers). The second condition is that the generated code must be valid for the template arguments. In this case the type must have a useable > operator with the correct behavior. We will shortly see that the latter requirement is an important one.

In most cases we can omit the explicit template type arguments (the type or types in the angle brackets used when the function is called) for a function template, because the compiler will be able to deduce the relevant type(s) from the argument(s) supplied for the generated function. Here is an example for you to try.

T R Y T H I S

1 #include <iostream>

2 #include <string>

GENERIC FUNCTIONS

125

3

4 template<typename value_type>

5 value_type max(value_type first, value_type second){ 6 return first > second ? first : second;

7 }

8

9 int main( ){

10try{

11std::cout << max(12, 24) << '\n';

12std::cout << max(12.3, -1.4) << '\n';

13std::cout << max('a', 'b') << '\n';

14}

15catch(...){std::cerr << "\n***An exception was thrown***\n";}

16}

Create a project and try out that short program. Notice that the results are correct for each of the three calls of max( ). The compiler has worked out that the first one is comparing two ints, the second compares two doubles and the third compares two chars.

Now change line 13 to

std::cout << max('b', 'a') << '\n';

and check that the result is still ‘b’. Next change that line to:

std::cout << max("b", "a") << '\n';

On my system the result is still ‘b’. However, when you try

std::cout << max("a", "b") << '\n';

you should get a surprise – the result is ‘a’. (Some systems may reverse the last two results.) Something odd is happening here, and it is an example of the kind of problem you may have to deal with. 'a' and 'b' are char literals. In other words, they are values of type char. When we ask that they be compared the compiler generates code that treats them as small integers. The code representing 'a' has a lower value than the code that represents 'b' (they are actually 97 and 98 respectively if the system is using ASCII).

However, when we use double quotes we create a string literal. The program uses some special storage it has available to store the codes for the specific string of chars that we have specified. It then adds one more location in which it stores a zero as an end-of-string marker. The upshot is that "a" and "b" are not any kind of integer (they are actually arrays of char, but do not worry if your previous programming experience has not covered this idea). There are no comparison operators between string literals (that may come as a surprise if you previously used languages that do provide comparisons between string literals), so the compiler looks for an alternative. What it does is compare the addresses where the string literals are stored. The answers you get from the last two versions of the program depend on where the string literals are stored, not on what letters are used. On the compiler I am using it stores earlier string literals at higher (larger) addresses than later ones.

We fix the problem by telling the compiler what we want to compare by writing:

std::cout << max<std::string>("b", "a") << '\n';

There are other ways to fix it but this works fine so there is no reason to add complications.

126

CHAPTER 7

Ambiguity

Try replacing one of the lines using max( ) in the program we are currently studying with:

std::cout << max(12.2, 24) << '\n';

In other words, make the first argument have a different type to the second. As human beings, we have no difficulty in recognizing that we are implicitly dealing with floating-point values even though the second one is written as an int value. The compiler is more restricted. It tries to deduce the type that must be passed to the value type template parameter and comes up with two different answers. The C++ rule for type deduction for template parameters is that only exact matches count, and that all choices for deduction must result in exactly the same type.

We can easily fix this example in one of two ways. We can change the type of the second parameter by writing it as 24.0, or we can explicitly provide the template type parameter by writing:

std::cout << max<double>(12.2, 24) << '\n';

Both ways will resolve the ambiguity and direct the compiler to make an appropriate choice. As to which is the better solution, that depends on the context. It is up to the programmer to choose an appropriate solution from the available options.

Overloading

A function template can co-exist with a function of the same name. If both the function template and the plain function can exactly match the types of the arguments in a call using implicit type deduction, the plain one is preferred. If the function template cannot provide an exact match but the plain one can be called by converting the type of the arguments then the plain one will be used. Here is some code for you to experiment with to help understand these rules:

T R Y T H I S

1 #include <iostream>

2 #include <string>

3

4 template<typename value_type>

5 value_type max(value_type first, value_type second){ 6 return first > second ? first : second;

7 }

8

9 int max(int first, int second){

10return first > second ? first : second;

11}

12

13int main( ){

14try{

15std::cout << max(1, 2.5) << '\n';

16}

17catch(...){std::cerr << "\n***An exception was thrown***\n";}

18}

GENERIC FUNCTIONS

127

When you	try to compile this, the compiler issues a warning (at	least it will if you have
not turned	the warning off). Notice the nature of the warning; it	is telling you that it has

to narrow a floating-point value to an int. Why is that? At line 15, it looks for a version of max( ) that it can use. Because the types of the two arguments are different, it abandons the function template (because that requires that the deduced types for the template parameter be the same for both the function arguments – they aren’t: the first is an int and the second is a double). However, I have also provided a plain (non-template) version of max( ). In this case, the arguments still do not exactly match, but the compiler spots that it can convert the second argument to an int value by rounding it to 2. Therefore, it chooses that option and warns the programmer that it narrowed a value from a double to an int.

In this case, we should probably take this warning seriously, because the value we get back is not actually the maximum of the values we supplied.

Instrumenting Code

Sometimes, when we are testing code, we want some extra information during the execution of a program that we would not want if we were producing a finished product. We call the process of adding source code to provide such extra information ‘instrumenting the code’. Suppose we want to check that the compiler chooses the plain version of max( ) in preference to generating a function from the function template if both are exact matches. We could modify the two definitions so that each reports on its use:

template<typename value_type>

value_type max(value_type first, value_type second){ std::cout << "Template used.\n";

return first > second ? first : second;

}

int max(int first, int second){ std::cout << "Plain function used.\n";

return first > second ? first : second;

}

T R Y T H I S

Use those two definitions with the following version of main( ):

1 int main( ){

2try{

3 int i(3);

4int j(5);

5std::cout << max(i, j);

6}

7 catch(...){std::cerr << "\n***An exception was thrown***\n";}

8 }

I have added some variables to the program just to make it clear that they are allowed. Indeed we could call max( ) with expressions; for example, max(i * 2, j + 6). I hope you noticed that as long as both the expressions result in int values we get the message ‘Plain function used.’