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:

Quote:

---

../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?

Yes, that should be 'Iterator<T>'. I have simplified things for the post. Line 68 is the line where the 'delete' operator is called (I have edited my post).

Probably because you are calling delete on a forward-declared type. The compiler doesn't know how to destruct it because it hasn't been defined.

gg

But then, how can I ever delete the pointers? Or is my iterator pattern simply not correct...

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):

Quote:

---

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.

Quote:

---

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

---

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

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

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.

Quote:

---

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.

Quote:

---

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 ).

Quote:

---

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.

Quote:

---

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.

Quote:

---

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"?

Quote:

---

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!!

Quote:

---

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++.

:-)

and I have never even programmed in plain C! Just a copy of what "they" say...

Quote:

---

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:

Quote:

---

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 ).

Okay here's the deal w/inheriting std::vector and the template arguments:

Case 1:

Code:

---


#include <vector>

class SizeVector : public std::vector<int>{ // template parameter is defined

};

int main(){

  SizeVector szvec; // template parameter not needed
  return 0;
}

---

Case 2:

Code:

---


#include <vector>

template <typename T>
class SizeVector : public std::vector<T>{ // template parameter ambiguous

};

int main(){

  SizeVector<int> szVec; // template parameter needed
  return 0;
}

---

So it depends on what you need your class to do I guess.

Here's an example of how to do this in SizeVector's initialization list:

Code:

---

#include <iostream>
#include <vector>

template <typename T>
class SizeVector : public std::vector<T> {
       
        public:
               
                SizeVector<T>() : std::vector<T>() {} // Default constructor
               
                SizeVector<T>( const std::vector<T>& rhs ) // Alternate constructor copies an existing std::vector
                : std::vector<T>( rhs ) {}
};

int main(){
       
        std::vector<int> aVector;
        aVector.push_back( 5 );
       
        SizeVector<int> szVector( aVector );
       
        std::cout << szVector[0] << "\n";
       
        return 0;
}

---

Don't inherit from std::vector.

If you want a mathematical vector ("an element of vector space"), an iterator seems unneeded to me.

Thanks dudeomanodude, your comments are really helpful. I will attack it tomorrow evening...

I won't derive from std::vector, since that purpose does not fulfill the Liskov substitution principle? (corned beef I've read your posts!). At least it's not an abstraction relation.

My vector template class will be by specialized by any field of numbers (in the strict sense), for example complex, real, signed integers etc etc. It will be part of a complete as possible algebraic structure, but this is a future dream. I have therefore prepared many traits and policy/promotion classes for my algebraic template classes. It was really the iterator patterns which I don't know that well.

I will use my iterators for sure, for coherence with matrices and the various algorithms on their multiplication or other. Storage of matrices will strongly depend on their structure, this is where many many template parameters for storage policies etc etc will come (and some are yet) into play. Parametrized iterators will keep algorithms on objects of these classes, so independent of storage, transparent. That is what I see as the largest beauty of generic programming.

I'll definitely have questions about iterators, thanks a lot in the mean time!!

Quote:

---

I won't derive from std::vector, since that purpose does not fulfill the Liskov substitution principle?

---

No, in this case it's simply a language-technical issue. vector is not meant to be derived from. You can do it, but there's restrictions you'll have to observe. Anyway, the C++ way of doing things is to supply the additional functionality you want in free functions, or to write a class that has a vector as a member.

And a math vector with a variable number of dimensions (which is what one built from std::vector would be, or else there's little point in using std::vector) isn't terribly useful.

Quote:

---

a math vector with a variable number of dimensions isn't terribly useful.

---

This is where I doubt to make the dimension a template parameter, for the moment I haven't.

Thanks a lot!