An interesting POO problem in C++

[AllanNabhan]

Hi !

I have an interesting POO problem using C++. Can somebody help me?

I want to implement a generic interface for sequential containers. I demand all sequential containers (deque, vector, list ...) to derive from a single virtual base class, SequentialContainer. (All classes are actually templatized; I will omit to mention the class parameter). I also want the containers to be able to provide, on demand, an iterator properly initialized on their data. I demand this to be part of the generic interface.

This mean that we need a generic iterator class Iterator, and that the SequentialContainer class provides a method such as:

(1) Iterator SequentialContainer::Iter(void); /* or maybe with initialisation instructions instead of void */

The class Iterator will, by the way, implement a generic interface for iterators, providing for example an incrementation operator.



Now, we want to implement actual sequential containers Deque and List. Of course, they derive from the base class SequentialContainer:

class Deque : public SequentialContainer {
...
};

class List : public SequentialContainer {
...
};

Now, we need the actual iterators. Since it is not at all the same to iterate on a Deque or on a List, the implementation has to be specialized depending on the container. It means that, from the base class Iterator, we must derive subclasses DequeIterator, ListIterator.

And now, we reach my problem: the base class defined the Iter() interface as (1) i.e. returning an Iterator object, not DequeIterator or ListIterator.

It is not elegant to introduce supplementary class specific methods such as:

(2) DequeIterator List::Iterator(void);

when we already have (1). On the other hand, the Iterator base class cannot know about child classes, and we can't have copy constructors from child to parent.

How you would solve this? Is there a simple solution? Or do we need to erase the premise (1)? Or do we need a trick to avoid subclassing Iterator into DequeIterator / ListIterator?

Thank you for your suggestions.

Allan

 

[Cagliostro]

Implement class iterator as nested in template class SequentialContainer:

template<class T> SequentialContainer
{
protected:
class t_iterator
{
T...
}
};
implement deque and other classes like this:
template<class T>class Deque : public SequentialContainer<T>
{
...
public:
class iteratorublic SequentialContainer<T>::t_iterator
{
.....
};
};
in this implementation will not exist type cast from iterator to base of iterator

Ion Filipski

 

[globos]

And what about to make the method :

 Iterator& SequentialContainer<T>::iterator ()

a deferred one(pure virtual)?

template<class T>
class SequentialContainer
{
public:
...
  virtual Iterator& iterator () = 0;
...
};

template<class T>
class List
{
public:
...
  Iterator& iterator ()
  {
    return *new ListIterator ();
  }
...
};

Effective containers like List, Deque, etc. implement the iterator () method, i.e. returning an instance of the actual concrete Iterator class needed.

--
Globos

 

[Cagliostro]

template<class T> SequentialContainer
{
protected:
class t_iterator
{
T...
}
public:
t_iterator& Iterator() = 0;
//you will be obligated to implement it in child classes

};


Ion Filipski

 

[globos]

If you don't use class nesting between containers and iterators, the solution I gave is fine and concise. Using classes nesting, which is not a precise OO concept to me(although it is used in UML, Java, C++), I don't know.
By the way can you explain just a little bit how concrete iterators are instanciated in your solution? I don't see how it is possible to not specify instanciation of concrete iterators.

Thanks.

--
Globos

 

[Cagliostro]

I acn not understand, you are a programmer or a student? My responce was quite enough you to understand if you would be a programmer.

Ion Filipski

 

[globos]

template<class T> SequentialContainer
{
protected:
   class t_iterator
   {
      T...
   }
};
implement deque and other classes like this:
template<class T>class Deque : public SequentialContainer<T>
{
  ...
public:
   class iterator:public SequentialContainer<T>::t_iterator
   {
   .....
   };
};

Don't be irritated, how do you instantiate iterators in that solution?

--
Globos

 

[globos]

AllanNabhan :
&quot;I also want the containers to be able to provide, on demand, an iterator properly initialized on their data. I demand this to be part of the generic interface.&quot;

The Qt library(

http://doc.trolltech.com/3.2/)

provides containers classes(QList, QMap, etc.) that don't have methods dedicated to the instantiation of iterator classes. Instead, it's up to the clients to instanciate the iterator on the container they want to iterate on, for example :

QList<float> floats;
//...
QListIterator<float>  ifloat (floats);
while (ifloat.current () != NULL)//iteration on floats
{
  //...
  ++ifloat;
}

The constructor of QListIterator is defined as :

QListIterator<G> (const QList<G>& list)

This way you don't have to define specific methods on concrete containers that instantiate iterators(because they just don't have to exist!) as you mentioned in 2).
It allows to use iterators that are allocated in the stack, so clients don't have to bother to free them.

Another solution is to have active data structures, i.e. structures that provide a cursor position and features to iterate on their data.
But i usually prefer a separate iteration mechanism, it seems safer.

--
Globos

 

[Cagliostro]

Deque<type> yourDeque;
Deque<type>::iterator& x = (Deque<type>::iterator&)yourDeque.Iterator();

Ion Filipski

 

[globos]

Ok, so the following code was part of your solution :

template<class T> class SequentialContainer
{
protected:
class t_iterator
{
T...
};
public:
virtual t_iterator& Iterator() = 0;
//you will be obligated to implement it in child classes

};

I thought it was a response to my previous post, it's clearer to me now. Putting iterators classes inside their containers(nested) or outside is only a matter of style then, though i prefer to keep them isolated(one class per header file principle).


> Deque<type> yourDeque;
> Deque<type>::iterator& x = (Deque<type>::iterator&)yourDeque.Iterator();

It's better to do :

 SequentialIterator<type>::iterator& x = yourDeque.Iterator();

In order to avoid to downcast the iterator returned from

Iterator ()

.
But if

Deque<type>::iterator

provides specific iteration features and clients need them , they still have to perform the downcast(a dynamic_cast is better than a C cast style? it forces to use RTTI).

Finally, I really think Qt's way is cleaner, needs no cast to work with the concrete iterator, and no references nor pointers needed.

--
Globos

 

[Cagliostro]

I can't understand, why is STL bad? Why you are trying to reinvent the bike..?

Ion Filipski

 

[globos]

STL? Please re-read my post I did not mention it, why are you talking about STL and bikes?
I was talking about Qt, not STL. I was just saying that Qt's way to use iterators is clean, and might be a good design choice concerning AllanNabhan's problem. Be careful, I am not saying to use Qt classes, but just to get inspired from them for the design the SequentialContainer iteration mechanism.
You see, i'm not completly reinventing the bike, nor the mono-bike

--
Globos

 

[AllanNabhan]

Hi !

Thank you for your interesting replies.

I am thinking of a container lib that would take full advantage of polymorphism and where, for example, algorithms
would be operating on generic interfaces; e.g.

void Sort(SequentialContainer& container);


I think this question was for me:

> I can't understand, why is STL bad? Why you are trying to reinvent the bike..?

There is nothing wrong with STL. Reinventing the bike is a good way to learn. View this as an exercise.

It is interesting to see that in both approachs, we are obliged to give up the initial interface

Iterator SequentialContainer::Iter(void);

since we now get

Iterator & SequentialContainer::Iter(void).

In the end, I may end up using QT way, as suggested, but I will also think about the possibilities offered by Ion's method.

Thank you for your help.

Allan

 

[globos]

AllanNabhan :
> It is interesting to see that in both approachs, we are
> obliged to give up the initial interface
>
> Iterator SequentialContainer::Iter(void);
>
> since we now get
>
> Iterator & SequentialContainer::Iter(void).
>
> In the end, I may end up using QT way, as suggested, but
> I will also think about the possibilities offered by
> Ion's method.

If you choose this way :

template<class T>
class SequentialContainer
{
public:
...
  virtual Iterator

<T>

& iterator () = 0;
...
};

This means that clients of this class must delete iterators, and that's why I prefer Qt's approach. But the drawback with Qt's way is that clients are obliged to use concrete iterators classes, here's a snippet of a client's code :

QPtrList<float> reals;
//fill reals ...
QPtrListIterator<float> ireal (reals);//iterator on reals
//iterate on reals ...

If a client decide to move to another collection class like a QPtrVector for example, then he has to change every declarations of QPtrListIterator to QPtrVector in his code.
Obviously, this way does not encourage iterating regardless on the actual type of containers.

In this sense, the first approach is better, and its memory management problem can be solved using std::auto_ptr class, change the interface to :

#include <memory>
using namespace std;

template<class T>
class SequentialContainer
{
public:
...
  virtual auto_ptr< Iterator<T> > iterator () const = 0;
...
};

template<class T>
class List
{
public:
...
  auto_ptr< Iterator<T> > iterator () const
  {
    return auto_ptr< Iterator<T> > (new ListIterator<T> (this));
  }
...
};

Clients can type for example :

SequentialContainer<float>* reals = new List<float>;
//fill reals ...
auto_ptr< Iterator<float> > ireal = reals.iterator ();
//iterate on reals ...
while (!ireal->is_off ())
{
  //do stuff...
  ireal->forth ();
}
//&quot;delete ireal;&quot; statement is no longer needed

This makes the code a little bit fatter but safer.

--
Globos