CS 311 Spring 2008
Assignment 5

Assignment 5 is due at 5 p.m. Tuesday, April 8. It is worth 20 points.

Procedures

E-mail answers to the exercises below to ffggc@uaf.edu, using the subject “DA5”.

• Your answers should consist of one file: seqt.h, from Exercise A. This file (or a single archive file containing them) should be attached to your e-mail message.
• Be sure to include your name in your e-mail.
• I may not read your homework e-mail immediately. If you wish to discuss the assignment (or anything else) with me, send me a separate message with a different subject line.

Exercises (20 pts total)

Exercise A — “Smart Array” Class Template

Purpose

In this exercise, you will write a smart-array class. The class will be somewhat smarter than SArray, from Assignment 2; in particular, the array will be resizable. It will also be exception-safe and efficient.

Key to this assignment is exception safety. Make sure that exceptions thrown by value-type operations are properly handled, and that all safety guarantees are documented.

And as always, make your code high quality.

Instructions

Implement a C++ class template that manages and allows access to a resizable array. The type of items in the array should be specified by the client. Be sure to follow the coding standards. All standards now apply!

• Call your class template “SeqT”, so that, for example, a SeqT with value type double would be declared as a SeqT<double>.
• Implement your class template in file seqt.h. Since this is a template, there should be no associated source file.
• Your class template should act as if it maintains a single array with a given size and value type.
• Include the following functions, and no others, in the public interface of your package:
  • Default ctor: creates a SeqT of size zero.
  • Copy ctor, copy assignment, dctor.
    • The copy operations should create an entirely new copy of the data, so that modifying the copy does not change the original.
  • 1-parameter ctor. One parameter: a non-negative integer giving the number of items in the SeqT.
  • Bracket operator. One parameter: an integer subscript from 0 to size–1 (where size is the number of items in the array), return a reference to the proper item. Hint: “integer” does not necessarily mean “int”.
  • size. No parameters. Returns the number of items in the array.
  • empty. No parameters. Returns a boolean value indicating whether the array has size zero.
  • resize. One parameter: the new size. Resizes the array, maintaining the values of all data items that lie in both the old and the new array. May need to reallocate-and-copy, but only does so when necessary.
  • insert. Two parameters: an iterator and a data item. Inserts the data item just before the position pointed to by the iterator. Returns an iterator to the inserted item.
  • remove. One parameter: an iterator. Removes the item referenced by the iterator. Returns an iterator to the item just after the removed item (or end if the removed item was the last).
  • begin. No parameters. Returns an iterator to item 0 in the array.
  • end. No parameters. Returns an iterator to one-past the end of the array.
  • swap. One parameter: another SeqT having the same value type. Swaps the values of *this and the parameter. Must be constant-time and offer the No-Throw Guarantee.
• Include the following member types in your class:
  • value_type. The type of each item in the array.
  • size_type. The type of the size of an array and an index into an array.
  • iterator. The type of a random-access iterator that allows modification of the item it references.
  • const_iterator. The type of a random-access iterator that does not allow modification of the item it references.
• A const SeqT<T> should be one that does not allow modification of the items in its array. A non-const SeqT should allow such modification.
• You may not use any C++ Standard Library classes in your implementation. (You may use simple types, like std::size_t and algorithms, like std::swap, std::rotate, and std::copy.)
• You may not create any new implicit type conversions. Hint: 1-parameter constructors, “explicit”.
• All of your public functions should have the highest reasonable levels of efficiency and exception safety. In particular:
  • All public functions must offer at least the Basic Guarantee.
  • Where it is absolutely necessary to offer the No-Throw Guarantee, it must be offered.
  • Copy assignment should be written in the exception-safe manner discussed in class.
• All of your functions must be exception-neutral; that is, exceptions thrown by value-type operations must propagate unchanged to the caller.
• The resize and insert functions should be written so that insert-at-end is amortized constant time.
• You may not forbid any member function of the value type from throwing, except for the destructor.

Test Program

I have written a test program: seqt_test.cpp. If you compile and run your package with this program (unmodified!), then it will test whether your package works properly.

Do not turn in seqt_test.cpp.

Reminders

• Starting from class Sequence (on the web page) would be a good idea. Remember however, that SeqT is a template, has no separate source file, and needs a rather different copy ctor than Sequence has.
• Every function needs documentation of preconditions, postconditions, and exceptions thrown, and (now) exception-safety guarantee.
• Every class needs class invariants.
• Every template needs requirements on (template parameter) types.
• Moving from a value type of int, as in class Sequence, to an arbitrary value type, means that there are now many more possible sources of error conditions. Check every single one, and make sure you deal with it appropriately.
• Sample code and ideas are on the lecture slides.

CS 311 Spring 2008: Assignment 5 / Updated: 2 Apr 2008 / Glenn G. Chappell / ffggc@uaf.edu