Chapter 6. arrays, vectors, C++20 Ranges and Functional-Style Programming

6.1 Introduction

This chapter introduces data structures—collections of related data items. The C++ standard library refers to data structures as containers. We discuss two containers consisting of data items of the same type:

• fixed-size arrays and

• resizable vectors that can grow and shrink dynamically at execution time.

To use them, you must include the <array> and <vector> headers, respectively.

After discussing how arrays are declared, created and initialized, we demonstrate various array manipulations. We show how to search arrays to find particular items and sort arrays to put their data in ascending or descending order. We show that attempting to access data that is not within an array’s or vector’s bounds causes an exception—a runtime indication that a problem occurred. Then we use exception handling to resolve (or handle) that exception. Chapter 15 covers exceptions in more depth.

PERF Like many modern languages, C++ offers "functional-style" programming features. These can help you write more concise code that’s less likely to contain errors and easier to read, debug and modify. Functional-style programs also can be easier to parallelize to get better performance on today’s multi-core processors. We introduce functional-style programming with C++20’s new <ranges> library. Finally, we continue our objects natural presentation with a case study that creates and manipulates objects of the C++ standard library’s class template vector. After reading this chapter, you’ll be familiar with two array-like collections—arrays and vectors.

6.2 arrays

An array’s elements (data items) are arranged contiguously in memory. The following diagram shows an integer array called c that contains five elements:

One way to refer to an array element is to specify the array name followed by the element’s position number in square brackets ([]). The position number is more formally called an index or subscript. The first element has the index 0 (zero). Thus, the elements of array c are c[0] (pronounced "c sub zero") through c[4]. The value of c[0] is -45, c[2] is 0 and c[4] is 1543.

The highest index (in this case, 4) is always one less than the array’s number of elements (in this case, 5). Each array knows its own size, which you can get via its size member function, as in

c.size()

An index must be an integer or integer expression. An indexed array name is an lvalue—it can be used on the left side of an assignment, just as non-array variable names can. For example, the following statement replaces c[4]’s value:

c[4] = 87;

The brackets that enclose an index are an operator with the same precedence as a function call’s parentheses. See Appendix A for the complete operator precedence chart.

6.3 Declaring arrays

arrays occupy space in memory. To specify an array’s element type and number of elements, use a declaration of the form

array<type, arraySize> arrayName;

The notation <type, arraySize> indicates that array is a class template. Like function templates, the compiler can use class templates to create many class template specializations for various types—such as an array of ints, an array of doubles or an array of Employees. You’ll begin creating custom types in Chapter 10. The compiler reserves the appropriate amount of memory, based on the type and arraySize. To tell the compiler to reserve five elements for integer array c, use the declaration:

Click here to view code image

array<int, 5> c; // c is an array of 5 int values

6.4 Initializing array Elements in a Loop

The program in Fig. 6.1 declares five-element integer array n (line 9). Line 5 includes the <array> header, which contains the definition of class template array.

 1  // fig06_01.cpp
 2  // Initializing an array's elements to zeros and printing the array.
 3  #include "fmt/format.h" // C++20: This will be #include <format>
 4  #include <iostream>
 5  #include <array>
 6  using namespace std;
 7
 8  int main() {
 9     array<int, 5> n; // n is an array of 5 int values
10
11     // initialize elements of array n to 0
12     for (size_t i{0}; i < n.size(); ++i) {        
13        n[i] = 0; // set element at location i to 0
14     }                                             
15
16     cout << fmt::format("{}{:>10}
", "Element", "Value");
17
18     // output each array element's value
19     for (size_t i{0}; i < n.size(); ++i) {        
20     cout << fmt::format("{:>7}{:>10}
", i, n[i]);
21     }                                             
22
23     cout << "
Element" << setw(10) << "Value" << endl;
24
25     // access elements via the at member function
26     for (size_t i{0}; i < n.size(); ++i) {
27        cout << fmt::format("{:>7}{:>10}
", i, n.at(i));
28     }
29
30     // accessing an element outside the array's bounds with at
31     cout << n.at(10) << endl;
32  }

Element Value
      0     0
      1     0
      2     0
      3     0
      4     0
Element Value
      0     0
      1     0
      2     0
      3     0
      4     0
terminate called after throwing an instance of 'std::out_of_range'
  what(): array::at: __n (which is 10) >= _Nm (which is 5)
Aborted

Assigning Values to array Elements in a Loop

Security Lines 12—14 use a for statement to assign 0 to each array element. Like other non-static local variables, array elements are not implicitly initialized to zero (static arrays are). In a loop that processes array elements, ensure that the loop-termination condition prevents accessing elements outside the array’s bounds. In Section 6.6, we present the range-based for statement, which provides a safer way to process every element of an array.

Type size_t

Lines 12, 19 and 26 declare each loop’s control variable as type size_t. The C++ standard specifies that size_t is an unsigned integral type. Use this type for any variable that represents an array’s size or subscripts. Type size_t is defined in the std namespace and is in header <cstddef>, which typically is included for you by other standard library headers that use size_t. If you compile a program that uses type size_t and receive errors indicating that it’s not defined, simply add #include <cstddef> to your program.

Displaying the array Elements

20 The first output statement¹ (line 16) displays the column headings for the columns printed in the subsequent for statement (lines 19-21). These output statements use C++20 textformatting features introduced in Section 4.15 to output the array in tabular format.

1. At the time of this writing, C++20’s <format> header is not implemented by the three compilers we use, so several of this chapter’s examples use the {fmt} library. Once the <format> header is available, you can replace "fmt/format.h" with <format> and remove the fmt:: before each format call.

Avoiding a Security Vulnerability: Bounds Checking for array Subscripts

When you use the [] operator to access an array element (as in lines 12-14 and 19-21), Security C++ provides no automatic array bounds checking to prevent you from referring to an element that does not exist. Thus, an executing program can “walk off” either end of an array without warning. Class template array’s at member function performs bounds checking. Lines 26-28 demonstrate accessing elements’ values via the at member function. You also can assign to array elements by using at on the left side of an assignment, as in:

n.at(0) = 10;

Line 31 demonstrates accessing an element outside the array’s bounds. When member function at encounters an out-of-bounds subscript, it generates a runtime error known as an exception. In this program, which we compiled with GNU g++ and ran on Linux, line 31 resulted in the runtime error message:

Click here to view code image

terminate called after throwing an instance of 'std::out_of_range'
  what(): array::at: __n (which is 10) >= _Nm (which is 5)
Aborted

then the program terminated. This error message indicates that the at member function (array::at) checks whether a variable named __n (which is 10) is greater than or equal to a variable named _Nm (which is 5). In this case, the subscript is out of bounds. In GNU’s implementation of array’s at member function, __n represents the element’s subscript, and _Nm represents the array’s size. Section 6.15 introduces how to use exception handling to deal with such runtime errors. Chapter 15 covers exception handing in depth.

Security Allowing programs to read from or write to array elements outside the bounds of arrays are common security flaws. Reading from out-of-bounds array elements can cause a program to crash or even appear to execute correctly while using bad data. Writing to an out-of-bounds element (known as a buffer overflow²) can corrupt a program’s data in memory and crash a program. In some cases, attackers can exploit buffer overflows by overwriting the program’s executable code with malicious code.

2. For more information on buffer overflows, see http://en.wikipedia.org/wiki/Buffer_overflow.

6.5 Initializing an array with an Initializer List

The elements of an array also can be initialized in the array declaration by following the array name with a brace-delimited comma-separated list of initializers. The program in Fig. 6.2 uses an initializer list to initialize an integer array with five values (line 9) then displays the array’s contents.

 1   // fig06_02.cpp
 2   // Initializing an array in a declaration.
 3   #include <iostream>
 4   #include <iomanip>
 5   #include <array>
 6   using namespace std;
 7
 8   int main() {
 9      array<int, 5> n{32, 27, 64, 18, 95}; // list initializer
10
11     // output each array element's value
12     for (size_t i{0}; i < n.size(); ++i) {
13        cout << n.at(i) << " ";
14     }
15
16     cout << endl;
17   }

32 27 64 18 95

Fewer Initializers Than array Elements

If there are fewer initializers than array elements, the remaining array elements are initialized to zero. For example, the following initializes an array’s elements to zero

Click here to view code image

array<int, 5> n{}; // initialize elements of array n to 0

because there are fewer initializers (none in this case) than array elements. This technique can be used only in the array’s declaration, whereas the initialization technique shown in Fig. 6.1 can be used repeatedly to “reinitialize” an array’s elements at execution time.

More Initializers Than array Elements

The number of initializers in an array’s initializer list must be less than or equal to the array size. The array declaration

Click here to view code image

array<int, 5> n{32, 27, 64, 18, 95, 14};

causes a compilation error, because there are six initializers and only five array elements.

6.6 C++11 Range-Based for and C++20 Range-Based for with Initializer

11 It’s common to process all the elements of an array. The C++11 range-based for statement allows you to do this without using a counter, avoiding the possibility of “stepping outside” the array’s bounds.

Figure 6.3 uses the range-based for to display an array’s contents (lines 12-14 and 23-25) and to multiply each of the array’s element values by 2 (lines 17-19). In general, when processing all elements of an array, use the range-based for statement, because it ensures that your code does not access elements outside the array’s bounds. At the end of this section, we’ll compare the counter-controlled for and range-based for statements.

 1    // fig06_03.cpp
 2    // Using range-based for.
 3    #include <iostream>
 4    #include <array>
 5    using namespace std;
 6
 7    int main() {
 8       array<int, 5> items{1, 2, 3, 4, 5}; // list initializer
 9
10       // display items before modification
11       cout << "items before modification: ";
12       for (const int item : items) {
13          cout << item << " ";
14       }
15       
16       // multiply the elements of items by 2
17       for (int& itemRef : items) { // itemRef is a reference to an int
18          itemRef *= 2;
19       }
20
21       // display items after modification
22       cout << "
items after modification: ";
23       for (const int item : items) {
24          cout << item << " ";
25       }
26
27       // total elements of items using range-based for with initialization
28       cout << "

calculating a running total of items' values: ";
29       for (int runningTotal{0}; const int item : items) {
30          runningTotal += item;
31          cout << "
item: " << item << "; running total: " << runningTotal;
32       }
33
34       cout << endl;
35    }

items before modification: 1 2 3 4 5
items after modification: 2 4 6 8 10
calculating a running total of items' values:
item: 2; running total: 2
item: 4; running total: 6
item: 6; running total: 12
item: 8; running total: 20
item: 10; running total: 30

Using the Range-Based for to Display an array’s Contents

The range-based for statement simplifies the code for iterating through an array. Line 12 can be read as “for each iteration, assign the next element of items to int variable item, then execute the loop’s body” or simply as “for each item in items." In each iteration, item represents one element value (but not an index) in items. In the range-based for’s header, you declare a range variable to the left of the colon (:) and specify an array’s name to the right.³

3. You can use the range-based for statement with most of the C++ standard library’s containers, which we discuss in Chapter 17.

Using the Range-Based for to Modify an array’s Contents

Lines 17-19 use a range-based for statement to multiply each element of items by 2. In line 17, the range variable’s declaration indicates that itemRef is an int&—that is, a reference to an int. Recall that a reference is an alias for another variable in memory—in this case, one of the array’s elements. Any change you make to itemRef changes the value of the corresponding array element.

C++20: Range-Based for with Initializer

20 If you have a variable needed only in the scope of a range-based for loop, C++20 adds the range-based for with initializer statement. Like the if and switch statements with initializers, variables defined in the initializer of a range-based for exist only for the duration of the loop. The initializer in line 29 initializes the variable runningTotal to 0, then lines 29-32 calculate the running total of items’ elements.

Avoiding Subscripts

The range-based for statement can be used in place of the counter-controlled for statement whenever code looping through an array does not require accessing the element’s subscript. For example, totaling the integers in an array requires access only to the element values. Their positions in the array are irrelevant.

External vs. Internal Iteration

In this program, lines 12-14 are equivalent to the following counter-controlled iteration:

Click here to view code image

for (int counter{0}; counter < items.size(); ++counter) {
   cout << items[counter] << " ";
}

This style of iteration is known as external iteration and is error-prone. As implemented, this loop requires a control variable (counter) that the code mutates (modifies) during each loop iteration. Every time you write code that modifies a variable, it’s possible to introduce an error into your code. There are several opportunities for error in the preceding code. For example, you could:

• initialize the for loop’s control variable counter incorrectly

• use the wrong loop-continuation condition or

• increment control variable counter incorrectly.

The last two problems might result in accessing elements outside the array items’ bounds.

The range-based for statement, on the other hand, uses functional-style internal iteration, which hides the counter-controlled iteration details. You specify what array the range-based for should process. It knows how to get each value from the array and how to stop iterating when there are no more values.

6.7 Setting array Elements with Calculations; Introducing constexpr

Figure 6.4 sets the elements of a 5-element array named values to the even integers 2, 4, 6, 8 and 10 (lines 13-15) and prints the array (lines 18-20). These numbers are generated (line 14) by multiplying each successive value of the loop counter, i, by 2 and adding 2.

 1   // fig06_04.cpp
 2   // Set array s to the even integers from 2 to 10.
 3   #include <iostream>
 4   #include <array>
 5   using namespace std;
 6
 7   int main() {
 8     // constant can be used to specify array size
 9     constexpr size_t arraySize{5}; // must initialize in declaration
10      
11     array<int, arraySize> values{}; // array values has 5 elements
12
13     for (size_t i{0}; i < values.size(); ++i) { // set the values
14        values.at(i) = 2 + 2 * i;
15     }
16
17     // output contents of array s in tabular format
18     for (const int value : values) {
19     cout << value << " ";
20     }
21
22     cout << endl;
23   }

2 4 6 8 10

Constants

PERF 11 In Chapter 5, we introduced the const qualifier to indicate that a variable’s value does not change after it is initialized. C++11 introduced the constexpr qualifier to declare variables that can be evaluated at compile-time and result in a constant. This allows the compiler to perform additional optimizations and can improve application performance because there’s no runtime overhead.⁴ A constexpr variable is implicitly const.

PERF

4. As you’ll see in later chapters, constexpr also can be applied to functions if they evaluate to a constant value at compile-time. This eliminates the overhead of runtime function calls, thus further improving application performance. In C++20, C++17 and C++14, many functions and member functions throughout the C++ standard library have been declared constexpr.

Line 9 uses constexpr to declare the constant arraySize with the value 5. A variable declared constexpr or const must be initialized when it’s declared; otherwise, a compilation error occurs. Attempting to modify arraySize after it’s initialized, as in

arraySize = 7;

results in a compilation error.⁵

5. In error messages, some compilers refer to a const fundamental-type variable as a “const object.” The C++ standard defines an “object” as any “region of storage.” Like class objects, fundamental-type variables also occupy space in memory, so they’re often referred to as “objects” as well.

Defining the size of an array as a constant instead of a literal value makes programs clearer and easier to update. This technique eliminates magic numbers—numeric literal values that do not provide you with any context that helps you understand their meaning. Using a constant allows you to provide a name for a literal value and can help explain that value’s purpose in the program.

6.8 Totaling array Elements

Often, the elements of an array represent a series of values to be used in a calculation. For example, if the elements of an array represent exam grades, a professor may wish to total the array elements and use that result to calculate the class average for the exam. Processing a collection of values into a single value is known as reduction—one of the key operations in functional-style programming, which we’ll discuss in Section 6.14. Figure 6.5 uses a range-based for statement (lines 13-15) to total the values in the four-element array integers. Section 6.14 shows how to perform this calculation using the C++ standard library’s accumulate function.

 1   // fig06_05.cpp
 2   // Compute the sum of the elements of an array.
 3   #include <iostream>
 4   #include <array>
 5   using namespace std;
 6
 7   int main() {
 8      constexpr size_t arraySize{4};
 9      array<int, arraySize> integers{10, 20, 30, 40};
10      int total{0};
11
12      // sum contents of array a
13      for (const int item : integers) {
14         total += item;
15      }
16      
17      cout << "Total of array elements: " << total << endl;
18   }

Total of array elements: 100

6.9 Using a Primitive Bar Chart to Display array Data Graphically

Many programs present data graphically. For example, numeric values are often displayed as bars in a bar chart, with longer bars representing proportionally larger values. One simple way to display numeric data graphically is with a bar chart that shows each numeric value as a bar of asterisks (*). This is a simple example of visualization using primitive techniques.

A professor might graph the number of exam grades in each of several categories to visualize the grade distribution. Suppose the grades were 87, 68, 94, 100, 83, 78, 85, 91, 76 and 87. There was one grade of 100, two grades in the 90s, four in the 80s, two in the 70s, one in the 60s and none below 60. Our next program (Fig. 6.6) stores this data in an array of 11 elements, each corresponding to a grade range. For example, element 0 contains the number of grades in the range 0-9, element 7 indicates the number of grades in the range 70-79, and element 10 indicates the number of grades of 100. Upcoming examples will calculate grade frequencies based on a set of grades. In this example, we initialize the array n with frequency values.

 1    // fig06_06.cpp
 2    // Printing a student grade distribution as a primitive bar chart.
 3    #include <iostream>
 4    #include <array>
 5    using namespace std;
 6
 7    int main() {
 8       constexpr size_t arraySize{11};
 9       array<int, arraySize> n{0, 0, 0, 0, 0, 0, 1, 2, 4, 2, 1};
10
11       cout << "Grade distribution:" << endl;
12
13       // for each element of array n, output a bar of the chart
14       for (int i{0}; const int item : n) {
15          // output bar labels ("0-9:", ..., "90-99:", "100:")
16          if (0 == i) {
17             cout << " 0-9: ";
18          }
19          else if (10 == i) {
20             cout << " 100: ";
21          }
22          else {
23             cout << i * 10 << "-" << (i * 10) + 9 << ": ";
24          }
25          
26          ++i;
27
28          // print bar of asterisks
29          for (int stars{0}; stars < item; ++stars) {
30             cout << '*';
31          }
32
33          cout << endl; // start a new line of output
34       }
35    }

Grade distribution:
  0-9:
10-19:
20-29:
30-39:
40-49:
50-59:
60-69: *
70-79: **
80-89: ****
90-99: **
  100: *

Figure 6.6 reads the numbers from the array and graphs the information as a bar chart, displaying each grade range followed by a bar of asterisks indicating the number of grades in that range. To label each bar, lines 16-24 output a grade range (e.g., “70-79: ”) based on the current value of i. The nested for statement (lines 29-31) outputs the current bar as the appropriate number of asterisks. Note the loop-continuation condition in line 29 (stars < item). Each time the program reaches the inner for, the loop counts from 0 up to item, thus using a value in array n to determine the number of asterisks to display. In this example, elements 0-5 contain zeros because no students received a grade below 60. Thus, the program displays no asterisks next to the first six grade ranges.

6.10 Using array Elements as Counters

11 Sometimes, programs use counter variables to summarize data, such as a survey’s results. Figure 5.3’s die-rolling simulation used separate counters to track the number of occurrences of each side of a die as the program rolled the die 60,000,000 times. Figure 6.7 reimplements that simulation using an array of counters. This version also uses the C++11 random-number generation capabilities that were introduced in Section 5.10.

 1    // fig06_07.cpp
 2    // Die-rolling program using an array instead of switch.
 3    #include "fmt/format.h" // C++20: This will be #include <format>
 4    #include <iostream>
 5    #include <array>
 6    #include <random>
 7    #include <ctime>
 8    #include "gsl/gsl"
 9    using namespace std;
10
11    int main() {
12       // use the default random-number generation engine to
13       // produce uniformly distributed pseudorandom int values from 1 to 6
14       default_random_engine engine(gsl::narrow_cast<unsigned int>(time(0)));
15       uniform_int_distribution<int> randomInt(1, 6);
16
17       constexpr size_t arraySize{7}; // ignore element zero
18       array<int, arraySize> frequency{}; // initialize to 0s
19
20       // roll die 60,000,000 times; use die value as frequency index
21       for (int roll{1}; roll <= 60'000'000; ++roll) {
22          ++frequency.at(randomInt(engine));
23       }
24
25       cout << fmt::format("{}{:>13}
", "Face", "Frequency");
26
27       // output each array element's value
28       for (size_t face{1}; face < frequency.size(); ++face) {
29          cout << fmt::format("{:>4}{:>13}
", face, frequency.at(face));
30       }
31    }

Face   Frequency
   1     9997901
   2     9999110
   3    10001172
   4    10003619
   5     9997606
   6    10000592

Figure 6.7 uses the array frequency (line 18) to count the occurrences of die values. Line 22 of this program replaces the entire switch statement in lines 19-40 of Fig. 5.3, by using a random value to determine which frequency element to increment for each die roll. The call randomInt(engine) produces a random subscript from 1 to 6, so frequency must be large enough to store six counters. We use a seven-element array in which we ignore element 0—it’s clearer to have the die value 1 increment frequency.at(1) rather than frequency.at(0). So, each face value is used directly as a frequency index. We also replace lines 44-49 of Fig. 5.3 by looping through array frequency to output the results (Fig. 6.7, lines 28-30).

6.11 Using arrays to Summarize Survey Results

Our next example uses arrays to summarize the results of data collected in a survey. Consider the following problem statement:

Twenty students were asked to rate on a scale of 1 to 5 the quality of the food in the student cafeteria, with 1 being “awful” and 5 being “excellent.” Place the 20 responses in an integer array and determine the frequency of each rating.

This is a popular type of array-processing application (Fig. 6.8). We wish to summarize the number of responses of each rating (that is, 1-5). The array responses (lines 14-15) is a 20-element integer array of the students’ responses to the survey. The array responses is declared const, as its values do not (and should not) change. We use a six- element array frequency (line 18) to count the number of occurrences of each response. Each element of the array is used as a counter for one of the survey responses and is initialized to zero. As in Fig. 6.7, we ignore element 0.

 1    // fig06_08.cpp
 2    // Poll analysis program.
 3    #include "fmt/format.h" // C++20: This will be #include <format>
 4    #include <iostream>
 5    #include <array>
 6    using namespace std;
 7
 8    int main() {
 9      // define array sizes
10      constexpr size_t responseSize{20}; // size of array responses
11      constexpr size_t frequencySize{6}; // size of array frequency
12
13      // place survey responses in array responses
14      const array<int, responseSize> responses{
15         1, 2, 5, 4, 3, 5, 2, 1, 3, 1, 4, 3, 3, 3, 2, 3, 3, 2, 2, 5};
16
17      // initialize frequency counters to 0
18      array<int, frequencySize> frequency{};
19
20      // for each answer, select responses element and use that value
21      // as frequency index to determine element to increment
22      for (size_t answer{0}; answer < responses.size(); ++answer) {
23         ++frequency.at(responses.at(answer));
24      }
25
26      cout << fmt::format("{}{:>12}
", "Rating", "Frequency");
27
28      // output each array element's value
29      for (size_t rating{1}; rating < frequency.size(); ++rating) {
30         cout << fmt::format("{:>6}{:>12}
", rating, frequency.at(rating));
31      }
32   }

Rating Frequency
     1         3
     2         5
     3         7
     4         2
     5         3

The first for statement (lines 22-24) takes one response at a time from the array responses and increments one of the counters frequency.at(1) to frequency.at(5). The key statement in the loop is line 23, which increments the appropriate counter, depending on the value of responses.at(answer).

Let’s consider several iterations of the for loop. When control variable answer is 0, the value of responses.at(answer) is the value of responses.at(0) (i.e., 1 in line 15), so the program interprets ++frequency.at(responses(answer)) as

++frequency.at(1)

which increments the value in array element 1. To evaluate the expression in line 23, start with the value in the innermost set of square brackets (answer). Once you know answer’s value (which is the value of the control variable in line 22), plug it into the expression and evaluate the expression in the next outer set of square brackets—that is, responses.at(answer), which is a value selected from the responses array in lines 14–15. Then use the resulting value as the index for the frequency array to specify which counter to increment.

When answer is 1, responses.at(answer) is the value of responses.at(1), which is 2, so the program interprets ++frequency.at(responses(answer)) as

++frequency.at(2)

which increments array element 2.

When answer is 2, responses[answer] is the value of responses.at(2), which is 5, so the program interprets ++frequency.at(responses(answer)) as

++frequency.at(5)

which increments array element 5, and so on. Regardless of the number of responses processed in the survey, the program requires only a six-element array (ignoring element zero) to summarize the results, because all the response values are between 1 and 5 and the index values for a six-element array are 0 through 5.

6.12 Sorting and Searching arrays

In this section, we use the built-in C++ standard library sort function⁶ to arrange the elements in an array into ascending order and the built-in binary_search function to determine whether a value is in the array.

6. The C++ standard indicates that sort uses an O(n log n) algorithm, but does not specify which one.

Sorting data—placing it into ascending or descending order—is one of the most important computing applications. Virtually every organization must sort some data and, in many cases, massive amounts of it. Sorting is an intriguing problem that has attracted some of the most intense research efforts in the field of computer science.

Often it may be necessary to determine whether an array contains a value that matches a certain key value. The process of finding a particular element of an array is called searching.

Demonstrating Functions sort and binary_search

Figure 6.9 begins by creating an unsorted array of strings (lines 11-12) and displaying the contents of the array (lines 16-18). Next, line 20 uses the C++ standard library function sort to sort the elements of the array colors into ascending order. The sort function’s arguments specify the range of elements that should be sorted—in this case, the entire array. The arguments begin(colors), and end(colors) return “iterators” that represent the array’s beginning and end, respectively. Chapter 17 discusses iterators in depth. Functions begin and end are defined in <array>. As you’ll see, function sort can be used to sort the elements of several different types of data structures. Lines 24-26 display the contents of the sorted array.

 1    // fig06_09.cpp
 2    // Sorting and searching arrays.
 3    #include <iostream>
 4    #include <array>
 5    #include <string>
 6    #include <algorithm> // contains sort and binary_search
 7    using namespace std;
 8
 9    int main() {
10       constexpr size_t arraySize{7}; // size of array colors
11       array<string, arraySize> colors{"red", "orange", "yellow",
12          "green", "blue", "indigo", "violet"};
13       
14       // output original array
15       cout << "Unsorted colors array:
";
16       for (string color : colors) {
17          cout << color << " ";
18       }
19       
20       sort(begin(colors), end(colors)); // sort contents of colors
21       
22       // output sorted array
23       cout << "
Sorted colors array:
";
24       for (string item : colors) {
25          cout << item << " ";
26       }
27
28       // search for "indigo" in colors
29       bool found{binary_search(begin(colors), end(colors), "indigo")};
30       cout << "

"indigo" " << (found ? "was" : "was not")
31          << " found in colors array" << endl;
32
33       // search for "cyan" in colors
34       found = binary_search(begin(colors), end(colors), "cyan");
35       cout << ""cyan" " << (found ? "was" : "was not")
36          << " found in colors array" << endl;
37    } 

Unsorted colors array:
red orange yellow green blue indigo violet
Sorted colors array:
blue green indigo orange red violet yellow

"indigo" was found in colors array
"cyan" was not found in colors array

Lines 29 and 34 use binary_search to determine whether a value is in the array. The sequence of values first must be sorted in ascending order—binary_search does not verify this for you. Performing a binary search on an unsorted array is a logic error that could lead to incorrect results. The function’s first two arguments represent the range of elements to search, and the third argument is the search key—the value to find in the array. The function returns a bool indicating whether the value was found. In Chapter 18, we’ll use the C++ Standard function find to obtain the location of a search key in an array.

6.13 Multidimensional arrays

You can use arrays with two dimensions (i.e., indices) to represent tables of values consisting of information arranged in rows and columns. To identify a particular table element, we must specify two indices—by convention, the first identifies the row and the second identifies the column. arrays that require two indices to identify a particular element are called two-dimensional arrays or 2-D arrays. arrays with two or more dimensions are known as multidimensional arrays. The following diagram illustrates a two- dimensional array, a:

The array contains three rows and four columns, so it’s said to be a 3-by-4 array. In general, an array with m rows and n columns is called an m-by-n array.

We have identified every element in the diagram above with an element name of the form a[row][column]. Similarly, you can access each element with at, as in:

a.at(i).at(j)

The elements names in row 0 all have a first index of 0; the elements names in column 3 all have a second index of 3. Referencing a two-dimensional array element as a[x, y] or a.at(x, y) is an error. Actually, a[x, y] and a.at(x, y) are treated as a[y] and a.at(y), respectively, because C++ evaluates the expression x, y (containing a comma operator) simply as y (the last of the comma-separated expressions).

Figure 6.10 demonstrates initializing two-dimensional arrays in declarations. Lines 12-13 each declare an array of arrays with two rows and three columns.

 1    // fig06_10.cpp
 2    // Initializing multidimensional arrays.
 3    #include <iostream>
 4    #include <array>
 5    using namespace std;
 6
 7    constexpr size_t rows{2};
 8    constexpr size_t columns{3};
 9    void printArray(const array<array<int, columns>, rows>& a);
10
11    int main() {
12      const array<array<int, columns>, rows> array1{1, 2, 3, 4, 5, 6};
13      const array<array<int, columns>, rows> array2{1, 2, 3, 4, 5};   
14
15      cout << "Values in array1 by row are:" << endl;
16      printArray(array1);
17
18      cout << "
Values in array2 by row are:" << endl;
19      printArray(array2);
20    }
21
22    // output array with two rows and three columns
23    void printArray(const array<array<int, columns>, rows>& a) {
24       // loop through array's rows
25       for (auto const& row : a) {
26          // loop through columns of current row
27          for (auto const& element : row) {
28             cout << element << ' ';
29          }
30      
31          cout << endl; // start new line of output
32      }
33    }

Values in array1 by row are:
1 2 3
4 5 6

Values in array2 by row are:
1 2 3
4 5 0

Declaring an array of arrays

In the line 12 and line 13 declarations, notice the type:

array<array<int, columns>, rows>

The outer array type indicates that it has rows (2) elements of type

array<int, columns>

So, each of the outer array’s element is an array of ints containing columns (3) elements.

Initializing an array of arrays

Line 12’s array1 declaration has six initializers. The compiler initializes row 0’s elements, followed by row 1’s elements. So, 1, 2 and 3 initialize row 0’s elements, and 4, 5 and 6 initialize row 1’s elements. Line 13’s array2 declaration provides only five initializers. The initializers are assigned to row 0, then row 1. Any elements that do not have an explicit initializer are initialized to zero, so array2[1][2] is 0.

Displaying an array of arrays

The program calls function printArray to output each array’s elements. Notice that the function prototype (line 9) and definition (lines 23-33) specify that the function receives a two-row and three-column array. The parameter receives the array by reference and is declared const because the function does not modify the array’s elements.

Nested Range-Based for Statements

11To process the elements of a two-dimensional array, we use a nested loop in which the outer loop iterates through the rows, and the inner loop iterates through the columns of a given row. Function printArray’s nested loop is implemented with range-based for statements. Lines 25 and 27 introduce the C++11 auto keyword, which tells the compiler to infer (determine) a variable’s data type based on the variable’s initializer value. The outer loop’s range variable row is initialized with an element from the parameter a. Looking at the array’s declaration, you can see that it contains elements of type

array<int, columns>

so the compiler infers that row refers to a three-element array of int values (again, columns is 3). The const& in row’s declaration indicates that the reference cannot be used to modify the rows and prevents each row from being copied into the range variable. The inner loop’s range variable element is initialized with one element of the array represented by row, so the compiler infers that element refers to an int because each row contains three int values. In many IDEs, hovering the mouse cursor over a variable declared with auto displays the variable’s inferred type. Line 28 displays the value from a given row and column.

Nested Counter-Controlled for Statements

We could have implemented the nested loop with counter-controlled iteration as follows:

Click here to view code image

for (size_t row{0}; row < a.size(); ++row) {
   for (size_t column{0}; column < a.at(row).size(); ++column) {
      cout << a.at(row).at(column) << ' '; // a[row][column]
   }
    cout << endl;
}

Initializing an array of arrays with a Fully Braced Initializer List

You may wish to initialize a two-dimensional array using separate initializer sublists for each row. For example, line 12 could be written as:

Click here to view code image

const array<array<int, columns>, rows> array1{
   {{1, 2, 3}, // row 0
    {4, 5, 6}} // row 1
};

If an initializer sublist has fewer elements than the row, the row’s remaining elements would be initialized to 0.

Common Two-Dimensional array Manipulations: Setting a Columns’ Values

The following for statement sets all the elements in row 2 of array a (from the beginning of this section) to zero:

Click here to view code image

for (size_t column{0}; column < 4; ++column) {
   a.at(2).at(column) = 0; // a[2][column]
}

The for statement varies only the second index (i.e., the column index). The preceding for statement is equivalent to the following assignment statements:

Click here to view code image

a.at(2)(0)  = 0;  // a[2][0]
a.at(2)(1)  = 0;  // a[2][1]
a.at(2)(2)  = 0;  // a[2][2]
a.at(2)(3)  = 0;  // a[2][3]

Common Two-Dimensional array Manipulations: Totaling All the Elements with Nested Counter-Controlled for Loops

The following nested counter-controlled for statement totals the elements in the array a (that we defined in Section 6.13’s introduction):

Click here to view code image

total = 0;
for (size_t row{0}; row < a.size(); ++row) {
   for (size_t column{0}; column < a.at(row).size(); ++column) {
      total += a.at(row).at(column); // a[row][column]
   }
}

The for statement totals the array’s elements one row at a time. The outer loop begins by setting the row index to 0, so the elements of row 0 may be totaled by the inner loop. The outer loop then increments row to 1, so the elements of row 1 can be totaled. Then, the outer for statement increments row to 2, so the elements of row 2 can be totaled.

Common Two-Dimensional array Manipulations: Totaling All the Elements with Nested Range-Based for Loops

Nested range-based for statements are the preferred way to implement the preceding loop:

Click here to view code image

total = 0;
for (auto row : a) { // for each row
   for (auto column : row) { // for each column in row
      total += column;
   }
}

6.14 Intro to Functional-Style Programming

PERF Like other popular languages, such as Python, Java and C#, C++ supports several programming paradigms—procedural, object-oriented, generic (template-oriented) and “functional-style.” C++’s “functional-style” features help you write more concise code with fewer errors, and that’s easier to read, debug and modify. Functional-style programs also can be easier to parallelize to get better performance on today’s multi-core processors.

6.14.1 What vs. How

As a program’s tasks get more complicated, the code can become harder to read, debug and modify, and more likely to contain errors. Specifying how the code works can become complex. With functional-style programming, you specify what you want to do, and library code typically handles “the how” for you. This can eliminate many errors.

Consider the following range-based for statement from Fig. 6.5, which totals the elements of the array integers:

Click here to view code image

for (const int item : integers) {
   total += item;
}

Though this procedural code hides the iteration details, we still have to specify how to total the elements by adding each item into the variable total. Each time you modify a variable, you can introduce errors. Functional-style programming emphasizes immutability— it avoids operations that modify variables’ values. If this is your first exposure to functional-style programming, you might be wondering, “How can this be?” Read on.

Functional-Style Reduction with accumulate

Figure 6.11 replaces Fig. 6.5’s range-based for statement with a call to the C++ standard library accumulate algorithm (from header <numeric>). By default, this function knows how to reduce a container’s values to the sum of those values. As we’ve mentioned, reduction is a key functional-style programming concept. The next example shows that you can customize how accumulate performs its reduction.

 1    // fig06_11.cpp
 2    // Compute the sum of the elements of an array.
 3    #include <array>
 4    #include <iostream>
 5    #include <numeric>
 6    using namespace std;
 7
 8    int main() {
 9       constexpr size_t arraySize{4};
10       array<int, arraySize> integers{10, 20, 30, 40};
11       cout << "Total of array elements: " <<
12          accumulate(begin(integers), end(integers), 0) << endl;
13    }

Total of array elements: 100

Like function sort in Section 6.12, function accumulate’s first two arguments specify the range of elements to total—in this case, all the elements from the beginning to the end of integers. The function internally increments the running total of the elements it processes, hiding those calculations. The third argument is that total’s initial value.

Function accumulate uses internal iteration, which also is hidden from you. The function knows how to iterate through a range of elements and add each element to the running total. Stating what you want to do rather than programming how to do it is known as declarative programming—a key aspect of functional programming.

6.14.2 Passing Functions as Arguments to Other Functions— Introducing Lambda Expressions

Many standard library functions allow you to customize how they work by passing other functions as arguments. Functions that receive other functions as arguments are called higher-order functions—a key aspect of functional programming. For example, function accumulate totals elements by default. It also has an overloaded version, which receives as its fourth argument a function that specifies how to perform the reduction. Rather than simply totaling the values, Fig. 6.12 calculates the product of the values.

 1    // fig06_12.cpp
 2    // Compute the product of an array's elements using accumulate.
 3    #include <array>
 4    #include <iostream>
 5    #include <numeric>
 6    using namespace std;
 7
 8    int multiply(int x, int y) {
 9       return x * y;
10    }
11
12    int main() {
13      constexpr size_t arraySize{5};
14      array<int, arraySize> integers{1, 2, 3, 4, 5};
15
16      cout << "Product of integers: "
17         << accumulate(begin(integers), end(integers), 1, multiply) << endl;
18
19      cout << "Product of integers with a lambda: "
20         << accumulate(begin(integers), end(integers), 1,      
21               [](const auto& x, const auto& y){return x * y;}) << endl;
22    }

Product of integers: 120
Product of integers with a lambda: 120

Calling accumulate with a Named Function

Line 17 calls accumulate for the array integers containing the values 1-5. We’re calculating the product of the values, so the third argument (i.e., the initial value of the reduction) is 1, rather than 0; otherwise, the final product would be 0. The fourth argument is the function to call for every array element—in this case, multiply (defined in lines 8–10). To calculate a product, this function must receive two arguments—the product so far and a value from the array—and must return a value, which becomes the new product. As accumulate iterates through the range of elements, it passes the current product and the next element as arguments. For this example, accumulate internally calls multiply five times:

• The first call passes the initial product (1) and the array’s first element (1), producing the product 1.

• The second call passes the current product (1) and the array’s second element (2), producing the product 2.

• The third call passes 2 and the array’s third element (3), producing the product 6.

• The fourth call passes 6 and the array’s fourth element (4), producing the product 24.

• The last call passes 24 and the array’s fifth element (5), producing the final result 120, which accumulate returns to its caller.

Calling accumulate with a Lambda Expression

11 In some cases, you may not need to reuse a function. In such cases, you can define a function where it’s needed by using a C++11 lambda expression (or simply lambda). A lambda expression is an anonymous function—that is, a function without a name. The call to accumulate in lines 20-21 uses the following lambda expression to perform the same task as multiply (line 17):

Click here to view code image

[](const auto& x, const auto& y){return x * y;}

Lambdas begin with the lambda introducer ([]), followed by a comma-separated parameter list and a function body. This lambda receives two parameters, calculates their product and returns the result.

14 You saw in Section 6.13 that auto enables the compiler to infer a variable’s type based on its initial value. Specifying a lambda parameter’s type as auto enables the compiler to infer the parameter’s type, based on the context in which the lambda appears. In this example, accumulate calls the lambda once for each element of the array, passing the current product and the element’s value as the lambda’s arguments. Since the initial product (1) is an int and the array contains ints, the compiler infers the lambda parameters’ types as int. Using auto to infer each parameter’s type is a C++14 feature called generic lambdas. The compiler also infers the lambda’s return type from the expression x * y—both x and y are ints, so this lambda returns an int.

We declared the parameters as const references:

• They are const so the lambda’s body does not modify the caller’s variables.

PERF

• They are references for performance to ensure that the lambda does not copy large objects.

This lambda could be used with any numeric type that supports the multiplication operator. Chapter 18 discusses lambda expressions in detail.

20

6.14.3 Filter, Map and Reduce: Intro to C++20’s Ranges Library

The C++ standard library has enabled functional-style programming for many years. C++20’s new ranges library⁷ (header <ranges>) makes functional-style programming more convenient. In this section, we introduce two key aspects of this library—ranges and views:

7. At the time of this writing, only GNU C++ 10.1 implements the ranges library. We compiled and executed this example using the GNU GCC Docker container version 10.1 from https://hub.docker.com/_/gcc. Refer to the Chapter 1 test-drives for details on compiling and executing programs with this Docker container.

• A range is a collection of elements that you can iterate over, so an array, for example, is a range.

• A view enables you to specify an operation that manipulates a range. Views are composable—you can chain them together to process a range’s elements through multiple operations.

The program of Fig. 6.13 demonstrates several functional-style operations using C++20 ranges. We’ll cover more features of this library in Chapter 18.

 1    // fig06_13.cpp
 2    // Functional-style programming with C++20 ranges and views.
 3    #include <array>
 4    #include <iostream>
 5    #include <numeric>
 6    #include <ranges>
 7    using namespace std;
 8
 9    int main() {
10       // lambda to display results of range operations
11       auto showValues = [](auto& values, const string& message) {
12          cout << message << ": ";
13
14          for (auto value : values) {
15             cout << value << " ";
16          }
17
18          cout << endl;
19    };
20

showValues Lambda for Displaying This Application’s Results

17 Throughout this example, we display various range operations’ results using a range-based for statement. Rather than repeating that code, we could define a function that receives a range and displays its values. For flexibility, we could use a function template, so it will work with ranges of various types. Here, we chose to define a generic lambda and demonstrate that you can store a lambda in a local variable (showValues; lines 11-19). You can 17 use the variable’s name to call the lambda, as we do in lines 22, 27, 32, 38 and 49. C++17 made minor changes to the range-based for statement so that it eventually could be used with C++20 ranges, as we do in lines 14-16.

Generating a Sequential Range of Integers with views::iota

PERF In many of this chapter’s examples, we creted an array, then processed its values. This required pre-allocating the array with the appropriate number of elements. In some cases, you can generate values on demand, rather than creating and storing the values in advance. Operations that generate values on demand use lazy evaluation, which can reduce your program’s memory consumption and improve performance when all the values are not needed at once. Line 21 uses the <range> library’s views::iota to generate a range of integers from its first argument (1) up to, but not including, its second argument (11). The values are not generated until the program iterates over the results, which occurs when we call showValues (line 22) to display the generated values.

Click here to view code image

21    auto values1 = views::iota(1, 11); // generate integers 1-10
22    showValues(values1, "Generate integers 1-10");
23

Generate integers 1-10: 1 2 3 4 5 6 7 8 9 10

Filtering Items with views::filter

A common functional-style programming operation is filtering elements to select only those that match a condition. This often produces fewer elements than the range being filtered. One way to implement filtering would be a loop that iterates over the elements, checks whether each element matches a condition, then do something with that element. That requires external iteration, which can be error-prone (as we discussed in Section 6.6).

With ranges and views, we can use views::filter to focus on what we want to accomplish—get the even integers in the range 1-10. The expression

Click here to view code image

values1 | views::filter([](const auto& x) {return x % 2 == 0;});

in line 26 uses the | operator to connect multiple operations. The first operation (values1 from line 21) generates 1-10, and the second filters those results. Together, these operations form a pipeline. Each pipeline begins with a range, which is the data source (the values 1-10 produced by values1), followed by an arbitrary number of operations, each separated from the next by |.

Click here to view code image

24    // filter each value in values1, keeping only the even integers
25    auto values2 =                                                     
26       values1 | views::filter([](const auto& x) {return x % 2 == 0;});
27    showValues(values2, "Filtering even integers");
28

Filtering even integers: 2 4 6 8 10

The argument to views::filter must be a function that receives one value to process and returns a bool indicating whether to keep the value. In this case, we passed a lambda that returns true if its argument is divisible by 2.

After lines 25-26 execute, values2 represents a pipeline that can generate the integers 1-10 and filter those values, keeping only the even integers. The pipeline concisely represents what we want to do, but not how to implement it—views::iota knows how to generate integers, and views::filter knows how to use its function argument to determine whether to keep each value received from earlier in the pipeline.

When showValues iterates over values2, views::iota produces a value, then views::filter calls its argument to determine whether to keep the value. If so, the range- based for statement receives that value from the pipeline and displays it. Otherwise, the processing steps repeat with the next value generated by views::iota.

Mapping Items with views::transform

Another common functional-style programming operation is mapping elements to new values (possibly of different types). Mapping produces a result with the same number of elements as the original data being mapped. With C++20 ranges, views::transform performs mapping operations. The pipeline in lines 30-31 adds another operation to the pipeline from lines 25-26, mapping the filtered results from values2 to their squares with the lambda expression passed to views::transform in line 31.

Click here to view code image

29    // map each value in values2 to its square
30    auto values3 =                                                   
31       values2 | views::transform([](const auto& x) {return x * x;});
32    showValues(values3, "Mapping even integers to squares");
33

Mapping even integers to squares: 4 16 36 64 100

The argument to views::transform is a function that receives a value to process and returns the mapped value (possibly of a different type). When showValues iterates over the results of the values3 pipeline:

• views::iota produces a value.

• views::filter determines whether the value is even and, if so, passes it to the next pipeline step; otherwise, processing proceeds with the next value generated by views::iota.

• views:transform calculates the square of the even integer (as specified by line 31’s lambda), then the range-based for loop in showValues displays the value and processing proceeds with the next value generated by views::iota.

Combining Filtering and Mapping Operations into a Pipeline

A pipeline may contain an arbitrary number of operations separated by | operators. The pipeline in lines 35-37 combines all of the preceding operations into a single pipeline, and line 38 displays the results.

Click here to view code image

34    // combine filter and transform to get squares of the even integers
35    auto values4 =                                                    
36       values1 | views::filter([](const auto& x) {return x % 2 == 0;})
37               | views::transform([](const auto& x) {return x * x;}); 
38    showValues(values4, "Squares of even integers");
39

Squares of even integers: 4 16 36 64 100

Reducing a Range Pipeline with accumulate

C++ standard library functions like accumulate also work with range pipelines. Line 42 performs a reduction that sums the squares of the even integers produced by the pipeline in lines 35-37.

Click here to view code image

40    // total the squares of the even integers
41    cout << "Sum the squares of the even integers from 2-10: " <<
42       accumulate(begin(values4), end(values4), 0) << endl;
43

Sum the squares of the even integers from 2-10: 220

Filtering and Mapping an Existing Container’s Elements

Various C++ containers, including arrays and vectors (Section 6.15), can be used as the data source in a range pipeline. Line 45 declares an array containing 1-10, then uses it in a pipeline that calculates the squares of the even integers in the array.

Click here to view code image

44     // process a container's elements
45     array<int, 10> numbers{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
46     auto values5 =                                                    
47        numbers | views::filter([](const auto& x) {return x % 2 == 0;})
48                | views::transform([](const auto& x) {return x * x;}); 
49     showValues(values5, "Squares of even integers in array numbers");
50  }

Squares of even integers in array numbers: 4 16 36 64 100

6.15 Objects Natural Case Study: C++ Standard Library Class Template vector

We now continue our objects natural presentation by taking objects of C++ standard library class template vector8 “out for a spin.” A vector is similar to an array, but also supports dynamic resizing. vector is defined in header <vector> (Fig. 6.14, line 5) and belongs to namespace std. At the end of this section, we’ll demonstrate vector’s bounds checking capabilities (which array also has). There, we’ll introduce C++’s exception- handling mechanism, which can be used to detect and handle an out-of-bounds vector index. At that point, we’ll discuss the <stdexcept> header (line 6).

8. Chapter 17 discusses more vector capabilities.

 1    // fig06_14.cpp
 2    // Demonstrating C++ standard library class template vector.
 3    #include <iostream>
 4    #include "fmt/format.h" // C++20: This will be #include <format>
 5    #include <vector>   
 6    #include <stdexcept>
 7    using namespace std;
 8
 9    void outputVector(const vector<int>& items); // display the vector
10    void inputVector(vector<int>& items); // input values into the vector
11

Creating vector Objects

Lines 13-14 create two vector objects that store values of type int—integers1 contains seven elements, and integers2 contains 10 elements. By default, all the elements of each vector object are set to 0. Like arrays, vectors can be defined to store most data types, by replacing int in vector<int> with the appropriate type.

Click here to view code image

12   int main() {
13      vector<int> integers1(7); // 7-element vector<int>
14      vector<int> integers2(10); // 10-element vector<int>
15

Notice that we used parentheses rather than braces to pass the size argument to each vector object’s constructor. When creating a vector, if the braces contain one value of the vector’s element type, the compiler treats the braces as a one-element initializer list, rather than the vector’s size. So the following declaration actually creates a one-element vector<int> containing the int value 7, not a 7-element vector:

vector<int> integers1{7};

vector Member Function size; Function outputVector

Line 17 uses vector member function size to obtain integers1’s size (i.e., the number of elements). Line 19 passes integers1 to function outputVector (lines 95-101), which displays the vector’s elements using a range-based for. Lines 22 and 24 perform the same tasks for integers2.

Click here to view code image

16    // print integers1 size and contents
17    cout << "Size of vector integers1 is " << integers1.size()
18       << "
vector after initialization:";
19    outputVector(integers1);
20
21    // print integers2 size and contents
22    cout << "
Size of vector integers2 is " << integers2.size()
23       << "
vector after initialization:";
24    outputVector(integers2);
25

Size of vector integers1 is 7
vector after initialization: 0 0 0 0 0 0 0

Size of vector integers2 is 10
vector after initialization: 0 0 0 0 0 0 0 0 0 0

Function inputVector

Lines 28-29 pass integers1 and integers2 to function inputVector (lines 104-108) to read values for each vector’s elements from the user.

Click here to view code image

26    // input and print integers1 and integers2
27    cout << "
Enter 17 integers:" << endl;
28    inputVector(integers1);
29    inputVector(integers2);
30
31    cout << "
After input, the vectors contain:
"
32       << "integers1:";
33    outputVector(integers1);
34    cout << "integers2:";
35    outputVector(integers2);
36

Enter 17 integers:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

After input, the vectors contain:
integers1: 1 2 3 4 5 6 7
integers2: 8 9 10 11 12 13 14 15 16 17

Comparing vector Objects for Inequality

In Chapter 5, we introduced function overloading. A similar concept is operator overloading, which allows you to define how a built-in operator works for a custom type. The C++ standard library already defines overloaded operators == and != for arrays and vectors, so you can compare two arrays or two vectors for equality or inequality, respectively. Line 40 compares two vector objects using the != operator. This operator returns true if the contents of two vectors are not equal—that is, they have different lengths or the elements at the same index in both vectors are not equal. Otherwise, != returns false.

Click here to view code image

37    // use inequality (!=) operator with vector objects
38    cout << "
Evaluating: integers1 != integers2" << endl;
39
40    if (integers1 != integers2) {
41       cout << "integers1 and integers2 are not equal" << endl;
42    }
43

Evaluating: integers1 != integers2
integers1 and integers2 are not equal

Initializing One vector with the Contents of Another

A new vector can be initialized with the contents of an existing vector. Line 46 creates a vector object integers3 and initializes it with a copy of integers1. This invokes class template vector’s copy constructor to perform the copy operation. You’ll learn about copy constructors in detail in Chapter 14. Lines 48-50 output the size and contents of integers3 to demonstrate that it was initialized correctly.

Click here to view code image

44    // create vector integers3 using integers1 as an
45    // initializer; print size and contents
46    vector<int> integers3{integers1}; // copy constructor
47
48    cout << "
Size of vector integers3 is " << integers3.size()
49       << "
vector after initialization: ";
50    outputVector(integers3);
51

Size of vector integers3 is 7
vector after initialization: 1 2 3 4 5 6 7

Assigning vectors and Comparing vectors for Equality

Line 54 assigns integers2 to integers1, demonstrating that the assignment (=) operator is overloaded to work with vector objects. Lines 56-59 output the contents of both objects to show that they now contain identical values. Line 64 then compares integers1 to integers2 with the equality (==) operator to determine whether the contents of the two objects are equal after the assignment (which they are).

Click here to view code image

52    // use overloaded assignment (=) operator
53    cout << "
Assigning integers2 to integers1:" << endl;
54    integers1 = integers2; // assign integers2 to integers1
55
56    cout << "integers1: ";
57    outputVector(integers1);
58    cout << "integers2: ";
59    outputVector(integers2);
60
61    // use equality (==) operator with vector objects
62    cout << "
Evaluating: integers1 == integers2" << endl;
63
64    if (integers1 == integers2) {
65       cout << "integers1 and integers2 are equal" << endl;
66    }
67

Assigning integers2 to integers1:
integers1: 8 9 10 11 12 13 14 15 16 17
integers2: 8 9 10 11 12 13 14 15 16 17

Evaluating: integers1 == integers2
integers1 and integers2 are equal

Using the at Member Function to Access and Modify vector Elements

Lines 69 and 73 use vector member function at to obtain an element and use it as an rvalue and as an lvalue, respectively. Recall from Section 4.12 that an rvalue cannot be modified, but an lvalue can. If the index is valid, member function at returns either

• a reference to the element at that location—this is a modifiable lvalue that can be used to change the value of the corresponding vector element, or

• a const reference to the element at that location—this is a nonmodifiable lvalue that cannot be used to change the value of the corresponding vector element.

A nonmodifiable lvalue is treated as a const object. If at is called on a const array or via a reference that’s declared const, the function returns a const reference.

Click here to view code image

68     // use square brackets to use the value at location 5 as an rvalue
69     cout << "
integers1.at(5) is " << integers1.at(5);
70
71     // use square brackets to create lvalue
72     cout << "

Assigning 1000 to integers1.at(5)" << endl;
73     integers1.at(5) = 1000;
74     cout << "integers1: ";
75     outputVector(integers1);
76

integers1.at(5) is 13

Assigning 1000 to integers1.at(5)
integers1: 8 9 10 11 12 1000 14 15 16 17

As is the case with arrays, vectors also have a [] operator. C++ is not required to perform bounds checking when vector elements are accessed with square brackets. Therefore, you must ensure that operations using [] do not accidentally attempt to manipulate elements outside the bounds of the vector.

Exception Handling: Processing an Out-of-Range Index

Line 80 attempts to output the value in integers1.at(15). The index 15 is outside the vector’s bounds. Member function at’s bounds checking recognizes the invalid index and throws an exception, which indicates a runtime problem. The name “exception” suggests that the problem occurs infrequently. Exception handling enables you to create fault-tolerant programs that can process (or handle) exceptions. In many cases, this allows a program to continue executing as if no problems were encountered. For example, Fig. 6.14 still runs to completion, even though we attempt to access an out-of-range index. More severe problems might prevent a program from continuing normal execution, instead requiring the program to notify the user of the problem, then terminate. Here we introduce exception handling briefly. You’ll throw exceptions from your own custom functions in Chapter 11. We’ll discuss exception handling in detail in Chapter 15.

Click here to view code image

77     // attempt to use out-of-range index
78     try {                                                      
79        cout << "
Attempt to display integers1.at(15)" << endl;
80        cout << integers1.at(15) << endl; // ERROR: out of range
81     }                                                          
82     catch (const out_of_range& ex) {                           
83        cerr << "An exception occurred: " << ex.what() << endl; 
84     }                                                          
85

Attempt to display integers1.at(15)
An exception occurred: invalid vector<T> subscript

The try Statement

By default, an exception causes a C++ program to terminate. To handle an exception and possibly enable the program to continue executing, place any code that might throw an exception in a try statement (lines 78-84). The try block (lines 78-81) contains the code that might throw an exception, and the catch block (lines 82-84) contains the code that handles the exception if one occurs. As you’ll see in Chapter 15, you can have many catch blocks to handle different types of exceptions that might be thrown in the corresponding try block. If the code in the try block executes successfully, lines 82-84 are ignored. The braces that delimit try and catch blocks’ bodies are required.

Executing the catch Block

When the program calls vector member function at with the argument 15 (line 80), the function attempts to access the element at location 15, which is outside the vector’s bounds—integers1 has only 10 elements at this point. Because bounds checking is performed at execution time, vector member function at generates an exception—specifically line 80 throws an out_of_range exception (from header <stdexcept>) to notify the program of this problem. At this point, the try block terminates immediately, and the catch block begins executing—if you declared any variables in the try block, they’re now out of scope and are not accessible in the catch block.

PERF The catch block declares a type (out_of_range) and an exception parameter (ex) that it receives as a reference. The catch block can handle exceptions of the specified type. Inside the block, you can use the parameter’s identifier to interact with a caught exception object. Catching an exception by reference increases performance by preventing the exception object from being copied when it’s caught.

what Member Function of the Exception Parameter

When lines 82-84 catch the exception, the program displays a message indicating the problem that occurred. Line 83 calls the exception object’s what member function to get the exception object’s error message and display it. Once the message is displayed in this example, the exception is considered handled, and the program continues with the next statement after the catch block’s closing brace. In this example, lines 87-91 execute next. We use exception handling again in Chapters 11-13, and Chapter 15 presents a deeper look.

Changing the Size of a vector

One key difference between a vector and an array is that a vector can dynamically grow and shrink as the number of elements it needs to accommodate varies. To demonstrate this, line 87 shows the current size of integers3, line 88 calls the vector’s push_back member function to add a new element containing 1000 to the end of the vector, and line 89 shows the new size of integers3. Line 91 then displays integers3’s new contents.

Click here to view code image

86     // changing the size of a vector
87     cout << "
Current integers3 size is: " << integers3.size() << endl;
88     integers3.push_back(1000); // add 1000 to the end of the vector
89     cout << "New integers3 size is: " << integers3.size() << endl;
90     cout << "integers3 now contains: ";
91     outputVector(integers3);
92 }
93

Current integers3 size is: 7
New integers3 size is: 8
integers3 now contains: 1 2 3 4 5 6 7 1000

Functions outputVector and inputVector

Function outputVector uses a range-based for statement to obtain the value in each element of the vector for output. As with class template array, you could also do this using a counter-controlled loop and the [] operator, but the range-based for is recommended. Function inputVector uses a range-based for statement with an int& range variable, so it can be used to store an input value in the corresponding vector element.

Click here to view code image

94    // output vector contents
95    void outputVector(const vector<int>& items) {
96       for (const int item : items) {
97          cout << item << " ";
98       }
99
100       cout << endl;
101   }
102
103   // input vector contents
104   void inputVector(vector<int>& items) {
105      for (int& item : items) {
106         cin >> item;
107      }
108   }

C++11: List Initializing a vector

Many of the array examples in this chapter used list initializers to specify the initial array element values. C++11 also allows this for vectors (and other C++ standard library data structures).

Straight-Line Code

As you worked through this chapter’s examples, you saw lots of for loops. But one thing you may have noticed in the first objects natural sections is that much of the code for creating and using objects is straight-line sequential code. Working with objects often flattens the coding process into lots of sequential member-function calls.

6.16 Wrap-Up

This chapter began our introduction to data structures, exploring the use of C++ standard library class templates array and vector to store data in and retrieve data from lists and tables of values. The chapter examples demonstrated how to declare an array, initialize an array and refer to individual elements of an array. We passed arrays to functions by reference and used the const qualifier to prevent the called function from modifying the array’s elements, thus enforcing the principle of least privilege. You learned how to use C++11’s range-based for statement to manipulate all the elements of an array. We also showed how to use C++ standard library functions sort and binary_search to sort and search an array, respectively. You learned how to declare and manipulate multidimensional arrays of arrays. We used nested counter-controlled and nested range-based for statements to iterate through all the rows and columns of a two-dimensional array. We also showed how to use auto to infer a variable’s type based on its initializer value. We introduced functional-style programming in C++ using C++20’s new ranges. In later chapters, we’ll continue our coverage of data structures. In our first objects natural case study, we demonstrated the capabilities of the C++ standard library class template vector. In that example, we discussed how to access array and vector elements with bounds checking and demonstrated basic exception-handling concepts.

We’ve now introduced the basic concepts of classes, objects, control statements, functions, array objects and vector objects. In Chapter 7, we present one of C++’s most powerful features—the pointer. Pointers keep track of where data and functions are stored in memory, which allows us to manipulate those items in interesting ways. As you’ll see, C++ also provides a language element called an array (different from the class template array) that’s closely related to pointers. In contemporary C++ code, its considered better practice to use C++11’s array class template rather than traditional arrays.