These questions refer to the reference counted linked list class described in lab 6. You should be able to answer these questions even if you haven't finished that lab yet. For any questions about overheads, assume we're using a simpleminded C++ compiler that does not try to do any clever optimizations.
1) When a list is assigned, the reference counted list class should _not_ need to make a copy of the elements in the list. If the list class did copy the elements, then functions like the following would need more memory (and time):
void stupid(RCList &l) {
RCList l2, l3, l4;
l2 = l;
l3 = l;
l4 = l;
}
If we use only the functions described in the assignment except for "debug", can we detect any other difference between these two possible implementations? That is, is there any way for a programmer to write a program to determine whether or not list elements are actually copied, without using "debug" to look at reference counts, adding extra functions to check the count, or measuring memory or time required?
If there is a way to find out which implementation is being used, describe it; if this is impossible, explain why it cannot be done.
2) The RCList could be extended with the "template" mechanism to allow RCList's with other kinds of elements. The public section would look like this:
template <class T> class RCList {
public:
RCList(const RCList<T> &r);
RCList &operator=(const RCList<T> &rhs);
RCList(); ~RCList();
bool is_null() const;
const T &head() const; // car
RCList<T> rest() const; // cdr
friend RCList<T> prepend(const T &d, const RCList<T> &l); // cons
We could then create a list of doubles like this:
RCList<double> dl;
Or if we had classes X and Y, we could create one list containing elements of type X, and two containing elements of type Y:
RCList <X> only_list_of_X;
RCList <Y> first_list_of_Y, second_list_of_Y;
Assuming we have created the four lists shown above,
a) How many copies of each RCList member function will be in our executable program?
b) How does the run-time overhead of manipulating the list "dl" compare to the run-time overhead of manipulating a list from our non-templatized class (in the lab assignment)?
3) Question 2 shows how to create lists containing only X's or only Y's. Consider the problem of creating a list that contains some elements of type X and some of type Y.
a) Show how this can be done.
b) If we create one list of doubles (i.e. "dl" above) and three such "mixed" lists (to replace the other three lists above), how many copies of each RCList member function will be in our executable program?
c) Describe how the run-time overhead of this approach compares to the run-time overhead of the lists created in Question 2.