Sheet 11

Task 1

Drill for Chapter 20 on page 753.

1. Define an array of int s with the ten elements { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }.
2. Define a vector<int> with those ten elements.
3. Define a list<int> with those ten elements.
4. Define a second array, vector, and list, each initialized as a copy of the first array, vector, and list, respectively.
5. Increase the value of each element in the array by 2; increase the value of each element in the vector by 3; increase the value of each element in the list by 5.
6. Write a simple copy() operation,

   template<typename Iter1, typename Iter2>
   // requires Input_iterator<Iter1>() && Output_iterator<Iter2>()
   Iter2 copy(Iter1 f1, Iter1 e1, Iter2 f2);
   

   that copies [f1,e1) to [f2,f2+(e1–f1)) and returns f2+(e1–f1) just like the standard library copy function. Note that if f1==e1 the sequence is empty, so that there is nothing to copy.

7. Use your copy() to copy the array into the vector and to copy the list into the array.
8. Use the standard library find() to see if the vector contains the value 3 and print out its position if it does; use find() to see if the list contains the value 27 and print out its position if it does. The “position” of the first element is 0, the position of the second element is 1, etc. Note that if find() returns the end of the sequence, the value wasn’t found.

Remember to test after each step.

Task 2

Do exercises 7, 8 and 11 of Chapter 20 on page 755.

• Find the lexicographical last string in an unsorted vector<string>.

• Define a function that counts the number of characters in a Document.

• Given a list<int> as a (by-reference) parameter, make a vector<double> and copy the elements of the list into it. Verify that the copy was complete and correct. Then print the elements sorted in order of increasing value.

Task 3

Do exercise of Chapter 20 on page 755.

Run a small timing experiment to compare the cost of using vector and list. Generate N random int values in the range [0:N). As each int is generated, insert it into a vector<int> (which grows by one element each time). Keep the vector sorted; that is, a value is inserted after every previous value that is less than or equal to the new value and before every previous value that is larger than the new value. Now do the same experiment using a list<int> to hold the ints. For which N is the list faster than the vector? Try to explain your result. This experiment was first suggested by John Bentley.

To time a program use:

// timing
#include <chrono>
using namespace std::chrono;

then in some function:

auto t1 = system_clock::now();
// some calculations
auto t2 = system_clock::now();
cout << iterations << " iterations took "
     << duration_cast<milliseconds>(t2 - t1).count() << " milliseconds\n";