1. Containers c1 and c2 are either sets or multisets. Suppose the following code runs without error:

   X c1(c2.begin(), c2.end());
   assert(c1.size() < c2.size());
   

   What is X, the type of c1? What is c2's type? Explain your answers.

   ---

   After being initialized from c2, c1 has fewer values than does c2. The only container that we have studied so far that can drop values being inserted into it is the set, which doesn't insert duplicate values; c1 can only be of type set<T>. Because c2 contains duplicate values, it can't be of type set<T>, and so must be of type multiset<T>.

   ---

2. Explain the differences, if any, between finding a value v in a set or multiset using the find(v) member function and using the lower_bound(v) member function.

   ---

   The s.find(v) member returns an iterator to the value v in s if v exists, otherwise it returns s.end(). The s.lower_bound(v) member function returns an iterator to the leftmost value in s that is not smaller than v, otherwise it returns s.end() if no such value exists.

   If s.lower_bound(v) returns a valid iterator, that iterator may point to a value greater than v. If s.find(v) returns a valid iterator, that iterator always points to v. Also, for multisets, s.lower_bound(v) returns the leftmost possible iterator while s.find(v) returns any possible iterator.

   A couple of people tried to argue for different execution efficiencies, but both find(v) and lower_bound(v) have O(log n) worst case execution-time behavior.

   ---

3. Explain how equality between values in sets or multisets is determined.

   ---

   Given a set's comparison function C, two values x and y from the set are equal if both C(x, y) and C(y, x) are false.

   A number of people gave answers using the operator ==(), which is not at all correct. Most people mentioned using operator <() to determine equality, but it's actually the compare function that's used. It may be that the compare function uses < internally, but it's not a requirement.

   ---

4. Define the following tree-related terms:
   • parent
   • child
   • sibling
   • root
   • leaf

   Your definitions should be in English; don't draw any pictures.

   ---

   A node N's parent is the node pointing to N in the tree; a node has at most one parent.

   A node N's child is a node to which N points.

   Two nodes are siblings if they have the same parent.

   The root is the only node in the tree with no parent.

   A leaf is a node with no children.

   See Nyhoff page 519 for more details.

   ---

This page last modified on 3 August 2000.