Alg-Code: 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

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:
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:
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:

IntList L;  // L's no-arg constructor function is called

or when the object is dynamically allocated:

IntList *p;       // no constructor called yet
p = new IntList;  // now the no-arg constructor is called

To use a constructor with parameters, just put the values for the parameters in parentheses as follows:

IntList L(1, 10);          // L's 2-arg constructor will be called
IntList *p;
p = new IntList(0, 5, 22); // L's 3-arg constructor will be called

TEST YOURSELF NOW

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).
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:
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:

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:
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).
A vector can be passed by value or by reference (a C++ array is always passed by reference).

TEST YOURSELF NOW

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:
then function NonEmpty should create and return a vector that contains the 3 strings:

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:

vector <string> NonEmpty(vector <string> V) {
  // count the number of non-empty strings in V
  int num = 0;
  for (int k=0; k<V.size(); k++) {
    if (V[k] != "") num++;
  }
  
  // declare a vector of the right size and fill it in
  vector <string> newV(num);
  int index = 0;
  for (int k=0; k<V.size(); k++) {
    if (V[k] != "") {
      newV[index] = V[k];
      index++;
    }
  }
  
  // return result
  return newV;
}

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(n²), while the solution given above is O(n), where n is the number of non-empty strings in vector V.
Question 2:

void Expand(vector <int> &V) {
  V.resize(2*V.size());
}

Note that it is crucial to make Expand's parameter a reference parameter.

Alg-Code

Pages

Welcome~~~

Saturday, February 12, 2011

Two Useful C++ Class

Contents