Virtual Iterators

[richard.forrest1]

I have a problem with an abstract interface class whose implementation
classes need to return different iterator types (but with the same
value_types etc).

Classes A and B both conform to the same abstract Interface class. Interface
has a pair of virtual functions begin() and end() that generate a typical
STL style range. Classes A and B provide different implementations, maybe
using different types of container. The problem is that, to conform to the
interface, A and B must return the same type (or a derived type). They can
not do this directly as their containers (and hence their iterators) are of
different types.

class Interface
{
public:
virtual VirtualIterator begin() = 0;
virtual VirtualIterator end() = 0;
};

class A : public Interface
{
public:
virtual VirtualIterator begin() {return
make_virtual_iterator(container_.begin());}
virtual VirtualIterator end() {return
make_virtual_iterator(container_.end());}
private:
OneKindOfContainer container_;
};

class B : public Interface
{
public:
virtual VirtualIterator begin() {return
make_virtual_iterator(container_.begin());}
virtual VirtualIterator end() {return
make_virtual_iterator(container_.end())}
private:
AnotherKindOfContainer container_;
};

I think I see how to solve this problem by creating (as the example hints
at) a kind of VirtualIterator class that maintains a pointer to heap based
copy of the real iterator. But this issue must be fairly common and I would
much rather reuse a tried and tested solution than roll my own. I looked at
the boost iterator library but it does not seem to provide what I am looking
for. This made me a bit concerned because it seems to be very well thought
out and comprehensive. Is there something fundamentally wrong with what I am
considering here? Or perhaps there is a really trivial solution I am
overlooking?

Richard Forrest

 

[Victor Bazarov]

I have a problem with an abstract interface class whose implementation
classes need to return different iterator types (but with the same
value_types etc).

Classes A and B both conform to the same abstract Interface class. Interface
has a pair of virtual functions begin() and end() that generate a typical
STL style range. Classes A and B provide different implementations, maybe
using different types of container. The problem is that, to conform to the
interface, A and B must return the same type (or a derived type). They can
not do this directly as their containers (and hence their iterators) are of
different types.

class Interface
{
public:
virtual VirtualIterator begin() = 0;
virtual VirtualIterator end() = 0;
};

class A : public Interface
{
public:
virtual VirtualIterator begin() {return
make_virtual_iterator(container_.begin());}
virtual VirtualIterator end() {return
make_virtual_iterator(container_.end());}
private:
OneKindOfContainer container_;
};

class B : public Interface
{
public:
virtual VirtualIterator begin() {return
make_virtual_iterator(container_.begin());}
virtual VirtualIterator end() {return
make_virtual_iterator(container_.end())}
private:
AnotherKindOfContainer container_;
};

I think I see how to solve this problem by creating (as the example hints
at) a kind of VirtualIterator class that maintains a pointer to heap based
copy of the real iterator. But this issue must be fairly common and I would
much rather reuse a tried and tested solution than roll my own. I looked at
the boost iterator library but it does not seem to provide what I am looking
for. This made me a bit concerned because it seems to be very well thought
out and comprehensive. Is there something fundamentally wrong with what I am
considering here? Or perhaps there is a really trivial solution I am
overlooking?

For now, having only thought about your problem for a minute, I have only
one question: what are you going to do with 'VirtualIterator'? What does
its interface look like? I can see it that you are going to compare its
value to 'end' to know when to stop iterating, but I cannot imagine yet
if you have two different and unrelated containers, what else you could
do with a VirtualIterator object. Unless, of course, it's an iterator that
conforms to the iterator semantics laid out in the Standard, then it has to
have 'value_type' and 'reference' and ...

Do you have the answers?

V

 

[Siemel Naran]

For now, having only thought about your problem for a minute, I have only
one question: what are you going to do with 'VirtualIterator'? What does
its interface look like? I can see it that you are going to compare its
value to 'end' to know when to stop iterating, but I cannot imagine yet
if you have two different and unrelated containers, what else you could
do with a VirtualIterator object. Unless, of course, it's an iterator that
conforms to the iterator semantics laid out in the Standard, then it has to
have 'value_type' and 'reference' and ...

I imagine you can pass VirtualIterator to standard functions like std::copy.
Here is one implementation. It has to be copy constructible, so it won't be
a polymorphic class. It will define a nested polymorphic abstract class
implement that represents the real iterator (though it does not have to be a
nested class), and this class will have pure virtual functions for cloning,
assigment, increment, decrement, equal. VirtualIterator will contain a
std::auto_ptr<implement> or the like. Derived classes like class A above
will define concrete iterator implement classes. Here is my implementation.


template <class T>
class poly_iterator
{
public:
typedef std::forward_iterator_tag iterator_category;
typedef T value_type ;
typedef T & reference ;
...

class implement; // abstract class

poly_iterator(implement * iter) : d_iter(iter) {} // take ownership of
object
poly_iterator(const poly_iterator& that) :
d_iter(that.d_iter->clone()) { }
poly_iterator& operator=(const poly_iterator& that);
~poly_iterator() { delete d_iter; }

bool operator==(const poly_iterator& that) const
{ same(*this,that); return this->d_iter->equal(*that.d_iter); }
bool operator!=(const poly_iterator& that) const;

reference operator*() const { return d_iter->get(); }
pointer operator->() const { return &d_iter->get(); }
poly_iterator& operator++() { d_iter->next(); return *this; }


public:
class implement
{
public:
virtual ~implement() { }
virtual implement * clone() const = 0;
virtual bool equal(const implement&) const = 0;
virtual T& get() const = 0;
virtual void next() = 0;
virtual void prev() = 0;
};

template <class Iter>
class usualimplement : public implement {
public:
typedef Iter actual_iterator;
explicit usualimplement(Iter iter) : d_iter(iter) { }
usualimplement * clone() const { return new
usualimplement(*this); }
bool equal(const implement& that) const { return this->d_iter
==static_cast<const usualimplement&>(that).d_iter; }
T& get() const { return *d_iter; }
void next() { ++d_iter; }
void prev() { --d_iter; }
private:
Iter d_iter;
};


private:
implement * d_iter; // dynamically created object

static void same(const poly_iterator& lhs, const poly_iterator& rhs)
{ assert(typeid(*lhs.d_iter)==typeid(*rhs.d_iter)); }
};

 

[Victor Bazarov]

I imagine you can pass VirtualIterator to standard functions like

std::copy.

std::copy is not a function. It's a template.

Here is [...]

I still would like to hear from the OP...

 

[richard.forrest1]

I have just done a Google search on "polymorphic iterator" and it is a well
known concept. There is even a reference to it in GOF (page 271).

It seems I was just calling it the wrong thing.

Thanks for you help guys,

Richard

 

[richard.forrest1]

----- Original Message -----
From: "Victor Bazarov" <[email protected]>
Newsgroups: comp.lang.c++
Sent: Saturday, April 03, 2004 5:00 AM
Subject: Re: Virtual Iterators


First of all I take Siemel Narans hint that VirtualIterator would be better
named PolymorphicIterator and have done so from now on. This is really a
response to Victor's questions. I am looking at Siemel's example code snipet
now (thanks) and will respond to this when I think I understand it properly.

The PolymorphicIterator conforms to one of the STL iterator concepts.
The purpose of PolymorphicIterator is that any client of an Interface object
can iterate through all or part of the range [begin(),end()) without having
to know the type of the underlying container. Of course the iterators
underlying the PolymorphicIterator must have the same value_type etc. They
must also conform to the PolymorphicIterator's STL iterator concept.

I am not trying to write a "universal container class" or anything silly
like that. All I want to do is provide a limited interface for a client to
be able to read the a range of attribute values.

Let me give a simple (contrived) example of the use of this. We have an
interface class AbstractPolygon and two derived classes ConstantPolygon and
ChangablePolygon. A ConstantPolygon object represents a polygon that can not
be edited. A ChangablePolygon object represents a polygon whose vertices may
be inserted or erased.

AbstractPolygon provides a pair of virtual abstract functions vertexBegin(),
vertexEnd() that provide a sequence of the vertices of the polygon.
ConstantPolygon and ChangablePolygon provide implementations of these
functions. ConstantPolygon's underlying representation happens to be a
vector of vertices. But ChangablePolygon's underlying representation is
chosen to be a linked list of vertices.

Now clients that perform constant operations (e.g. rendering, calculating
area etc) just need to use AbstractPolygons. They use the AbstractPolygon's
vertexBegin() and vertexEnd() functions to obtain the start and end of the
range of vertices and iterate through it, doing whatever they do. The
PolymorphicIterator hides the fact that the underlying iterator may be a
vector<Vertex>::const_iterator or a list<Vertex>::const_iterator.

Of course there are other ways to solve this problem. We could provide a new
virtual abstract member function in AbstractPolygon and a corresponding
implementation in each derived class for every possible use of the
iterators. But this couples the algorithms too tightly to the polygons.
Adding new algorithms would be very inconvienient. Using the Visitor pattern
might help in some ways but adds its own restrictions. In this case
PolymorphicIterators are what are required.


Thanks for your comments.

Richard

 

[richard.forrest1]

In case anyone is interested I have just discovered that Boost has a
polymorphic iterator class being developped right now.
They call it boost::any_iterator. It sounds like just what I want )))

See link for details.
http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?LibrariesUnde
rConstruction


Thanks once again.

Richard