custom iterator for a hash table

[henrisco82]

I am trying to build a custom iterator for a hash table. How can i make the ++ operator move to the next bin after iterating through all the elements in the list without changing the index values of the array in the begin() function.

Thanks.


template<class T, int N, class F>
class my_hashset{
private:
struct Elem{
T data;
Elem *next;
};
Elem *HashTable[N];

public:


/** Default constructor. */
my_hashset(){
for(int i = 0; i < N; i++){
HashTable[i] = new Elem;
HashTable[i]->data = 0;
HashTable[i]->next = nullptr;
}

}

/** Nested class implementing forward iterator. */
class Iterator{
private:
Elem *ptr;
friend class my_hashset<T,N,F>;

public:
Iterator(Elem *ptr): ptr(ptr){}

Iterator& operator++(){
ptr = ptr->next;
return *this;
}

T& operator*(){
return ptr->data;
}

bool operator!=(Iterator temp){
return ptr != temp.ptr;
}

};



/** Creates a begin iterator. */
Iterator begin(){
return Iterator(HashTable[0]);
}

/** Creates an end iterator. */
Iterator end(){
return Iterator(0);
}


/** Insert a new element in the set. */
void insert(const T &item){
int index = hashFunc(item);
if(HashTable[index]->data == 0){
HashTable[index]->data = item;
}else{
Elem *ptr = HashTable[index];
Elem *n = new Elem;
n->data = item;
n->next = nullptr;


while(ptr->next != nullptr){
ptr = ptr->next;
}

ptr->next = n;
}

}


int hash_function(const T &x){
return x % N;
}
};


int main()
{
my_hashset<int,2,int_hash> h1;
h1.insert(77);
h1.insert(22);
h1.insert(50);
h1.insert(23);
h1.insert(10);
h1.insert(97);
h1.insert(15);


for(auto it = h1.begin(); it != h1.end(); ++it){
cout << *it << endl;
}


return 0;
}

[coder777]

Iterator needs the entire HashTable and additionally the index within that table.

[gunnerfunner]

You've taken on a fair challenge here:
(a) you need to first provide your own implementation of the hash table, my_hashset, which, by the look of it, corresponds to the standard library's unordered set (unique elements only) or unordered multiset (non-unique elements OK)

(b) at the very least, provide your own hash function to implement your hash table - this is currently not provided. You can open up the unordered_set header file to see what additionals might be required, you might need a (friend) swap() method as well: http://stackoverflow.com/questions/7758580/writing-your-own-stl-container/7759622

(c) for custom iterators you should provide both iterator and const_iterator and if you wish to make them standard library compliant derive your custom iterator classes from std::iterator with the following typedefs:

using iterator_category = std::forward_iterator_tag;	
using value_type = T;
using pointer = std::shared_ptr<T>;
using reference = T&;
using size_type = size_t;
using difference_type = std::ptrdiff_t;
//http://stackoverflow.com/questions/8054273/how-to-implement-an-stl-style-iterator-and-avoid-common-pitfalls/8054856 

(d) for the iterator classes you'll then have to provide the operator overloads for de-reference, in-direction, pre & post increment, == , !=

(e) finally, back at the container level, provide begin(), end(), cbegin(), cend()

Good luck!!