9: Arrays and Vectors

What We Will Cover Reminders: Please silence all cell phones and pagers Sit at a computer station, start your computer and login When class is over, please shut down your computer. Remember that you lose any files not saved in the student folder. Continuations 9.1: Introduction to Vectors 9.1.1: Using Lists for Data 9.1.2: Defining Vectors 9.1.3: Accessing Vector Items 9.1.4: Changing the Vector Size 9.1.5: Vector Parameters and Return Values Exercise 9.1 9.1.6: Summary 9.2: Working with Vectors 9.2.1: Bounds Errors 9.2.2: Finding Values 9.2.3: Removing Elements 9.2.4: Inserting Elements 9.2.5: Parallel Vectors 9.2.6: Processing a Vector of Objects Exercise 9.2 9.2.7: Summary 9.3: Arrays 9.3.1: Introduction to Arrays 9.3.2: Declaring and Initializing Arrays 9.3.3: Arrays as Function Parameters 9.3.4: Character Arrays Exercise 9.3 9.3.5: Summary Wrap Up Due Next: A8-Getting Classy (4/19/12) A9-Keeping Lists (4/26/12) Continuations Homework Questions? A8-Getting Classy (4/19/12) Questions from last class? ^ top 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 ^ top 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 ^ top 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 A vector is a ________ of data values organized using a ________ name. The name for each data value in a vector is ________ or item. True or false: each vector slot can store any number of values. The number of "slots" created by the following statement is ________. vector<int> scores(42); ^ top 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 <iostream> #include <vector> using namespace std; int main() { vector<int> 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 The number inside of the square brackets of a vector is called an ________ or subscript. Of the following, ________ will correctly access the fifth element of a vector named "foo". foo[5] foo(5) foo[4] foo.vector[4] The first element in any vector has an index value of ________. -1 0 1 2 If you declare s vector with 100 elements, the index number of the last element is ________. ^ top 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 Adjusting the Size 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 <iostream> #include <vector> using namespace std; int main() { vector<int> 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; } More Information C++ Vectors: from cppreference.com vector: from cplusplus.com Check Yourself True or false: you can change the number of "slots" in a vector. The find out the number of "slots" in a vector use the function ________. The function to add an element to the end of a vector is ________. The remove an element from the end of a vector use the function ________. ^ top 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 <iostream> #include <vector> 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<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; } int main() { vector<int> 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<double> 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 True or false: you can pass a vector argument to a function, either by value or by reference. To prevent a function from changing the value of a parameter use the keyword ________ before the parameter type. True or false: you can return a vector from a function using a return statement. ^ top Exercise 9.1 In this exercise we explore the use of vectors to collect data items. Specifications 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; } Add a statement to define a vector named names that is suitable for holding a list of names. For more information see section 9.1.2: Defining Vectors. 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"); For more information see section 9.1.4: Changing the Vector Size. 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 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 For more information see section 9.1.3: Accessing Vector Items. 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. Define a function named showNames() with a string vector parameter using the following code: void showNames(vector<string>& names) { // add function statments here } For more information see section 9.1.5: Vector Parameters and Return Values. 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. After the other statements in main(), but before the return 0 statement, call the showNames() function. For more information see section 9.1.5: Vector Parameters and Return Values. 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. Save your program source code to submit to Blackboard as part of assignment 9. Listing of namelist.cpp Check Yourself As time permits, be prepared to answer these questions. You can find more information by following the links after the question. Why would you want to use a vector? (9.1.1) How do you define a vector? (9.1.2) If you declare a vector with 100 elements, what is the number of the maximum element? (9.1.3) What is a vector index? (9.1.3) For a vector named foo, what code do you write to determine its current size? (9.1.4) For a vector named foo, what code do you write to add an element to the end of the vector? (9.1.4) For a vector named foo, what code do you write to remove an element from the end of the vector? (9.1.4) Give an example of a useful function that: Has a vector of integers as a value parameter Has a vector of integers as a reference parameter Has a vector of integers as a return value Describe each function; do not implement them. (9.1.5) ^ top 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 More Information C++ Vectors: from cppreference.com vector: from cplusplus.com ^ top 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 ^ top 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<iostream> #include <vector> using namespace std; const int SIZE = 3; const int NUM_VALUES = 5; int main(void) { vector<int> 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 True or false: C++ always throws an error when a vector exceed its bounds. To reliably check when a vector exceed its bounds call the function ________. What is wrong with the following code? vector<int> scores; scores[0] = 90; Nothing. Cannot declare vectors without a size argument because the vector would be useless. The first slot of a vector must contain the number 0. Assigning a value outside the bounds of the vector. ^ top 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 <iostream> #include <vector> 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<int>& 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<int> 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<int> 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 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. The above technique for searching a vector is known as sequential or ________ search. True or false: when searching a vector you must always start at index 0 and proceed to the end. ^ top 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: Overwrite the element to be removed with the last element of the vector 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: Move all elements up by one slot 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 <iostream> #include <vector> 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<int>& 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<int> v) { for (unsigned i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; } int main() { const int SIZE = 20; vector<int> 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 True or false: to remove an element, overwrite the element with another and shrink the size of the vector. If order does not matter then overwrite the element to remove with the ________ element of the vector. If we want to preserve the order of elements, we use a ________ statement to move elements. ^ top 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: Add a new empty element (slot) at the end of the vector Move all elements after the insertion location up by one slot 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 <iostream> #include <vector> 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<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; } /** Prints all the elements in a vector to the console. @param v the vector to print */ void print(vector<int> v) { for (unsigned i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; } int main() { const int SIZE = 20; vector<int> 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 True or false: the easiest place to insert an element is at the end of a vector. The steps for adding an element to the middle of a vector are: Insert a "slot" at the ________ of the vector Move all the elements after the insertion slot down by one Assign the ________ value to element at the insertion slot To move the elements we use a ________ statement. ^ top 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 Bread 2.99 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 <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; } void Product::print() const { cout << name << " @ " << price << endl; } int main() { const int SIZE = 3; vector<Product> 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 True or false: parallel vectors are when several vectors store data about one item. Data at the same index across parallel vectors is known as a ________. The problem with using parallel vectors is ________. vectors must all the same length we must keep all the elements of a slice at the same index any function needing the item must have a parameter for every part of the slice all of these To avoid parallel vectors use a ________ to store all the data about an item. ^ top 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 <iostream> #include <vector> 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<Product>& store); int main() { cout << "Enter a list of products.\n"; vector<Product> 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<Product>& 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; temp.read(); 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 Of the following, ________ is NOT one of the steps for adding elements to a vector of objects. Construct a temporary object Read data into the temporary object Add the object to the vector List the elements of the vector True or false: a convenient way to put data into an object is to write a member function to read the data. Of the following functions called from main(), ________ is made to a non-member function. Product bread; bread.read(); bread.print(); list(products); True or false: calling a member function, outside of a class, requires an object. (see lesson 8.2.6) ^ top Exercise 9.2 In this exercise we explore how to add items to and list items of a vector of objects. Specifications 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 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; } // Add a new product to the store void addProduct(vector<Product>& 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[1] = Product("Bread", 2.99); 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. 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. In the main() function after the comment that says: // Enter new code here add a function call to the listProducts() function you just defined. 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 2 Bread @ 2.99 3 Cheese @ 3.95 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; prod.read(); 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. 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); addProduct(store); listProducts(store); 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 2 Bread @ 2.99 3 Cheese @ 3.95 Adding a new product: Enter the name of the product: Crackers Enter the price for a Crackers: 2.49 1 Milk @ 3.95 2 Bread @ 2.99 3 Cheese @ 3.95 4 Crackers @ 2.49 As you can see, you should be able to add a new product to the list. 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) { addProduct(store); } else if (choice != 0) { cout << "\nInvalid choice!\n"; } } cout << "\nGoodbye!\n"; 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 2. Add a new product Choice (0-2): Also, you should be able to add and list products as often as you like. Save your program source code to submit to Blackboard as part of assignment 9. Partial Listing of prodvector.cpp Check Yourself As time permits, be prepared to answer these questions. You can find more information by following the links after the question. What are the bounds of a vector? What is a bounds error? (9.2.1) What are the steps for finding a particular value in a vector? (9.2.2) 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) What is the easiest location to use for inserting values into a vector? (9.2.4) What are the steps for inserting a value into the middle of a vector? (9.2.4) What are parallel vectors? (9.2.5) Why are parallel vectors indications of poor programming? (9.2.5) How can parallel vectors be avoided? (9.2.5) How can you read data into an object before inserting it into a vector? (9.2.6) ^ top 9.2.7: Summary In this section we discussed how to use some common list-processing algorithms In addition, we discussed some common errors made with vectors 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: Overwrite the element to be removed with the last element of the vector Shrink the size of the vector However, if order matters then we must: Move all elements down by one slot 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: Add a new element at the end of the vector 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 ^ top 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 ^ top 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 Besides vectors, we can use ________ to store lists of data. True or false: arrays cannot be resized. True or false: we use arrays because they are more convenient than vectors. ^ top 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 <iostream> #include <vector> 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 Enter the code to declare an array, named myArray, and allocate space for 10 values of type double. answer Like a vector, the first element in any array has an index value of ________. -1 0 1 2 Of the following, ________ will correctly access the fifth element of an array named "foo". foo[5] foo(5) foo[4] array.foo[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. answer True or false: the programmer must keep track of the size of an array, which should be stored in a constant. ^ top 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<iostream> 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 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; } the data parameter is missing the size inside the square brackets you cannot assign a value to the parameter size array parameters require an ampersand (&) arrays cannot be return types True or false: array parameters do not include the array size inside the square brackets. To prevent a function from modifying an array, add the ________ keyword to the parameter declaration. ^ top 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 The size of the following C-string is ________. char msg[] = "Hello"; True or false: all C-strings require a '\0' character at the end, and an assignment statement adds one automatically. True or false: some useful C functions require a C-string parameter and will not work with type string. To convert a string to a C-string, use the string member function ________. More Information On C-string Functions Standard C String and Character: from cppreference.com cstdlib: from cplusplus.com cstring: from cplusplus.com cctype: from cplusplus.com ^ top Exercise 9.3 In this exercise we explore declaring, allocating and assigning values to arrays containing lists of data. Specifications 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; } 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}; For more information see section 9.3.2: Declaring and Initializing Arrays. After declaring and initializing the array, call the print() function using the code: cout << "Integer scores:\n"; print(scores, NUM_SCORES); For more information see section 9.3.3: Arrays as Function Parameters. 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 Declare and initialize an array of double values holding the temperatures 25.7, 30.3 and 40.9 in order. For more information see section 9.3.2: Declaring and Initializing Arrays. Write a print() function with two parameters: one for the array and one for the size of the array. For more information see section 9.3.3: Arrays as Function Parameters. After declaring and initializing the array, call the print() function. For more information see section 9.3.3: Arrays as Function Parameters. 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 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. For more information see section 9.3.4: Character Arrays. After declaring and initializing the array, display the C-string using cout. For more information see section 9.3.4: Character Arrays. 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 Save your program source code to submit to Blackboard as part of assignment 9. Check Yourself As time permits, be prepared to answer these questions. You can find more information by following the links after the question. What is the syntax for declaring an array? (9.3.1) Why must the programmer track both the capacity and number of elements used in an array? (9.3.1) What are two ways to declare and initialize an array? (9.3.2) What is the syntax of an array parameter? (9.3.3) True or false? An array parameter is always pass by reference. (9.3.3) What is a C-string? (9.3.4) What is the ending character for a C-string? (9.3.4) How large should you make a C-string? Why? (9.3.4) What function can you use to convert a string to a C-string? (9.3.4) What function can you use to convert a C-string to a double? (9.3.4) ^ top 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; ^ top Wrap Up Due Next: A8-Getting Classy (4/19/12) A9-Keeping Lists (4/26/12) When class is over, please shut down your computer You may complete unfinished exercises at the end of the class or at any time before the next class. ^ top Home | Blackboard | Day Schedule | Eve Schedule Syllabus | Help | FAQ's | HowTo's | Links Last Updated: April 23 2012 @01:04:45