1.5 How to Use Arrays and Vectors

Following are the first eight elements from six numerical sequences:

Fibonacci:  1, 1, 2, 3, 5, 8, 13, 21 


Lucas:      1, 3, 4, 7, 11, 18, 29, 47 


Pell:       1, 2, 5, 12, 29, 70, 169, 408 


Triangular: 1, 3, 6, 10, 15, 21, 28, 36 


Square:     1, 4, 9, 16, 25, 36, 49, 64 


Pentagonal: 1, 5, 12, 22, 35, 51, 70, 92 

Our program must display a pair of elements from a sequence and allow the user to guess the next element. If the user guesses right and wishes to continue, the program then displays a second pair of elements, then a third, and so on. How might we do that?

If succeeding element pairs are taken from the same sequence, the user, recognizing one pair, recognizes them all. That is not very interesting. So we'll pick an element pair from a different numeric sequence with each iteration of the main program loop.

For now, we'll display a maximum of six element pairs per session: one pair from each of the six sequences. We'd like to implement this so that we can loop through the display of the element pairs without having to know which sequence we are displaying with each loop iteration. Each iteration must have access to three values: the element pair and the element that follows them in the sequence.

The solution we discuss in this section uses a container type that can hold a contiguous sequence of integer values that we can reference not by name but by position within the container. We store 18 values in the container as a collection of six tuples: The first two represent the element pair to display; the third represents the next sequence element. With each iteration of the loop, we add 3 to the index value, in this way stepping through the six tuples in turn.

In C++, we can define a container as either a built-in array or an object of the stan-dard library vector class. In general, I recommend the use of the vector class over that of the built-in array. However, a great deal of existing code uses the built-in array, and it is important to understand how to use both representations.

To define a built-in array, we must specify the type of element the array is to hold, give the array a name, and specify a dimension ?that is, the number of elements the array can hold. The dimension must be a constant expression ?that is, an expression that does not require run-time evaluation. For example, the following code declares pell_seq to be an array of 18 integer elements.

const int seq_size = 18; 


int pell_seq[ seq_size ]; 

To define a vector class object, we must first include the vector header file. The vector class is a template, so we indicate the type of its element in brackets following the name of the class. The dimension is placed in parentheses; it does not need to be a constant expression. The following code defines pell_seq as a vector class object holding 18 elements of type int. By default, each element is initialized to 0.

#include <vector> 


vector<int> pell_seq( seq_size ); 

We access an element of either an array or a vector by specifying its position within the container. This element indexing uses the subscript operator ([]). One potential "gotcha" is that the first element begins at position 0 and not 1. The last element is indexed at 1 less than the size of the container. For pell_seq, the correct indexes are 0 through 17, not 1 through 18. (Getting this wrong is common enough that it has its own name: the infamous off-by-one error.) For example, to assign the first two elements of the Pell sequence, we write

pell_seq[ 0 ] = 1; // assign 1 to first element 


pell_seq[ 1 ] = 2; // assign 2 to second element 

Let's calculate the next ten elements of the Pell sequence. To iterate over the elements of a vector or an array, we typically use a for loop, the other primary C++ loop statement. For example,

for ( int ix = 2; ix < seq_size; ++ix ) 


      pell_seq[ ix ] = pell_seq[ ix-2 ] + 2*pell_seq[ ix-1 ]; 

The for loop consists of the following elements:

for ( init-statement; condition; expression ) 


      statement 

The init-statement is executed once before the loop is executed. In our example, ix is initialized to 2 before the loop begins executing.

condition serves as the loop control. It is evaluated before each iteration of the loop. For as many iterations as condition evaluates as true, statement is executed. statement can be either a single statement or a statement block. If the first evaluation of condition evaluates to false, statement is never executed. In our example, condition tests whether ix is less than seq_size.

expression is evaluated after each iteration of the loop. It is typically used to modify the objects initialized within init-statement and tested in condition. If the first evaluation of condition evaluates to false, expression is never executed. In our example, ix is incremented following each iteration of the loop.

To print the elements, we iterate over the entire collection:

cout << "The first " << seq_size 


     << " elements of the Pell Series:\n\t"; 





for ( int ix = 0; ix < seq_size; ++ix ) 


      cout << pell_seq[ ix ] << ' '; 





cout << '\n'; 

If we choose, we can leave out the init-statement, expression, or, less frequently, the condition portion of the for loop. For example, we could rewrite the preceding for loop as

int ix = 0; 


// ... 





for ( ; ix < seq_size; ++ix ) 


      // ... 

The semicolon is necessary to indicate the empty init-statement.

Our container holds the second, third, and fourth elements of each of our six sequences. How can we fill the container with the appropriate values? A built-in array can specify an initialization list, providing a comma-separated list of values for all or a subset of its elements:

int elem_seq[ seq_size ] = { 


   1, 2, 3,  // Fibonacci 


   3, 4, 7,  // Lucas 


   2, 5, 12, // Pell 


   3, 6, 10, //Triangular 


   4, 9, 16, // Square 


   5, 12, 22 // Pentagonal 


}; 

The number of values provided for the initialization list must not exceed the array dimension. If we provide fewer initial values than the dimension, the remaining elements are initialized to 0. If we wish, we can let the compiler calculate the array size based on the number of initial values we provide:

// compiler computes a size of 18 elements 


int elem_seq[] = { 


    1, 2, 3,  3, 4, 7,  2, 5,  12, 


    3, 6, 10, 4, 9, 16, 5, 12, 22 


}; 

The vector class does not support an explicit initialization list. A somewhat tedious solution is to assign each element explicitly:

vector<int> elem_seq( seq_size ); 


elem_seq[ 0 ] =1; 


elem_seq[ 1 ] =2; 


// ... 


elem_seq[ 17 ] =22; 

One alternative is to initialize a built-in array and use that to initialize the vector:

int elem_vals[ seq_size ] = { 


    1, 2, 3,  3, 4, 7,  2, 5,  12, 


    3, 6, 10, 4, 9, 16, 5, 12, 22 }; 





// initialize elem_seq with values of elem_vals 


vector<int> elem_seq( elem_vals, elem_vals+seq_size ); 

elem_seq is passed two values. These values are actually addresses. They mark the range of elements with which to initialize the vector. In this case, we have marked the 18 elements contained within elem_vals to be copied into elem_seq. In Chapter 3, we look at the actual details of how this works.

For now, let's see how we can use elem_seq. One difference between the built-in array and a vector class is that a vector knows its size. Our earlier for loop iterating across the built-in array looks slightly different when applied to the vector:

// elem_seq.size() returns the number of elements 


//      contained within the vector elem_seq 


cout << "The first " << elem_seq.size() 


     << " elements of the Pell Series:\n\t"; 





for ( int ix = 0; ix < elem_seq.size(); ++ix ) 


      cout << pell_seq[ ix ] << ' '; 

cur_tuple represents our index into the current sequence to display. We initialize it to 0. With each loop iteration we add 3 to cur_tuple, setting it to index the first element of the next sequence to display.

int cur_tuple = 0; 





while ( next_seq == true && 


        cur_tuple < seq_size ) 


{ 


        cout << "The first two elements of the sequence are: " 


             << elem_seq[ cur_tuple ] << ", " 


              << elem_seq[ cur_tuple+1 ] 


              << "\nWhat is the next element? "; 


        // ... 


        if ( usr_guess == elem_seq[ cur_tuple+2 ] ) 


             // correct! 





        // ... 





        if ( usr_rsp == 'N' || usr_rsp == 'n' ) 


             next_seq = false; 


        else cur_tuple += 3; 


} 

It would also be useful to keep track of which sequence is currently active. Let's store the name of each sequence as a string:

const int max_seq = 6; 


string seq_names[ max_seq ] = { 


   "Fibonacci", 


   "Lucas", 


   "Pell", 


   "Triangular", 


   "Square", 


   "Pentagonal" 


}; 

We can use seq_names as follows:

if ( usr_guess == elem_seq[ cur_tuple+2 ] ) 


{ 


     ++num_cor; 


     cout << "Very good. Yes, " 


          << elem_seq[ cur_tuple+2 ] 


          << " is the next element in the " 


          << seq_names[ cur_tuple/3 ] << "sequence.\n"; 


} 

The expression cur_tuple/3 yields, in turn, 0, 1, 2, 3, 4, and 5, providing the index into the array of string elements that identify the active sequence.