1. A colleague has been reading your code, hoping to learn the secrets of the STL experts. Upon finding the function

   template<typename T>
   bool less_than(const list<T> & l1, const list<T> & l2) {
     return l1 < l2;
     }
   

   your colleague tells you that less_than() is incorrect because the < operator isn't defined for lists. Explain whether or not your colleague is correct. If your colleague is wrong, explain the most likely source of your colleague's confusion.

   Your answer to this question should rely only on the features and properties of the list container; you should not, for example, argue that your colleague is wrong because the code compiles without error.

   ---

   Your colleague is wrong; as with all other sequenced containers, < is defined for lists and has the usually lexicographic interpretation.

   Your colleague has most likely confused lists with list iterators. The < operator is not defined for list iterators, which are bidirectional.

   ---

2. A colleague of yours is learning the STL, and is surprised to discover that the list container defines the sort() and unique() member functions, even through there are sort() and unique() generic algorithms. Seeking enlightenment, your colleague comes to you and asks you to justify this apparent duplication of effort. What justification do you give your colleague?

   Your answer to this question should give two separate justifications, one for sort() and the other for unique().

   ---

   The sort() generic algorithm requires random iterators, but list iterators are bidirectional, which means lists cannot be used with the sort() generic algorithm. Because sorting is a useful operation, the list class includes a sort() member function.

   The unique() generic algorithm requires bidirectional iterators, and can can applied to lists. However, because unique() is a generic algorithm, it doesn't take advantage of the list's special insert and delete properties and is therefore less efficient than it could be for lists. The list's unique() member function does take advantage of these properties, and is therefore more efficient than the generic version when applied to lists.

   See Musser and Saini Section 6.3.6 for more information.

   ---

3. You are implementing a fast list data structure, and you know that the list data structure will never have more than n values inserted into it. Given this fact, do you choose sequential storage or linked lists to implement the list data structure? Justify your choice.

   ---

   If the list data structure has to be fast, you pretty much have to use a linked list representation, regardless of the value of n. If you use sequential storage, you'll have to shift values right as you insert new elements (and shift them left as you erase them). This could require n shift operations when inserting into the left end of an n-element block of sequential storage.

   With linked lists, inserting values into (and deleting values from) the list takes constant time independent of where the value is inserted (or erased).

   ---

4. When using arrays to implement linked lists, is it necessary to have a free list (that is, must you use a free list when implementing a linked list with arrays)? If it is not necessary, explain why it might be useful to include a free list in your implementation.

   ---

   No, it isn't. All you need is a distinguished index value to mark the array elements that aren't being used.

   A free list makes it faster to find free array elements. With no free list, you have to search the index array for a free element, which might require that you look at (approximately) n values before you find a good on, given an n-element array. Using a free list, you can find a free element in constant time by looking at the head of the free list and adjusting the free-list head to point to the next free element, if any.

   See Nyhoff Section 8.3 for details.

   ---

This page last modified on 21 July 2000.