Iterator::begin(): what happens when there's nothing in the container?

[h9uest]

Hi:

Question background:
I'm trying to implement a simple template hash map. I get stuck on implementation of iterator.

To be specific about "getting stuck", let's see some code:

template<class KEY, class VALUE>
class HashMap
{
	struct Node // data structure that is held in bucket array
	{
		KEY key;
		VALUE val;
		Node * next;
	};

	//bucket array
	Node ** buckets;
	int nbucket;//number of buckets; a fixed prime number, say 37
	int nelement;//number of elements in the hashmap

	// hash key into some peculiar number
	unsigned int hashCode(KEY k);
	// compression function: compresses the peculiar number into bucket array index
	unsigned int compFunct(unsigned int);

	public:
	class Iterator
	{
		friend class HashMap<KEY, VALUE>;
		HashMap<KEY, VALUE> * p_hmap;
		Node * cursor;//current node in hashmap
		int pos;//conceptual index: [0,nelement-1]
		int chain;//which bucket at the moment? [0, nbucket-1]


		public:
		Iterator() //for simplicity, has only default constructor
		{
			cout << "In default constructor of Iterator\n";
			cursor = NULL;
			pos = 0;
			chain = 0;
		};
		~Iterator()
		{
		};

		Iterator& operator ++ ()// in prefix ++
		{
			cout << "In prefix ++\n";
			
			if(p_hmap == NULL)
			{
				cout << "check\n";//exception here
			};

			if(cursor == NULL)
			{
				cursor = p_hmap->begin();
			}
			else
			{
				if(cursor->next == NULL)//cursor is last entry in current list
				{
					//find next one in next list
					do
					{
						chain ++;
					} while(buckets[chain] == NULL);
					cursor  = buckets[chain];
				}
				else
				{
					//cursor = next one in current list
					cursor = cursor->next;
				};
			};
			pos ++;
		};


		//Iterator& operator -- ();
		//Iterator& operator * ();
		Iterator& operator = (Iterator & that)
		{
			return that;
		};

		//Iterator& operator != ();
	};


	HashMap();
	void insert(KEY, VALUE);
	void erase(KEY);

	Iterator begin();// where question lies
	virtual ~HashMap();

	void showState(); // for debug use
};

1, When I'm implementing HashMap<KEY, VALUE>::begin(), I don't know what I should do when there's nothing in the hashmap. I checked the C++ standard (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf), but didn't find any info on this scenario. Anyone has any idea? Or someone might want to share some source code of a compiler vendor?

2, In the standard, I saw many types of iterators: insert iterator, output iterator, forward iterator ... Are they really necessary? Okay, I'm thinking about making only one type of iterator and overloading a bunch of operators(e.g. --, ++, etc). Effectively, I'm having all those types of iterators, am I not?
Correct me please, if I'm wrong.


3, If anyone finds my way of implementing the iterator to be a silly one, be sure to let me know! I want some criticism and advice!

Thanks a lot, and I'm looking forward to some comments!

[Peter87]

If the container is empty begin() should return the same as end().

The different types of iterators just says what kind of operators the iterator supports. Some functions requires a certain kind of iterators to work. std::sort requires random access iterators while std::find requires an intput iterator.