[Notes] Ch.17 Vectors in C++ (Runestone)

I. Introduction 

Indexing in C++ also uses random access to read and write data, but the indices start a 0 (just like with strings in C++). 

 

 II. Declaring and Initializing Vectors in C++ 

1. Vectors in C++

(1) In C++, a vector is used to store a sequence of elements. 

-> The elements must be homogenous (all of the same type)  

(2) This is conceptually similar to a vector in MATLAB, but the details are different. 

(3) To use vectors, first include the vector library: 

#include <vector>

Using namespace std;

(4) Declare a vector like this: 

Int: in addition to the base type of vector, provide the type of elements it will hold. 

someInts: The name someInts will refer to the vector as a whole. 

(5) A vector can store elements of any type, as long as they match the type with which it is declared. 

2. Initializing a vector 

(1) By default, a vector is empty. 

 (2) Specify one number to allocate an initial number of elements. Their values aren’t initialized, though. 

?

?

?

?

?

(3) You can provide a default initial value for all elements. 

42

42

42

42

(4) You can provide different initial values for the elements.

1

5

7

Ex) Vectors following will create:  

 

13

13

13

13

13

?

?

?

?

 

Four elements created, but no values in the elements. 

 

2

9

1

4

[ ] empty vector. 

?

?

?

?

Four elements created, but no values in the elements. 

[ ] empty vector. 

64.5

64.5

10.35

0.9

-705.689

III. Indexing into Vectors in C++ 

1. Vector indexing 

(1) Can use indexing with [] to work individual elements. 

-> As with strings, indices start with 0 and go up to length – 1. 

42

42

42

42

=>

0

1

2

3

 

42

42

5

42

=>

0

1

2

3

2. Indexing out of bounds

(1) As with strings, it’s possible to index off the end of a vector, which results in undefined behavior at runtime. 

(2) Basically, this goes to whatever memory happens to be next to the vector. 

-> Maybe you get “lucky” and this memory wasn’t important. 

-> Maybe you mess up another variable that happens to be there. 

-> Maybe your program isn’t allowed to use that chunk of memory. 

-> This causes a crash called a segmentation fault (seg fault). 

 

3. The at function 

(1) You have the option to use the .at function rather than indexing with the square brackets.  

-> This contains an implicit check to make sure the index is valid. 

(2) The tradeoff is that at is slightly slower than []. 

Ex) The variable y is a vector of double values: 

  y

1.57

0.33

88.4

0.06

7.75

=>

0

1

2

3

4

 

Which code snippet will print the number 1.57? 

A: (1) cout << y.at(0) << endl;

     (2) cout << y[0] << endl; 

 

Ex) The variable x is a vector of int values: 

  x

99

54

63

9

18

27

=>

0

1

2

3

4

5

 Which code snippet will print the number 18?

A: (1) cout << x[4] << endl;

     (2) cout << 2 * x.at(3) << endl;

     (3) cout << x.at(1) -36 << endl;

     (4) cout << x.at(4) << endl; 

IV. Vector Functions 

Call the vector functions by using the dot notation. 

.size	Returns the number of elements
.front	Returns a reference to the first element
.back	Returns a reference to the last element
.at	Works like indexing, but does bounds checking
.empty	Returns whether the vector is empty (as a bool)
.clear	Removes all elements from the vector
.puch_back	Adds a new element to the back of the vector
.pop_back	Removes the last element in the vector.
.erease	Removes from the vector either a single element or a range of elements

V. Traversing a Vector 

Use a loop to traverse through each element in a vector: 

We can use a loop to traverse through each element in a vector:

vector<int> vec(4,42); for (int i = 0; I < vec,size(); ++i){        cout << vec.at(i) << endl;  }

Depending on your compiler setting, you will get a warning or an error when you use this loop to traverse a vector. The warning might say conversion from ‘size_t’ to  ‘int’ possible loss of data. 

 

This is because vec.size() technically returns a size_t data type, not an int. The size_t data type is used to hold the size of an object, like a vector. It can be used for indexing and counting, but it can never be negative (since a vector will never have a negative size). 

 

To avoid this warning, we can re-write our loop like this: 

vector<int> vec(4,42); for (size_t i = 0; i < vec,size(); ++i){        cout << vec.at(i) << endl;  }

We are declaring i to be a variable of type size_t rather than type int. This will do the exact same thing as the loop. 

Use size_t when you are comparing your loop index to the size() of a vector or other object. Other than that, no need to sued size_t in our loops. 

 

EXERCISE) Print Doubled Vector

The function printDoubled takes in a vector of int values and prints out 2 times the value of each element (there is no return value). A space is printed after each vector element. Complete the implementation of the printDoubled function.

 

IV. Adding / Removing Elements from a Vector 

1. Add an element to the back 

To add an element to the back, use push_back:

[ ] size: 0 

5

        0              Size: 1 

5

8

=>  Size: 2

0

1

5

8

0

1

2

=> Size: 5

0

1

2

3

4

2. Remove an element from the back

To remove an element from the back, use pop_back:

5

8

0

1

=> Size: 4

0

1

2

3

 

5

      0               size: 1

 

Ex) Which statement should we use to get from the vector on the left to the vector on the right? 

vec

4

38

52

109

-7

=>

0

1

2

3

4

->

    vec

4

38

52

109

=>

0

1

2

3

A: vec.pop_back();

 

Ex) Which statement should we use to get from the vector on the left to the vector on the right? 

vec

-9

-8

=>

0

1

->

vec

-9

-8

-7

-6

-5

=>

0

1

2

3

4

 A: for (int i = -7; i < -4; ++I) {

            vec.push_back(i);

     }          

IIV. Erasing Elements from a Vector 

1. vector erase

To remove elements from a vector, use erase. When using erase, you need to specify indices relative to begin(). (The begin() function refers to the first element in the vector.) 

 

 

EXERCISE) Erasing Zeros 

Arrange the lines of code below to write a program that erases all of the elements of a vector that are equal to zero. As you erase elements, the size of your vector will change. You want to check each element, but not in the same way as the “traversing a vector” pattern. Think about how to step through each element in the vector and pause to erase a zero if you find one but go to the next element if the value is not a zero. 

 

IIIV. Passing Vectors to Functions 

When passing vectors to functions, avoid using pass by value, because that makes an expensive copy of the vector (vectors are large data structures). Instead, use pass by reference or pass by const reference. Pass by reference allows the vector to be modified, which can be risky if you don’t need to modify the vector. Pass by const reference avoids the expensive copy of pass by value but doesn’t allow you to modify the vector. 

 

1. Pass by const reference 

(1) To prevent accidental modification, add the const keyword. 

-> const is short for “constant”. 

-> You’ll get a compiler error to warn you if you accidentally change it. 

2. Parameter Passing 

3. Pass by reference 

(1) Pass by reference gets rid of the expensive copy

-> it’s also risky, because it allows modification of the parameter. 

 

* Vector 는 cout 으로 바로 출력되지 않음. 그래서 for 으로 traversing 하던 function 에 cout 포함해서 출력하던 해야함. 그리고 C++ print 는 printf 이고 library 는 <iostream> 임

 

 

EXERCISE) Passing Vectors to Functions 

Ex) A function that checks to see if there are any zeros in a vector (and returns true of false). 

A: Pass by const reference 

• We don’t need to modify the vector but we don’t want to make an expensive copy, so pass by const reference is the best choice. 

 Ex) A function that sets all elements in the vector to be 25 (and returns nothing, but the original vector passed in is modified). 

A: Pass by reference 

• Need to modify the vector 

Ex) A function that sorts the elements to be in ascending order (and returns nothing, but the original vector passed in Is modified. 

A: Pass by reference

• Need to modify the vector

Ex) A function that finds the index of the element that matches a given value (and returns the index). 

A: pass by const reference 

• We don’t need to modify the vector but we don’t want to make an expensive copy, so pass by const reference is the best choice. 

IX. Common Patterns

1. Creating Vectors: “Make Space, Then Fill” 

If you know ahead of time how many elements you need, first allocate enough elements and then fill in the values. 

// make space… int N = 7;  vector<int> vec(N); // the vector now has N empty elements // … then fill for (int i = 0; i < N; ++i) {         vec[i] = 2*i +1;  //fill in the values  }

2. Creating Vectors: “Fill As You Go” 

If you don’t know ahead of time how many elements you need, just add them as you go by using push_back. The vector will grow as needed to accommodate everything. A common application of this pattern is reading values into a vector from a data file. 

// declare the vector  vector<double> data;    // open a file stream   ifstream fileIn (“sensor.dat”); // declare a variable to hold a value that is read in  double value; // proceed through the file reading each value in turn;  // the values are added to the vector using push_back; // the loop ends when no more values can be read in  // … then fill while (fileIn >> value) {         data.push_back(value);  } // close the file  fileIn.close ();

3. Using an Accumulator 

Sometimes, you want to compute the result of combining a set of elements. EX) You might want to find the sum or product of elements in a vector. To do this, start a “running total” with the identity for the operation you’re using. Then add elements one at a time. 

// Returns the sum of elements in a vector   int sum (const vector<int> &vec) { int sum = 0;  // Starting at 0 because it’s the additive identity  // Iterate through vector, adding each element to the running total  for (int i = 0; i < vec.size(); ++i ) { sum += vec.at(i); // can also index using vec[i]  } Return sum; }

4. Finding the “Best” Element 

Sometimes you want to find the “best” element according to some criteria. You might want to find the maximum or minimum value in a vector. To do this, start with the first element as the “best” element. Then, traverse the vector, keeping track of the “best value so far” and comparing the “best so far” to each element. If you find a new “best element”, replace “best so far” with that value, and continue on. 

* The approach shown here does not work on empty vectors because “the maximum of nothing” doesn’t make any sense. 

// Returns the value of the maximum element in the vector;  // the vector must not be an empty vector    int max_element (const vector<int> &vec) { int max_so_far =  vec.at(0); // Assume first is largest  // Iterate through vector, looking for any larger  for (int i = 0; i < vec.size(); ++i ) {     if ( vec.at(i) > max_so_far) { // compare the values         max_so_far = vec.at(i); // keep track of the best element          } } return max_so_far; }

5. Finding the Index of the “Best” Element 

Sometimes we want to know the index of the “best” element and not its value. 

We might want to know the location, or index, of the maximum value in a vector so we can look up the element later. To do this, we can use a similar approach to the “find the best element” pattern, but we keep track of the index of the “best” element instead of the value of the “best” element.

// Returns the value of the maximum element in the vector int index_of_max_element (const vector<int> &vec) { // First, check to see if this is an empty vector; if the vector is empty, return a -1  Immediately (an index number cannot be negative, so this return value indicates an empty vector)  if ( vec.empty()) { return -1;  }     int index_of_max =  0 // Assume first is largest  for (int i = 0; i < vec.size(); ++i ) {     if ( vec.at(i) > vec[index_of_max]) { // compare the values         index_of_max = i; // keep track of the index of the best element          } } return index_of_max;  }

6. Accessing Parallel Vectors 

To get data that is “parallel”, access each vector using the same index number. This is very similar to how we accessed parallel vectors in MATLAB. 

vector<string> states; vector<string> population; // code to “fill up” the states and populations vectors  // Display first state cout << “The first state is: “ << states.at(0);  cout << “ – population” << population.at(0) << endl; // Display 10th state cout << “The first state is: “ << states.at(9);  cout << “ – population” << population.at(9) << endl; // Display last state cout << “The first state is: “ << states.at(states.size()-1);  cout << “ – population” << population.at(states.size()-1) << endl;

7. Checking If Any Element Match Criteria 

Sometimes you want to check if any element(s) match some criteria. You might want to know “are there any zeros?” or “are there any elements greater than 100?”. Our strategy here is to always frame this as an “any” question, and then use a loop with early termination to check for any such element. 

// Returns whether there are any zeros in the vector  bool any_zeros(const vector<int> &vec) { // iterate and check for any zeros      for (int i = 0; i < vec.size(); ++i ) {          if ( vec.at(i) == 0 ) {         return true; // if we find a match, return immediately           }      }         return false;  // if we get here, then there were no matches   }

8. Checking If All Element Match Criteria 

Sometimes you want to check if all element(s) match some criteria. You might want to know “are all the elements zero?” or “are all the elements positive?”. Our strategy here is to frame this as a “checking if any match” pattern, and then use a loop with early termination to check for nay counterexamples. In other words, we can use negation to turn an “all” question into an “any” question. 

// Returns whether there are any zeros in the vector  bool all_positive(const vector<int> &vec) { // iterate and check for any non-positives       for (int i = 0; i < vec.size(); ++i ) {          if ( !(vec.at(i) > 0 )) {  //check for counterexamples         return false; // if we find one, return immediately because we found an element that did not match the criteria (and we don’t have to check the rest of the elements)            }      }         return true;  // if we made it here, then all the elements match the criteria!  }

9. Searching for a Value

Sometimes, you are looking for the location of a particular element. You might want to know the index of the first positive value. You might want to know at which index the value 0 first occurs. Our strategy here is to frame this as an “any” question, but we return the current index instead of a true value. 

// Returns the index at which the given value first occurs in the vector. If the value is not present, returns -1.    int find(const vector<int> &vec, int value) { // iterate and check for any zeros      for (int i = 0; i < vec.size(); ++i ) {          if ( vec.at(i) == value) {         return i; // if we find a match, return the index of the match           }      }         return -1;  // if we make it to here, there weren’t any matches; we can use -1 to represent ‘no elements found’    }

EXERCISE) Checking if All Negative  

The function all_negative takes in a vector of int values and returns true if the elements in the vector are all negative (otherwise, it returns false). Complete the implementation of the all_negative function. 

 

EXERCISE) Finding Minimum Value   

The function minVal takes in a vector of double values and returns the minimum value contained in the vector of double values. Write the function minVal.