Now that you have gotten the basic tree-set data structure completed, it's time to implement several of the common features of C++ collection classes: initialization from a list of values, and support for iteration over the contents of the tree-set.
TreeSet
s and Initializer ListsSince C++11, the STL collections support initialization from a list of values, like this:
// Initialize a vector of 7 integer values
vector<int> v = {1, 1, 2, 3, 5, 8, 13};
// This syntax also works:
vector<int> v{1, 1, 2, 3, 5, 8, 13};
You can add list initialization like this to your own classes by using the std::initializer_list<T>
type, declared in the <initializer_list>
C++ standard header file. Just make a constructor that takes an initializer-list of values of the appropriate type, and you will also be able to initialize your tree-set like this:
TreeSet s1 = {2, 3, 5};
TreeSet s2{2, 3, 5};
TreeSet
IterationIn-order tree traversal is not terribly difficult to implement, but it is made more complicated by the standard C++ iterator abstraction, which allows one to access the current element, or advance to the next element. Your TreeSet
class will need to provide functionality similar to the C++ iterator abstraction, like this:
TreeSet s{3, 5, 2, 1};
TreeSet::iterator it = s.begin();
while (it != s.end()) {
cout << ' ' << *it;
it++; // or ++it;
}
This should print out the result "1 2 3 5
"; in other words, the values are traversed in increasing order.
To implement this, the TreeSet
needs to provide an iterator implementation that can navigate the internal tree structure in order. It's cleanest and easiest to implement this as a separate TreeSetIter
class that can access the TreeSet
class' private state. Normally this would be disallowed, but the TreeSet
class can declare that the TreeSetIter
class is a friend class, and then TreeSetIter
will be able to access all of the internal details.
The TreeSetIter
class needs to hold some internal state that will allow it to remember where it is in traversing the binary search tree. At least one part of that state will be a smart-pointer to the current tree node. You may also need to maintain a std::vector
of nodes that the iterator has entered, like a stack, so that it can figure out where to go when the iterator is advanced.
You are encouraged to look at the Wikipedia article on tree traversal for more details of how to implement the iterator logic. The "iterativeInorder(node)
" pseudocode will steer you in the right direction.
TreeSetIter
FunctionalityThe TreeSetIter
class must provide the following operations:
Initialization. You do not have to provide copy-initialization or move-initialization; as long as you are not heap-allocating anything (why would you anyway?), the default implementations should suffice.
TreeSetIter & operator++()
(pre-increment operator) - advance the iterator to the next node in the binary search tree. The operator should return a reference to the iterator that was incremented, not a copy.
TreeSetIter operator++(int)
(post-increment operator) - advance the iterator to the next node in the binary search tree. The operator should return a copy of the iterator before it was incremented.
int operator*()
(dereference) - the iterator "points to" the current int
value, and dereferencing the iterator should return the int
value itself. For this operation the iterator may simply return the value out of the tree node.
bool operator==(const TreeSetIter &rhs) const
- return true
if the rhs
iterator references the same tree-node that this iterator references. Note that you are not comparing the values in the tree-nodes; you are comparing the pointers to the tree-nodes.
bool operator!=(const TreeSetIter &rhs) const
- inverse of ==
TreeSet
Iterator FunctionalityThe TreeSet
class itself must provide the following operations:
TreeSetIter begin() const
- return an iterator to the first value in the tree-set
TreeSetIter end() const
- return an iterator "past the end" of the tree-set. A good approach would be to initialize a TreeSetIter
object with an empty node-pointer.
A public declaration of the TreeSet::iterator
type. Like STL collections, this allows the TreeSet
to provide a more "standard" name for the iterator type, rather than requiring users to know internal implementation details. This can be done easily with a line like this in your TreeSet
class' public section:
using iterator = TreeSetIter;
Once these features are provided, you should be able to iterate over the contents of a TreeSet
in order. Exciting times.
TreeSet
FeaturesOnce iteration is complete, many other tree-set features become straightforward to write. Implement these member functions for your TreeSet
class, using your iterator implementation:
bool operator==(const TreeSet &rhs) const
- return true
if the rhs
set contains the same values as this set. Note that the two sets may have different internal tree structures and still compare as equal.
bool operator!=(const TreeSet &rhs) const
- inverse of ==
TreeSet TreeSet::plus(const TreeSet &s) const
- compute the set-union of this set and the provided set s
, returning a separate set containing the result.
Note: This is called plus()
and not union()
because union
is a C++ keyword.
Note: A more generalized data structure would also provide +
and +=
operators, etc. We are not requiring these operations because it starts to get tedious to implement and test all these operations. However, feel free to provide them if you wish.
TreeSet TreeSet::intersect(const TreeSet &s) const
- compute the set-intersection of this set and the provided set s
, returning a separate set containing the result.
TreeSet TreeSet::minus(const TreeSet &s) const
- compute the set-difference of this set and the provided set s
, returning a separate set containing the result.
Note: A more generalized data structure would also provide -
and -=
operators, etc. We are not requiring these operations because it starts to get tedious to implement and test all these operations. However, feel free to provide them if you wish.
A stream-output operator <<
for your TreeSet
type, which outputs the contents of the set in this format: "[1,2,3,4]
"
Note that the stream-output operator must not output a "\n
" character, or any whitespace.
An empty set would be output as: "[]
"
An updated test suite for your class is provided here. This program includes the testing from last week, as well as additional tests to exercise the new functionality. 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:
Makefile
treeset.h
treeset.cpp
(if present)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 © 2019-2020 by California Institute of Technology. All rights reserved. Generated from treeset-2.md.