1.11M Members

Beginner Iterator Class

 
0
 

I just started looking at iterators in my C++ class and don't think I fully understand enough about them to actually create one. I need to add an iterator to this doubly linked list program:

#ifndef CSLIST_H
#define CSLIST_H

#include <iostream>
#include <cstdlib>

using namespace std;

template <class T>
struct node // Create a structured node object
{
  T value; // value the node stores
  node<T>* next; // pointer to the next node
  node<T>* prev; // pointer to the previous node
};

template <class T>
class cslist
{
  public:
    cslist(); // default constructor
    int size() const; // return the number of integers store in the list
    bool empty() const; // returns true if list empty
    void push_front(const T& val); // insert an value to the front of the list
    void pop_front(); // removes one element from the front of the list
    void push_back(const T& val); // insert value to back of list
    void pop_back(); // remove element from the tail of the list
    T& front(); // fetch the first value stored in the list 
    T& back(); // fetch the last value stored in the list 
    node<T>* insert(node<T>* n, const T& val);	// insert an value at the pointed 
    // position, and return a pointer pointing at the inserted value
    void erase(node<T>* n); // delete a value at the pointed position
    void erase(node<T>* n1, node<T>* n2); // delete all node between two nodes 
    // including the value at the first pointer
    void clear(); // delete all values
    void print(); // print all value in the current list
    void insert_before(int val); // Insert node a specific position

  private:
    node<T>* head; // pointer to the head of the list
};

// constructor
template <class T>
cslist<T>::cslist() {
  head = new node<T>;
  head->next = head;
  head->prev = head;
}

// return the size of the list
template <class T>
int cslist<T>::size() const {
  int count = 0;
  node<T>* curr = head;

  while(curr->next != head) {
    count++;
    curr = curr->next; // move to next node
  }
	
  return count;
}

// check if empty
template <class T>
bool cslist<T>::empty() const {
  return (head == head->next);
}

// add an element to the front
template <class T>
void cslist<T>::push_front(const T& val) { // act as a stack
  node<T>* np = new node<T>;
  np->value = val;
   
  np->prev = head;
  np->next = head->next;

  head->next->prev = np;
  head->next = np;	
}

// remove the first element
template <class T>
void cslist<T>::pop_front() {
  erase(head->next);
}

// add an element to the back
template <class T>
void cslist<T>::push_back(const T& val) { // act as a queue
  node<T>* np = new node<T>;
  np->value = val;
	
  np->next = head;
  np->prev = head->prev;

  head->prev->next = np;
  head->prev = np;
}

// remove fron the last element
template <class T>
void cslist<T>::pop_back() {
  erase(head->prev);
}

// return the value at the front
template <class T>
T& cslist<T>::front() {
  return head->next->value;
}

// return the value at the back
template <class T>
T& cslist<T>::back() {
  return head->prev->value;
}

// insert a node by referencing the nodes to the left and right
//insert a node before  n
template <class T>
node<T>* cslist<T>::insert(node<T> *n, const T& val) {
  node<T>* np = new node<T>;	
  np->value = val;

  np->next = n;
  np->prev = n->prev;
	
  n->prev->next = np;
  n->prev = np;	

  return np;
}

// erase a node and all references to it
template <class T>
void cslist<T>::erase(node<T>* n) {
  if(n != head)
  {
    n->prev->next = n->next;
    n->next->prev = n->prev;
		
    delete n;
    n = 0;
  }	
}

// iterate through list and delete node a to b
template <class T>
void cslist<T>::erase(node<T>* n1, node<T>* n2) {
	
  do // deletion loop
  {
    n1 = n1->next;
    erase(n1->prev);
		
  }
  while(n1 != n2);
}

// delete all nodes
template <class T>
void cslist<T>::clear() {
  node<T>* curr = head;	
        
  while(curr->next != head) {
    erase(curr->next);
	}
}

// print the list
template <class T>
void cslist<T>::print() {
  node<T>* curr = head->next;
  cout << "\n********" << endl;
  if (empty() != true) {
    cout << "* list *\n********" << endl;

    while(head != curr)
    {
      cout << curr->value << endl;
      curr = curr->next;
    }
    cout << "********\n" << "size: " << size();
  }  else {
    cout << "empty...";
  }
  cout << "\n********" << endl;
}

// Unfinished - inserts a node infront of another
template <class T>
void cslist<T>::insert_before(int val) {
  node<T>* np = head;
  node<T>* found = new node<T>;
  do {
      if (np->value == val) {
        insert(found, val);
  }
  np = np->next;
  } while(np != head);

}

#endif

Currently, the class is a doubly linked template class, able to store data of any type. I have looked on this site and at the STL class provided on school computers but have had difficulty interpreting both resources to the point that I can translate them to my own code. Does anyone have any suggestions or references that are a little more beginner based that might help me figure out how to approach this problem? I am not even completely sure what the function of the iterator would be in this instance.

 
0
 

An iterator is simply a pointer to a node in your list. If you wrote all of that code, you should be able to figure out how to implement one and what its purpose is. Take the term "iterator" in a literal sense.

EDIT: Reread your question and it seems you didn't write the code. Your iterator would be used to search for a specific node in the list. So you would point to the first node in your list(in this case your iterator would be of type node*), check if that node contains the data you want to compare, if it does not, you point your iterator to the next node and check the data. Rinse and Repeat

 
0
 

An iterator is simply a pointer to a node in your list. If you wrote all of that code, you should be able to figure out how to implement one and what its purpose is. Take the term "iterator" in a literal sense.

EDIT: Reread your question and it seems you didn't write the code. Your iterator would be used to search for a specific node in the list. So you would point to the first node in your list(in this case your iterator would be of type node*), check if that node contains the data you want to compare, if it does not, you point your iterator to the next node and check the data. Rinse and Repeat

I did not write this specific code but I completed the same assignment independent from the partner I am now coding with. That is simply his version of the previous assignment.
I think the underlying issue was that we were under the wrong impression as to the function of iterators in this sense or any other. They were not terribly well described to us and most of the resources online explain them in a way that is not completely clear to me.

You
This article has been dead for over six months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: