Chapter Goals

To become familiar with using vectors to collect objects
To be able to access vector elements and resize vectors
To learn how to use one- and two-dimensional arrays
To learn about common array algorithms

Using Vectors to Collect Data Items

Vector — a collection of data items of the same type
Each element can be accessed separately
Here we define a vector of salaries vector<double> salaries(10);
Type is vector<double>
(10) indicates that the vector holds ten values
salaries stores a sequence of 10 double values

Figure 1 Figure of Salaries

Using Vectors to Collect Data Items

`[]` operator

To fill slot 4 with the value 35000: salaries[4] = 35000;
Slots numbers begin at zero
Slot 4 is the fifth slot in the vector
Indexed the same as the C-array

Figure 2 Vector Slot Filled with double Value

Using Vectors to Collect Data Items

Index values

Bounds error — an attempt to access a location that is not within the valid index range
Compiler does not catch bounds errors
The most common bounds error is the following: vector<double> salaries(10); cout << salaries[10];
Here, index values range from 0 to 9

Using Vectors to Collect Data Items

Index can be any integer value
To find the highest salary: double highest = salaries[0]; for (i = 1; i < 10; i++) if (salaries[i] > highest) highest = salaries[i];

Syntax : Vector Variable Definition

vector<type_name> variable_name;
vector<type_name> variable_name(initial_size);

Example:

vector<int> scores;
vector<Employee> staff(20);

Purpose:

Define a new variable of vector type, and optionally supply an initial size.

Syntax : Vector Subscript

vector_Expression[integer_expression]

Example:

 salaries[i + 1]

Purpose:

Access an element in a vector.

Working with Vectors

When a vector is defined without a size parameter, it is empty and can hold no elements
size() method gets vector size
A better loop: for (i = 1; i < salaries.size(); i++) if (salaries[i] > highest) highest = salaries[i];
This is common for visiting all elements in a vector
Note: i is a legal index if 0 ≤ i and i < v.size()

Working with Vectors

It is often difficult to know how many elements you need to store
push_back grows the vector as needed, adds new element to end vector<double> salaries; ... double s; cin >> s; ... salaries.push_back(s);
Resizing the vector may be costly
If possible, specify the size when you define the vector

Working with Vectors

pop_back removes the last element of a vector, shrinking its size by one
Does not return the element that is being removed
To capture element: double last = salaries[salaries.size() - 1]; salaries.pop_back();

`salvect.cpp`

Common Error

Bounds Errors

The most common vector error is accessing a nonexistent slot vector<double> data(10); data[10] = 5.4;
data has 10 elements with subscripts 0 to 9
No error message if program accesses a vector through an out-of-bounds subscript
Program will corrupt some memory making it act flaky or cause a horrible death many instructions later

Advanced Topic

Strings Are Vectors of Characters

Data type char denotes individual characters
string greeting = "Hello"; can be considered a vector of five characters 'H', 'e', 'l', 'l', 'o'
You can modify the characters in a string: greeting[3] = 'p'; greeting[4] = '!';
Manipulating the characters directly is more efficient than extracting substrings and concatenating strings

Vector Parameters and Return Values

A vector can be copied (pass-by-value) into a function
To compute the average of a vector of floating-point numbers, consider this function double average(vector<double> values) { if (values.size() == 0) return 0; double sum = 0; for (int i = 0; i < values.size(); i++) sum = sum + values[i]; return sum / values.size(); }

Vector Parameters and Return Values

Modifying a Vector

If a function modifies a vector, it must use a reference parameter
To raise all values in the vector by the given percentage: void raise_by_percent(vector<double>& values, double rate) { for (int i = 0; i < values.size(); i++) values[i] = values[i] * (1 + rate / 100); }
If a vector is passed by value, and a function modifies the vector, the modification affects the local copy of that value only, not the call parameter

Vector Parameters and Return Values

Returning a Vector

Useful if a function computes a result that consists of a collection of values of the same type
This function collects all values that fall in a certain range vector<double> between(vector<double> values, double low, double high) { vector<double> result; for (int i = 0; i < values.size(); i++) if (low <= values[i] && values[i] <= high) result.push_back(values[i]); return result; }

Vector Parameters and Return Values

Returning a Vector of Positions

Instead of returning matching values, you can return just the positions of all matching values in a vector vector<int> between_locations(vector<double> values, double low, double high) { vector<int> pos; for (int i = 0; i < values.size(); i++) { if (low <= values[i] && values[i] <= high) pos.push_back(i); } return pos; }
Now print the matches vector<int> matches = between_locations(salaries, 45000.0, 65000.0); for (int j = 0; j < matches.size(); j++) cout << salaries[matches[j]] << "\n";

Advanced Topic

Passing Vectors by Constant Reference

Passing a vector by value is inefficient, because the function must make a copy of all elements
Instead of: double average(vector<double> values)
You can use a constant reference: double average(const vector<double>& values)

Removing and Inserting Vector Elements

Removing an element — Where order is not important

Overwrite old element with last element
Shrink vector int last_pos = values.size() -1; values[pos] = values[last_pos]; values.pop_back();

Figure 5 Removing an Element in an Unordered Vector

Removing and Inserting Vector Elements

Removing an element — Where order is important

Move all elements following the element to be removed to a lower index
Shrink the size of the vector


for (int i = pos; i < values.size() - 1; i++)
   values[i] = values[i + 1];
values.pop_back();

See erase2.cpp

Figure 6 Removing an Element in an Ordered Vector

Removing and Inserting Vector Elements

Inserting, other than at the end

Create a new element at the end
Move all elements above the insertion location up (to a higher index) by one slot

int last = values.size() - 1;
values.push_back(values[last]);
for (int i = last; i > pos; i--)
   values[i] = values[i - 1];
values[pos] = s;

See insert.cpp

Figure 7 Inserting an Element in an Ordered Vector

Quality Tip

Make Parallel Vectors into Vectors of Objects

If using vectors of the same length, each of which stores a part of what conceptually should be an object, sometimes it is better to use a vector whose elements are objects
Example of parallel vectors storing product data: vector<string> names; vector<double> prices; vector<int> scores;
Issues with parallel vectors:
- Ensuring vectors always have the same length
- Ensuring all corresponding slices actually match
- Any function that operates on a slice must get all vectors as parameters

Quality Tip

Make Parallel Vectors into Vectors of Objects — Part 2

Instead, create a class named Product, which contains the name, price, and score
Use vector<Product> products;

Figure 9 Eliminating Parallel Vectors

Arrays

The built-in homogenous container in C/C++
Like vectors, arrays collect elements of the same type
Lower-level abstraction than the vector
Less convenient
Arrays are faster and more efficient than vectors
Vectors built on top of arrays

Defining and Using Arrays

An array of ten floating-point numbers: double salaries[10];
An array can be initialized when it is defined: double salaries[] = { 31000, 24000, 55000, 82000, 49000, 42000, 35000, 66000, 91000, 60000 };
Above, compiler determines the size by counting the values
Array size has to be known at compile time
Size of a statically-allocated array can not change

Syntax Array Variable Definition

type_name variable_name[size];

Example:

int scores[20];

Purpose:

Define a new variable of an array type.

Defining and Using Arrays

Companion Variable

Use a constant to describe the size: const int SALARIES_CAPACITY = 100; double salaries[SALARIES_CAPACITY];
Often the entire array is not in use; SALARIES_CAPACITY only stores the capacity
You must also remember how many elements in the array are of interest

Defining and Using Arrays

Companion Variable

Use a companion variable salaries_size to store the number of used elements
The following loop stores data in the salaries array int salaries_size = 0; while (more && salaries_size < SALARIES_CAPACITY) { cout << "Enter salary or 0 to quit: "; double x; cin >> x; if (cin.fail()) more = false; else { salaries[salaries_size] = x; salaries_size++; } }
You need to manually update salaries_size

Defining and Using Arrays

Compute highest salary: double highest = 0; if (salaries_size > 0) { highest = salaries[0]; int i; for (i = 1; i < salaries_size; i++) if (salaries[i] > highest) highest = salaries[i]; }

Array Parameters

Use empty [] to define an array parameter: double maximum(double a[], int a_size);
The function has no way of knowing the size of the array
Pass the size of the array in, too
Arrays are always passed by reference
Do not use an & to define an array parameter
Add the const keyword whenever a function does not actually modify an array double maximum(const double a[], int a_size)

Array Parameters

If a function adds elements to an array, pass:
- The array
- The current size as a reference (so function can update it)
- The maximum size
void read_data(double a[], int a_capacity, int& a_size) { a_size = 0; while (a_size < a_capacity) { double x; cin << x; if (cin.fail()) return; a[a_size] = x; a_size++; } }

Array Parameters

Arrays cannot be function return types
The caller must provide an array argument to be filled in by the function void between(double values[], int values_size, double low, double high, double result[], double& result_size)

Array Parameters — `salarray.cpp`

Character Arrays

Arrays that hold chars
How C and C++ store strings (before the STL)
char type denotes an individual character
- Delimited using single quotes
- Actually a 1-byte integer
'y' is different from "y"
An array that holds a string: char greeting[] = "Hello"; // Same as char greeting[6] = "Hello"
Last item is a sentinel, the null-terminator character
String constants ("Hello") are always null-terminated

Figure 10 A Character Array

Character Arrays

A function that reads a character array does not need its size
The null-terminator serves as a sentinel (for ASCII strings)
This is from the standard library: int strlen(const char s[]) { int i = 0; while (s[i] != '\0') i++; return i; }
A function that writes into a character array must know the maximum length
Code append.cpp, on the next slide, prints Hello, Wor

Character Arrays — `append.cpp`

Character Arrays

Some of the library functions (strcat) do not take a length parameter
Will write past the end of an array (it doesn't know the size)
Check the size yourself, or use strncat, strncpy, etc.
The string class in the STL is more convenient
- Minds these details for you
Use c_str() member function of the string class to convert string into a character array
Needed if dealing with a function that was written before the string class

Two-Dimensional Arrays

Use a two-dimensional array (or matrix) to store tabular data
C++ uses an array with two subscripts (literally, an array of arrays) to store a matrix: const int POWERS_ROWS = 11; const int POWERS_COLS = 6; double powers[POWERS_ROWS][POWERS_COLS];
Individual elements are accessed by double subscripts m[i][j] powers[3][4] = future_value(1,000 6.5, 25);
Use separate brackets!
powers[3,4] will compile, but isn't what you want

Figure 11 Accessing an Element in a Two-Dimensional Array

Two-Dimensional Arrays

Filling in Data

As with one-dimensional arrays, size can't be changed
To fill a two-dimensional array, you use two nested loops, like this:for (int i = 0; i < POWERS_ROWS; i++) for (int j = 0; j < POWERS_COLS; j++) powers[i][j] = value for row i, column j;
Still stored as a sequence in memory
Compiler finds table[i][j] by computing the offset: i * POWERS_COLS + j

Figure 12 A Two-Dimensional Array Is Stored as a Sequence of Rows

Two-Dimensional Arrays

Passing to Functions

Specify the number of columns when declaring a matrix parameter void print_table(const double table[][POWERS_COLS], int table_rows) { const int WIDTH = 10; cout << fixed >> setprecision(2); for (int i = 0; i < table_rows; i++) { for (int j = 0; j < POWERS_COLS; j++) cout << setw(WIDTH) << table[i][j]; cout << "\n"; } }
The compiler ignores the first index, if supplied
Function probably needs the number of rows as a separate argument (as with arrays)

Syntax : Two-Dimensional Array Definition

type_name variable_name[size₁][size₂];

Example:

double monthly_sales[NREGIONS][12];

Purpose:

Define a new variable that is a two-dimensional array.

Common Error

Omitting the Column Size of a Two-Dimensional Array Parameter

When passing a one-dimensional array to a function, you specify the size of the array as a separate parameter: double maximum(const double a[], int a_size)
For two-dimensional arrays you cannot simply pass in the number of rows and columns: void print(const double table[][], int table_rows, int table_cols) // NO!
You must specify the number of columns in the array parameter: const int TABLE_COLS = 6; void print(const double table[][TABLE_COLS], int table_rows) // OK

Chapter Goals

//<![CDATA[ section( "1" ) //]]> Using Vectors to Collect Data Items

Using Vectors to Collect Data Items

[] operator

Using Vectors to Collect Data Items

Index values

Using Vectors to Collect Data Items

Syntax //<![CDATA[ taxonomy( "1" ) //]]> : Vector Variable Definition

Example:

Purpose:

Syntax //<![CDATA[ taxonomy( "2" ) //]]> : Vector Subscript

Example:

Purpose:

//<![CDATA[ section( "2" ) //]]> Working with Vectors

Working with Vectors

Working with Vectors

salvect.cpp

Common Error //<![CDATA[ taxonomy( "1" ) //]]>

Bounds Errors

Advanced Topic //<![CDATA[ taxonomy( "1" ) //]]>

Strings Are Vectors of Characters

//<![CDATA[ section( "3" ) //]]> Vector Parameters and Return Values

Vector Parameters and Return Values

Modifying a Vector

Vector Parameters and Return Values

Returning a Vector

Vector Parameters and Return Values

Returning a Vector of Positions

Advanced Topic //<![CDATA[ taxonomy( "2" ) //]]>

Passing Vectors by Constant Reference

//<![CDATA[ section( "4" ) //]]> Removing and Inserting Vector Elements

Removing an element — Where order is not important

Removing and Inserting Vector Elements

Removing an element — Where order is important

Removing and Inserting Vector Elements

Inserting, other than at the end

Quality Tip //<![CDATA[ taxonomy( "2" ) //]]>

Make Parallel Vectors into Vectors of Objects

Quality Tip //<![CDATA[ taxonomy( "2" ) //]]>

Make Parallel Vectors into Vectors of Objects — Part 2

//<![CDATA[ section( "5" ) //]]> Arrays

//<![CDATA[ taxonomy( "5.1" ) //]]> Defining and Using Arrays

Syntax //<![CDATA[ taxonomy( "3" ) //]]> Array Variable Definition

Example:

Purpose:

Defining and Using Arrays

Companion Variable

Defining and Using Arrays

Companion Variable

Defining and Using Arrays

//<![CDATA[ taxonomy( "5.2" ) //]]> Array Parameters

Array Parameters

Array Parameters

Array Parameters — salarray.cpp

//<![CDATA[ taxonomy( "5.3" ) //]]> Character Arrays

Character Arrays

Character Arrays — append.cpp

Character Arrays

//<![CDATA[ taxonomy( "5.4" ) //]]> Two-Dimensional Arrays

Two-Dimensional Arrays

Filling in Data

Two-Dimensional Arrays

Passing to Functions

Syntax //<![CDATA[ taxonomy( "4" ) //]]> : Two-Dimensional Array Definition

Example:

Purpose:

Common Error //<![CDATA[ taxonomy( "2" ) //]]>

Omitting the Column Size of a Two-Dimensional Array Parameter

Using Vectors to Collect Data Items

`[]` operator

Syntax : Vector Variable Definition

Syntax : Vector Subscript

Working with Vectors

`salvect.cpp`

Common Error

Advanced Topic

Vector Parameters and Return Values

Advanced Topic

Removing and Inserting Vector Elements

Quality Tip

Quality Tip

Arrays

Defining and Using Arrays

Syntax Array Variable Definition

Array Parameters

Array Parameters — `salarray.cpp`

Character Arrays

Character Arrays — `append.cpp`

Two-Dimensional Arrays

Syntax : Two-Dimensional Array Definition

Common Error