Chapter 8, Pause Reflect

• 8.1--8.7

• 8.8--8.13

• 8.14--8.20

• 8.21--8.29

• 8.1 : In Program 8.1, dieroll.cpp, to simulate twelve sided dice (sums from 2 to 24) requires 16 more variables, the same number of case alternatives in the switch statement and the same number of output statements.

  The number of lines added is a linear function of the numer of sides on the dice being rolled. For example, for N-sided dice, the possible values are 2, 3, ..., 2N, which is (roughly) 2N different values --- the number of values is a linear function of N. The number of statements added is also a linear function of N since statements are added for initialization, update, and print, for a rough total of 3 * 2N statements which is still linear.

  When using a vector as in Program 8.2 only one constant, DICE_SIDES needs to be changed to simulate 12 sided dice.

• 8.2 : To simulate three six-sided dice requires changing the size of the vector from 2*DICE_SIDES + 1 to 3*DICE_SIDES+ 1 and changing the statement

      int sum = d.Roll() + d.Roll();
  

  to

      int sum = d.Roll() + d.Roll() + d.Roll();
  

• 8.3 :one solution is given below (one loop is used, with an if statement to avoid bad indexing of intVec). const int SIZE = 512; tvector<double> doubVec(SIZE); tvector<int> intVec(SIZE/2); int k; for(k=0; k < SIZE; k++) { doubVec[k] = 2.0 * k; if (k % 2 == 0) intVec[k/2] = 2*k; }

• 8.4 : It IS possible to create a vector of Balloon objects because the Balloon class does have a default or parameterless constructor.

• 8.5 : Here's a definition for a vector: tvector<string> compscientists(5); compscientists[0] = "Grace"; compscientists[1] = "Alan"; compscientists[2] = "John"; compscientists[3] = "Ada"; compscientists[4] = "Blaise"; Here's a loop to print the song given the vector above. int k; for(k=0; k < 5; k++) { Sing(compscientists[k]); }

• 8.6 : to use only 26 slots, indexed from 0 to 25, in letters.cpp requires changing each vector access. Vector accesses are as follows:
  • Instead of using CHAR_MAX as the size of the vector defined in main use either 26 or create a global constant (the constant is better) const int ALPH_SIZE = 26; Then change the definition of the vector to tvector<int> charCounts(ALPH_SIZE, 0);

  • In the function Count, replace counts[ch]++; with counts[ch-'a']++;

  • In the function Print replace counts[k] (which occurs in two places) with counts[k-'a'] and replace counts[k+MIDALPH]; with counts[k-'a' + MIDALPH];

• 8.7 : One solution is shown below: #include <iostream> #include <fstream> using namespace std; #include "tvector.h" #include "prompt.h" const int MAX_LETTER = 15; int main() { // make room for 15 letter words, all initialized to zero // and word length k in slot k tvector<int> counts(MAX_LETTER+1, 0); string word; ifstream input; string filename = PromptString("enter name of file: "); input.open(filename.c_str()); while (input >> word) { if (word.length() <= MAX_LETTER) { counts[word.length()]++; } } int k; cout << "length \t count" << endl; for(k=2; k <= MAX_LETTER; k++) { cout << k << "\t" << counts[k] << endl; } return 0; }

• 8.8: Here's one version of Initialize void Initialize(tvector<Track>& tracks, int & count) // post: count = # elements in tracks { tracks[0] = Track("Box of Rain",1); tracks[1] = Track("Friend of the Devil",2); tracks[2] = Track("Sugar Magnolia",3); tracks[3] = Track("Operator",4); tracks[4] = Track("Candyman",5); tracks[5] = Track("Ripple",6); tracks[6] = Track("Brokedown Palace",7); tracks[7] = Track("Till the Morning Comes",8); tracks[8] = Track("Attics of my Life",9); tracks[9] = Track("Truckin",10); count = 10; }

• 8.9 : The statement cout << tracks[k] << endl; will NOT work because operator << hasn't been defined for Track variables. It's possible to define the output operator for user-defined classes --- we'll see this in Chapter 9 with the ClockTime class.

• 8.10 : The test should be k < count - 1 because a random number between k and count-1 is chosen, however if the test is changed the program will still work. For example, when k is count - 2 (its largest value in the program) then the statement gen.RandInt(k,count-1); becomes gen.RandInt(count-2, count-1); if the guard is k < count, the gen.RandInt statement will be (the last time it's executed) gen.randInt(count-1,count-1); Which always generates the same number, count-1, so a Track is swapped with itself, which doesn't hurt, but isn't needed to make the algorihtm work.

• 8.11 : The assignment tracks[randTrack] = tracks[k] assigns one Track to another. Since a track contains two data elements (the title and the track number) each Track assignment is really two assignments since both data elements are assigned.

• 8.12 : If no vector/Track assignments are made, each vector value in the vector tracks has the default Track values which are the string "no title" and the track number zero/0. This means you'll see printed:

    0	no title
    0	no title
    0	no title
    0	no title
    0	no title
    0	no title
    0	no title
    0	no title
    0	no title
    0	no title
  

  both before and after shuffling, so you won't be able to tell if shuffling works.

• 8.13 : Here's code to shuffle the different way: for(k=0; k < 1000; k++) { int first = gen.RandInt(0,count-1); int second = gen.RandInt(0,count-1); Swap(a[first],a[second]); } this is worse because (a) it's possible things don't move at all, or move and then move back. The method in the book makes all possible arrangements equally likely. This isn't the case when 1,000 swaps are made.

8.14 -- 8.20

• 8.14: If the WordStreamIterator object is replaced by an ifstream object then when ReadAll finishes the stream will have been read completely, and the loop test in ReadAll, which will be something like this while (input >> word) { list.push_back(word); } will have failed. This means all subsequent extraction operations using operator >> will also fail, so nothing will be read in the function ReadAll2. It's possible to reset the stream so that it can be read again using clear (see Howto B), but that's not enough since the stream will still be "located" at its end and reading from the beginning will require using seekg -- for details see the implementation of the WordStreamIterator class which hides all these messy details to make it possible to read a stream many times in the same program.

• 8.15: The + 1 is used so that when the capacity is initially zero the increas has an effect. Without adding one, multiplying zero by two yields zero and the vector never grows.

• 8.16: The size will be the same as the capacity when resize is used, so it will be 131,071.

• 8.17: Instead of defining the vector tracks with 10 slots/Tracks, the vector would be defined like this: tvector<Track> tracks; Then a sequence of calls using push_back follow: tracks.push_back(Track("Box of Rain",1)); tracks.push_back(Track("Friend of the Devil",2)); // and so on Finally, both Print and Shuffle will need only the vector parameter, not a count, since the vector "knows" how many elements it contains and this value is accessible using size().

• 8.18: Since a vector doubles in size, when it has room for 512 elements it will have allocated

    2 + 4 + 8 + 16 + 32 + 64 + 128 + 256
  

  elements before allocating the final 512. This results in a total of 510 + 512 elements or 1,022 elements.

  When the capacity is 16,384 the vector will have allocated

    2 + 4 + 8 + ... + 4,096 + 8,192
  

  If all the values from 1 + 2 + ... + 8192 are added together, the sum is one less than the next power of two, or 16,383. Since the 1 isn't included (the first vector size is two), the total is 16,382 + 16,384 = 32,766 elements.

• 8.19: When the vector contains 32 elements it has allocated

    1 + 2 + 3 + 4 + ... + 32 = 32(33)/2 = 528
  

  When the capacitiy is 128 the total number of elements allocated is 128(129)/2 = 8,256 elements. When the capacity is 16,384 the total number of elements allocated is 16384(16385)/2 = 134,225,920 --- compare this with the 32,766 elements allocated in the previous problem.

• 8.20: By calling push_back there are fewer checks made internally in the tvector class functions. For example, when push_back is NOT used, and the indexing brackets are used with an explicit resize, each execution of list[count] = iter.Current(); causes two checks to be made regarding the index value count: one that count is positive and one that count isn't bigger than the vector's capacity/size. These checks are needed in general when a vector is indexed, but aren't needed in the code in program growdemo.cpp since whenever the vector is indexed the code has already ensured the index is within range.

8.21 -- 8.29

• 8.21: The vector list is a const reference parameter because it doesn't change, hence it is const, and it's passed by reference to avoid the overhead in making a copy that would be required if the vector was passed by value.

  The value returned for the string "apple" is 0, this is the correct value since "apple" belongs as the first element.

  The value of k becomes 3 and list[3] == "orange" which is less than "watermelon" so the loop body executes. k becomes 4, the first part of the loop test is false, and the loop doesn't execute and 4 is returned.

  The test k < len is needed to avoid a bad index when a string s is larger than all the elements in the vector. The largest valid index is size() - 1, so the check is needed.

• 8.22: Here's one version: void insertAt(tvector<string>& list, const string& s, int loc) // post: s inserted into list at index loc // order of list elements unchanged { int k; list.push_back(s); // add at end just to grow the vector for(k=list.size()-1; k > loc; k--) { list[k] = list[k-1]; // shift } list[loc] = s; // insert at position loc }

• 8.23: The fewest number of elements that are shifted is none, the new element is inserted at the end and that's where it belongs.

  The most number of elements shifted is n, when the new element belongs first (index zero) all the elements must be shifted.

• 8.24: Here's the "remove all by pop_back" function: void Clear(tvector<string>& list) // post: list contains size() elements // post: list contains zero elements { int len = list.size(); int k; for(k=0; k < len; k++) { list.pop_back(); } }

• 8.25: Here's one version: void deleteAt(tvector<string>& list, int loc) // post: item at index loc removed, // order of other items unchanged { int k; int last = list.size()-1; // maximum valid index for(k=loc; k < last; k++) { list[k] = list[k+1]; } list.pop_back(); // decrease size }

  If list represents ("avocado", "banana", "lemon", "orange") then to remove "banana" the call is:

  deleteAt(list, 1);

• 8.26: Here's the function: int vowelCount(const tvector<string>& list) // post: return # strings in list beginning with a vowel { int k; int count = 0; int len = list.size(); for(k=0; k < len; k++) { if (IsVowel(list[k].substr(0,1))) { count++; } } return count; }

  The number of strings that do NOT begin with a vowel is given by

  int consonants = list.size() - vowelCount(list);

• 8.27: Here's a version: int vowelVector(const tvector<string>& list) // post: return vector containing strings from list // that begin with a vowel { tvector<string> v; int k; int len = list.size(); for(k=0; k < len; k++) { if (IsVowel(list[k].substr(0,1))) { v.push_back(list[k]); } } return v; }

• 8.28: Here's one version: int sum(const tvector<int>& list) // post: returns list[0] + ... list[list.size()-1] { int k; int sum = 0; int len = list.size()-1; for(k=0; k < len; k++) { sum += list[k]; } return sum; }

• 8.29: Here's a version with an invariant: void removeDups(tvector<string>& list) // pre: list[0] <= ... <= list[list.size()-1] (sorted) // post: duplicates removed from still sorted list { int k; int len = list.size() - 1; int lastNonDupIndex = 0; // invariant: elements in [0..lastNonDupIndex] aren't duplicates for(k=1; k < len; k++) { if (list[k] != list[lastNonDupIndex]) { lastNonDupIndex++; list[lastNonDupIndex] = list[k]; } } list.resize(lastNonDupIndex+1); }