CS 170 - Programming Assignment #5

Information

• Handout
• Interface: HTML Text
• Partial implementation: HTML Text (Be sure to Doxygenize all of the function header comments properly, even functions that are provided for you.)
• Sample driver #1 (using integers): HTML Text output-1.txt
• Sample driver #2 (using structs): HTML Text output-2.txt
• FAQ for this assignment
• Sample command lines for compiling:

  g++ -o gnu driver-sample.cpp -O2 -Wall -Wextra -ansi -pedantic -Wconversion
  
  cl /W4 /WX /Zi /MT /EHsc /Oy- /Ob0 /D_CRT_SECURE_NO_WARNINGS /Fems.exe driver-sample.cpp
  

  Notice that the command lines above DO NOT include List.cpp. This is not a mistake. Including List.cpp on the command line will lead to problems and may produce very strange error messages.

• Additional stress test cases:
  • Driver: HTML Text
  • Output:
    1. Individual tests
    2. Combined

  • Random number generator files (we've used them in previous assignments)
    • - Header file (PRNG.h): HTML Text
    • - Implementation (PRNG.cpp): HTML Text
    
    You can select the test to run by putting the number on the command line. For example, assuming your executable is named foo.exe, to run test #3 you would do this:

    foo.exe 3
    

    If you want to time your program, use the time program (from Cygwin):

    c:\cygwin\bin\time -p foo.exe 3
    

    To run all of the tests, pass the number 0 or just leave it blank:

    c:\cygwin\bin\time -p foo.exe
    

    You need to provide the entire path to the time program because there is a built-in time command in Windows (which isn't useful for this).

    Linux and Mac OS users just have to type this:

    time ./foo
    

typename Usage

• Note that this implementation of the new_node method won't compile:

  template <typename T>
  List<T>::Node *List<T>::new_node(const T& data) const
  {
    Node *node = new Node(data); // create the node
    node->next = 0;              // no next pointer yet
    return node;
  } 
  

  The error message from g++ is this:

  List.cpp:407:1: error: need 'typename' before 'CS170::List::Node' because 'CS170::List' is a dependent scope
   List::Node *List::new_node(const T& data) const
   ^
  

  Corrected:

  template <typename T>
  typename List<T>::Node *List<T>::new_node(const T& data) const
  {
    Node *node = new Node(data); // create the node
    node->next = 0;              // no next pointer yet
    return node;
  } 
  

  Also notice the use of the typename keyword in the overloaded operator<< method in the implementation file.

  ---

  More details

  template <typename T>
  void f1(const T& a)
  {
    int b;
    T::foo * b;    // What is the meaning of this?
    T::bar * ptr;  // What is the meaning of this?
  }
  

  The error message:

  In function `void f1(const T&)':
  error: 'ptr' was not declared in this scope
  

  Let's look at the class:

  class X 
  {
    public:
      static const int foo = 10;
      typedef int bar;
  };
  

  The problem is more noticeable if we actually instantiate the class and call the function:

  int main(void)
  {
    X a;
    f1(a);
  
    return 0;
  }
  

  This gives us these errors:

  main.cpp: In function `void f1(const T&)':
  main.cpp:13: error: `ptr' undeclared (first use this function)
  main.cpp:13: error: (Each undeclared identifier is reported only once for each function it appears in.)
  main.cpp: In function `void f1(const T&) [with T = X]':
  main.cpp:19:   instantiated from here
  main.cpp:12: warning: statement has no effect
  main.cpp:13: error: dependent-name ` T::bar' is parsed as a non-type, but instantiation yields a type
  main.cpp:13: note: say `typename  T::bar' if a type is meant
  main.cpp: At global scope:
  main.cpp:10: warning: unused parameter 'a'
  

  The whole program:

   1.  class X 
   2. {
   3.   public:
   4.     static const int foo = 10;
   5.     typedef int bar;
   6. };
   7. 
   8. template <typename T>
   9. void f1(const T& a)
  10. {
  11.   int b;
  12.   T::foo * b;    // What is the meaning of this?
  13.   T::bar * ptr;  // What is the meaning of this?
  14. }
  15. 
  16. int main(void)
  17. {
  18.   X a;   // instantiate an X object
  19.   f1(a); // call f1 with [T = X]
  20. 
  21.   return 0;
  22. }
  

  Corrected:

  template <typename T>
  void f1(const T& a)
  {
    int b;
    T::foo * b;            // Implicit assumption: foo is non-type (value)
                           //   (multiplication expression)  
    typename T::bar * ptr; // Explicit: bar is a type
                           //   (pointer declaration)  
  }
  

  Stroustrup's The C++ Programming Language (Special Edition) discusses this in Appendix C.13.5.