ICS 65 Fall 2012
Project #5: Plug In Baby

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


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.

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.


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:

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.

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.


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.


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.