ICS 65 Fall 2012, Project #5: Plug In Baby

Due date and time: Sunday, December 9, 11:59pm

Introduction

Previously, you've explored the C++ standard library and built your understanding of many of the classes and functions that comprise it, as well as the general approaches used throughout it. As we've gradually lifted the veil on the C++ language, we've learned more and more about the techniques that are used to build the kinds of functionality you find in the standard library and to make its components well-behaved (e.g., template functions, template classes, copy constructors, assignment operators, destructors, and so on).

One of the standard library's strengths is its extensibility, i.e., the ability it gives its users to extend it with new functionality that plugs cleanly into its existing functionality. For example, new containers that follow the appropriate set of rules will automatically be compatible with standard generic algorithms; new generic algorithms will similarly be compatible with existing containers in the library; and, of course, new algorithms will also interact nicely with new containers. In any programming language, there is value in everyone in its community of users agreeing on how certain commonly-occurring problems will be solved; C++ is no different.

This project is an exploration of what it takes to build a standard-library-compatible container, and how to plug it into existing algorithms. We'll discover that we will also seamlessly plug into other C++ language features, such as the range-based for loop if we commit ourselves to following standard-library-compliant rules. Finally, we'll (optionally) consider the performance optimization afforded by extending the Big Three into the Big Five instead and some additional operations we could add if we wanted to make our sorted list more flexible.

A container for us to build

You are no doubt familiar already with the concept of a linked list, which is a collection of nodes, each of which stores one data element. The nodes are linked together in different ways (e.g., singly, doubly, circularly) depending on one's requirements, but the concept is similar no matter the implementation details: linked lists trade away the ability to easily jump from one node to another far-away node, while eliminating specific requirements about where elements can be stored in memory in relation to ecah other, allowing other things, such as being able to insert new elements without moving existing ones, to run more smoothly.

In this project, we'll build a sorted list, a linked list in which elements are stored in ascending order. It will be "well-behaved" in the ways we've discussed previously — most notably, it will manage its own memory appropriately — and it will support some of the basic idioms from the standard C++ library, such as providing iterators and the functions that create them, so that it will work with compatible generic algorithms and the range-based for loop.

The program

In this project, you'll build a standard-library-compliant implementation of a sorted list, the specific requirements for which are described below. Additionally, you'll build a test program that exercises your implementation, both in terms of how its individual member functions perform, and also how well it plugs into existing standard library algorithms.

There is no stated number of test cases that are required; your test program is done when you've covered all of the cases that you feel are important in order to verify that your sorted list is not only working on its own, but that it plugs into the standard library correctly.

The specific requirements

The ics65::sorted_list template class

Your primary goal is to write a template class called sorted_list in a namespace called ics65, which takes a single type parameter specifying what kind of elements it stores. So, for example, an ics65::sorted_list<int> would be a sorted list of integers. (Note that since we're attempting to write a template class that plugs into the standard library, we're adopting the standard library's naming convention in which names are all lowercase and words are separated by underscores.)

Fundamentally, your class should be well-behaved, in the sense that we've been discussing it this quarter: it cleans up any memory it allocates and it can be copied (with the copies being entirely separate from one another). Since you will no doubt need to dynamically allocate your nodes, the Big Three become necessary. Additionally, it will need to be as exception safe as you can make it, meaning that each function should provide either the basic guarantee, the strong guarantee, or the nothrow guarantee in the case that they throw exceptions.

The requirements for your template class follow.

It must contain a no-argument constructor that initializes the list to be empty
It must have a destructor, copy constructor, and overloaded assignment operator, because you'll need these to make it well-behaved
It must include the following member functions:
- add(), which takes a T object and adds it in the appropriate position in the list, returning void
- erase(), which takes an iterator and removes the object at that position in the list, returning void. Note that this function will either need to support every kind of iterator, or you'll need overloads that support each one
- This function should throw a std::out_of_range if the iterator is referring to the "past end" or "past rend" position (see below)
- clear(), which takes no parameters, makes the list empty, and returns void
- size(), which returns a size_t indicating the number of elements in the list. (size_t is a built-in type in C++ that indicates the size of a container; it's generally compatible with unsigned int.)
- empty(), which returns true if the list is empty and false otherwise.
Decide which of these member functions should be marked const, based on whether they change the list or not. If they can be made const while preserving their semantics, do it.
It must support forward iterators that allow reading from, but not writing to, the elements of the list. It's important that the iterators do not allow list elements to be modified, because they otherwise could be used to subvert the ordering property of the list. To support forward iterators, there are a few things you'll need to do:
- Two types, ics65::sorted_list<T>::iterator and ics65::sorted_list<T>::const_iterator, both of which represent a forward iterator that iterates through elements from first to last and allows them to be read but not written. (The reason we need both typenames even though they're the same is because users of standard-library-compliant containers will expect both types to be there.)
- Two more types, ics65::sorted_list<T>::reverse_iterator and ics65::sorted_list<T>::reverse_const_iterator, both of which represent a forward iterator that iterates through elements in reverse and allows them to be read but not written.
- All of these iterator types must support the necessary operator overloads, so that they are compatible with standard algorithms:
  - operator==, which compares two iterators to see if they refer to the same location
  - operator!=, which compares two iterators to see if they do not refer to the same location
  - operator++ (in both pre- and post-increment form), which advances the iterator (to the next node, in the case of a regular iterator; to the previous node, in the case of a reverse iterator)
  - operator* (the dereference operator, not multiplication!) and operator->, so that the iterator will function similarly to a pointer. Note that both of these operators should provide read-only access to the elements of the list no matter what (i.e., they return references or pointers to const values)
  Decide which of these operator overloads should be marked const, based on whether they change the meaning of the iterator or not; if they can be marked const while preserving their semantics, do it.
- There are a few other "marker" types that are required of your iterator. The easiest way to get these markers in place is to implement your iterator using a class that derives from std::iterator<std::forward_iterator_tag, T> (where T is the type of element in the list), which immediately fills in a few details that are necessary for forward iterators.
It must support the standard functions used to create iterators and reverse iterators on a container:
- begin(), which returns an iterator (or const_iterator, if the sorted_list is const) referring to the list's first element
- end(), which returns an iterator (or const_iterator, if the sorted_list is const) referring to the list's "past end" position, just beyond its last element
- rbegin(), which returns a reverse_iterator (or reverse_const_iterator, if the sorted_list is const) referring to the list's last element
- rend(), which returns a reverse_iterator (or reverse_const_iterator, if the sorted_list is const) referring to the list's "past rend" position, just before its first element
The only kind of comparison operator that should be used on T objects is operator< (i.e., you can compare them with the < operator, but not >, ==, <=, and so on). This is a fairly typical restriction in the standard C++ library, made so that controlling ordering requires overloading only one operator.

Since there are iterators that traverse the list in both directions, your linked list implementation will need to be doubly-linked. Note, too, that the notion of "past end" and "past rend" is most simply implemented by having special nodes at the beginning and end of the list, so your iterator can be fundamentally based around a pointer to a node.

Testing

Write a program that runs some unit tests against your sorted_list template class to ensure that it works as you expect. As C++ lacks a built-in unit testing framework, this is best done by simply writing a collection of functions and calling each of them explicitly from main(). Your goal is a program that tells you when something is broken, so focus on writing output that describes problems, as opposed to just dumping pages of debug output that you would need to manually verify.

As stated above, there is no explicit number of test cases that are required; your test program is done when you have covered everything you believe is important.

There are a couple of things from the standard library worth trying, just to get a feel for whether your sorted_list template class is plugging into the standard library as it should:

If you've followed the requirements above, your sorted_list should be compatible with the range-based for loop from C++11, which would make something like this legal:
```
ics65::sorted_list<std::string> theList;

// add some elements to theList

for (const std::string& s : list)
{
    std::cout << s << std::endl;
}
```
The range-based for loop requires begin() and end() functions, as well as standard-library-compliant iterators.
Additionally, generic algorithms in the standard library that use only forward iterators and don't modify the underlying list should be supported automatically, which would also make something like this legal:
```
ics65::sorted_list<int> aList;

// add some elements to aList

std::for_each(aList.begin(), aList.end(), [](int i) { std::cout << i << std::endl; });
```
Note that many of the generic algorithms in the standard library require other behavior — random-access iterators, the ability to change or rearrange the elements of the list — that would not be appropriate; we don't expect these to be compatible with our sorted_list.

Additional challenges to improve performance and flexibility

There are a few things we can do to improve the performance and flexibility of our template class. None of these is required and, as usual, extra credit is not offered, but if you're looking for a few additional things to improve your template class, here are some things you could consider.

Instead of supporting only forward iterators, support bidirectional iterators instead. You'd still want your iterators to be read-only (i.e., not to be able to change elements in the list), so that iterators can't be used to subvert the ordering properties of the list, but supporting the ability to traverse in both directions can be handy.
C++11 supports the ability to write move constructors and move assignment operators, which are called by the compiler in some special circumstances, such as when an object is being created as a copy of an existing object that is temporary or is on the verge of death, in which case the act of copying can be made more efficient. They also improve the performance of std::swap, which nowadays uses move semantics to speed things up. When I've occasionally mentioned that the Big Three is really the Big Five in C++11, that's what I meant; move constructors and move assignment operators are the fourth and fifth thing.
Allow a user of our sorted_list to configure how sorting is done by accepting a constructor parameter, a std::function<bool(const T&, const T&)>, which takes the place of the < operator for comparing T objects for the purposes of ordering them. Make sure there's a default for this parameter, so it defaults to < when not specified. (See std::less in the standard library for a handy way to set up that default.)
We can make our sorted_list more like the built-in std::list by adding a few additional useful operations to it: merge, remove, remove_if, unique, and lexicographical comparisons of the entire list using relational operators like operator== and operator<.

Starting point

This project has no starting point, as I'd like you to build it from scratch, though you do need to make sure you meet the requirements laid out above.

Deliverables

Submit the source (.cpp) and header (.h) files that comprise your sorted list template class and your test program. Afterward, take a moment to be sure that you submitted all of the files; if you missed one, we won't be able to compile and run your program, which can result in a substantial penalty, since we won't be able to evaluate your program's correctness.

Follow this link for a discussion of how to submit your project via Checkmate. Be aware that I'll be holding you to all of the rules specified in that document, including the one that says that you're responsible for submitting the version of the project that you want graded. We won't regrade a project simply because you accidentally submitted the wrong version.

Limitations

While the goal here is to plug into existing standard library functionality, you are required to implement your own linked list structure and manipulate nodes and their links by hand, as opposed to using std::list for that purpose.