Tags: collection, create, explain, iterator, lecturers, own, programming, rush, studies, task

Own iterator and collection in c++

On Programmer » C & C++

9,863 words with 8 Comments; publish: Sat, 09 Feb 2008 15:16:00 GMT; (200154.30, « »)

Hi,

I have a task to do at my studies. The lecturers was in rush, didn't explain much and i need help.

The task is to create own list (collection of any objects) and an iterator for it. The whole code has to be ours, not ready like in java with prebuild iterators and arraylists for exapmle.

The program has to be in c++. I know the iterator and collecion only from java - i know what they do, abut i don't have any idea how they works.

Iterator is an example of some programming pattern (the lecture is about patterns - we had only singleton and now this homework)

The lecturer gave us an example of c++ iterator:

vector<int> the_vector;

vector<int>::iterator the_iterator;

for( int i=0; i < 10; i++ )

the_vector.push_back(i);

int total = 0;

the_iterator = the_vector.begin();

while( the_iterator != the_vector.end() ) {

total += *the_iterator;

the_iterator++;

}

Now - maye u have some tutorial or own code?

All Comments

Leave a comment...

  • 8 Comments
    • http://www.cprogramming.com/tutorial/stl/iterators.html

      You can get more tutorials googleing a little.

      When you have a good idea of what is an iterator, you can implement your container (what is the exact nature of the container you must write?).

      For that, you'll need to define a container class, which will have probably some pointers to the data.

      For example, if you implement a linked list, you can have a pointer to the first node of the list.

      You'll need also a different class : the iterator class. This iterator class should be declared in the scope of the container class.

      You should also define a const_iterator class.

      The iterator class must be very small and fast to copy.

      For example, an iterator to a linked list can be a simple class containing a single pointer to the 'pointed' node.

      You must overload operator++ (both prefix and suffix operator) operator-- (both prefix and suffix) operator* operator== operator->, and maybe operator+= and operator-= and operator[] for your iterator class.

      You'll probably not need to overload operator= nor the copy constructor, and you'll not need to define a user destructor.

      The container will have a typedef for the iterator and const_iterator in its declaration.

      a begin() method will return an iterator to the begining of the container

      an end() method will return an iterator to the end of the container (which 'points' to the virtual element which just follows the last element of the container).

      For example, a linked list end() can be represented by a NULL pointer in the iterator class.

      You must also define a begin() and an end() const methods returning const_iterators.

      #1; Fri, 09 Nov 2007 00:51:00 GMT
    • Josuttis has an example in his book (The C++ Standard Library -

      A tutorial and Reference).

      At the following url

      http://www.josuttis.com/libbook/toc.html

      Under "STL Containers" , look at cont/carray.hpp

      and cont/carray1.cpp ... It is too simple for your

      needs. You will probably have to write your own

      iterator class.

      As SuperKoko mentioned, google will come up with some

      examples (Custom Iterator)

      #2; Fri, 09 Nov 2007 00:52:00 GMT
    • The problem with those is that he has to invent it from scratch, not use STL.

      However it is useful to learn about iterator-traits because you would need to decide which ones you have, and what operators you would need to overload. For a list you would not normally implement operator+ or operator+= to advance more than one place.

      #3; Fri, 09 Nov 2007 00:53:00 GMT
    • so what should i do? i shouldn't use STL, should i read what Philip told me to read?
      #4; Fri, 09 Nov 2007 00:54:00 GMT
    • You can try to do what i said.

      If you have problems at a step you can ask for help here.

      Have you an idea of how a linked list is implemented?

      If you have an idea, i suppose that you can start programming.

      If you don't know what is a linked list (i am not sure that you need to implement a linked list).

      You can search on the net.

      http://www.cs.rpi.edu/~musser/gp/List/lists1.html describes the doubly-linked lists of STL (i don't read the text, but it seems interesting).

      http://cslibrary.stanford.edu/103/ seems to describe the very basic of lists.

      #5; Fri, 09 Nov 2007 00:55:00 GMT
    • Ok

      I have started with simple items[10] - is it good iterator program?

      And now i have to modify it to have a contener list

      (i think with integer index and any object) - do you know how to modify it?

      I have done as follows (i have also problem with hasNext() - it doesn't compile:

      #include <iostream.h>

      class ListIterator; // This must be forward declared

      class List {

      private:

      //int z=0;

      int items[10];

      int sp;

      public:

      friend class ListIterator;

      List() { sp = -1; }

      void Add( int in ) { items[++sp] = in; }

      // int pop() { return items[sp--]; }

      int Length() {return sp;}

      bool isEmpty() { return (sp == -1); }

      ListIterator* createIterator() const;

      int getSp(){return sp;}

      };

      class ListIterator {

      const List* stk;

      int index;

      public:

      ListIterator( const List* s ) { stk = s; }

      int First() { index = 0; return stk->items[index];}

      int Next() { index++; return stk->items[index];}

      bool hasNext(){

      if (index==stk->getSp()) {return false;}

      else {return true;}

      }

      bool isDone() { return index == stk->sp+1; }

      int currentItem() { return stk->items[index]; }

      int getIndex() { return index; }

      //int lenght() { return stk }

      };

      ListIterator* List::createIterator() const { return new ListIterator( this ); }

      bool operator==( const List& l, const List& r ) {

      // 3. Clients ask the container object to create an iterator object

      ListIterator* itl = l.createIterator();

      ListIterator* itr = r.createIterator();

      // 4. Clients use the First(), isDone(), Next(), and currentItem() protocol

      for (itl->First(), itr->First(); ! itl->isDone(); itl->Next(), itr->Next())

      if (itl->currentItem() != itr->currentItem()) break;

      bool ans = itl->isDone() && itr->isDone();

      delete itl; delete itr;

      return ans;

      }

      int main( ) { // main returns an int, not void!!!!!

      int z;

      List s1;

      s1.Add(5);

      ListIterator* it=s1.createIterator();

      cout<<"Sp="<<s1.getSp()<<endl;

      it->Next();

      cout<<"Index="<<it->getIndex()<<endl;

      s1.Add(6);

      cout<<"Sp="<<s1.getSp()<<endl;

      cout<<"Index="<<it->getIndex()<<endl;

      s1.Add(7);

      cout<<"Sp="<<s1.getSp()<<endl;

      cout<<"Index="<<it->getIndex()<<endl;

      s1.Add(8);

      cout<<"Sp="<<s1.getSp()<<endl;

      cout<<"Sp="<<it->getIndex()<<endl;

      //while

      // while (it->hasNext()){

      cout<<"FRA";

      //}

      cout<<it->First()<<endl;

      cout<<it->isDone()<<endl;

      cout<<s1.Length()<<endl;

      cin>>z;

      }

      #6; Fri, 09 Nov 2007 00:56:00 GMT
    • #include <iostream.h>

      This should be

      #include <iostream>

      The <iostream> is the correct header. Then the iostream functions are in the std namespace. The <iostream.h> is a non-standard header and should not be used.

      Regards,

      Paul McKenzie

      #7; Fri, 09 Nov 2007 00:57:00 GMT
    • It is preferable to use a standard interface for iterators. So, you should make your interface look like the STL interface.

      Instead of a 'hasNext' member, you should have a pair of methods : begin()/end() in the container, returning iterators to the begining and to the end of the container.

      Overloading operator== allow the user to compare any iterator to end().

      Instead of defining First, Next, etc.. you should overload operators.

      the 'Length' method could be renamed as 'size'.

      These standard interfaces are important for the user, but also allow to write generic templates working with any container or any iterator.

      Also, the name List is confusing, because your container is not a linked-list.

      Array is a better name

      Here is a possible interface:

      template <class T,std::size_t MaxSize>

      class Array

      {

      public: // standard typedefs

      typedef T value_type;

      typedef T* pointer;

      typedef T& reference;

      typedef const T& const_reference;

      typedef const T* const_pointer;

      typedef std::size_t size_type;

      typedef std::ptrdiff_t difference_type;

      typedef pointer iterator;

      typedef const_pointer const_iterator;

      public:

      Array(size_type initial_size=0);

      ~Array();

      size_type size() const;

      size_type capacity() const;

      size_type max_size() const;

      bool empty() const; // returns true if empty

      iterator begin();

      iterator end();

      const_iterator begin() const;

      const_iterator end() const;

      const_reference operator[](size_type) const;

      reference operator[](size_type);

      void resize(size_type);

      void push_back(const_reference);

      void pop_back();

      reference() back();

      const_reference() back() const;

      private:

      size_type mCurrentSize;

      value_type Items[MaxSize];

      };

      iterators are very simple to implement here, because they can be implemented as raw pointers.

      But you can implement them manually if you want to learn how that can be done.

      #8; Fri, 09 Nov 2007 00:58:00 GMT