Reference Guide: Set Iterators

By virtue of polymorphism, all Set implementations use a single SetIterator that hides complexity of actual solution used (eg: HashSet). To make this possible, each class implementing Set needs to come with a SetIterator implementation adapted to the data structure they are using and keep it hidden to end users so they only work with abstractions.

Usage example:

HashSet<long> list; list.addToTail(1); list.addToTail(2); // This uses SetIterator<long>* for Set<long>*, instead of HashSet<long> for(auto it = list.begin(); *it!=*(list.end()); ++(*it)) { std::cout << (*(*it)) << std::endl; }

Whereas STL equivalent is:

std::unordered_set<long> set; set.insert(1); set.insert(2); // This uses iterator for std::unordered_set<long> directly for(auto it = set.begin(); it!=set.end(); ++it) { std::cout << (*it) << std::endl; }

As one can see above, because API iterators are polymorphic, they require an extra pointer compared to those of STL. Unlike STL, currently only forward non-const iterators are supported, but these will be added in the near future!


Forward iterator prototype for List, returned by latter's begin and end methods


template <typename T> class SetIterator


Method Signature Description
SetIterator SetIterator () Constructs iterator, setting offset
~SetIterator virtual ~SetIterator () Virtual destructor used when iterator is deallocated
operator* virtual const T& operator* () = 0 Dereferencing operator required when accessing current element
operator++ virtual void operator++ () = 0 Advance operator required when iterating
operator!= bool operator!= (const SetIterator<T>& it) Difference operator required when iterating