CS 509 Test 3

CS 509, Advanced Programming II

Fall 2002 - Test 3

Explain what's wrong with the following code and how to fix it:
```
clear(vector & c) 

  vector::iterator e = c.end()
  while c.begin() != e
    c.erase(c.begin())
```
Erasing the first element of a vector invalidates all the iterators to the values to the right of the former first value, including the end iterator. After the first iteration of the loop, e is invalid and the equality test is not guaranteed to produce valid results.
One fix is to replace the guard with something that can't be invalidated:
```
while !c.empty()
  c.erase(c.begin())
```
An even better fix, though, is to just call the clear() member function:
```
c.clear();
```
Use asymptotic analysis to determine which of these two algorithms is the asymptotically faster.
```
no_odds(vector & ivec)

  i = ivec.begin()
  while (i = find_if(i, ivec.end(), odd)) != ivec.end()
    *i *= 2

no_odds(list & ilst)

  while (i = find_if(ilst.begin(), ilst.end(), odd)) != ilst.end()
    *i *= 2
```
odd() is a predicate that returns true if and only if its input argument is odd. Make sure you clearly state your realistic assumptions.
In both loops the bodies do constant work, as do the calls to begin(), end(), and odd(). Both loops, in the worst case (when ivec contains only odd numbers), also do O(n) iterations The problem reduces to finding the amount of work done by each find_if().
In the first loop find_if() effectively makes a linear scan through ivec because it starts the next search at the point it stopped in the previous search. In the worst case find_if() does constant work for each iteration, and so the whole loop takes O(n)*O(1) = O(n) time.
In the second loop find_if() searches through ivec from the beginning on each iteration, which means it effectively performs O(n) work on each iteration. With O(n) iterations, that means the second loop does O(n)*O(n) = 0(n²) work.
From these estimates, the first loop should be faster than the second loop.
If i is a random-access iterator, what does *(i - 1) mean? Explain.
If i is a random-access iteration, then i - 1 is the iterator to the left of i and *(i - 1) is the value to the left of the value referenced by i.
Write a test case that determines if an implementation of the third assignment re-uses old register values when optimizing code.
Describe the input script and expected output, and explain how the expected output satisfies the required test.
One simple test is
```
move r0  a
move  b r0
move r0  a
move  c r0
```
The effect of this code is
```
b = a
c = a
```
Because a doesn't change its value in this code, the first and third statements have the same effect and the third statement is redundant. Eliminating it leads to the code
```
move r0  a 
move  b r0 ; move  c r0
```

This page last modified on 20 October 2002.