Thread: Iterator

Hi everyone,

The following code gives compiler warnings for the destructor:

Code:

  // myVector.h

  // forward declarations
  template<typename T>
    class Iterator;            // line 17

  template<typename T>
    class Vector 
    {
    private:
      size_t nb_elms;
      T* elms;

      Iterator<T>* CreateIterator( void) const
      {
	return ( new Iterator<T>( *this));
      }

    public:
      Vector( void) : nb_elms( size_t()) {}
      ~Vector( void) { delete iter; }          // line 68
      explicit Vector( size_t const& nbelms) 
        : nb_elms( nbelms), elms( new T[ nb_elms]), iter( CreateIterator())
      {}

      // iterator
      friend class Iterator;

      Iterator<T>* iter;
  
    };

Code:

  // myVectorIterator.h

  // forward class template declaration
  template<typename T>
    class Vector<T>;

  template<typename T>
    class Iterator
    {
    public:
    Iterator( const Vector<T>& p_vec) : 
      vector( &p_vec), index( size_t()){}

      Iterator<T>& first( void)
	{
	  index = 0;
	  return *this;
	}
      Iterator<T>& next( void)
	{
	  index++;
	  return *this;
	}

      T get( void)
	{
	  return vector[index];
	}

    private:
      Vector<T>* vector;
      size_t index;

    };

here are the warnings:

../Vector.h: In destructor ‘Vector<T>::~Vector() [with T = double]’:
testVector.C:21: instantiated from here
../Vector.h:68: warning: possible problem detected in invocation of delete operator:
../Vector.h:68: warning: invalid use of incomplete type ‘struct Iterator<double>’
../Vector.h:17: warning: declaration of ‘struct Iterator<double>’
../Vector.h:68: note: neither the destructor nor the class-specific operator delete will be called, even if they are declared when the class is defined.

The problem clearly is in the destructor, but when instantiating an object, I create a 'new' iterator in the constructor. So I should provide a destructor which deletes this pointer?

Comments on my iterator pattern are also more than welcome!


EDIT: I am using g++4.3

The only thing I see is:

Code:

RowIterator<T>& next( void)

Is that supposed to be Iterator<T> &?

Could you label/highlight line 68 for us?

Ok, when I '#include' the header file where my iterator has been defined, the warning about the 'delete' has been solved.
But now there is an error in the header file for the iterator (second code block):

myVectorIterator.h:9: error: ‘Vector’ is not a template

Is my iterator pattern correct? The class 'Vector' contains pointers to myVectorIterator, but the class 'myVectorIterator' contains a pointer to Vector. This cyclic pointing seems a little awkward to me....

I consider just putting a 'typedef' in the class Vector :

Code:

  // myVector.h

#include "myVectorIterator.h"

  template<typename T>
    class Vector 
    {
    private:
      size_t nb_elms;
      T* elms;

    public:
      Vector( void) : nb_elms( size_t()) {}
      ~Vector( void) { delete iter; }          // line 68
      explicit Vector( size_t const& nbelms) 
        : nb_elms( nbelms), elms( new T[ nb_elms])
      {}

      // iterator
      friend class Iterator;

      typedef Iterator<T> iter;
  
    };

But this does not solve the error message about the forward declaration in 'myVectorIterator.h' . I don't see any other way than the forward declaration...

Well, you can't have recursive inclusion between the two header files. Since the two work so closely together, though, consider putting them both in the same header, with forward declarations and out-of-line definitions where necessary.

Also, the typical C++ iterator works very differently.

This is generally how I handle iterators:

Code:

template <typename T>
class MyContainer{

  private:

    struct Element{

      T data;

      // etc.
    
    };

  public:

    class MyContainer_Iterator{

      public:

      private:

        Element* curr;
    };
};

So yes, I prefer to nest them.

In case of nesting, can the sub-class be derived from an interface "general_iterator" ?

Sure, if you want.

It might look like:

Code:

General_Iterator{

//...
};

Reverse_Iterator : public General_Iterator{

//...
}:

Circular_Iterator : public General_Iterator{

//...
};

But since your general_iterator should be public (so people can actually use it), the derived iterators need not be part of the class declaration. In other words, people who use your template class can also create their own iterators simply by inheriting yours, since they're public. I think this way is the more accepted way of doing things. Write your general purpose iterator (with behavior that everyone would expect) then if you'd like, write some special iterators outside the class using inheritance.

Should the iterator be a nested class in the container? Or should it be a member (composition)?

I'm not talking about where it's declared (although it's typically declared in the class). I'm talking about its semantics. Your iterators are like Java iterators.

Let me give you some general advice on this whole project of yours:

1) It is unecccesary to hold a T* in your vector class. If that's what you want to do, then that's up to you, but then you need to handle deleting everything you create with new (which I don't see in what you've posted here). You're trying to create a new iterator, which just doesn't make any sense to me.

2) You don't need to write "void" where you have no arguments. In other words this will do just fine:

Code:

MyFunction(){};

3) You're use of "const" is wrong. Your general iterator should dereference like this:

Code:

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

where "curr->data" is a pointer to some dummy container for T (Like I showed you in my previous post).

4) Your iterator is strange to say the least, at least it won't make any sense to someone used to using an STL iterator.

This is the kind of behavior C++ users should expect:

Code:

class Iterator{

  public:

    Iterator( Element* c = 0 ) : curr( c ) {}

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

    // Also overload ++prefix, --prefix( if desired ), etc.

  private:

    Element* curr;
};

There is no need for your iterator to hold a Vector<T>*.


That way, when I use your class and iterator in main it should be really intuitive for me:

Code:

Vector<int> myvec;
Vector<int>::Iterator it = myvec.begin();
for(; it != myvec.end(); ++it)
  std::cout << *it << "\n";

So you'll also need to write begin() and end() fucntions. ( They return a "const" iterator ).

It is unecccesary to hold a T* in your vector class.

I want to create a new Vector class, which is an array of values and related operators/functions. I do not want to use STL's vector, since it is not the same thing as I want (vector is really a container, I want it to be an element of a vector space). And second, it's the only way to really learn all details I think. Yes I 'delete' everything at destruction, thanks for reminding.

You don't need to write "void" where you have no arguments

I have read that there is a difference in compilation, but I might have read an old C++ standard.

You're use of "const" is wrong

Am I using it not correctly there where I use it? Or am I not exhaustively enough "const-correct"?

Your iterator is strange to say the least

Haha, this is also the first try I ever implement an iterator pattern, I have only _used_ iterators this far (so overloading the operator* came in my mind...)
I have found some websites, but yes I agree it is more Java style.

Pretty to declare all private attributes in a struct, then defining a pointer to that struct in the iterator class. This was what I kind of meant by a pointer to the aggregate when the iterator was not nested.

Thanks a lot for the examples!!

Originally Posted by MarkZWEERS

I have read that there is a difference in compilation, but I might have read an old C++ standard.

There's a difference between...
void foo(void)
and
void foo()
...in C, but not C++.

Pretty to declare all private attributes in a struct, then defining a pointer to that struct in the iterator class. This was what I kind of meant by a pointer to the aggregate when the iterator was not nested.

No. You misunderstand me. All the private attributes of your class do NOT go into the struct. The purpose of the struct is to provide a dummy container for T. "T" can be anything. Therefore you want to be able to manipulate all elements of T with "your" container, but only as those operations are relevant to the purpose of your container. I.e. - if T is another class object, than your Vector shouldn't change the value of any T object, but your Vector should do things like provide random-access to any T within, provide an iterator class for linear access to the T elements, etc. In other words, operations that T performs, stay with T and are handled within T's implementation. Whereas a Vector holds any number of T's and provides manipulations on the collection of those T's.

Here's the basic structure of the template:

Code:

template <typename T>
class SizeVector{

  private:
    struct Node{

      T data;
      // and perhaps pointers to other Nodes like next, prev, whatever
    };

  public:

    class Iterator{

      // You can implement your Iterator here...

    };

    // Write begin() and end() functions here that return  a "const Iterator"

    // SizeVector's Constructor
    SizeVector() : {}

    // And all of SizeVector's member functions

  private:

    // Here you can put SizeVector's "private" attributes.

};

// If you want you can implement your derived Iterators out here.

NOTE: I suggest choosing a better name for your class like I did (SizeVector), this will eliminate confusion for user's of your class.

EDIT:

TO help clarify my first paragraph, you want your Vector to manipulate Nodes (which happen to contain a T), so in reality, yo're never messing with T's thmeselves.

Also, I'm not exactly sure what you want when you said:

I want to create a new Vector class, which is an array of values and related operators/functions. I do not want to use STL's vector, since it is not the same thing as I want (vector is really a container, I want it to be an element of a vector space).

In your first sentence you say, as it seems to me, that you do indeed want a STL-like vector (hence the array of values w/related operators/functions). Then you utterly confuse me with "an element of a vector space." If you need to point-to or have a vector in your class, I suggest re-writing all this and simply inheriting the std::vector, and adding your own code as needed.

It doesn't seem like you'll need to have more than one vector in your class (i.e. your not creating a collection of vectors) so I wouldn't bother with having a pointer or reference to a vector in your class. Simply inherit one. One will exist either way, so at least inheriting one seems a little less-confusing to me anyway. This actually gives you a little more flexibility as well because you can create a default vector within your class, or copy an existing one. This can all be handled in your initialization list.

This means you can use your vector class like this:

Code:

SizeVector szVector1; // Default constructor, creates a default base std::vector

// or:

vector<int> aVector;
SizeVector szVector2( aVector ); // Alternate constructor which copies an existing vector.

Note that with the above you don't need to create a template, since the template parameter is handled by std::vector. ( If someone else can shed light on inheriting a std::vector that would be great, since I've never done it, and I'm hoping I'm right about not needing the template parameter for SizeVector ).