Welcome~~~


Another blog:
http://fun-st.blogspot.com/

It is easier to write an incorrect program than understand a correct one.

Saturday, February 12, 2011

Two Useful C++ Class

{From} http://pages.cs.wisc.edu/~hasti/cs368/CppTutorial/
{Note}  A wonderful tutorial, and especially introduce the 2 classes: string and vector

Contents


An Example C++ Class


C++ classes are similar to Java classes in many ways, but there are also important differences. Below is an example of a C++ class named IntList to be used to represent a list of integers; operations to add a value to the end of the list and to print the list are provided. The implementation uses a dynamically allocated array to store the integers; when the array is full, a new array of twice the size is allocated.
In Java, the class definition would all be in a single file. However, in C++ the code that defines the class would be split into two files: the first part specifies what member functions (methods) and data members (fields) the class will have. That code goes into a header file: a file with the extension .h. It is usually a good idea (though not a requirement as in Java) to give the file the same name as the class (so the file would be named IntList.h).
The second part of the class definition gives the code for the function bodies. That code goes in a source file (e.g., IntList.C).
The reason for splitting up the code is that it is generally a good idea to try to separate the interface from the implementation. Someone who wants to use an IntList really only needs to know what IntList operations are available; it is not necessary to know all the details about how an IntList is implemented. However, splitting up the code in this way is not required by C++. Some people prefer to include code for the member functions in the .h file when that code involves only one or two statements.
Here is the code that would be in IntList.h:
    #include <iostream>
    
    class IntList {
      public:
        IntList();                         // constructor; initialize the list to be empty
        void AddToEnd(int k);              // add k to the end of the list
        void Print(ostream &output) const; // print the list to output
    
      private:
        static const int SIZE = 10;      // initial size of the array
        int *Items;                      // Items will point to the dynamically allocated array
        int numItems;                    // number of items currently in the list
        int arraySize;                   // the current size of the array
    };
Things to note about the example so far:
  • The class declaration must end with a semi-colon.
  • The public and private members are grouped (as opposed to Java, where each method and each field is declared either public or private). It is generally considered a good idea to put the public members first, but that is not a C++ requirement.
  • As in Java, the class's constructor function must have the same name as the class, and no return type (not even void).
  • Function Print is declared to be a const function. In general, member functions that do not change any of the data members of the class should be declared const. The reason for this is that an IntList may be passed as a const-reference parameter. For example, suppose that the IntList Print member function was not declared const. Then the following code would cause a compile-time warning or error:
      void f(const IntList &L) {
         L.Print(cout);
      }
        
    Because L is a const-reference parameter, it is the compiler's job to be sure that L is not modified by f (and that means that no data members of L are modified). The compiler doesn't know how the Print function is implemented; it only knows how it was declared, so if it is not declared const, it assumes the worst, and complains that function f modifies its const-reference parameter L.
  • As in Java, a class can contain static data members. Every instance of the class will include its own copy of each of the non-static data members (e.g., each IntList object will include its own Items array, numItems integer, and arraySize integer), but there will be only one copy of each static data member for the whole class.
  • Only static data members can be initialized as part of the class declaration. Other data members are initialized by the class's constructor function(s).
Here is the code that would be in IntList.C (the actual code for the AddToEnd and Print functions has been omitted):
    #include "IntList.h"
    
    IntList::IntList(): Items(new int[SIZE]), numItems(0), arraySize(SIZE) {
    }
    
    void IntList::AddToEnd(int k) {
       ...
    }
    
    void IntList::Print(ostream &output) const {
       ...
    }
Things to note about this part of the example:
  • It is important to include the corresponding .h file; otherwise, you will get compile-time errors. In the #include, the name of the file is enclosed in quotes, not in angle brackets. Angle brackets are used for including standard library header files, and quotes are used for including your own header files (this tells the compiler where to look for the header file).
  • To tell the compiler that you are defining the member functions of the IntList class, you must prefix each function name with: IntList:: (note that this prefix comes after the function's return type).
  • The definition of the IntList constructor uses a member initialization list to initialize the three fields. This is equivalent to the following code:
      IntList::IntList() {
                   Items = new int[SIZE];
                   numItems = 0;
                   arraySize = SIZE;
               }
             
    In general, a member initialization list consists of a list of data member names with their initial values in parentheses, separated by commas. The initial value does not have to be a constant; it can be any expression. It is OK to initialize some data members in the member initialization list, and to initialize others using code inside the body of the constructor function. The member initialization list is executed before the body of the function, so if you initialize a data member in the member initialization list, it will already have its initial value inside the body of the constructor function. The main reason to use a member initialization list is when a data member is itself a class object, and you don't want the default initialization of that object. If you initialize the data member inside the body of the constructor function it will already have been initialized using its default (no-arg) constructor, which is a waste of time.

Constructor Functions

As in Java, constructor functions can be overloaded (there can be multiple constructors for a class, as long as each has a different number and/or type of parameters). In C++, a constructor function is called either when a class object is declared:
or when the object is dynamically allocated: To use a constructor with parameters, just put the values for the parameters in parentheses as follows:

TEST YOURSELF NOW


  1. Extend the IntList class defined above by adding a member function called Length. The function should return the number of items currently in the list. Write the new declaration that would be added to IntList.h as well as the new code that would be added to IntList.C (write the complete code for the new function , not just ... as in the example).
  2. Add a 2-argument constructor to the IntList class to allow an IntList to be initialized to contain n copies of value v. (So the two arguments are n and v, both of type int.) Again, write both the new declaration that would be added to IntList.h, and the new code that would be added to IntList.C.
solution

Two Useful Standard Classes: string and vector

The string class

To use the string class you must #include <string> (be sure that you do not include string.h, because then you will get the header file for C-style strings rather than for the C++ string class).

  • A string variable can be declared with or without an initial value:
      string s1;             // s1 is initialized to the empty string
      string s2("hello");    // s2 is initialized to the string "hello"
      string s3 = "goodbye"; // s3 is initialized to the string "goodbye"
  • The string class provides a size function:
      string s1, s2 = "hello";
      cout << s1.size();         // s1's size is 0
      cout << s2.size();         // s2's size is 5
  • Two strings can be compared using ==
      string s1("abc");
      string s2;
      s2 = "abc";
      if (s1 == s2) ...    // yes!  the two strings ARE equal
  • Strings can be concatenated using the + operator
      string s1("hello");
      string s2("goodbye");
      string s3 = s1 + " and " + s2;  // the value of s3 is "hello and goodbye"
  • The individual characters in strings can be accessed or updated using indexing (starting with 0), but you cannot index beyond the current length of the string.
      string s1 = "hello";
      for (int k=s1.size()-1; k>=0; k--) cout << s1[k];  // write s1 backwards
      for (int k=s1.size()-1; k>=0; k--) s1[k] = 'a';    // change s to "aaaaa"
      s[10] = 'a';                                       // ERROR! s only has 5
                                                         // chars
More detailed documentation on strings is available: click here.

The vector class


To use the vector class you must #include <vector>. A vector is similar to an array, but vectors provide some operations that cannot be performed using C++ arrays, and vectors can be passed both by value and by reference (unlike C++ arrays, which are always passed by reference). Unfortunately, there is no bounds checking for vectors (i.e., an index out of bounds does not necessarily cause a runtime error).

  • A vector variable is declared with the type of its elements and its size; for example:
      vector <int> v1(10);  // v1 is a vector of 10 integers
      vector <char> v2(5);  // v2 is a vector of 5 characters
    The specified size can be any expression that evaluates to a non-negative integer value.
  • Use indexing to access the elements of a vector as you would for an array:
      vector <int> v(10);
      for (int k=0; k<10; k++) {
          v[k] = 3;
      }
  • The vector class provides a size function:
      vector <int> v1(10);
      vector <double> v2(5);
      cout << v1.size();         // v1's size is 10
      cout << v2.size();         // v2's size is 5
  • The vector class provides a resize function:
      vector <int> v(1);
      v[0] = 10;
      v.resize(2*v.size());
      v[1] = 20;
      v.resize(1);
    The resize operation preserves as many of the old values as possible (so in the example, after the first resize operation, v[0] is still 10; after the second resize operation, v[0] is still 10, but there is no element of v equal to 20).
  • Two vectors can be compared using == (they are equal iff they have the same size, and corresponding values are the same).
  • One vector can be assigned to another using = (the types of the two vectors must be compatible; e.g., if the vectors are named v1 and v2, the assignment v1 = v2 is OK iff the assignment v1[0] = v2[0] is OK). The size of the vector being assigned to doesn't matter; it is changed after the assignment to be the same as the size of the vector being assigned from (for example, if v1.size() == 2, and v2.size() == 10, the assignment v1 = v2 is fine -- after it is executed, v1.size() == 10). Assigning from one vector to another does not introduce aliasing; for example, after the assignment v1 = v2, changing an element of v1 has no effect on v2 (or vice versa).
  • A function can return a vector (a function cannot return a C++ array).
      vector <int> f( ) { ... }
  • A vector can be passed by value or by reference (a C++ array is always passed by reference).
      void f( vector  A );  // A is passed by value
      void f( vector  &B ); // B is passed by reference

TEST YOURSELF NOW


  1. Write a function named NonEmpty that has one parameter, a vector of strings V, and that returns another vector of strings that contains just the non-empty strings in V. For example, if parameter V contains the 6 strings:
      "hello", "", "bye, "", "", "!"
    then function NonEmpty should create and return a vector that contains the 3 strings:
      "hello", "bye, "!"
  2. Write a function named Expand that has one parameter, a vector of ints V. Expand should change V so that it is double its original size, and contains (in its first half) the values that were originally in V. Test your function with the following main function:
      #include <iostream>
      #include <vector>
      
      int main() {
        vector  v(1);
        
        for (int k = 1; k <= 16; k++) {
          if (v.size() < k) {
            cout << "vector size before calling Expand: " << v.size() << endl;
            Expand(v);
            cout << "vector size after calling Expand: " << v.size() << endl;
          }
          v[k-1] = k;
        }
        cout << "[ ";
        for (int k = 0; k < v.size(); k++) {
          cout << v[k] << ' ';
        }
        cout << "]\n";
        return 0;
      }
    When you run this program, the output should be:
      vector size before calling Expand: 1
      vector size after calling Expand: 2
      vector size before calling Expand: 2
      vector size after calling Expand: 4
      vector size before calling Expand: 4
      vector size after calling Expand: 8
      vector size before calling Expand: 8
      vector size after calling Expand: 16
      [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ]
solution

Solutions to Self-Study Questions


Test Yourself #1


Question 1:
To extend the IntList class to include member function Length, the following would be added to the public part of the class declaration (in the file IntList.h):
    int Length() const;
Note that Length should be a const member function because it does not modify any fields. The code for the Length function (to be added to the file IntList.C) is:
    int IntList:: Length() const {
        return numItems;
    }
Question 2:
To extend the IntList class by adding a 2-argument constructor, the following would be added to the public part of the class declaration:
    IntList(int n, int v);
and the following would be added to IntList.C:
    IntList::IntList(int n, int v): Items(new int[SIZE]), numItems(0),
                                    arraySize(SIZE) {
      for (int k=0; k<n; k++) AddToEnd(v);
    }
Note that this version of the 2-argument constructor first initializes the list to be empty (by setting numItems to zero), then uses the AddToEnd function to add value v to the list n times. Of course, the code that stores v in the Items array could be included here instead of calling AddToEnd; however, it is usually better to call a function than to duplicate code.

Test Yourself #2

Question 1:
Note that this solution make two passes through vector V: the first pass counts the number of non-empty strings in vector V, and the second pass fills in the new vector newV (after it has been declared to have the appropriate size). An alternative would be to start by defining newV to have size 0, and make a single pass through vector V, resizing newV by 1 each time another non-empty string is found in V. The problem with that approach is that resizing a vector from size n to size n+1 probably takes time O(n) (to copy the values). (The actual time depends on the implementation of resize; a straightforward implementation that allocates exactly the amount of memory requested will be O(n).) Therefore, the alternative approach would be O(n2), while the solution given above is O(n), where n is the number of non-empty strings in vector V.
Question 2:
Note that it is crucial to make Expand's parameter a reference parameter.

No comments:

Post a Comment