Designing a const-correct iterator hierarchy

[Lorenzo Castelli]

This is an old problem of mine.

Basically I have an abstract base class which represents a generic iterator
over a collection of elements, and various derived classes that implement
the traversing on specific data structures.
For each iterator I want to be able to specify the four possible const
combinations, corresponding to the various [const] void* [const] for
pointers, with the possibility to perform conversions from non-const to
const just like you can do with pointers.
Also I obviously want the conversions from the specific iterators to the
generic base.

The first solution I employed was to create a hierarchy like
AbstractConstIterator <-- AbstractIterator <-- ConcreteIterator.
Client code used just AbstractConstIterator and AbstractIterator, so that
all possible combinations of const and all conversions were possible.

Unfortunately the elements pointed by the iterators are themselves a
hierarchy, and in particular there is an AbstractElement class and some
derived ConcreteElement. Each ConcreteIterator corresponds to a particular
ConcreteElement.
Also the various ConcreteElement classes extend the functionalities
available in the abstract base class with some new methods specific of the
type.
Since the client code sometimes needs to access those specific
functionalities, I had to make ConcreteIterator externally visible and
provide the specific ConcreteElements using covariance return.

In order to provide the four possible combinations of const and all the
required conversions, I changed the hierarchy this way:
- AbstractConstIterator <-- AbstractIterator
- AbstractConstIterator <-- ConcreteConstIterator
- AbstractIterator, ConcreteConstIterator <-- ConcreteIterator

Then I made the two inheritances from AbstractConstIterator virtual, in
order to avoid a double base class in ConcreteIterator (among the other
things, to avoid problems when comparing pointers to AbstractConstIterator
for equality).

Now the problem is that, while this design works correctly and provides the
functionalities I need, I don't like the fact that I'm using a run-time
facility (virtual inheritance) only to solve a compile-time problem
(const-correctness).

I thought this scenario were pretty common, but I haven't been able to find
previous discussions about it.

Do you have any suggestion?

 

[Greg]

This is an old problem of mine.

Basically I have an abstract base class which represents a generic iterator
over a collection of elements, and various derived classes that implement
the traversing on specific data structures.
For each iterator I want to be able to specify the four possible const
combinations, corresponding to the various [const] void* [const] for
pointers, with the possibility to perform conversions from non-const to
const just like you can do with pointers.
Also I obviously want the conversions from the specific iterators to the
generic base.

The first solution I employed was to create a hierarchy like
AbstractConstIterator <-- AbstractIterator <-- ConcreteIterator.
Client code used just AbstractConstIterator and AbstractIterator, so that
all possible combinations of const and all conversions were possible.

Unfortunately the elements pointed by the iterators are themselves a
hierarchy, and in particular there is an AbstractElement class and some
derived ConcreteElement. Each ConcreteIterator corresponds to a particular
ConcreteElement.
Also the various ConcreteElement classes extend the functionalities
available in the abstract base class with some new methods specific of the
type.
Since the client code sometimes needs to access those specific
functionalities, I had to make ConcreteIterator externally visible and
provide the specific ConcreteElements using covariance return.

In order to provide the four possible combinations of const and all the
required conversions, I changed the hierarchy this way:
- AbstractConstIterator <-- AbstractIterator
- AbstractConstIterator <-- ConcreteConstIterator
- AbstractIterator, ConcreteConstIterator <-- ConcreteIterator

Then I made the two inheritances from AbstractConstIterator virtual, in
order to avoid a double base class in ConcreteIterator (among the other
things, to avoid problems when comparing pointers to AbstractConstIterator
for equality).

Now the problem is that, while this design works correctly and provides the
functionalities I need, I don't like the fact that I'm using a run-time
facility (virtual inheritance) only to solve a compile-time problem
(const-correctness).

I thought this scenario were pretty common, but I haven't been able to find
previous discussions about it.

Do you have any suggestion?

The obvious question to ask is why not model these iterators after one
of the five categories of iterators defined in the Standard Library? In
addition to the five iterator categories, the Standard defines both
constant and mutable iterators - depending on whether the referenced
value can be modified through the iterator. The Standard's constant and
mutable iterators seem to correspond quite closely to two of the
iterator types in your model. And these are the only two cases that
really need to be modeled explicitly. For iterator instances that are
themselves const, the "const" keyword applied to the iterator variable
declaration should be sufficient. In other words, two of your four
iterators can be modeled at the language level.

Using the Standard Library iterators (found <iterator>) as a model for
your own iterator classes would also address your primary complaint.
Because in order to implement a compile-time solution, it will be
necessary to forego an iterator model that relies on inheritance and
use one that is based on templates instead. The latter model inherently
describes runtime relationships, while the former inherently describes
relationships defined at compile-time. Therefore the Standard library
iterator model - which is implemented with templates - would provide a
compile-time solution.

Greg

 

[Lorenzo Castelli]

The obvious question to ask is why not model these iterators after one
of the five categories of iterators defined in the Standard Library? In
addition to the five iterator categories, the Standard defines both
constant and mutable iterators - depending on whether the referenced
value can be modified through the iterator. The Standard's constant and
mutable iterators seem to correspond quite closely to two of the
iterator types in your model. And these are the only two cases that
really need to be modeled explicitly. For iterator instances that are
themselves const, the "const" keyword applied to the iterator variable
declaration should be sufficient. In other words, two of your four
iterators can be modeled at the language level.

Using the Standard Library iterators (found <iterator>) as a model for
your own iterator classes would also address your primary complaint.
Because in order to implement a compile-time solution, it will be
necessary to forego an iterator model that relies on inheritance and
use one that is based on templates instead. The latter model inherently
describes runtime relationships, while the former inherently describes
relationships defined at compile-time. Therefore the Standard library
iterator model - which is implemented with templates - would provide a
compile-time solution.

The fact is that I need a "late-binding" solution. I probably didn't make
myself sufficiently clear.

I need the class hierarchy and the virtual functions because I need to
handle situations where the type of the iterator can be known only at
runtime.
For example I sometimes have containers of heterogeneous data structures,
and I have to implement algorithms that apply some function (that involves
traversing) to all the structures in the container. In this case virtual
functions are obviously required to select the right traversal algorithm for
each single structure in the container.
So I'm perfectly okay with virtual functions and I actually need that kind
of runtime support.

What I don't like too much is the fact the current design forces me to use
virtual inheritance too.
Since the iterators down in the hierarchy provide additional
functionalities, I have to make them publicly available. And each of them
should be able to be specified in all the four const combinations.

As you said I can use the const keyword to provide two combinations, so I'm
left to design only constant and mutable iterators.
Now the problem is with derived mutable iterators: this kind of iterators
should be able to be used in any situation a base mutable iterator is
required (so I derived from it), and also should be usable where a derived
constant iterator is required (so I derived from this class too). And this
is where multiple inheritance comes up, and consequently the use of virtual
inheritance.

Conversely suppose that I didn't care about const-correctness, and I just
provided support for mutable iterators.
In this case the hierarchy would be simply composed by
AbstractMutableIterator <-- DerivedMutableIterator. No need for multiple
(and virtual) inheritance.

So here is my problem: in my design I had to add virtual inheritance just to
provide support for const-correctness. A runtime facility for a compile-time
feature.
That's why I don't like my design too much and I'm wondering if there exists
alternative solutions.