By now, you should have a rather sophisticated tree-set data structure that supports many useful operations. However, it isn't generic; it can only store int values, and it can only maintain them in ascending order. This week you will take your tree-set class and turn it into a class template, parameterized on both the element type and the comparison function.
This process will be mostly straightforward, although you probably have a significant amount of code written at this point, and you will need to be careful as you make changes to avoid breaking any functionality. Besides the TreeSet class itself, you will need to convert your iterator class into a class template as well. Finally, templates only live in .h files, without any corresponding .cpp file, so at the completion of this lab you will only have a treeset.h file.
Your TreeSet class template should take two type parameters, T (the element type) and Compare (the comparison function):
// Should end up with [1, 3, 4]
TreeSet<int> intSet{3, 1, 4, 1};
// Should end up with [4, 3, 1]
TreeSet<int, std::greater> reversedIntSet{3, 1, 4, 1};The element type T is straightforward to understand, but the comparison function Compare is a bit more nuanced. Conceptually, this will be a function of this form:
// Return true if lhs should come before rhs.
bool cmp(const T &lhs, const T &rhs);However, it should be obvious that cmp isn't a type; it's a function.
In C++, templates parameterized with functions can take function objects, which are classes (or structs) that implement operator() so that objects of that type may be invoked as if they were a function. In our case, Compare can be any class (or class template) that implements this function:
// Implement parentheses operator so we can be called like a function with
// two arguments of type T. Return true if lhs should come before rhs.
bool operator()(const T &lhs, const T &rhs)This might be an example function object for keeping int values in increasing order:
class IntLess {
public:
// Implement (a, b) to return true for a < b.
bool operator()(int a, int b) const {
return a < b;
}
};To use this function object, we must instantiate it, then use it as if it were a function:
IntLess cmp; // Comparator for int values
if (cmp(3, 5))
cout << "As expected, 3 is less than 5.\n";The C++ Standard Library provides a large number of common function objects for programs to use, and many of the collections and algorithms in the Standard Library can be customized with these function objects. Two of the most common ones are the std::less and std::greater class templates.
It is reasonable to expect that most users of your TreeSet class template will want the elements to be stored in increasing order, so make sure that your template specifies the default value of Compare to be std::less.
Converting your TreeSet class to a template is a substantial amount of code to update. Of course you are welcome to dive right in, but if you want to take a more cautious approach, here is one possible sequence of steps:
If you still have a treeset.cpp file, migrate all the code into the treeset.h file, and get rid of the treeset.cpp file. You can either put the function definitions within the class declaration (pretty gross), or you can put them after the class declaration, marking them with the inline keyword (slightly less gross). After completing this step, the tests from the previous lab should still pass.
Convert your TreeSet class to a class template, which takes the two template parameters specified above. Focus initially on migrating your code to support the element-type parameter T first, without worrying about Compare. This should get many of the tests for this lab to start passing.
Go through your TreeSet code, looking for code that enforces the element ordering properties. Make sure all of this code is written such that only the less-than operator < is used. (After making any changes, you can try running the test suite again.)
Once you have made any necessary changes, you can modify the code to instantiate the Compare class, and use the instance for comparing elements instead of the < operator.
At this point, you should be in the home stretch to get all tests to pass. If you have tests that persistently fail, consider whether your function declarations allow TreeSet objects with different comparison functions, or if some other constraint is not being imposed. In general, your TreeSet operations are only expected to work for TreeSet objects that have the same type and the same comparison function.
An exhaustive, template-aware test suite for your class is provided here. This program does the same testing as the previous suite, although the code is revised to use a template instead of a simple class. Additionally, it includes tests to exercise your TreeSet with strings, and also specifying the Compare function to alter the order in which elements are stored.
It is definitely possible to run into very subtle bugs in your template implementation, with seemingly no explanation. In general, you need to be very careful about how you specify class-template arguments to functions, or else your code may allow incompatible tree-set objects to be accepted by functions. Make sure to fix any test failures you encounter.
Make sure your Makefile continues to work with your code updates, and with the new tests from this week.
As always, make sure you have written Doxygen-format comments for all updates to your class this week. We expect your comments to be complete and concise. You are not required to provide structural commands for function arguments, return values, etc., unless you really want to.
Once you have completed the above tasks, submit your work through csman. Make sure to submit these files:
Makefiletreeset.htreeset.cpp THIS WEEK!You do not need to submit the test code; we will test your program with a fresh copy of these files.
Please also complete and submit a feedback survey with your submission, telling us about your experience with this assignment. Doing so will help us to improve CS11 Advanced C++ in the future.
Copyright © 2020 by California Institute of Technology. All rights reserved. Generated from treeset-3.md.