• Choose a category
• All
• Classic-Fiction

By Root 1249 0

dependent on the internal implementation of the container. The first purpose of an iterator is to refer to a single element in the container. In the case of the hashmap, each element is in an STL list, so perhaps the hashmap iterator can be a wrapper around a list iterator referring to the element in question. However, the second purpose of a bidirectional iterator is to allow the client to progress to the next or previous element from the current. In order to progress from one bucket to the next, you need to track also the current bucket and the hashmap object to which the iterator refers.

Once you’ve chosen your implementation, you must decide on a consistent representation for the end iterator. Recall that the end iterator should really be the “past-the-end” marker: the iterator that’s reached by applying ++ to an iterator referring to the final element in the container. The hashmap iterator can use as its end iterator the end iterator of the list of the final bucket in the hashmap.

The HashIterator Class

Given the decisions made in the previous section, it’s time to define the HashIterator class. The first thing to note is that each HashIterator object is an iterator for a specific instantiation of the hashmap class. In order to provide this one-to-one mapping, the HashIterator must also be a class template on the same parameters as the hashmap class.

The main question in the class definition is how to conform to the bidirectional iterator requirements. Recall that anything that behaves like an iterator is an iterator. Your class is not required to subclass another class in order to qualify as a bidirectional iterator. However, if you want your iterator to be usable in the generic algorithms functions, you must specify its traits. The discussion on writing STL algorithms earlier in this chapter explains that iterator_traits is a class template that defines five typedefs for each iterator type. It can be partially specialized for your new iterator type if you want. Alternatively, the default implementation of the iterator_traits class template just grabs the five typedefs out of the iterator class itself. Thus, you can define those typedefs directly in your iterator class. In fact, C++ makes it even easier than that. Instead of defining them yourself, you can just subclass the iterator class template, which provides the typedefs for you. That way you only need to specify the iterator type and the element type as template arguments to the iterator class template. The HashIterator is a bidirectional iterator, so you can specify bidirectional_iterator_tag as the iterator type. Other legal iterator types are input_iterator_tag, output_iterator_tag, forward_iterator_tag, and random_access_iterator_tag. For the HashIterator, the element type is pair.

Basically, it all boils down to the fact that you should subclass your iterator classes from the generic iterator class template.

Here is the basic HashIterator class definition:

// HashIterator class definition

template

class HashIterator : public std::iteratorpair>

{

public:

HashIterator(); // Bidirectional iterators must supply default ctor

HashIterator(size_t bucket,

typename list>::iterator listIt,

const hashmap* inHashmap);

pair& operator*() const;

// Return type must be something to which -> can be applied.

// Return a pointer to a pair, to which the compiler will

// apply -> again.

pair* operator->() const;

HashIterator& operator++();

const HashIterator operator++(int);

HashIterator& operator--();

const HashIterator operator--(int);

// Don't need to define a copy constructor or operator= because the

// default behavior is what we want

// Don't need destructor because the default behavior

// (not deleting mHashmap) is what we want.

// The following