9: Arrays and Vectors

Advanced Search Quick Index Instructor's Page Home Blackboard CodeLab Announcements Day Schedule Eve Schedule Course Info Room Policies Help FAQ's How To's Links Español Chinese Japanese Hide Navigation
Edward Parrish © 2003-2006

9: Arrays and Vectors
What We Will Cover

Announcements

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/23/09)
A9-Keeping Lists (4/30/09)

Continuations

Homework Questions?

A8-Getting Classy (4/23/09)

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 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 of the data types, in this case an int
^ 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, the assignment to the slot with index 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;
}
^ 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

^ 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;
}
^ 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.
Submit your program source code 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;
}
^ 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;
}
^ 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 down 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;
}
^ 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 above the insertion location up by one slot

Assign the value at the insertion location
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;
}
^ top

9.2.5: Parallel Vectors

Suppose you 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

You 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

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

The following program shows such a vector of objects

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;
}
^ top

9.2.6: Processing a Vector of Objects

When we have a vector of objects, we can read data from a keyboard into the vector

To accomplish this, we create a temporary object

Then we assign value to the temporary object

Once the object is ready we add it to the 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
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& store);
Note the difference in the way the functions are called
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
^ 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.
Submit your program source code 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 faster and more efficient than vectors

Thus, you need to know about arrays so you can work with them as needed

^ 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 must specify which slot to use with the [] operator:
scores[4] = 98;
The slots of arrays are numbered starting at 0, just like vectors

Also, the index can be any integer value >= 0
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;
^ 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 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

There is no size() member function
When we call the function, we do NOT include the []:
print(data, size); // function call
Unlike all other parameters, array parameters are always passed by reference

However, we use [] rather than an & when defining 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

To "return" an array, the caller of the function must provide an array parameter to hold the result
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 error messages if you accidentally change 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;
}
^ 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 view the character

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 actually specify the size of the array variable for a character array constant
If we so 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;
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
Submit your program source code 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

Reminders

Due Next: A8-Getting Classy (4/23/09)
A9-Keeping Lists (4/30/09)

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 | Announcements | Day Schedule | Eve Schedule
Course info | Help | FAQ's | HowTo's | Links Last Updated: May 01 2009 @11:48:52

What We Will Cover

Continuations

Homework Questions?

Questions from last class?

9.1: Introduction to Vectors

Learner Outcomes

9.1.1: Using Lists for Data

Storing Lists of Data

9.1.2: Defining Vectors

9.1.3: Accessing Vector Items

Using Slots

Using Vectors to Collect Data Items

Example Program Collecting and Displaying Data Items

9.1.4: Changing the Vector Size

Adjusting the Size

Collecting and Displaying a Variable Number of Data Items

More Information

9.1.5: Vector Parameters and Return Values

Computing Test Statistics

Exercise 9.1

Specifications

Listing of namelist.cpp

Check Yourself

9.1.6: Summary

More Information

9.2: Working with Vectors

Learner Outcomes

9.2.1: Bounds Errors

Example Program with Vector Bounds Errors

9.2.2: Finding Values

Finding a Value in a Vector

9.2.3: Removing Elements

Removing Elements of a Vector

9.2.4: Inserting Elements

Inserting Elements into a Vector

9.2.5: Parallel Vectors

A Slice in Parallel Vectors

Problems with Parallel Vectors

Example Program with a Vector of Objects

9.2.6: Processing a Vector of Objects

Member vs. Non-member Functions

Exercise 9.2

Specifications

Partial Listing of prodvector.cpp

Check Yourself

9.2.7: Summary

9.3: Arrays

Learner Outcomes

9.3.1: Introduction to Arrays

9.3.2: Declaring and Initializing Arrays

Initializing Array Items

Example Program Using Arrays

Initializing Vectors From Arrays

9.3.3: Arrays as Function Parameters

Using the const Modifier

Example Program Using Arrays with Functions

9.3.4: Character Arrays

Use for C-Strings

More Information On C-string Functions

Exercise 9.3

Specifications

Check Yourself

9.3.5: Summary

Wrap Up

Reminders

Listing of `namelist.cpp`

Partial Listing of `prodvector.cpp`

Using the `const` Modifier