CS 509, Advanced Programming II

Fall 2001 - Test 4

1. The following question appears on your neighbor's test:

   Give an example where it would be better to use a map with an integer key rather than a vector. (Hint: "When the data needs to be sorted." is not a correct answer.)

   Explain why an answer involving sorting is not correct.

   ---

   The sorting in a map is done by key value, not by element value. Vectors are automatically sorted by key, so a map is doing more work to get what requires no work in a vector.

   ---

2. Describe the weakest (least powerful) iterator needed to implement the search(s1, e1, s2, e2) generic algorithm. Justify your answer. The search() generic algorithm looks for the value sequence indicated by [s2, e2) in the value sequence indicated by [s1, e1).

   ---

   The search() generic algorithm is implemented roughly as

   search(s1, e1, s2, e2) 
   
     for (i = s1; i != e1; i++)
       j = i
       for (k = s2; k != e2 && j != e1; k++, j++)
         if (*j != *k)
           break
       if (k == e2)
         return i
   
     return e1
   

   The iterator assignments mean that the parameter iterators must be at least forward iterators. All the other operators applied are provided by either input or output iterators, so the weakest iterator needed is the forward iterator.

   ---

3. Let m have type map<int,string>. Given that

   copy(m.begin(), m.end(), back_inserter(x))
   

   compiles and runs without problems, what is the type of x?

   ---

   A valid iterator into m is a reference to a value of type pair<int,string>, which is the type of the value being inserted into x. Because x is an argument to back_inserter(), x must be a container that supports push_back(). Of the containers we know about, x must be of type vector<pair<int,string> > or list<pair<int,string> >.

   ---

4. Provide an upper-bound asymptotic estimate for the run-time of the following code:

   vector<Student_Info>
   extract_fails(vector<Student_Info> & students) {
   
     vector<Student_Info>::iterator iter = 
       stable_partition(students.begin(), students.end(), pgrade);
     vector<Student_Info> fail(iter, students.end());
     students.erase(iter, students.end());
   
     return fail;
     }
   

   Be sure to clearly state your assumptions.

   ---

   Starting with the atomic statements, the analysis is

     vector<Student_Info>::iterator iter = 
       stable_partition(O(1), O(1), O(1));
     vector<Student_Info> fail(O(1), O(1));
     students.erase(O(1), O(1));
   
     return fail;
   

   The iterator functions work in constant time, as does the pgrade() function, which is just a comparison and two integer returns.

   In the worst case, the stable_partition() generic algorithm needs to touch each element of the iterator range once and so executes in O(n) time, where n is the number of records in the range. By the same reasoning, creating a vector from an iterator range containing n elements should take O(n) time. Similarly for erase(), which needs to touch each element in the range once in the worst case. The return statement involves a copy, which should take O(n). This analysis now produces

     vector<Student_Info>::iterator iter = O(n)
     O(n)
     O(n)
   
     O(n)
   

   Assigning one vector to another should take O(n) time, and the sequence rule reduces the analysis to O(n) time.

   ---

This page last modified on 3 November 2001.