# 9: Arrays and Vectors

## 9.1: Introduction to Vectors

### Learner Outcomes

At the end of the lesson the student will be able to:

• Use vectors to collect data items
• Access vector elements and resize vectors
• Pass vectors to functions and return them from functions

### 9.1.1: Using Lists for Data

• Often times we need to process a group of the same types of data
• For instance:
• Bank account transactions
• Salaries for employees in a company
• Test scores for a group of students
• Temperature data over some period of time
• Consider how we might process the following student test scores:  90 95 87 89 98 96 85 79 95 100
• With this data, we can calculate statistics like:
• Highest score
• Lowest score
• Average (mean) score
• Difference (deviation) of each score from the average
• We can write a program to read this data and make the calculations
• However, to calculate the difference from the mean, we need to first find the mean
• Thus, we have to process all the data twice: one to find the mean and another to calculate the difference of each score from the mean
• To process the data more than one, the best approach is to keep all the data in main memory

#### Storing Lists of Data

• If we know there are 10 inputs, we can use 10 separate variables
• Using separate variables quickly becomes prohibitive as the list gets larger (100 scores)
• Fortunately, C++ has techniques we can use to organize lists of data
• In this section we will discuss vectors
• In a later section we will discuss arrays

### 9.1.2: Defining Vectors

• A vector is a collection of data items all of the same type
• The vector data type is defined in the standard library `vector`:
```#include <vector>
using namespace std;
```
• The general syntax for defining a vector is:
```vector<dataType> variableName;
or
vector<dataType> variableName(initialSize);
```
• Where:
• variableName: the name you make up for the vector
• dataType: the data type of all the vector items
• initialSize (optional): the number of data items the vector can initially hold
• As an example, the following is the declaration of a vector named `scores` that holds 10 values of type `int`:
`vector<int> scores(10);`
• The data type of `scores` is `vector<int>`
• When a program executes this statement, it creates 10 contiguous slots in memory like this:

`scores = `  ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

• Each of the memory slots can hold one data value

#### Check Yourself

1. A vector is a ________ of data values organized using a ________ name.
2. The name for each data value in a vector is ________ or item.
3. True or false: each vector slot can store any number of values.
4. The number of "slots" created by the following statement is ________.
`vector<int> scores(42);`

### 9.1.3: Accessing Vector Items

• We must specify which slot to use with the `[]` operator
• For instance:
`scores[4] = 98;`
• The number inside the brackets is called an index or subscript
• In C++, the slots of vectors are numbered starting at 0, as shown below:

`scores = `  ` ` ` ` ` ` ` ` `98` ` ` ` ` ` ` ` ` ` `
 `[0]` `[1]` `[2]` `[3]` `[4]` `[5]` `[6]` `[7]` `[8]` `[9]`

• Thus, assignment to the slot with an index of 4 is put into the fifth slot

#### Using Slots

• We declared our example vector with a data type of `int`:
`vector<int> scores(10);`
• Because `scores` is a vector containing `int` values, we can use a slot, such as `scores[4]`, just like any variable of type `int`:
```scores[4]++;
cout << scores[4] << endl;
```
• This includes using a slot as an argument to a function with a parameter of the same type:
```void myFun(int singleScore);
...
myFun(scores[4]);
```

#### Using Vectors to Collect Data Items

• Note that the index of a vector can be any integer value
• Thus, we can use an integer variable for the index
• We can use an integer variable with a loop to read data into the vector
• Also, we can display the contents of a vector using a loop
• The following program shows an example of collecting and displaying data items

#### Example Program Collecting and Displaying Data Items

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ``` ```#include #include using namespace std; int main() { vector scores(10); cout << "Enter 10 scores:\n"; for (int i = 0; i < 10; i++) { cin >> scores[i]; } cout << "You entered:\n"; for (int i = 0; i < 10; i++) { cout << scores[i] << endl; } return 0; } ```

#### Check Yourself

1. The number inside of the square brackets of a vector is called an ________ or subscript.
2. Of the following, ________ will correctly access the fifth element of a vector named "foo".
1. `foo[5]`
2. `foo(5)`
3. `foo[4]`
4. `foo.vector[4]`
3. The first element in any vector has an index value of ________.
1. -1
2. 0
3. 1
4. 2
4. If you declare s vector with 100 elements, the index number of the last element is ________.

### 9.1.4: Changing the Vector Size

• We can find the size of a vector by calling the `size()` member function:
`int numScores = scores.size();`
• The `size()` function is commonly used in counting loops as well:
```for (unsigned i = 0; i < scores.size(); i++) {
// do something with scores[i]
}
```
• The `unsigned` data type is shorthand for `unsigned int`
• An `unsigned int` is an integer data type like `int` but without the sign bit
• Note that using `size()` is better than using a magic number

• Defining a vector without an initial size creates an empty vector that can hold no elements:
```vector<int> scores;
cout << scores.size() << endl;
```
• A vector of size 0 is actually useful because we can change the size of a vector
• If we know the size of data we are working with, then we should declare the size when we define the vector
• However, we do not always know the size of data we will work with
• Oftentimes the user will decide how many data items to enter into the program
• In this case, we can start with an empty vector and grow the vector whenever we add another element
• The `push_back()` function resizes the vector by adding one element to its end:
`scores.push_back(value);`
• Another member function, `pop_back()`, removes the last element of a vector, shrinking its size by one:
`scores.pop_back();`
• The example program listed below shows how to collect data with a variable number of elements
• The standard defines many other useful functions for vectors as well, which you can examine by following the links under More Information

#### Collecting and Displaying a Variable Number of Data Items

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ``` ```#include #include using namespace std; int main() { vector scores; cout << "Enter scores (-1 to quit):\n"; int value = 0; while (value != -1) { cin >> value; if (value != -1) { scores.push_back(value); } } cout << "You entered:\n"; for (unsigned i = 0; i < scores.size(); i++) { cout << scores[i] << endl; } return 0; } ```

#### Check Yourself

1. True or false: you can change the number of "slots" in a vector.
2. The find out the number of "slots" in a vector use the function ________.
3. The function to add an element to the end of a vector is ________.
4. The remove an element from the end of a vector use the function ________.

### 9.1.5: Vector Parameters and Return Values

• Functions often have vector parameters and return types:
```vector<double> avgDiff(const vector<int>& v, double a) {
vector<double> diff(v.size());
for (unsigned i = 0; i < v.size(); i++) {
diff[i] = v[i] - a;
}
return diff;
}
```
• We can pass vectors by value or by reference
• Passing by reference is more efficient than passing by value
• However, pass by reference lets us change the vector as well
• Thus, we use pass by reference if we want to change items in the vector
• If we do not want to change items in the vector, we use a constant reference
• A constant reference gives us the constancy of value parameters with the efficiency of reference parameters

#### Computing Test Statistics

 ```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 57 58 59 60 61 62 63 64 65 ``` ```#include #include using namespace std; /** Returns a vector containing the deviations from the mean. @param v The values to compare to the average. @param a The average value @return A vetcor containing the deviations from the mean. */ vector avgDiff(const vector& v, double a) { vector diff(v.size()); for (unsigned i = 0; i < v.size(); i++) { diff[i] = v[i] - a; } return diff; } int main() { vector scores; cout << "Enter scores (-1 to quit):\n"; int data = 0; while (data != -1) { cin >> data; if (data != -1) { scores.push_back(data); } } if (scores.size() <= 0) { cout << "No data!\n"; exit(1); } int highest = scores[0]; int lowest = scores[0]; int sum = 0; for (unsigned i = 0; i < scores.size(); i++) { sum = sum + scores[i]; if (scores[i] > highest) { highest = scores[i]; } if (scores[i] < lowest) { lowest = scores[i]; } } double average = 1.0 * sum / scores.size(); cout << "Highest score: " << highest << endl; cout << "Lowest score: " << lowest << endl; cout << "Average score: " << average << endl; cout << "Score differences:\n"; vector diff = avgDiff(scores, average); for (unsigned i = 0; i < diff.size(); i++) { cout << scores[i] << " differs from the mean by " << diff[i] << endl; } return 0; } ```

#### Check Yourself

1. True or false: you can pass a vector argument to a function, either by value or by reference.
2. To prevent a function from changing the value of a parameter use the keyword ________ before the parameter type.
3. True or false: you can return a vector from a function using a return statement.

### Exercise 9.1

In this exercise we explore the use of vectors to collect data items.

#### Specifications

1. Copy the following program into a text editor, save it as `namelist.cpp`, and then compile and run the starter program to make sure you copied it correctly.
```#include <iostream>
#include <vector>
using namespace std;

int main() {
// Enter code here

return 0;
}
```
2. Add a statement to define a vector named `names` that is suitable for holding a list of names.

3. Add code to use a loop and `getline()` to enter names into the list:
```cout << "Enter a list of names\n"
<< "When finished enter the word: done\n";
string input;
do {
getline(cin, input);
if (input != "done") {
names.push_back(input);
}
} while (input != "done");
```

4. Compile and run your modified program to make sure you made the changes correctly. When you run the program, the output should look like:
```Enter a list of names
When finished enter the word: done
Able Ableson
Baker Bakerson
Charlie Charleston
done
```
5. Add a statement that prints the first element of the vector. When you compile and run your program, it should display an additional statement like:
```The first name on the list is: Able Ableson
```

6. Add a statement that prints the last element of the vector. When you compile and run your program, it should display an additional statement like:
```The last name on the list is: Charlie Charleston
```

Note that names.size() returns the number of slots in the vector. The last slot is one less than the size because slots are numbered starting at zero. For more information see sections 9.1.3: Accessing Vector Items and 9.1.4: Changing the Vector Size.

7. Define a function named `showNames()` with a string vector parameter using the following code:
```void showNames(vector<string>& names) {
}
```

8. Inside the `showNames()` function, use a `for` loop and the `size()` function to display the names you entered.

For more information see the example in section 9.1.3: Accessing Vector Items.

9. After the other statements in `main()`, but before the `return 0` statement, call the `showNames()` function.

10. Compile and run your modified program to make sure you made the changes correctly. When you run the program, the output should look like:
```Enter a list of names.
When finished enter the word: done
Able Ableson
Baker Bakerson
Charlie Charleston
done

The first name on the list is: Able Ableson
The last name on the list is: Charlie Charleston

You entered:
Able Ableson
Baker Bakerson
Charlie Charleston
```

If there are any problems, compare your source code to the listing below.

11. Save your program source code to submit to Blackboard as part of assignment 9.

#### Check Yourself

1. Why would you want to use a vector? (9.1.1)
2. How do you define a vector? (9.1.2)
3. If you declare a vector with 100 elements, what is the number of the maximum element? (9.1.3)
4. What is a vector index? (9.1.3)
5. For a vector named `foo`, what code do you write to determine its current size? (9.1.4)
6. For a vector named `foo`, what code do you write to add an element to the end of the vector? (9.1.4)
7. For a vector named `foo`, what code do you write to remove an element from the end of the vector? (9.1.4)
8. Give an example of a useful function that:
1. Has a vector of integers as a value parameter
2. Has a vector of integers as a reference parameter
3. Has a vector of integers as a return value
Describe each function; do not implement them. (9.1.5)

### 9.1.6: Summary

• Often times we need to process a list of data
• Vectors offer a convenient way to process such a list
• The vector data type is defined in the standard library `vector`:
```#include <vector>
using namespace std;
```
• As an example, the following is the declaration of a vector named `scores` that holds 10 values of type `int`:
`vector<int> scores(10);`
• This code creates 10 contiguous slots in memory that can hold an `int`
• We must specify which slot to use with the `[]` operator:
`scores[4] = 98;`
• The number inside the brackets is called an index or subscript
• We can use any slot like a variable of the vector data type:
`cout << scores[4] << endl;`
• The index of a vector can be any integer value, which means we can use variables or expressions to specify the index
• This lets us use vectors with loop, like:
```for (int i = 0; i < 10; i++) {
cout << scores[i] << endl;
}
```
• We can find the size of a vector by calling the `size()` function
• If we know the size of data we are working with, then we should declare the size when we define the vector
• However, we do not always know the size of data we will work with
• Oftentimes the user will decide how many data items to enter into the program
• In this case, we can start with an empty vector and grow the vector whenever we add another element
• The `push_back()` function resizes the vector by adding one element to its end:
`scores.push_back(data);`
• Another member function, `pop_back()`, removes the last element of a vector, shrinking its size by one:
`scores.pop_back();`
• Functions often have vector parameters and return types
• We can pass vectors by value or by reference

## 9.2: Working with Vectors

### Learner Outcomes

At the end of the lesson the student will be able to:

• Apply some common list-processing algorithms to vectors

### 9.2.1: Bounds Errors

• Trying to access an element (slot) that does not exist in the vector is an error:
```vector<int> scores(10);
scores[10] = 90;
```
• However, the standard C++ implementation of vector does not generate an error message
• When we make an error like this, C++ silently reads or overwrites another memory location
• In a small program, we may not notice this error
• However, in a larger program we would get strange errors and the occasional spectacular crash
• Another related error is to forget the size of a vector
• For instance:
```vector<int> scores;
scores[0] = 90;
```
• Remember that defining a vector without an initial size creates an empty vector that can hold no elements
• Note that we can have C++ check the size for us by using the `at()` member function
• Instead of reading garbage at the end of the vector, the `at()` function reports an error
• The following program shows an example of a bounds error using both subscript notation `[]` and the `at()` function

#### Example Program with Vector Bounds Errors

 ```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 ``` ```#include #include using namespace std; const int SIZE = 3; const int NUM_VALUES = 5; int main(void) { vector values(SIZE); cout << "I will store " << NUM_VALUES << " numbers in a " << SIZE << "-element vector!\n"; for (int i = 0; i < NUM_VALUES; i++) { values[i] = i + 1; } cout << "Printing using subscript notation:\n"; for (int i = 0; i < NUM_VALUES; i++) { cout << values[i] << endl; } cout << "Printing using the at() function:\n"; for (int i = 0; i < NUM_VALUES; i++) { cout << values.at(i) << endl; } cout << "If you see this, the computer did not " << "crash!\n"; return 0; } ```

#### Check Yourself

1. True or false: C++ always throws an error when a vector exceed its bounds.
2. To reliably check when a vector exceed its bounds call the function ________.
3. What is wrong with the following code?
```vector<int> scores;
scores[0] = 90;
```
1. Nothing.
2. Cannot declare vectors without a size argument because the vector would be useless.
3. The first slot of a vector must contain the number 0.
4. Assigning a value outside the bounds of the vector.

### 9.2.2: Finding Values

• Suppose you want to find a particular value in a vector
• This is known as searching a list
• An easy and straightforward algorithm is linear search (a.k.a. sequential search)
• In linear search you:
• Start at the beginning of the list
• Compare each value in the list looking for matches:
• If the value is found, then return the position (index)
• If you reach the end of the list, return "not found"
• Since an index must be `>= 0`, then we can use `-1` as the "not found" value
• The following example demonstrates linear search

#### Finding a Value in a Vector

 ```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 57 58 ``` ```#include #include using namespace std; /** Finds the position of an item in a vector. @param v The vector with the elements to search. @param item The value to search for. @return The index of the first match, or -1 if not found. */ int find(const vector& v, int item) { for (unsigned i = 0; i < v.size(); i++) { if (item == v[i]) { return i; } } return -1; } /** Prints all the elements in a vector to the console. @param v the vector to print. */ void print(vector v) { for (unsigned i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; } int main() { const int SIZE = 20; const int MAX_NUM = 100; srand(time(0)); vector test(SIZE); for (unsigned i = 0; i < test.size(); i++) { test[i] = 1 + rand() % MAX_NUM; } print(test); cout << "Enter number to search for: "; int num; cin >> num; int slot = find(test, num); if (slot >= 0) { cout << "Found " << num << " in slot " << slot << endl; } else { cout << num << " not found\n"; } return 0; } ```

#### Check Yourself

1. True or false: to find a value in a vector, start at one end and search each slot until you find the value or reach the end.
2. The above technique for searching a vector is known as sequential or ________ search.
3. True or false: when searching a vector you must always start at index 0 and proceed to the end.

### 9.2.3: Removing Elements

• Once we find an item in a list, we may want to remove it
• If the order is not important then:
1. Overwrite the element to be removed with the last element of the vector
2. Shrink the size of the vector
• For instance:
```void erase(vector<int>& v, int pos) {
int lastPos = v.size() - 1;
v[pos] = v[lastPos];
v.pop_back();
}
```
• The following diagram from the textbook shows this operation
• However, if order matters then we must:
1. Move all elements up by one slot
2. Shrink the size of the vector
• For instance:
```void erase(vector<int>& v, int pos) {
for (unsigned i = pos; i < v.size() - 1; i++) {
v[i] = v[i + 1];
}
v.pop_back();
}
```
• The following diagram from the textbook shows this operation
• Also, the following example program demonstrates the technique in code

#### Removing Elements of a Vector

 ```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 ``` ```#include #include using namespace std; /** Removes an item from the vector preserving the order and reducing the size of the vector by one. @param v The vector with the element to remove. @param pos The number of the element to remove. */ void erase(vector& v, int pos) { for (unsigned i = pos; i < v.size() - 1; i++) { v[i] = v[i + 1]; } v.pop_back(); } /** Prints all the elements in a vector to the console. @param v the vector to print */ void print(vector v) { for (unsigned i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; } int main() { const int SIZE = 20; vector test(SIZE); for (unsigned i = 0; i < test.size(); i++) { test[i] = i; } print(test); cout << "Enter position to remove: "; int pos; cin >> pos; erase(test, pos); print(test); return 0; } ```

#### Check Yourself

1. True or false: to remove an element, overwrite the element with another and shrink the size of the vector.
2. If order does not matter then overwrite the element to remove with the ________ element of the vector.
3. If we want to preserve the order of elements, we use a ________ statement to move elements.

### 9.2.4: Inserting Elements

• If we want to add an item to a vector, the easiest way is at the end:
`v.push_back(item);`
• However, if we want to insert an item in the middle of a list we must:
1. Add a new empty element (slot) at the end of the vector
2. Move all elements after the insertion location up by one slot
3. Assign the new value to the element at the insertion slot
• For example:
```void insert(vector<int>& v, int pos, int value) {
int last = v.size() - 1;
v.push_back(v[last]);
for (int i = last; i > pos; i--) {
v[i] = v[i - 1];
}
v[pos] = value;
}
```
• The following diagram from the textbook shows this operation
• Also, the following example program demonstrates the technique in code

#### Inserting Elements into a Vector

 ```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 ``` ```#include #include using namespace std; /** Inserts an item into a vector. @param v The vector to which to add the element. @param pos The index before which to insert the element. @param value The element to insert. */ void insert(vector& v, int pos, int value) { int last = v.size() - 1; v.push_back(v[last]); for (int i = last; i > pos; i--) { v[i] = v[i - 1]; } v[pos] = value; } /** Prints all the elements in a vector to the console. @param v the vector to print */ void print(vector v) { for (unsigned i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; } int main() { const int SIZE = 20; vector test(SIZE); for (unsigned i = 0; i < test.size(); i++) { test[i] = i; } print(test); cout << "Enter position to insert: "; int pos; cin >> pos; cout << "Enter value to insert: "; int value; cin >> value; insert(test, pos, value); print(test); return 0; } ```

#### Check Yourself

1. True or false: the easiest place to insert an element is at the end of a vector.
2. The steps for adding an element to the middle of a vector are:
1. Insert a "slot" at the ________ of the vector
2. Move all the elements after the insertion slot down by one
3. Assign the ________ value to element at the insertion slot
3. To move the elements we use a ________ statement.

### 9.2.5: Parallel Vectors

• Suppose we want to process a series of product data like name, price, quantity, etc.
• Here is some sample data:
Name Price
Milk 3.95
Cheese 3.95
• We want to be able to display the data and process the items in various ways
• One possibility is to create multiple vectors as shown in the diagram below
• These vectors are called parallel vectors because they must be processed together
• Each slice (name, price, etc.) contains data that must be processed together and kept in order together

#### A Slice in Parallel Vectors

Name Vector
` `
` `
` `
` `
`Bread`
` `
` `
` `
` `
` `
Price Vector
` `
` `
` `
` `
`2.99`
` `
` `
` `
` `
` `

`[0]`
`[1]`
`[2]`
`[3]`
`[4]` Slice
`[5]`
`[6]`
`[7]`
`[8]`
`[9]`

#### Problems with Parallel Vectors

• Parallel vectors become a headache in larger programs:
• Each vector must be the same length
• Each slice is filled with values that belong together
• Any function that operates on a slice must get several vectors as parameters
• We can make our problems easier by using a single vector instead of parallel vectors
• To use a single vector, look at the slice and find the concept it represents
• Then make the concept into a class
• Finally, eliminate the parallel vectors and replace them with a single vector of objects
• The following program shows such a vector of objects
• Notice the use of the second technique for constructing objects we mentioned in lesson 8.2.6

#### Example Program with a Vector of Objects

 ```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 ``` ```#include #include using namespace std; class Product { public: Product(); Product(string newName, double newPrice); void print() const; private: string name; double price; }; Product::Product() { name = "Unknown"; price = 0.0; } Product::Product(string newName, double newPrice) { name = newName; price = newPrice; } void Product::print() const { cout << name << " @ " << price << endl; } int main() { const int SIZE = 3; vector list(SIZE); list[0] = Product("Milk", 3.95); list[1] = Product("Bread", 2.99); list[2] = Product("Cheese", 3.95); cout << "Products in my store:\n"; for (unsigned i = 0; i < list.size(); i++) { Product temp = list[i]; temp.print(); } return 0; } ```

#### Check Yourself

1. True or false: parallel vectors are when several vectors store data about one item.
2. Data at the same index across parallel vectors is known as a ________.
3. The problem with using parallel vectors is ________.
1. vectors must all the same length
2. we must keep all the elements of a slice at the same index
3. any function needing the item must have a parameter for every part of the slice
4. all of these
4. To avoid parallel vectors use a ________ to store all the data about an item.

### 9.2.6: Processing a Vector of Objects

• Let us look at how to add elements to a vector of objects
• First, we construct a temporary object like:
`Product temp;`
• Next, we read data into the temporary object
• A convenient technique is to use a `read()` function like:
`temp.read();`
• Finally, we add the temporary object to the vector like:
`list.push_back(temp);`
• If we need to enter multiple values, we use a loop like we did for our "exciting game" simulation in lesson 4.3.3
• The following example shows how to add products to a vector of objects

#### Example of Adding Elements to a Vector of Objects

 ```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 57 58 59 60 61 62 63 ``` ```#include #include using namespace std; class Product { public: Product(); Product(string newName, double newPrice); void read(); void print() const; private: string name; double price; }; Product::Product() { name = "Unknown"; price = 0.0; } Product::Product(string newName, double newPrice) { name = newName; price = newPrice; } void Product::read() { cout << "Enter the name of the product: "; cin >> ws; getline(cin, name); cout << "Enter the price for a " << name << ": "; cin >> price; } void Product::print() const { cout << name << " @ " << price << endl; } void listProducts(vector& store); int main() { cout << "Enter a list of products.\n"; vector list; string repeat = "y"; while(repeat == "y") { Product temp; temp.read(); list.push_back(temp); cout << "Enter another product? (y/n) "; cin >> repeat; } cout << "Products in my store:\n"; listProducts(list); return 0; } void listProducts(vector& list) { for (unsigned num = 0; num < list.size(); num++) { Product temp = list[num]; temp.print(); } } ```

#### Member vs. Non-member Functions

• The above example has two member functions (besides the constructors):
• `void read();`
• `void print() const;`
• In addition, the example has one non-member function:
```void listProducts(vector<Product>& store);
```
• Notice the difference in the way the functions are called in the `main()` function
• To call a member function we need an object of the class, like:
```Product temp;
```
• To call a non-member function, we do NOT need an object of a class:
```listProducts(list);
```
• Also note that member functions typically have fewer parameters than non-member functions
• The reason is that member functions work with the data contained in the object
• In the following exercise we will work with both member and non-member functions

#### Check Yourself

1. Of the following, ________ is NOT one of the steps for adding elements to a vector of objects.
1. Construct a temporary object
2. Read data into the temporary object
3. Add the object to the vector
4. List the elements of the vector
2. True or false: a convenient way to put data into an object is to write a member function to read the data.
3. Of the following functions called from `main()`, ________ is made to a non-member function.
4. list(products);
4. True or false: calling a member function, outside of a class, requires an object. (see lesson 8.2.6)

### Exercise 9.2

In this exercise we explore how to add items to and list items of a vector of objects.

#### Specifications

1. Copy the following program into a text editor, save it as `prodvector.cpp`, and then compile and run the starter program to make sure you copied it correctly.
```#include <iostream>
#include <vector>
using namespace std;

class Product {
public:
Product();
Product(string newName, double newPrice);
void print() const;
private:
string name;
double price;
};

Product::Product() {
name = "Unknown";
price = 0.0;
}

Product::Product(string newName, double newPrice) {
name = newName;
price = newPrice;
}

cout << "Enter the name of the product: ";
cin >> ws;
getline(cin, name);
cout << "Enter the price for a " << name << ": ";
cin >> price;
}

void Product::print() const {
cout <<  name << " @ " << price << endl;
}

// Add a new product to the store

// List the products in the store
void listProducts(vector<Product>& store);

int main() {
const int SIZE = 3;
vector<Product> store(SIZE);
store[0] = Product("Milk", 3.95);
store[2] = Product("Cheese", 3.95);

// Enter new code here

return 0;
}
```

Notice that we are using our `Product` class from lesson 8. Also notice that in `main()` we add three `Product` objects to a vector.

2. After the closing curly brace of the `main()` function, add the following function definition:
```void listProducts(vector<Product>& store) {
cout << "\nListing products:\n";
for (unsigned num = 0; num < store.size(); num++) {
cout << (num + 1) << " ";
store[num].print(); // call print() in Product
}
}
```

Note that this function is calling the `print()` member function of `Product`. For more information see section 9.2.5: Parallel Vectors.

3. In the `main()` function after the comment that says:
```// Enter new code here
```

add a function call to the `listProducts()` function you just defined.

4. Compile and run your modified program to make sure you made the changes correctly. When you run the program, the output should look like:
```Listing products:
1 Milk @ 3.95
3 Cheese @ 3.95
```
5. After the closing curly brace of the `main()` function, add the following function definition:
```void addProduct(vector<Product>& store) {
cout << "\nAdding a new product:\n";
Product prod;
store.push_back(prod);
}
```

Note that this function is calling the `read()` member function of `Product`. For more information see section 9.2.6: Processing a Vector of Objects.

6. In the `main()` function after the function call to `listProducts()`, add a function call to `addProduct()` followed by another call to `listProducts()` like:
```listProducts(store);
listProducts(store);
```
7. Compile and run your modified program to make sure you made the changes correctly. When you run the program, the output should look like:
```1 Milk @ 3.95
3 Cheese @ 3.95

Enter the name of the product: Crackers
Enter the price for a Crackers: 2.49
1 Milk @ 3.95
3 Cheese @ 3.95
4 Crackers @ 2.49
```

As you can see, you should be able to add a new product to the list.

8. Now we want to create a short menu to call our functions. Replace the sequence of three function calls in `main()` with the following code:
```int choice = 1;
while (choice != 0) {
cout << "\n0. Exit program\n"
<< "1. Report inventory\n"
<< "2. Add a new product\n"
<< "Choice (0-2): ";
cin >> choice;
cin.ignore(1000, '\n');
if (choice == 1) {
listProducts(store);
} else if (choice == 2) {
} else if (choice != 0) {
cout << "\nInvalid choice!\n";
}
}
cout << "\nGoodbye!\n";
```
9. Compile and run your modified program to make sure you made the changes correctly. When you run the program, the output should look like:
```0. Exit program
1. Report inventory
Choice (0-2):
```

Also, you should be able to add and list products as often as you like.

10. Save your program source code to submit to Blackboard as part of assignment 9.

#### Check Yourself

1. What are the bounds of a vector? What is a bounds error? (9.2.1)
2. What are the steps for finding a particular value in a vector? (9.2.2)
3. If the order of items in a vector matters, what are the steps for removing an element from the middle of a vector? (9.2.3)
4. What is the easiest location to use for inserting values into a vector? (9.2.4)
5. What are the steps for inserting a value into the middle of a vector? (9.2.4)
6. What are parallel vectors? (9.2.5)
7. Why are parallel vectors indications of poor programming? (9.2.5)
8. How can parallel vectors be avoided? (9.2.5)
9. How can you read data into an object before inserting it into a vector? (9.2.6)

### 9.2.7: Summary

• In this section we discussed how to use some common list-processing algorithms
• Trying to access a slot that does not exist in the vector is one such error
• However, the standard C++ implementation of vector does not generate an error message when using `[]`
• When we make such an error, C++ silently reads or overwrites another memory location
• In a large program we would get strange errors and the occasional spectacular crash
• To avoid this problem, you can use the `at()` member function instead:
```vector<int> values(3);
...
for (int i = 0; i < 5; i++) {
cout << values.at(i) << endl; // crashes
}
```
• One of the algorithms we discussed was linear search
• We use linear search to find a specific element of a vector
• Linear search is easy to implement using a simple loop:
```int find(const vector<int>& v, int item) {
for (unsigned i = 0; i < v.size(); i++) {
if (item == v[i]) {
return i;
}
}
return -1;
}
```
• We discussed how to remove an item from a list as well
• If order does not matter then we can:
1. Overwrite the element to be removed with the last element of the vector
2. Shrink the size of the vector
• However, if order matters then we must:
1. Move all elements down by one slot
2. Shrink the size of the vector
• Again, we can implement this operation using a loop:
```void erase(vector<int>& v, int pos) {
for (unsigned i = pos; i < v.size() - 1; i++) {
v[i] = v[i+1];
}
v.pop_back();
}
```
• In addition to removing items from a list, we often need to insert items
• We can either add items to the end of a list or in the middle
• If we add items to the end, we can just call the `push_back()` function of the vector:
`v.push_back(item);`
• However, if we want to insert an item in the middle of a list we must:
1. Add a new element at the end of the vector
2. Move all elements above the insertion location up by one slot
• For example:
```void insert(vector<int>& v, int pos, int value) {
int last = v.size() - 1;
v.push_back(v[last]);
for (int i = last; i > pos; i--) {
v[i] = v[i - 1];
}
v[pos] = value;
}
```
• Sometimes we need to keep track of multiple attributes about a list of items
• The naive way to code this is to use parallel vectors
• Parallel vectors become a headache in larger programs:
• Each vector must be the same length
• Each slice is filled with values that belong together
• Any function that operates on a slice must get several vectors as parameters
• To remove parallel vectors, look at the slice and find the concept it represents
• Then make the concept into a class
• Finally, eliminate the parallel vectors and replace them with a single vector of objects
• We looked at an example of a vector of `Product` objects

## 9.3: Arrays

### Learner Outcomes

At the end of the lesson the student will be able to:

• Declare and allocate memory for arrays
• Generate code to initialize arrays
• Access array elements
• Use arrays with functions

### 9.3.1: Introduction to Arrays

• Another way to organize lists of the same type is to use arrays
• Arrays are similar to vectors is many ways, but have some significant differences
• Arrays are a lower-level abstraction than vectors, so they are less convenient
• For example, arrays cannot be resized
• Instead, you usually create some extra space in each array and check to make sure you do not run out of room
• Vectors are a recent addition to C++, so many older programs use arrays instead
• Also, arrays are slightly faster and potentially more efficient than vectors
• Thus, you need to know about arrays so you can work with them as needed

#### Check Yourself

1. Besides vectors, we can use ________ to store lists of data.
2. True or false: arrays cannot be resized.
3. True or false: we use arrays because they are more convenient than vectors.

### 9.3.2: Declaring and Initializing Arrays

• Declaring an array is slightly different from declaring a vector:
```dataType variableName[size];
```
• Where:
• dataType: the data type of all the array items
• variableName: the name you make up for the array
• size: the number of data items the array can hold
• For example, the following is the declaration of an array named `scores` that holds 10 values of type `int`:
`int scores[10]`
• Arrays can never change size and the array size must be set when the program is compiled
• When defining an array, you must guess the maximum number of elements you need to store:
```const int MAX_SCORES = 100;
int scores[MAX_SCORES];
```
• The programmer must keep track of the capacity
• We use a constant to hold the capacity of the array as shown above
• This allows us to know the size anywhere in our code
• If we need to change the size, we change only a single constant and recompile

#### Initializing Array Items

• Like vectors, we specify which slot to use with the `[]` operator:
`scores[4] = 98;`
• The indexes of arrays are numbered starting at 0, just like vectors
• We can assign a value to an array element any time after it is declared:
```const int MAX_SCORES = 5;
int scores[MAX_SCORES];
scores[0] = 90;
scores[1] = 95;
scores[2] = 87;
scores[3] = 89;
scores[4] = 98;
```
• Unlike vectors, we can initialize array elements in the declaration statement:
• Called static initialization
• We use a comma-separated list inside curly-braces
• For example:
```int scores[] = { 90, 95, 87, 89, 98 };
```
• This produces the same array as in the previous example
• The compiler computes the size automatically by counting the items in the list
• If we want a larger array with only the first few elements initialized, we can use:
```int scores[MAX_SCORES] = {90, 95, 87};
```
• Note that if we do not assign a value to an array element, its value is not known
• Unlike a vector, C++ does not assign default values

#### Example Program Using Arrays

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ``` ```#include #include using namespace std; int main() { const int MAX_SCORES = 10; int scores[MAX_SCORES]; cout << "Enter " << MAX_SCORES << " scores:\n"; for (int i = 0; i < MAX_SCORES; i++) { cin >> scores[i]; } cout << "You entered:\n"; for (int i = 0; i < MAX_SCORES; i++) { cout << scores[i] << endl; } return 0; } ```

#### Initializing Vectors From Arrays

• Static initialization is handy for short lists of items
• However, vectors do not support static initialization
• To get the benefits of static initialization with vectors, we can use an array to initialize a vector
• The following code snippet shows how:
```const int SIZE = 5;
int values[SIZE] = { 90, 95, 87, 89, 98 };
vector<int> scores(values, &values[SIZE]);

// Display the vector contents
for (unsigned i = 0; i < scores.size(); i++) {
cout << scores[i] << " ";
}
cout << endl;
```

#### Check Yourself

1. Enter the code to declare an array, named `myArray`, and allocate space for 10 values of type `double`.

2. Like a vector, the first element in any array has an index value of ________.
1. -1
2. 0
3. 1
4. 2
3. Of the following, ________ will correctly access the fifth element of an array named "foo".
1. `foo[5]`
2. `foo(5)`
3. `foo[4]`
4. `array.foo[4]`
4. Enter the code to declare an array, named `myArray`, allocate space for 5 doubles and assign the values 1.2, 2.3 and 3.4 to the first 3 elements.

5. True or false: the programmer must keep track of the size of an array, which should be stored in a constant.

### 9.3.3: Arrays as Function Parameters

• When writing a function with an array parameter, we place an empty `[]` after the parameter name:
```void print(int values[], int size);
```
• We pass the size of the array to the function so the function knows the size of the array
• There is no `size()` member function for an array
• When we call the function, we do NOT include the `[]`:
```print(data, size); // function call
```
• Unlike other parameters, array parameters are always passed by reference
• However, we use `[]` rather than an `&` when declaring the array parameter
• For example:
```void read(int data[], int capacity, int& size) {
size = 0;
int value;
while (size < capacity && (cin >> value)) {
data[size] = value;
size++;
}
}
```
• Note the use of both the `capacity` and `size` parameters
• The `capacity` parameter tells the function the maximum array size
• The `size` parameter records how many items the user entered into the array
• The programmer must keep track of both the capacity and size when working with arrays
• Note that arrays cannot be function return types
• Since arrays are always passed by reference, then returning an array with a return statement is not necessary

#### Using the `const` Modifier

• Normally, a function can change the values of array elements
• We can prevent the modification using the `const` modifier:
```void print(const int values[], int size);
```
• The compiler will issue an error message if you try to change the value of an array element
• If a function with a constant array parameter calls another function using the `const` array parameter as an argument, the called function must use a `const` array parameter as well
• Otherwise, the compiler will issue an error
• The following program shows arrays used with functions

#### Example Program Using Arrays with Functions

 ```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 ``` ```#include using namespace std; /** Fills an array with values from the keyboard. @param data The array to fill with data. @param capacity The capacity of the array. @param size The number of items entered. */ void read(int data[], int capacity, int& size) { size = 0; int value; while (size < capacity && (cin >> value)) { data[size] = value; size++; } } /** Displays an array to the screen @param data The array to fill with data. @param size The number of items in the array. */ void print(const int values[], int size) { for (int i = 0; i < size; i++) { cout << values[i] << endl; } } int main() { const int MAX_ITEMS = 10; int data[MAX_ITEMS]; int size = 0; cout << "Enter numbers (Ctrl-Z/D to quit):\n"; read(data, MAX_ITEMS, size); cout << "You entered:\n"; print(data, size); return 0; } ```

#### Check Yourself

1. The problem with the following function is ________.
```double[] readItems(double data[], int cap, int& size) {
size = 0;
double value;
bool more = true;
while (more) {
if (size < capacity) {
cin >> value;
data[size] = value;
size++;
} else {
more = false;
}
return data;
}
```
1. the `data` parameter is missing the size inside the square brackets
2. you cannot assign a value to the parameter `size`
3. array parameters require an ampersand (&)
4. arrays cannot be return types
2. True or false: array parameters do not include the array size inside the square brackets.
3. To prevent a function from modifying an array, add the ________ keyword to the parameter declaration.

### 9.3.4: Character Arrays

• There was a time when C++ had no `string` class
• Instead, we used a variation of a `char` array often called a C-string
• We processed strings by manipulating these C-string `char` arrays
• Recall that the `char` type denotes a single character and is delimited by single quotes:
```char input = 'y'; // do NOT confuse with "y"
```
• C-strings are declared like char arrays but have a special assignment syntax:
```char s[10] = "Hi Mom!";
cout << s << endl;
```
• Each `char` is stored in the array with a special null character `'\0'` ending the string
• The null character is a control character like `'\n'`
• We cannot actually see the control character in a `cout` statement
• When we declare a C-string like the one above, it is stored one character per array element as shown in the following diagram

• We do not need to specify the size of the array variable for a character array constant
• If we do not specify a size, the compiler will count the characters and create an array of the correct size:
`char s[] = "Hi Mom!";`
• Note that the size of the array computed by the compiler is 7 for this example

#### Use for C-Strings

• Many string functions in the standard library depend on `'\0'` terminators in character arrays
• For example, the following function returns the size of a C-string:
```int strlen(const char s[]) {
int i = 0;
while (s[i] != '\0') {
i++;
}
return i;
}
```
• This function will not work without the null `'\0'` terminator in the `char` array
• Generally we should use the `string` class and avoid using `char` arrays
• The `string` class is safer and far more convenient
• Sometimes we need to convert a `string` into a C-string to call a function written before the string class was invented
• We can easily convert a `string` to a C-string using the `c_str()` member function
• For example, we may want to convert a `string` to a number using `atof()`, which needs a C-string argument:
```string input = "9.99";
double num = atof(input.c_str());
cout << num << endl;
```

#### Check Yourself

1. The size of the following C-string is ________.
```char msg[] = "Hello";
```
2. True or false: all C-strings require a '`\0`' character at the end, and an assignment statement adds one automatically.
3. True or false: some useful C functions require a C-string parameter and will not work with type `string`.
4. To convert a `string` to a C-string, use the `string` member function ________.

### Exercise 9.3

In this exercise we explore declaring, allocating and assigning values to arrays containing lists of data.

#### Specifications

1. Copy the following program into a text editor, save it as `myarrays.cpp`, and then compile and run the starter program to make sure you copied it correctly.
```#include <iostream>
using namespace std;

void print(const int values[], int size);

int main() {
// A list of integer scores

// A list of doubles holding temperatures

// A list of chars holding vowels

return 0;
}

void print(const int values[], int size) {
for (int i = 0; i < size; i++) {
cout << values[i] << " ";
}
cout << endl;
}
```
2. Declare and initialize an array for a list of 10 integer scores after the comment:
```// A list of integer scores
```
and using the following code:
```const int NUM_SCORES = 10;
int scores[NUM_SCORES] = {90, 91, 92, 93, 94,
95, 96, 97, 98, 99};
```

3. After declaring and initializing the array, call the `print()` function using the code:
```cout << "Integer scores:\n";
print(scores, NUM_SCORES);
```

4. Compile and run the program to make sure you made the changes correctly. When you run the program, the output should look like:
```Integer scores:
90 91 92 93 94 95 96 97 98 99
```
5. Declare and initialize an array of `double` values holding the temperatures `25.7`, `30.3` and `40.9` in order.

6. Write a `print()` function with two parameters: one for the array and one for the size of the array.

7. After declaring and initializing the array, call the `print()` function.

8. Compile and run the program to make sure you made the changes correctly. When you run the program, the output should look like:
```Integer scores:
90 91 92 93 94 95 96 97 98 99
Double temperatures:
25.7 30.3 40.9
```
9. Declare and allocate an array of `char` values as a C-string and assign the C-string the vowels a, e, i, o and u.

10. After declaring and initializing the array, display the C-string using `cout`.

11. Compile and run the program to make sure you made the changes correctly. When you run the program, the output should look like:
```Integer scores:
90 91 92 93 94 95 96 97 98 99
Double temperatures:
25.7 30.3 40.9
C-string vowels:
aeiou
```
12. Save your program source code to submit to Blackboard as part of assignment 9.

#### Check Yourself

1. What is the syntax for declaring an array? (9.3.1)
2. Why must the programmer track both the capacity and number of elements used in an array? (9.3.1)
3. What are two ways to declare and initialize an array? (9.3.2)
4. What is the syntax of an array parameter? (9.3.3)
5. True or false? An array parameter is always pass by reference. (9.3.3)
6. What is a C-string? (9.3.4)
7. What is the ending character for a C-string? (9.3.4)
8. How large should you make a C-string? Why? (9.3.4)
9. What function can you use to convert a `string` to a C-string? (9.3.4)
10. What function can you use to convert a C-string to a `double`? (9.3.4)

### 9.3.5: Summary

• In this section we looked at how to use arrays
• Arrays are a lower-level abstraction than vectors, so they are less convenient
• Vectors are a recent addition to C++, so many older programs use arrays instead
• Declaring an array is similar to declaring a vector:
`int scores[10]`
• Arrays can never change size and the array size must be set when the program is compiled
• When defining an array, we must guess on the maximum number of elements we need to store
• Then we must keep track of both the capacity and number of elements in use in an array
• When writing a function with an array parameter, we place an empty `[]` after the parameter name:
```void print(int values[], int size);
```
• We need to pass the size of the array into the function, because the function has no other way of knowing the size of the array
• Sometimes we must pass both the capacity and size of an array to a function:
```void read(int data[], int capacity, int& size);
```
• The `capacity` parameter tells the function the maximum array size
• The `size` parameter records how many items the user entered into the array
• Unlike all other parameters, array parameters are always passed by reference
• However, we never use an & when defining an array parameter
• Also note that functions cannot return arrays
• There was a time when C++ had no `string` class
• Instead, we used a variation of a `char` array often called a C-string
• Generally we should use the `string` class and avoid using `char` arrays
• The `string` class is safer and far more convenient
• Sometimes we need to convert a `string` into a C-string to call a function written before the string class was invented
• We can easily convert a `string` to a C-string using the `c_str()` member function:
```string input = "9.99";
double num = atof(input.c_str());
cout << num << endl;
```

## Wrap Up

Due Next:
A8-Getting Classy (4/19/12)
A9-Keeping Lists (4/26/12)