1.
(a) The map would not be an acceptable parameter because
  operator+ is not defined for pair. You would get a compiler error.

(b) Not all iterators support + (only random access iterators do).
  In particular, list and set could not be used in canSum
  if the alternative was in the code.

(c) The running time is O(N^2), independent of the type of container.

(d) Since it takes 64 seconds to run 100,000 elements on computer A,
  it must take 4 seconds to run 100,000 elements on computer B.
  If we now have twice as much time, for an O(N^2) algorithm, we
  can solve a problem roughly sqrt(2) = 1.414 times as large.
  So in 8 seconds, we could solve a problem of size roughly 140,000.


2.
  map<const char *, int, LessThan> people;

  class LessThan
  {
    public:
      bool operator() ( const char *lhs, const char *rhs ) const
      {
        return strcmp( lhs, rhs ) < 0;
      }
  };


3.
  To start off, the 1,000,000 strings themselves take 16 bytes each of
  overhead plus the space to store 12,000,000 characters. So the
  strings require 28 Meg no matter what we do.

  In a list, we have the excess of two pointers per node; with
  1,000,000 nodes and 4 byte pointers, thats 8 Meg. There is also
  the overhead of maintaining 10,000 lists (i.e. storing front and back),
  but this is negligible (perhaps 80K), and is safe to ignore.

  In a vector, we have the excess of roughtly 1/3 extra strings,
  which will be empty. This is roughly 333,000 strings at 16 bytes each,
  or 5.3 Meg. There's also the negligible overhead of maintaining
  10,000 vectors (i.e. storing a pointer, length, capacity), but
  that's only 120K, and we can ignore it too.

  So the vector is using up about 3 Meg less than a list; perhaps
  slightly less. And just storing the strings is 28 meg. So the
  difference works out to 33 Meg for vectors versus 36 Meg for lists.
  
  If we are desperate for space, we would prefer the vector, but the
  actual difference here is only about 10%.

4.
(a)
  template <class Comparable>
  class DoubleEnded
  {
    public:
      bool isEmpty( ) const                    // O(1)
        { return items.empty( ); }
      bool makeEmpty( )                        // O(N log N )
        { Comparable dc; while( !isEmpty( ) ) deleteMin( dc ); }
      void insert( const Comparable & x )      // O(log N)
        { items.insert( x ); }     
      const Comparable & findMin( ) const      // O(log N)
        { return *items.begin( ); }
      const Comparable & findMax( ) const      // O(log N)
        { return *--items.end( ); }
      void deleteMin( Comparable & x )         // O(log N)
        { x = findMin( ); erase( items.begin( ) ); }
      void deleteMin( Comparable & x )         // O(log N)
        { x = findMax( ); erase( --items.end( ) ); }

   private:
     set<Comparable> items;
     typedef set<Comparable>::iterator iter;
     typedef set<Comparable>::const_iterator citer;
  };


  <<ALTERNATIVE USING DIFFERENT VERSIONS OF erase>>

      bool makeEmpty( )                        // O(N)
        { items.erase( items.begin( ), items.end( ) );
      void deleteMin( Comparable & x )         // O(log N)
        { erase( x = findMin( ) ); }
      void deleteMin( Comparable & x )         // O(log N)
        { erase( x = findMax( ) ); }