CS 311 Fall 2009
Assignment 5

Assignment 5 is due at 5 p.m. Thursday, November 5. It is worth 25 points.

Procedures

This is a group assignment. Please work in a group of 2 or 3. Each group only needs to turn in a single copy of the assignment. Under normal circumstances, each will receive the same grade on the assignment.

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

• Your answers should consist of one file: tsmarray.h, from Exercise A. This file (or an archive file containing it) should be attached to your e-mail message.
• Be sure to include the names of all group members in your e-mail.
• Suggestion: Cc the submission e-mail to all group members, so that I can reply to all indicating that it has been received.
• 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 (25 pts total)

Exercise A — Templated Smart-Array Class

Purpose

In this exercise, you will write a class template that acts as a “smart array”. It will not be quite as good as std::vector, but it will be significantly better than KSArray, 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 “TSmArray”, so that, for example, a TSmArray with value type double would be declared as TSmArray<double>.
• Implement your class template in file tsmarray.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 TSmArray 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 TSmArray.
  • 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 that referenced 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 TSmArray 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 TSmArray<T> should be one that does not allow modification of the items in its array. A non-const TSmArray 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. Self-assignment should do nothing (other than returning the object).
• 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: tsmarray_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 tsmarray_test.cpp.

Reminders

• Starting from class SmArray (on the web page) would not be a bad idea. Remember however, that TSmArray is a template, has no separate source file, and needs a rather different copy constructor than SmArray has.
• Every function needs documentation of preconditions, postconditions, and also whether it is exception-neutral, and the exception-safety guarantee it offers. (They are all supposed to be exception-neutral.)
• Every class needs class invariants.
• Every template needs requirements on (template parameter) types.
• Moving from a value type of int, as in class SmArray, 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 Friday, October 30 lecture slides.

CS 311 Fall 2009: Assignment 5 / Updated: 30 Oct 2009 / Glenn G. Chappell / ffggc@uaf.edu