Adding an Iterator

In the previous assignment, your TreeSet<T> class template had an iterator that allowed users to iterate through all elements in the tree set in sorted order. In this part of the assignment, you'll implement a similar iterator for your HashSet<T> class template so that users can iterate through all elements in the hash set.

One key difference between the two iterators is that the TreeSet<T> iterator covered the elements of the set in sorted order, whereas your HashSet<T> iterator will cover the elements in an unspecified order (which may vary depending on the hash function used, the order of insertions, and the current size of the hash table).

You should be able to copy and paste a lot of the code from your TreeSet<T> iterator implementation, but you'll need to make some changes to account for the different underlying data structure. In particular,

• The encoding of the iterator's position will be different. Instead of the stack of Node* pointers you used for the TreeSet<T> iterator, you'll need to keep track of which bucket you're in, and a const_iterator for the std::forward_list<T> within that bucket.

• The logic for advancing the iterator to the next element will also be different (and much simpler!). To advance the iterator,

  • If there is another element in the current bucket's std::forward_list<T>, move to that element.
  • Otherwise, move to the next non-empty bucket in the hash table and set the iterator to the first element in that bucket's std::forward_list<T>.
  • If there are no more elements in the hash table, set the iterator to the end position and the list iterator to a default-constructed std::forward_list<T>::const_iterator.

It may be helpful to write a helper function that scans forward from a given bucket index to find the next non-empty bucket. Such a function can be useful in both begin() and operator++().

Your Task

If you do this part, you need to:

• Implement a nested ConstIter class within your HashSet<T> class template that supports the following operations:
  • Copy constructor
  • operator*() to access the current element
  • operator++() to advance to the next element
  • operator==() and operator!=() for comparison
• Add a type alias const_iterator for ConstIter within your HashSet<T> class template.
• Implement the begin and end member functions for your HashSet<T> class template that return const_iterator objects representing the beginning and the end of the hash set.
• Add the necessary friend declarations to allow ConstIter to access private members of HashSet<T> if needed.
• Add type aliases to your ConstIter class for value_type, reference, pointer, difference_type, and iterator_category to conform to the C++ iterator requirements.
• Write tests to verify that your iterator works correctly, including tests for iterating over an empty hash set, a hash set with one element, and a hash set with multiple elements.

When You're Done

Don't forget to add some details about what you did to Fun.md. The sample solution includes an iterator implementation, so you can leave your tests in hashset-test.cpp enabled if you'd like rather than commenting them out.

(When logged in, completion status appears here.)

Go to Parent Page Next Page