help w/template iters

**sh3rpa** · 10-04-2007

ok this is an abridged version of what i've got:

Code:

template <typename T> class List
{
    public:

        ...

        class Iterator;

    private:

        class Node;

        Node *head, *tail;
};

template <typename T> class List<T>::Node
{
    public:

        ...

    private:

        T data;
        Node *next, *prev;
};

template <typename T> class List<T>::Iterator
{
    public:

        Iterator(Node* n) : node(n) {}
       ~Iterator() {}

        Iterator& operator++()
        {
            if (node != NULL)
            {
                node = node->next;
            }
            return(*this);
        }

        Iterator& operator++(int)
        {
            Iterator i(*this);
            ++(*this);
            return(i);
        }

    private:

        Node *node;
};

as you can see, this is a doubly linked-list template class. My question is how can I implement an Iterator in a List member function?

For example, if I have display() function, how do I use an Iterator for list traversal?

**Prelude** · 10-04-2007

>My question is how can I implement an Iterator in a List member function?
You don't need to unless you're going for sheer simplicity of the implementation. The iterator is there for client code to traverse your list without having to know about the details of the implementation. So your list class would have something like this:

Code:

template <typename T>
class List {
public:
  // ...
  Iterator begin() { return Iterator ( head ); }
  Iterator end() { return Iterator ( tail ); }
};

Then, (assuming you've defined your list such that tail is one past the last item and head is the first item) clients can do this:

Code:

List<int> foo;

// ...

List<int>::Iterator it = foo.begin();
List<int>::Iterator end = foo.end();

while ( it != end ) {
  // Do something with it
}

**sh3rpa** · 10-04-2007

what i'd like to do is something like:

Code:

template <typename T> void List<T>::display()
{
    /*  Declare an Iterator  */

    while ( myIter != end )
    {
        /*  Display the Node data "T"  */
        
       myIter++;  // to advance to the next Node in the List
    }
}

what is troubling me is:

1) how do I declare the Iterator in the member function with the class setup in my OP?

2) how can I display something like the data (which belongs to Node) using the Iterator?

**twomers** · 10-04-2007

1) List<T>::iterator iter;
2) You could overload its << operator ...

**sh3rpa** · 10-04-2007

I'm still having a problem...

Even if I do just this:

Code:

template <typename T> void List<T>::display()
{
    List<T>::Iterator i;
}

...i get errors:

E:\EricsStuff\Builds\list.cpp In member function `void List<T>::dis()':

481 E:\EricsStuff\Builds\list.cpp expected `;' before "i"

E:\EricsStuff\Builds\list.cpp In member function `void List<T>::dis() [with T = int]':

17 E:\EricsStuff\Builds\driver.cpp instantiated from here

481 E:\EricsStuff\Builds\list.cpp dependent-name ` List<T>::Iterator' is parsed as a non-type, but instantiation yields a type

481 E:\EricsStuff\Builds\list.cpp say `typename List<T>::Iterator' if a type is meant

**CornedBee** · 10-04-2007

481 E:\EricsStuff\Builds\list.cpp say `typename List<T>::Iterator' if a type is meant

It's rare that a compiler is this helpful.

But actually, just saying Iterator should be enough.

**sh3rpa** · 10-04-2007

Originally Posted by CornedBee

It's rare that a compiler is this helpful.

That was compiled using MinGW: -ansi -pedantic -Wall, if you're wondering.

I just got off of work, so it's too late to play around with this now (it almost Midnight)

**matsp** · 10-05-2007

Ok, so sticking iterators inside a class is USUALLY not a good something you should do.

In class design, the members of a class should be "what's necessary to solve the problem and ntohing more". If the iterator is going to be used like a for- or while-loop iterator variable, that is only used within a function, then it shouldn't be part of the class - it should be a local iterator in the function(s) that need the iteration.

Note that this is for several reasons:
1. Class members that aren't needed take up extra space for every instance of the class. Local variables only take up space when you are in the function using that variable.
2. The more "stuff" there is in a class, the harder it is to do further work on it.
3. It is harder to access a class member (from the compilers perspective) than a local variable in a function.
4. The compiler may not realize how this variable is used and that it's actually not needed to be stroed back into the class when you are finished with it, that no other calls to member functions can't occur at this time, etc, etc, so the compiler will generate less good code (perhaps always storing any iterator changes back into the class, when this is completely unnecessary).

--
Mats

**CornedBee** · 10-05-2007

I don't think sh3rpa has actual instances of the iterator in the class.

**matsp** · 10-05-2007

Originally Posted by CornedBee

I don't think sh3rpa has actual instances of the iterator in the class.

Ah, no, you are right. Sorry I wasted some space.

--
Mats

**sh3rpa** · 10-05-2007

Originally Posted by CornedBee

I don't think sh3rpa has actual instances of the iterator in the class.

What exactly does that mean: *instances of the iterator in the class* ???

I mean, the class *Iterator* itself IS declared in class List. I'm confused. I guess I've never known exactly what *instance* means. Please explain.

**laserlight** · 10-05-2007

Simply put, an instance is an object. So an instance of Iterator means an Iterator object.

**matsp** · 10-05-2007

Instance of a class is the "object that is of a type class".

Code:

class something {
... 
};

something *ptr;
something aa;
ptr = new something;

ptr is (in the above codesegment) pointing to an instance of a class.
likewise, aa is an instance of a class.

So, if your iterator is part of your class, then that's (usually) wrong, as I explained earlier.

--
Mats

**sh3rpa** · 10-05-2007

ok thanx, i get the whole *instance* thing now.

But if an Iterator is declared in a member function, then it's only local to that function, and therefore is NOT an instance of the class right?

For example:

Code:

void myClass::my fucntion()
{
    Iterator i;

    ...
}

Iterator i is only local, right?

**matsp** · 10-05-2007

Yes, that's exactly how your are supposed to do it. Local variable in the member function.

--
Mats

Thread: help w/template iters

Thread Tools

Search Thread

Display

help w/template iters