An iterator is when you implement a abstract way of cycling through data. I have below created a internal iterator wrapper that will allow the class to implement a iterator for that class. Below the class is kinder like a stack where you place one item at the root of the stack and then place another item in a link (next item) attached to the last node of the stack (where the last item is, be it at the root if empty)
You can create a wrapper for the class externally as well, but in this instance I am creating it internally.
To start with I have created a internal class within the stack class called a Node, the Node is the item on the stack (the data inserted in a array as such). Also I created a basic class definition at the top the class so that the rest of the class knows that there is a thing called a Node, but the implementation is below.
// forward declaration for the class structure below. class Node; |
As said before, there is a root node that, this is where the start of the array in essence is, and the last node, where the last inserted node as placed. On each node there is a method to return the value attached to that node and also a link to the next node on the linked list.
class Node { public: Node(const int& val) : nextNode(NULL), nodeValue(val) {} int& getVal() {return(nodeValue);} Node* nextNode; private: int nodeValue; }; |
now we have the node class setup, which means that when we add to the stack we can now place the values added to a dynamic linked list and a way to go through them. Now we just need to add values into the stacked list.
void theStack::addValue(int valueToAdd) { if (rootNode == NULL) { rootNode = new Node(valueToAdd); lastNode = rootNode; }else { Node* p = new Node(valueToAdd); lastNode->nextNode = p; lastNode =p; } } |
this will place the new item either at the root node or attached to the next node to the last added node and then re-sets the last node added to point to where the new node, so that when another node is added it will be added in the correct place.
Here comes the iterator part.
To start with the internal part of the class, the internal iterator wrapper as such, we use the iterator class to extend/implement the iterator functions that we have to implement for the iterator aspects to work, here I am using the forward_iterator_tag as part of the parameter to the iterator and also we are returning a int value (which is what the stack is implementing as a linked list of integers, if you want to return another type just put in what ever your return type is.
class Iterator : public iterator<forward_iterator_tag, int> |
here are function/methods of a iterator to allow the stack iterator to go through the linked list (array of integers).
class Iterator : public iterator<forward_iterator_tag, int> { private: // the intP is a integer pointer Node* intP; public: Iterator(Node* p) : intP(p) {} ~Iterator() {} // assignment Iterator& operator=(const Iterator& otherValue); // equal or not equal to bool operator==(const Iterator& otherValue); bool operator != (const Iterator& otherValue); // increment the pointer to the next value Iterator& operator++(); // increment the pointer to the next next etc value Iterator& operator++(int); // return type here is a int because that is what I said at the top of the class setup // e.g. iterator<forward_iterator_tag, int> int& operator*(); }; |
of course we need to know when the begin and the end of the linked list is, this is the root and the last nodes, for a iterator to know where to start and end when you are going from start to end with using a iterator style of coding. Here is a way of using the iterator to loop through the values added, below is code that setups up the stack (theStack) class with some values (5,10,3), and then using a for loop to go through the values within the linked list (this is where the iterator part comes in)
theStack stacky; stacky.addValue(5); stacky.addValue(10); stacky.addValue(3); printf("Value in the stack was\n"); for (theStack::Iterator theIterator= stacky.begin(); theIterator != stacky.end(); theIterator++) { // (int) wrapping the return value into a int type, *theIterator getting the pointered to value printf("%d\n", ((int)*theIterator)); } |
in the full source code below is the implementations of the iterator and the stack
#include <iostream> #include <iterator> #include <stdio.h> using namespace std; class theStack { private: // forward declaration for the class structure below. class Node; // the pointers to the root nodes and the last node on the stack as such. Node* rootNode; Node* lastNode; public: theStack(): rootNode(NULL), lastNode(NULL) {} ~theStack() { delete rootNode; } // add objects to the DrawingObject void addValue(int valueToAdd); class Iterator : public iterator<forward_iterator_tag, int> { private: // the intP is a integer pointer Node* intP; public: Iterator(Node* p) : intP(p) {} ~Iterator() {} // assignment Iterator& operator=(const Iterator& otherValue); // equal or not equal to bool operator==(const Iterator& otherValue); bool operator != (const Iterator& otherValue); // increment the pointer to the next value Iterator& operator++(); // increment the pointer to the next next etc value Iterator& operator++(int); // return type here is a int because that is what I said at the top of the class setup // e.g. iterator<forward_iterator_tag, int> int& operator*(); }; // the begin and end of the iterator look up Iterator begin(); Iterator end(); // here we define the Node class private: class Node { public: Node(const int& val) : nextNode(NULL), nodeValue(val) {} int& getVal() {return(nodeValue);} Node* nextNode; private: int nodeValue; }; }; int main(int argc, char **argv) { theStack stacky; stacky.addValue(5); stacky.addValue(10); stacky.addValue(3); printf("Value in the stack was\n"); for (theStack::Iterator theIterator= stacky.begin(); theIterator != stacky.end(); theIterator++) { // (int) wrapping the return value into a int type, *theIterator getting the pointered to value printf("%d\n", ((int)*theIterator)); } return 0; } void theStack::addValue(int valueToAdd) { if (rootNode == NULL) { rootNode = new Node(valueToAdd); lastNode = rootNode; }else { Node* p = new Node(valueToAdd); lastNode->nextNode = p; lastNode =p; } } // the definitions of the class theStack // Iterator class implementations theStack::Iterator& theStack::Iterator::operator=(const Iterator& otherValue) { intP = otherValue.intP; return (*this); } bool theStack::Iterator::operator==(const Iterator& otherValue) { return (intP == otherValue.intP); } bool theStack::Iterator::operator != (const Iterator& otherValue) { return (intP != otherValue.intP); } // increment the pointer to the next value theStack::Iterator& theStack::Iterator::operator++() { if (intP != NULL) intP = intP->nextNode; return (*this); } // if the loop has a increment by more than 1 then just increment the value still by one. // if you are implementing another stack then you could get to the next next next etc nodes theStack::Iterator& theStack::Iterator::operator++(int) { if (intP != NULL) intP = intP->nextNode; return (*this); } int& theStack::Iterator::operator*() { return(intP->getVal()); } theStack::Iterator theStack::begin() { return(Iterator(rootNode)); } theStack::Iterator theStack::end() { return(Iterator(NULL)); } |
Output would be
Value in the stack was 5 10 3 |
