Courses/CS 2124/Lab Manual/The Standard Template Library

From A-State Computer Science Wiki
< Courses‎ | CS 2124‎ | Lab Manual
Revision as of 13:08, 18 April 2014 by Matthew.hardin (Talk | contribs) (The STL Iterator)

Jump to: navigation, search

A portion of this lab is to be done during the scheduled lab time. The take-home programming assignment is to be turned in before the next lab; see the lab website. The in-lab portion is worth 40% of the lab credit; the programming assignment is worth the other 60%. See the website for details on how the programming assignment will be graded. You are not responsible for user errors in input unless specified in the assignment. Feedback will be provided explaining your grade on each assignment.

It is important that you complete each step before going on to the next, as the exercises build upon one another. You will find it helpful to diagram the action of each method or function as you go along. If you have difficulty in some step, DO NOT proceed before resolving it; seek assistance from your lab proctor. You will not be able to fully appreciate the remaining content of the lab and you are likely to compound the problem.


This lab introduces the use of STL, the C++ Standard Template Library, through a series of examples.

Topics Covered in this Lab:
  • STL iterators
  • STL algorithms
  • STL containers
Questions Answered in this Lab:
  • How does an STL iterator differ from a pointer in a conventional program?
  • How are STL algorithms used?
  • What type of STL container is appropriate to a given situation?
Demonstrable Skills Acquired in this Lab:
  • Understanding of how STL containers, iterators, and algorithms work together
  • Appreciation for what the STL can replace in a conventional program
Createproject.pngCreate a project oop12 with the empty C++ header and source files listed below; upon completion of the in-lab portion of this assignment, submit all of these files in zip file
Makefile// directs compiling and linking of others?
main.cpp// contains main function

The STL Iterator

This exercise begins by using an STL iterator to read integers from the standard input (the keyboard). Put an include for the header file iterator in file main.cpp. Create a function main in file main.cpp with the following code segment; note the definition and usage of the istream_iterator object input.

Verbatimcode.pngCode Illustration
   int a [100];
   int size = 0;
   cout << "Enter an integer (-1 to end): ";
   std::istream_iterator <int> input (cin);
   while (*input != -1)  // dereference
      a[size++] = *input;  // dereference
      cout << "Enter an integer (-1 to end): ";
      input++;  // increment
   }  // end while

Notice how iterator input is associated with input stream cin. Notice also how input is dereferenced and incremented as a pointer variable might be in a conventional C++ program.

Add a short loop to function main to print the contents of array a to the standard output cout; print one space between each pair of values.

Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate this output for the lab instructor.

The STL Algorithm

An STL algorithm can be used to print the contents of the array as well; add an include for the header file algorithm to file master.h and add the following to function main.

Verbatimcode.pngCode Illustration
   std::ostream_iterator <int> output (cout, " ");
   std::copy (a, a+size, output);
   cout << endl;

The STL algorithm copy will move everything from the location specified in the first parameter up to, but not including, the location specified in its second parameter to its third parameter. Since a is the name of an array, it is essentially the address of the first array element; the addition of size to a results in a location one past the last element stored in a. Notice how iterator output is associated with cout; the character-string parameter specifies what should be written between values.

The STL Container

An STL container can be used to store and manipulate data. In particular, the STL vector container can be used where an array might be used in a conventional C++ program. Add an include for the header file vector to file master.h and add the following to function main.

Verbatimcode.pngCode Illustration
   std::vector <int> v;
   cout << "\n\nEnter # for max subsequence search (-999 to end): ";
   std::istream_iterator <int> input2 (cin);
   while (*input2 != -999)
      v.push_back (*input2);
      cout << "Enter # for max subsequence search (-999 to end): ";
   }  // end while

The STL vector object v will be filled with numbers from the keyboard via another istream_iterator object, input2. The vector member function push_back is used to add data to the end of its object.

The values stored in a vector may be manipulated using an iterator. Add the following to function main.

Verbatimcode.pngCode Illustration
   std::vector<int>::const_iterator vIndx;
   for (vIndx = v.begin(); vIndx != v.end(); vIndx++)
      cout << *vIndx << ' ';
   cout << endl;

The vector member function begin returns a reference to the first item in the container; function end returns a reference to just past the last item in the container, hence the use of the != operator.

The same effect may be achieved with the copy algorithm; add the following to function main.

Verbatimcode.pngCode Illustration
   std::copy (v.begin(), v.end(), output);
   cout << endl;

Note here again how copy uses references to the first item and one past the last item in the container. FOR IN-LAB CREDIT: Demonstrate the results of copy for the lab instructor.

Example Problem: Maximal Subsequence

Consider now the problem of finding the subsequence in a series of values whose sum is maximal. A vector will be used to implement a search for this subsequence. A brute-force algorithm is developed here; a more elegant solution is to be devised in the homework.

Consider for example a sequence of five values: a_1, a_2, a_3, a_4 and a_5. There are five subsequences starting with a_1, and each of their sums must be considered: a_1 by itself, a_1 + a_2, a_1 + a_2 + a_3, a_1 + a_2 + a_3 + a_4, and a_1 + a_2 + a_3 + a_4 + a_5. Similarly, there are four subsequences starting with a_2, three with a_3, two with a_4 and just one with a_5 (a_5 by itself). In general, there will be n + (n-1) + (n-2) + \ldots + 1 = n(n+1)/2 subsequences to consider for n values. A nested loop can be written to generate these subsequences; the outer loop will keep track of the starting location while the inner loop keeps track of the ending location. Two iterators shall be used for this purpose. Add the following to function main.

Verbatimcode.pngCode Illustration
   std::vector <int>::const_iterator beginIndx;
   std::vector <int>::const_iterator endIndx;

   for (beginIndx = v.begin(); beginIndx != v.end(); beginIndx++)
      for (endIndx = beginIndx; endIndx != v.end(); endIndx++)
         // body;

The body of this loop must use another iterator, e. g., sumIndx, to move between beginIndx and endIndx, summing the elements between them. This sum should be compared to a running maximum sum; if it is found to be greater than the current maximum, the sum should be stored as the new maximum and the current beginning and ending indices should be saved. This being done, the results can be displayed with the following addition to function main.

Verbatimcode.pngCode Illustration
   cout << "maximal subsequence is ";
   std::copy (maxBeginIndx, maxEndIndx+1, output);
   cout << endl;

The iterators maxBeginIndx and maxEndIndx in the above code fragment are defined like beginIndx and endIndx in the preceding fragment. Note that maxEndIndx+1 is passed to algorithm copy here since copy always expects an ending location one past the last value to be copied.

Execute the program and verify that it is working correctly.

Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate the algorithm for input of the lab instructor's choosing.

Labsubmitsinglefile.png FOR IN-LAB CREDIT: Zip up these files: Makefile master.h main.cpp
Name the file and upload to CSCADE.