.capacity() member function to
lists. Describe what .capacity() for lists would do how you would implement
it.
Capacity for vectors indicates the total amount of space available for storing
elements before the vector has to be resized to add more space for more
elements. Because lists always have the exact amount of space needed to store
elements (or, alternatively and equivalently, lists are always resized when
inserting an element), .capacity() for lists would be equivalent to
.size().
There are other ways to implement lists, which would lead to different answers
to this question. For example, the list implementation could cache deleted
nodes on a free list, which would save the cost of repeatedly allocating and
deleting nodes. In this case, .capacity() would return the sum of the
sizes of the data and free lists.
Most answers got across the relation between .capacity() and allocation.
One answer identified list capacity with .max_size(), which would mean that
(under the interpretation here), lists would never allocate more space.
Yes, indices can be invalidated. Suppose i is set to the index of the
left-most even integer in a vector v. Doing v.insert(v.front(), 1)
would invalidate i in the sense that it no longer points to the left-most
even integer.
On the other hand, indices are not invalidated when the vector is resized to grow: an index to the ith element in the old vector is still an index to the ith element in the new vector.
Most answers to this question were correct, but chose another approach than the
one given in the previous paragraph, pointing out that the second .at() in
i = v.size() - 1; v.at(i); v.pop_back(); v.at(i);
would blow up even though i hadn't changed. The wrong answers were wrong
because they claimed that indices couldn't be invalidated.
Unfortunately, your colleague's strategy doesn't work; provide a test case in which your colleague's algorithm might fail to produce a maximally-compressed string.
Hints: Your test case only needs three strings. You should consider the case when there is more than one largest-overlap pair P in step 2.
Your colleague's greedy solution to Assignment 2 works as long as the greedy choice is unambiguous; that is, there is only one largest-overlap pair to pick. As soon as there is more than one largest-overlap pair, you colleague's algorithm can fail.
To see why, consider the three strings are abb, bb, and bbc as
input. The pair-wise maximum overlap is 2 for the pairs abb (abb +
bb) and abbc (abb + bbc). If the algorithm chooses
abb, then the next step leads to the maximally compressed string
abbc. However, if the algorithm chooses abbc, then the next step is
to form the final compressed string abbcbb, which is not maximally
compressed.
The wrong answers for this question were interesting, because they chose a test case in which the final compressed string size was the same no matter which choice was made. The correct answers followed mostly the argument in the previous paragraph.
Given the iterator range (b, e) following your colleague's scheme, write a
loop to iterate through the range, assuming b and e are input
iterators. Make sure your code can handle all possible (valid) ranges.
The straightforward solution is
while (b != e) process(b) b++
that is, march b to the right until it hits e. This solution works
for one-past-the-end iterator ranges, but doesn't work here because your
colleague's iterator ranges are at-the-end ranges. In particular, b == e
is not a termination condition; it describes an iterator range with only one
element.
We can fix this problem by repeating the processing step after the loop. We
know that if the loop terminates, then b == e, so we're justified in doing
while (b != e) process(b) b++ // b == e here process(e)
We have handled the case where b is to the left of e, and when b
is equal to e, but thanks to your colleague's scheme, we still have to
consider the case when b is to the right of e.
Mercifully, you colleague has made this (relatively) easy for us. The end iterator is one to the left of the begin iterator for empty ranges, which tempts us to try something like
if (e + 1 != b)
while (b != e)
process(b)
b++
process(e)
Unfortunately, e is an input iterator and doesn't support + int; we
have to do instead
if (++e != b)
while (b != e)
process(b)
b++
process(e)
But this isn't quite right, because after doing ++e, e is now
pointing to an element not in the range, which means the final process() is
now incorrect, a problem easily fixed.
if (++e != b)
while (b != e)
process(b)
b++
Finally, note that ++e != b has the same logical value as b != e,
which means that we can get rid of the if statement (but not moving e one
to the right):
++e while (b != e) process(b) b++
Note that our correct solution is just our original incorrect solution with
++e in front. This leads us to the a second way to solve this problem
(one you are probably wondering if I would ever get around to): Your
colleague's iterator-range scheme (at-the-end) can be turned into the
traditional iterator-range scheme (one-past-the-end) by just moving the end one
to the right.
First, because you had an old version of the test, it asked you to write a for loop. This was revised to just a loop in the current version of the test because suggesting a for loop was misleading. Because of this mistake, I did not grade the answer to this question on the basis of the loop used.
But the loop didn't make any difference anyway: all the answers to this question were wrong, and they were wrong due to invalid iterator operations. Most answers included something like
for ( ; b < e; b++)
Everybody apparently ignored the requirement that b and e are input
iterators, and input iterators don't support the less-than operator.
This page last modified on 25 February 2004.