Tree-Set, Part 2: Iteration

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.

TreeSets and Initializer Lists

Since 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 Iteration

In-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 Functionality

The TreeSetIter class must provide the following operations:

TreeSet Iterator Functionality

The TreeSet class itself must provide the following operations:

Once these features are provided, you should be able to iterate over the contents of a TreeSet in order. Exciting times.

Additional TreeSet Features

Once iteration is complete, many other tree-set features become straightforward to write. Implement these member functions for your TreeSet class, using your iterator implementation:

Testing, Documentation, Build Automation

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.

Submitting Your Work

Once you have completed the above tasks, submit your work through csman. Make sure to submit these files:

You do not need to submit the test code; we will test your program with a fresh copy of these files.

Assignment Feedback Survey

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.