10. Functions10.1 Why Functions?
At times, a certain portion of codes has to be used many times.
Instead of re-writing the codes many times, it is better to put them into a "subroutine", and "call" this "subroutine" many time - for ease of maintenance and understanding. Subroutine is called method (in Java) or function (in C/C++).
The benefits of using functions are:
- Divide and conquer: construct the program from simple, small pieces or components. Modularize the program into self-contained tasks.
- Avoid repeating codes: It is easy to copy and paste, but hard to maintain and synchronize all the copies.
- Software Reuse: you can reuse the functions in other programs, by packaging them into library codes.
Two parties are involved in using a function: a caller who calls the function, and the function called.
The caller passes argument(s) to the function.
The function receives these argument(s), performs the programmed operations within the function's body, and returns a piece of result back to the caller.
10.2 Using FunctionsGet Started with an Example
Suppose that we need to evaluate the area of a circle many times, it is better to write a function called getArea(), and re-use it when needed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| /* Test Function (TestFunction.cpp) */
#include <iostream>
using namespace std;
const int PI = 3.14159265;
// Function Prototype (Function Declaration)
double getArea(double radius);
int main() {
double radius1 = 1.1, area1, area2;
// call function getArea()
area1 = getArea(radius1);
cout << "area 1 is " << area1 << endl;
// call function getArea()
area2 = getArea(2.2);
cout << "area 2 is " << area2 << endl;
// call function getArea()
cout << "area 3 is " << getArea(3.3) << endl;
}
// Function Definition
// Return the area of a circle given its radius
double getArea(double radius) {
return radius * radius * PI;
}
|
area 1 is 3.63
area 2 is 14.52
area 3 is 32.67
In the above example, a reusable function called getArea() is defined, which receives a parameter (in double) from the caller, performs the calculation, and return a piece of result (in double) to the caller. In the main(), we invoke getArea() functions thrice, each time with a different parameter.
In C++, you need to declare a function prototype (before the function is used), and provide a function definition, with a body containing the programmed operations.
Function Definition
The syntax for function definition is as follows:
returnValueType functionName ( parameterList ) {
functionBody ;
}
- The parameterList consists of comma-separated parameter-type and parameter-name, i.e., param-1-type param-1-name, param-2-type param-2-name,...
- The returnValueType specifies the type of the return value, such as int or double. An special return type called void can be used to denote that the function returns no value. In C++, a function is allowed to return one value or no value (void). It cannot return multiple values. [C++ does not allow you to return an array!]
The "return" Statement
Inside the function's body, you could use a return statement to return a value (of the returnValueType declared in the function's header) and pass the control back to the caller. The syntax is:
return expression; // Evaluated to a value of returnValueType declared in function's signature
return; // For function with return type of void
Take note that invoking a function (by the caller) transfers the control to the function. The return statement in the function transfers the control back to the caller.
Function Naming Convention
A function's name shall be a verb or verb phrase (action), comprising one or more words. The first word is in lowercase, while the rest are initial-capitalized (known as camel-case). For example, getArea(), setRadius(), moveDown(), isPrime(), etc.
Function Prototype
In C++, a function must be declared before it can be called. It can be achieved by either placing the function definition before it is being used, or declare a so-called function prototype.
A function prototype tells the compiler the function's interface, i.e., the return-type, function name, and the parameter type list (the number and type of parameters). The function can now be defined anywhere in the file. For example,
// Function prototype - placed before the function is used.
double getArea(double); // without the parameter name
int max(int, int);
You could optionally include the parameter names in the function prototype. The names will be ignored by the compiler, but serve as documentation. For example,
// Function Prototype
double getArea(double radius); // parameter names are ignored, but serve as documentation
int max(int number1, int number2);
Function prototypes are usually grouped together and placed in a so-called header file.
The header file can be included in many programs. We will discuss header file later.
Another Example
We have a function called max(int, int), which takes two int and return their maximum. We invoke the max() function from the main().
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| /* Testing max function (TestMaxFunction.cpp) */
#include <iostream>
using namespace std;
int maximum(int, int); // Function prototype (declaration)
int main() {
cout << maximum(5, 8) << endl; // Call maximum() with literals
int a = 6, b = 9, c;
c = maximum(a, b); // Call maximum() with variables
cout << c << endl;
cout << maximum(c, 99) << endl; // Call maximum()
}
// Function definition
// A function that returns the maximum of two given int
int maximum(int num1, int num2) {
return (num1 > num2) ? num1 : num2;
}
|
The "void" Return Type
Suppose that you need a function to perform certain actions (e.g., printing) without a need to return a value to the caller, you can declare its return-value type as void. In the function's body, you could use a "return;" statement without a return value to return control to the caller.
In this case, the return statement is optional.
If there is no return statement, the entire body will be executed, and control returns to the caller at the end of the body.
Actual Parameters vs. Formal Parameters
Recall that a function receives arguments from its caller, performs the actions defined in the function's body, and return a value (or nothing) to the caller.
In the above example, the variable (double radius) declared in the signature of getArea(double radius) is known as formal parameter.
Its scope is within the function's body.
When the function is invoked by a caller, the caller must supply so-called actual parameters (or arguments), whose value is then used for the actual computation. For example, when the function is invoked via "area1 = getArea(radius1)", radius1 is the actual parameter, with a value of 1.1.
Scope of Function's Local Variables and Parameters
All variables, including function's parameters, declared inside a function are available only to the function.
They are created when the function is called, and freed (destroyed) after the function returns.
They are called local variables because they are local to the function and not available outside the function.
They are also called automatic variables, because they are created and destroyed automatically - no programmer's explicit action needed to allocate and deallocate them.
Boolean Functions
A boolean function returns a bool value (of either true or false) to the caller.
Suppose that we wish to write a function called isOdd() to check if a given number is odd.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| /*
* Test Boolean function (BooleanfunctionTest.cpp).
*/
#include <iostream>
using namespace std;
// Function Prototype
bool isOdd(int);
int main() {
cout << boolalpha; // print bool as true or false
cout << isOdd(5) << endl; // true
cout << isOdd(6) << endl; // false
cout << isOdd(-5) << endl; // false
}
bool isOdd(int number) {
if (number % 2 == 1) {
return true;
} else {
return false;
}
}
|
This seemingly correct codes produces false for -5, because -5%2 is -1 instead of 1. You may rewrite the condition:
bool isOdd(int number) { if (number % 2 == 0) { return false; } else { return true; }}The above code produces the correct answer, but is poor. For boolean function, you should simply return the resultant bool value of the comparison, instead of using a conditional statement, as follow:
bool isEven(int number) { return (number % 2 == 0);} bool isOdd(int number) { return !(number % 2 == 0); // OR return !isEven(number);} int main() { int number = -9; if (isEven(number)) { // Don't write (isEven(number) == true) cout << "Even" << endl; }}10.3 Default ArgumentsC++ introduces so-called default arguments for functions. These default values would be used if the caller omits the corresponding actual argument in calling the function. Default arguments are specified in the function prototype, and cannot be repeated in the function definition. The default arguments are resolved based on their positions. Hence, they can only be used to substitute the trailing arguments to avoid ambiguity. For example,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| /* Test Function default arguments (functionDefaultArgument.cpp) */
#include <iostream>
using namespace std;
// Function prototype - Specify the default arguments here
int fun1(int = 1, int = 2, int = 3);
int fun2(int, int, int = 3);
int main() {
cout << fun1(4, 5, 6) << endl; // No default
cout << fun1(4, 5) << endl; // 4, 5, 3(default)
cout << fun1(4) << endl; // 4, 2(default), 3(default)
cout << fun1() << endl; // 1(default), 2(default), 3(default)
cout << fun2(4, 5, 6) << endl; // No default
cout << fun2(4, 5) << endl; // 4, 5, 3(default)
// cout << fun2(4) << endl;
// error: too few arguments to function 'int fun2(int, int, int)'
}
int fun1(int n1, int n2, int n3) {
// cannot repeat default arguments in function definition
return n1 + n2 + n3;
}
int fun2(int n1, int n2, int n3) {
return n1 + n2 + n3;
}
|
You should specify the default arguments in the function prototype (declaration).
They can only be defined once (one-definition rule), and cannot be repeated in the function definition.
Default argument is not absolutely necessary. The codes could be hard to maintain.
10.4 Function Overloading
C++ introduces function overloading (or function polymorphism, which means many forms), which allows you to have multiple versions of the same function name, differentiated by the parameter list (number, type or order of parameters). The version matches the caller's argument list will be selected for execution. For example,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| /* Test Function Overloading (FunctionOverloading.cpp) */
#include <iostream>
using namespace std;
void fun(int, int, int); // Version 1
void fun(double, int); // Version 2
void fun(int, double); // Version 3
int main() {
fun(1, 2, 3); // version 1
fun(1.0, 2); // version 2
fun(1, 2.0); // version 3
fun(1.1, 2, 3); // version 1 - double 1.1 casted to int 1 (without warning)
// fun(1, 2, 3, 4);
// error: no matching function for call to 'fun(int, int, int, int)'
// fun(1, 2);
// error: call of overloaded 'fun(int, int)' is ambiguous
// note: candidates are:
// void fun(double, int)
// void fun(int, double)
// fun(1.0, 2.0);
// error: call of overloaded 'fun(double, double)' is ambiguous
}
void fun(int n1, int n2, int n3) { // version 1
cout << "version 1" << endl;
}
void fun(double n1, int n2) { // version 2
cout << "version 2" << endl;
}
void fun(int n1, double n2) { // version 3
cout << "version 3" << endl;
}
|
Overloaded functions cannot be differentiated by the return-type (compilation error).
*Name Mangling
To differentiate between different versions of an overloaded function, many compilers (such as GNU GCC) adopt a name mangling or name decoration scheme for naming functions.
// Compile source into object code FunctionOverloading.o
> g++ -c FunctionOverloading.cpp
// List the symbol table
> nm FunctionOverloading.o
......
000000b5 T __Z3fundi
000000ed T __Z3funid
00000089 T __Z3funiii
......
Each of the function is identified via a prefix __Z, followed by an integer containing the number of characters of the function name (3 in this case for "fun"), followed by the parameter type list (where i for int and d for double). For example, di means a double followed by an int; id for an int followed by a double; iii for 3 ints.
You can choose to use the C's naming protocol by appending the keyword extern "C" to the function prototype.
C does not support function overloading. Thus, it does not need name mangling. It simply append an underscore in front of the function name. For example,
extern "C" void fun(int, int, int, int); // Compiled as _fun
10.5 Functions and Arrays
You can also pass arrays into function. However, you also need to pass the size of the array into the function.
This is because there is no way to tell the size of the array from the array argument inside the called function.
For example,
Example: Computing the Sum of an Array and Print Array's Contents
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| /* Function to compute the sum of an array (SumArray.cpp) */
#include <iostream>
using namespace std;
// Function prototype
int sum(int array[], int size); // Need to pass the array size too
void print(int array[], int size);
// Test Driver
int main() {
int a1[] = {8, 4, 5, 3, 2};
print(a1, 5);
// {8,4,5,3,2}
cout << "sum is " << sum(a1, 5) << endl; // sum is 22
}
// Function definition
// Return the sum of the given array
int sum(int array[], int size) {
int sum = 0;
for (int i = 0; i < size; ++i) {
sum += array;
}
return sum;
}
// Print the contents of the given arrayv
oid print(int array[], int size) {
cout << "{";
for (int i = 0; i < size; ++i) {
cout << array;
if (i < size - 1) {
cout << ",";
}
}
cout << "}" << endl;
}
|
10.6 Pass-by-Value vs. Pass-by-Reference
There are two ways that a parameter can be passed into a function: pass by value vs. pass by reference.
Pass-by-Value
In pass-by-value, a "copy" of argument is created and passed into the function. The invoked function works on the "clone", and cannot modify the original copy. In C/C++, fundamental types (such as int and double) are passed by value. That is, you cannot modify caller's value inside the function - there is no side effect.
Example (Fundamental Types are Passed by Value)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| /* Fundamental types are passed by value into Function (TestPassByValue.cpp) */
#include <iostream>
using namespace std;
// Function prototypes
int inc(int number);
// Test Driver
int main() {
int n = 8;
cout << "Before calling function, n is " << n << endl; // 8
int result = inc(n);
cout << "After calling function, n is " << n << endl; // 8
cout << "result is " << result << endl; // 9
}
// Function definitions
// Return number+1
int inc(int number) {
++number; // Modify parameter, no effect to caller
return number;
}
|
Pass-by-Reference
On the other hand, in pass-by-reference, a reference of the caller's variable is passed into the function. In other words, the invoked function works on the same data. If the invoked function modifies the parameter, the same caller's copy will be modified as well.
In C/C++, arrays are passed by reference. That is, you can modify the contents of the caller's array inside the invoked function - there could be side effect in passing arrays into function.
C/C++ does not allow functions to return an array. Hence, if you wish to write a function that modifies the contents of an array (e.g., sorting the elements of an array), you need to rely on pass-by-reference to work on the same copy inside and outside the function. Recall that in pass-by-value, the invoked function works on a clone copy and has no way to modify the original copy.
Example (Array is passed by Reference): Increment Each Element of an Array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| /* Function to increment each element of an array (IncrementArray.cpp) */
#include <iostream>
using namespace std;
// Function prototypes
void inc(int array[], int size);
void print(int array[], int size);
// Test Driver
int main() {
int a1[] = {8, 4, 5, 3, 2};
// Before increment
print(a1, 5); // {8,4,5,3,2}
// Do increment
inc(a1, 5); // Array is passed by reference (having side effect)
// After increment
print(a1, 5); // {9,5,6,4,3}
}
// Function definitions
// Increment each element of the given array
void inc(int array[], int size) { // array[] is not const
for (int i = 0; i < size; ++i) {
array++; // side-effect
}
}
// Print the contents of the given array
void print(int array[], int size) {
cout << "{";
for (int i = 0; i < size; ++i) {
cout << array;
if (i < size - 1) {
cout << ",";
}
}
cout << "}" << endl;
}
|
Array is passed into function by reference. That is, the invoked function works on the same copy of the array as the caller. Hence, changes of array inside the function is reflected outside the function (i.e., side effect).
Why Arrays are Pass-by-Reference?
Array is designed to be passed by reference, instead of by value using a cloned copy. This is because passing huge array by value is inefficient - the huge array needs to be cloned.
10.7 const Function Parameters
Pass-by-reference risks corrupting the original data. If you do not have the intention of modifying the arrays inside the function, you could use the const keyword in the function parameter. A const function argument cannot be modified inside the function.
Use const whenever possible for passing references as it prevent you from inadvertently modifying the parameters and protects you against many programming errors.
Example: Search an Array using Linear Search
In a linear search, the search key is compared with each element of the array linearly. If there is a match, it returns the index of the array between [0, size-1]; otherwise, it returns -1 or the size of of the array (some implementations deal with only positive indexes). Linear search has complexity of O(n).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| /* Search an array for the given key using Linear Search (LinearSearch.cpp) */
#include <iostream>
using namespace std;
int linearSearch(const int a[], int size, int key);
int main() {
const int SIZE = 8;
int a1[SIZE] = {8, 4, 5, 3, 2, 9, 4, 1};
cout << linearSearch(a1, SIZE, 8) << endl; // 0
cout << linearSearch(a1, SIZE, 4) << endl; // 1
cout << linearSearch(a1, SIZE, 99) << endl; // 8 (not found)
}
// Search the array for the given key
// If found, return array index [0, size-1]; otherwise, return size
int linearSearch(const int a[], int size, int key) {
for (int i = 0; i < size; ++i) {
if (a == key) return i;
}
return size;
}
|
Program Notes:
Example: Sorting an Array using Bubble Sort
Wiki "Bubble Sort" for the detailed algorithm and illustration. In brief, we pass thru the list, compare two adjacent items and swap them if they are in the wrong order. Repeat the pass until no swaps are needed. For example,
{8,4,5,3,2,9,4,1}
PASS 1 ...
{8,4,5,3,2,9,4,1} => {4,8,5,3,2,9,4,1}
{4,8,5,3,2,9,4,1} => {4,5,8,3,2,9,4,1}
{4,5,8,3,2,9,4,1} => {4,5,3,8,2,9,4,1}
{4,5,3,8,2,9,4,1} => {4,5,3,2,8,9,4,1}
{4,5,3,2,8,9,4,1} => {4,5,3,2,8,4,9,1}
{4,5,3,2,8,4,9,1} => {4,5,3,2,8,4,1,9}
PASS 2 ...
{4,5,3,2,8,4,1,9} => {4,3,5,2,8,4,1,9}
{4,3,5,2,8,4,1,9} => {4,3,2,5,8,4,1,9}
{4,3,2,5,8,4,1,9} => {4,3,2,5,4,8,1,9}
{4,3,2,5,4,8,1,9} => {4,3,2,5,4,1,8,9}
PASS 3 ...
{4,3,2,5,4,1,8,9} => {3,4,2,5,4,1,8,9}
{3,4,2,5,4,1,8,9} => {3,2,4,5,4,1,8,9}
{3,2,4,5,4,1,8,9} => {3,2,4,4,5,1,8,9}
{3,2,4,4,5,1,8,9} => {3,2,4,4,1,5,8,9}
PASS 4 ...
{3,2,4,4,1,5,8,9} => {2,3,4,4,1,5,8,9}
{2,3,4,4,1,5,8,9} => {2,3,4,1,4,5,8,9}
PASS 5 ...
{2,3,4,1,4,5,8,9} => {2,3,1,4,4,5,8,9}
PASS 6 ...
{2,3,1,4,4,5,8,9} => {2,1,3,4,4,5,8,9}
PASS 7 ...
{2,1,3,4,4,5,8,9} => {1,2,3,4,4,5,8,9}
PASS 8 ...
{1,2,3,4,4,5,8,9}
Bubble sort is not efficient, with complexity of O(n2).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| /* Sorting an array using Bubble Sort (BubbleSort.cpp) */
#include <iostream>
using namespace std;
void bubbleSort(int a[], int size);
void print(const int a[], int size);
int main() {
const int SIZE = 8;
int a[] = {8, 4, 5, 3, 2, 9, 4, 1};
print(a, SIZE);
cout << endl;
bubbleSort(a, SIZE);
print(a, SIZE);
cout << endl;
}
// Sort the given array of size
void bubbleSort(int a[], int size) {
bool done = false; // terminate if no more swap thru a pass
int pass = 0; // pass number, for tracing
int temp; // use for swapping
while (!done) {
cout << "PASS " << ++pass << " ..." << endl; // for tracing
done = true;
// Pass thru the list, compare adjacent items and swap
// them if they are in wrong order
for (int i = 0; i < size - 1; ++i) {
if (a > a[i+1]) {
print(a, size); // for tracing
temp = a;
a = a[i+1];
a[i+1] = temp;
done = false; // swap detected, one more pass
cout << "=> "; // for tracing
print(a, size);
cout << endl;
}
}
}
}
// Print the contents of the given array of size
void print(const int a[], int size) {
cout << "{";
for (int i = 0; i < size; ++i) {
cout << a;
if (i < size - 1) cout << ",";
}
cout << "} ";
}
|
Program Notes:
Example: Sorting an Array using Insertion Sort
Wiki "Insertion Sort" for the algorithm and illustration. In brief, pass thru the list. For each element, compare with all previous elements and insert it at the correct position by shifting the other elements. For example,
{8,4,5,3,2,9,4,1}
{8} {4,5,3,2,9,4,1}
{4,8} {5,3,2,9,4,1}
{4,5,8} {3,2,9,4,1}
{3,4,5,8} {2,9,4,1}
{2,3,4,5,8} {9,4,1}
{2,3,4,5,8,9} {4,1}
{2,3,4,4,5,8,9} {1}
{1,2,3,4,4,5,8,9}
Insertion sort is also not efficient, with complexity of O(n2).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| /* Sorting an array using Insertion Sort (InsertionSort.cpp) */
#include <iostream>
using namespace std;
void insertionSort(int a[], int size);
void print(const int a[], int iMin, int iMax);
int main() {
const int SIZE = 8;
int a[SIZE] = {8, 4, 5, 3, 2, 9, 4, 1};
print(a, 0, SIZE - 1);
cout << endl;
insertionSort(a, SIZE);
print(a, 0, SIZE - 1);
cout << endl;
}
// Sort the given array of size using insertion sort
void insertionSort(int a[], int size) {
int temp; // for shifting elements
for (int i = 1; i < size; ++i) {
// for tracing
print(a, 0, i - 1); // already sorted
print(a, i, size - 1); // to be sorted
cout << endl;
// For element at i, insert into proper position in [0, i-1]
// which is already sorted.
// Shift down the other elements
for (int prev = 0; prev < i; ++prev) {
if (a < a[prev]) {
// insert a at prev, shift the elements down
temp = a;
for (int shift = i; shift > prev; --shift) {
a[shift] = a[shift-1];
}
a[prev] = temp;
break;
}
}
}
}
// Print the contents of the array in [iMin, iMax]
void print(const int a[], int iMin, int iMax) {
cout << "{";
for (int i = iMin; i <= iMax; ++i) {
cout << a;
if (i < iMax) cout << ",";
}
cout << "} ";
}
|
Program Notes:
Example: Sorting an Array using Selection Sort
Wiki "Selection Sort" for the algorithm and illustration. In brief, Pass thru the list. Select the smallest element and swap with the head of the list. For example,
{8,4,5,3,2,9,4,1}
{} {8,4,5,3,2,9,4,1} => {} {1,4,5,3,2,9,4,8}
{1} {4,5,3,2,9,4,8} => {1} {2,5,3,4,9,4,8}
{1,2} {5,3,4,9,4,8} => {1,2} {3,5,4,9,4,8}
{1,2,3} {5,4,9,4,8} => {1,2,3} {4,5,9,4,8}
{1,2,3,4} {5,9,4,8} => {1,2,3,4} {4,9,5,8}
{1,2,3,4,4} {9,5,8} => {1,2,3,4,4} {5,9,8}
{1,2,3,4,4,5} {9,8} => {1,2,3,4,4,5} {8,9}
{1,2,3,4,4,5,8,9}
Selection sort is also not efficient, with complexity of O(n2).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| /* Sorting an array using Selection Sort (SelectionSort.cpp) */
#include <iostream>
using namespace std;
void selectionSort(int a[], int size);
void print(const int a[], int iMin, int iMax);
int main() {
const int SIZE = 8;
int a[SIZE] = {8, 4, 5, 3, 2, 9, 4, 1};
print(a, 0, SIZE - 1);
cout << endl;
selectionSort(a, SIZE);
print(a, 0, SIZE - 1);
cout << endl;
}
// Sort the given array of size using selection sort
void selectionSort(int a[], int size) {
int temp; // for swaping
for (int i = 0; i < size - 1; ++i) {
// for tracing
print(a, 0, i - 1);
print(a, i, size - 1);
// [0, i-1] already sort
// Search for the smallest element in [i, size-1]
// and swap with a
int minIndex = i; // assume fist element is the smallest
for (int j = i + 1; j < size; ++j) {
if (a[j] < a[minIndex]) minIndex = j;
}
if (minIndex != i) { // swap
temp = a;
a = a[minIndex];
a[minIndex] = temp;
}
// for tracing
cout << "=> ";
print(a, 0, i - 1);
print(a, i, size - 1);
cout << endl;
}
}
// Print the contents of the array in [iMin, iMax]v
oid print(const int a[], int iMin, int iMax) {
cout << "{";
for (int i = iMin; i <= iMax; ++i) {
cout << a;
if (i < iMax) cout << ",";
}
cout << "} ";
}
|
Program Notes:
"const" Fundamental-Type Function Parameters?
You could also use const for fundamental-type function parameters (such as int, double) to prevent the parameters from being modified inside the function. However, as fundamental-type parameters are passed by value (with a cloned copy), there will never be side effect on the caller. We typically do not use the const keyword for fundamental types. In other words, const is used to indicate that there shall NOT be side-effect.
10.8 Pass-by-Reference via "Reference" Parameters
As mentioned, parameters of fundamental types (such as int, double) are passed-by-value. That is, a clone copy is used inside the function. Change to the cloned copy inside the function has no side-effect to the caller's copy.
Nonetheless, you can pass a fundamental type parameter by reference via the so-called reference parameter denoted by &. For example,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| /* Test Pass-by-reference for fundamental-type parameter via reference declaration (TestPassByReference.cpp) */
#include <iostream>
using namespace std;
int squareByValue (int number);
// Pass-by-valuevoid squareByReference (int & number);
// Pass-by-reference
int main() {
int n1 = 8;
cout << "Before call, value is " << n1 << endl; // 8
cout << squareByValue(n1) << endl; // no side-effect
cout << "After call, value is " << n1 << endl; // 8
int n2 = 9;
cout << "Before call, value is " << n2 << endl; // 9
squareByReference(n2); // side-effect
cout << "After call, value is " << n2 << endl; // 81
}
// Pass parameter by value - no side effect
int squareByValue (int number) {
return number * number;
}
// Pass parameter by reference by declaring as reference (&)
// - with side effect to the caller
void squareByReference (int & number) {
number = number * number;
}
|
In function squareByReference(), we declare the parameter number is passed by reference by declaring its type as int & (reference of int). In this way, the caller's copy is used inside the function (instead of a cloned copy in pass-by-value). Changes inside the function has side-effect.
Pass-by-reference is NOT commonly used for fundamental types (such as int, double) - the above example is purely meant for academic illustration. But it is used extensively for compound types (such as arrays and objects) to avoid cloning huge data for better performance. We shall revisit pass-by-reference in Object-Oriented Programming (OOP) chapters.
10.9 Mathematical Functions (Header <cmath>)
C++ provides many common-used Mathematical functions in library <cmath> (ported over from C's "math.h").
The signatures of some of these functions are:
| sin(x), cos(x), tan(x), asin(x), acos(x), atan(x): Take argument-type and return-type of float, double, long double. | | atan2(y, x): Return arc-tan of y/x. Better than atan(x) for handling 90 degree. | | sinh(x), cosh(x), tanh(x): hyper-trigonometric functions. | | pow(x, y), sqrt(x): power and square root. | | ceil(x), floor(x): returns the ceiling and floor integer of floating point number. | | fabs(x), fmod(x, y): floating-point absolute and modulus. | | exp(x), log(x), log10(x): exponent and logarithm functions. |
10.10 Generating Random Numbers
The cstdlib header (ported from C's stdlib.h) provides a function rand(), which generates a pseudo-random integral number between 0 and RAND_MAX (inclusive). RAND_MAX is a constant defined in cstdlib (typically the maximum value of 16-/32-bit signed integer, such as 32767). You can generate a random number between [0,n) via rand() % n.
rand() generates the same squence of pseudo-random numbers on different invocations. The cstblib also provides a srand() function to seed or initialize the random number generator. We typically seed it with the current time obtained via time(0) function (in <ctime> header), which returns the number of seconds since January 1st, 1970.
Example 1: Test rand() and srand(time(0))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| /* Test Random Number Generation (TestRand.cpp) */
#include <iostream>
#include <cstdlib> // for rand(), srand()
#include <ctime> // for time()
using namespace std;
int main() {
// rand() generate a random number in [0, RAND_MAX]
cout << "RAND_MAX is " << RAND_MAX << endl; // 32767
// Generate 10 pseudo-random numbers between 0 and 99
// without seeding the generator.
// You will get the same sequence, every time you run this program
for (int i = 0; i < 10; ++i) {
cout << rand() % 100 << " "; // need <cstdlib> header
}
cout << endl;
// Seed the random number generator with current time
srand(time(0)); // need <cstdlib> and <ctime> header
// Generate 10 pseudo-random numbers
// You will get different sequence on different run,
// because the current time is different
for (int i = 0; i < 10; ++i) {
cout << rand() % 100 << " "; // need <cstdlib> header
}
cout << endl;
}
|
Example 2: Test rand()'s Distribution
We shall test the rand()'s distribution by repeatedly throwing a 6-sided die and count the occurrences.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| /* Test rand() distribution by throwing a die repeatedly (TestRandomDie.cpp) */
#include <iostream>
#include <iomanip>
#include <cstdlib> // for rand(), srand()
#include <ctime> // for time()
using namespace std;
const int TOTAL_COUNT = 2000000; // Close to INT_MAX
const int NUM_FACES = 6;
int frequencies[6] = {0}; // frequencies of 0 to 5, init to zero
int main() {
srand(time(0)); // seed random number generator with current time
// Throw the die and count the frequencies
for (int i = 0; i < TOTAL_COUNT; ++i) {
++frequencies[rand() % 6];
}
// Print statistics
cout << fixed << setprecision(2);
for (int i = 0; i < NUM_FACES; i++) {
cout << i+1 << ": " << frequencies
<< " (" << 100.0 * frequencies / TOTAL_COUNT << "%)" << endl;
}
}
|
1: 333109 (16.66%)
2: 333113 (16.66%)
3: 333181 (16.66%)
4: 333562 (16.68%)
5: 333601 (16.68%)
6: 333434 (16.67%)
As seen from the output, rand() is fairly uniformly-distributed over [0, RAND_MAX].
10.11 Exercises[TODO]
|
發表於 2016-1-1 19:24:51
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
轉播
分享
淘帖