abstract base class containing class

[scg_]

What follows is a question by an absolute beginner – you have been warned:
I am using the following class layout, which is inspired by Bruce
Eckel's "Thinking in C++":

template <class T>
class B {
private:
T* data_;
int size_;
public:
int size() const {return size_;}
class iterator;
friend class iterator;
class iterator {
T* p;
public:
iterator(): p(0) {}
iterator(const B<T>& x): p(x.data) {}
T& operator*() {return *p;}
T* operator++(){return ++p;}
};
iterator begin() const {return iterator(*this);}

\\...

};

Furthermore, I define a function operating on B objects,
essential_function(const B &), which relies on the member function
explicitly listed above. Since I recently decided to change the
implementation of some of the details of B, I thought setting up an
abstract base class would be auspicious. In particular, I was hoping to
implement the algorithm in terms of the purely virtual member functions
of the abstract class:

template <class T>
class A {
public:
virtual int size() const = 0;
class iterator;
friend class iterator;
class iterator {
public:
virtual T& operator*() const = 0;
virtual T* operator++() = 0;
};
virtual iterator begin() const = 0; // error
};

class B : public A<T> {
//...
};

Unfortunately, this class A layout does not compile due to covariant
return type issues, i.e. B<T>::iterator B<T>::begin() overrides
A<T>::iterator A<T>::begin().
When I comment the line "virtual iterator begin() const = 0", it
compiles. However, not much is gained, since I can not implement
essential_function(const A &) in terms of the abstract class A:

template <class T>
void essential_function(const A<T>& x) {
typename A<T>::iterator iter;
iter = x.begin();
}

error: cannot declare variable `iter' to be of type `A<T>::iterator'
because virtual functions are abstract ... and A<T> has no has no
member named 'begin'.

Don't get me wrong - I am not particularly surprised about the errors
(now that I spend some time thinking about it).
Still, how can I implement what I (in essence) suggest above?

Thanks

 

[Alf P. Steinbach]

* scg_:

What follows is a question by an absolute beginner – you have been warned:

It's unclear what you're trying to achieve.

It does seem as if you're strongly focused on some particular imagined solution
instead of the desired result.

I am using the following class layout, which is inspired by Bruce
Eckel's "Thinking in C++":

template <class T>
class B {
private:
T* data_;
int size_;
public:
int size() const {return size_;}
class iterator;
friend class iterator;
class iterator {
T* p;
public:
iterator(): p(0) {}
iterator(const B<T>& x): p(x.data) {}
T& operator*() {return *p;}
T* operator++(){return ++p;}
};
iterator begin() const {return iterator(*this);}

\\...

};

This looks like a DIY version of std::vector.

Use std::vector.


Cheers & hth.,

- Alf

 

[scg_]

* scg_:

It's unclear what you're trying to achieve.

It does seem as if you're strongly focused on some particular imagined
solution instead of the desired result.

This looks like a DIY version of std::vector.

Use std::vector.

Yes, this is true. I am after a solution that in essence resembles the
STL and the examples given in Bruce’s book. In short, I firstly want to
be able to instantiate objects that make accessible an iterator by means
of, e.g.

typename B<T>::iterator iter;
iter = x.begin();

(and similarly for class C<T>, D<T>, ...) and, secondly, I want to
program algorithms for these objects in terms of an abstract base class
A instead of B, C, .... I do not want to utilize templates to achieve
this, since the B objects are special insofar as they do require the
availability of certain member functions. Is this more revealing?
Concerning STL vectors or valarrays or ublas (my context is numerics),
you wouldbe right too, if I were about to implement production code.
However, I am only trying to get acquainted with the language. At the
current state, my implementation generalizes (arbitrary types and copy
on write semantics) Todd Veldhuizen’s "Expression Templates"
contribution in the 1994 C++ Report. It took me a while to comprehend
his approach, however I feel having substantially advanced in my command
of c++ in this way. If I were able to also enforce the class layout
described above, I would take another step towards understanding c++. On
the other hand, if the design is flawed from the beginning this would
also add to my c++ comprehension. std::vector are not what I am
currently after (and on the source level they are still too intimating).
Instead, DIY is the theme.

Thank you

 

[Noah Roberts]

template <class T>
class A {
public:
virtual int size() const = 0;
class iterator;
friend class iterator;
class iterator {
public:
virtual T& operator*() const = 0;
virtual T* operator++() = 0;
};
virtual iterator begin() const = 0; // error
};

This interface is broken in at least two ways. First, operator++ should
not return a T*, but an iterator reference (return *this after
incrementing). Second, you can't use polymorphism with static objects.
If you want iterator to be polymorphic, and the begin() function to be
able to return a sub, then you need to use heap allocation and the begin
function needs to return a pointer, reference, or some smart object that
can encapsulate the heap allocation (shared_ptr, auto_ptr, etc).
Otherwise, even if you do adjust begin() to return an iterator you'll
run into slicing and what the client gets will be an A<>::iterator, not
a subclass (in this case that just plain won't compile since iterator is
abstract).

Quite frankly, I doubt you need to do this. The strength of STL objects
is their use of compile time polymorphism. Trying to override that
seems to be a lot of work with little benefit. I've never needed to do
it. Doesn't mean you don't...just that you may not be looking at all
available solutions.

 

[James Kanze]

This interface is broken in at least two ways. First,
operator++ should not return a T*, but an iterator reference
(return *this after incrementing). Second, you can't use
polymorphism with static objects.

I'm not sure what you're trying to say with that last statement.
Objects with static lifetime can certainly be polymorphic. More
fundamentally, I think polymorphism is more an issue of types,
rather than object lifetime. But I'm pretty sure you're aware
of this, so you must be trying to say something different.

If you want iterator to be polymorphic, and the begin()
function to be able to return a sub, then you need to use heap
allocation and the begin function needs to return a pointer,
reference, or some smart object that can encapsulate the heap
allocation (shared_ptr, auto_ptr, etc). Otherwise, even if
you do adjust begin() to return an iterator you'll run into
slicing and what the client gets will be an A<>::iterator, not
a subclass (in this case that just plain won't compile since
iterator is abstract).

What you really need is the letter-envelope idiom, which permits
"values" to be polymorphic. It works, but it's fairly
complicated, and it has very significant runtime overhead. It
also tends to confuse readers, because value types don't
normally behave polymorphically.

Quite frankly, I doubt you need to do this. The strength of
STL objects is their use of compile time polymorphism.

One can argue whether this is a strength or a weakness. It
certainly reduces flexibility. On the other hand, any idiom
which assigns value semantics to things like iterators more or
less has to do so, or pay an enormous price in terms of
execution speed.

Trying to override that seems to be a lot of work with little
benefit. I've never needed to do it. Doesn't mean you
don't...just that you may not be looking at all available
solutions.

Making STL iterators polymorphic is fighting the system; you
just can't win.

There are cases where polymorphic iterators are useful.
Typically (at least in my experience), they're also cases where
you need reference semantics for iterators. In such cases, you
don't use the STL. You might use C++'s other iterator model,
std::streambuf, but that carries some extra baggage, and has a
number of restrictions (since it was designed to be used in a
special case of iterating only). Or you role your own; a simple
GoF iterator with reference semantics isn't very difficult, and
can trivially be made polymorphic.

 

[scg_]

This interface is broken in at least two ways. First, operator++ should
not return a T*, but an iterator reference (return *this after
incrementing). Second, you can't use polymorphism with static objects.
If you want iterator to be polymorphic, and the begin() function to be
able to return a sub, then you need to use heap allocation and the begin
function needs to return a pointer, reference, or some smart object that
can encapsulate the heap allocation (shared_ptr, auto_ptr, etc).
Otherwise, even if you do adjust begin() to return an iterator you'll
run into slicing and what the client gets will be an A<>::iterator, not
a subclass (in this case that just plain won't compile since iterator is
abstract).

Yes, this is exactly what I am observing. I was not aware of the term
"slicing" to indicate this issue.

Quite frankly, I doubt you need to do this. The strength of STL objects
is their use of compile time polymorphism. Trying to override that
seems to be a lot of work with little benefit. I've never needed to do
it. Doesn't mean you don't...just that you may not be looking at all
available solutions.

Thank you very much. Your comments have been exceedingly revealing.

 

[Noah Roberts]

Yes, this is exactly what I am observing. I was not aware of the term
"slicing" to indicate this issue.

See Scott Meyers, Effective C++.