extending an STL container class Question

[SuperKoko]

The public inheritance in that case is an implemetation detail, and shouldn't even be known by the user.

No, public inheritance always means "IS-A", and it is known by the user, because the user can use the derived object like a base object. That means that the user can use all the member functions of the vector.

private inheritance can be an implementation detail, but public inheritance, is never an implementation detail.

And, private inheritance itself is very useful in some cases, but can generally (not always) be replaced by composition (i mean, putting a field in the class's declaration).

[SuperKoko]

About virtual destructors, you must know that it is really useless to declare virtual destructors in classes that have no virtual functions.
Let me explain.
Consider for example std::vector<SomeType>.
Somebody wants to derive many classes from std::vector<SomeType> and to create a whole polymorphic complex hierarchy.
There is no problem if he uses polymorphically all is new hierarchy, because he defines a virtual destructor (and some other virtual functions, of course, because if that was not the case he could not use polymorphically the class except for destroying it) in a base class derived from std::vector<SomeType>.

But, now he wants to use a pointer that may be a pointer to std::vector<SomeType> or be a pointer to a derived object. That is, he wants to use polymorphically, not only its own new hierarchy, but also the old hierarchy. In that case, you could think that the std::vector implementation of the STL should declare its destructor as virtual.
But it has no meaning! Because std::vector does not contain any virtual member function, what means that the programmer cannot use polymorphically a pointer to std::vector<SomeType>. Even more, if he calls operator[] (for example) on a pointer to std::vector<SomeType>, it will inlines the call.
There is a general rule : never use virtual destructor in a class that don't contain any virtual members.

So, you may think. Why the std::vector implementation of the STL has not virtual members for all his members.
There are two responses:
1) Performance will be very, very bad.
2) A vector is not designed to be derived polymorphically.
Who wants to derive from std::vector, and redefine the operator[] and use polymorphically pointers to the old std::vector, and pointers to the new derived class? At least if there were an abstract base class containing the vector operations, it would have a meaning, but since all the implementation of std::vector is contained in the vector, you are constrained to loose all the memory space of the vector implementation if you want to derive from it and use another implementation.

A general rule:
Except if the class is specifically designed to be polymorphic, and be derived by everybody (for example std::basic_streambuf), you must not use polymorphically the class hierarchy of classes that are not already polymorphic, because... You cannot... Not only the destructor may not be virtual, but also there is probably no virtual functions that you could use polymorphically, and polymorphism needs virtual functions. And everybody knows that making a function virtual don't make it virtual in the parent classes, but only in the derived classes.

But, you can always derive from a class, and create a new class hierarchy derived from this class, and in that case you can use polymorphically all your newly-defined hierarchy.

And if you think that every class should be fully polymorphic, for every member functions, then you should program with Java and not C++.

[exterminator]

Superkoko has convinced me completely. I conclude that vectors could be inherited publicly and non-polymorphically. If some one does try some polymorphic usage, that would be conceptually wrong !! And the problems he would get into are completely his responsibilities. However, in this particular case I conclude that we would be losing some flexibility when the need arises for the change of the container. Yves, Graham and wien might not agree and it would be great to get some comments from them about the things pointed out by SuperKoko.

By the way..great thread !!! Cheers to all,
Exterminator.

[Graham]

OK. Let me try.

Point 1. I strongly disagree that event_list IS-A vector<Event>. It is implemented-in-terms-of a vector. Look at it this way: if you replaced vector<> by list<> or deque<>, would you expect to be unable to write an equivalent program? I suggest that it would be very simple to replace the vector by a deque, and so and event_list is a container of events, but not uniquely a vector. So, IS-A doesn't apply, therefore public inheritance doesn't apply.

In other words, you are inherting to reuse base code, which brings us to...

Point 2. Some more from Sutter and Alexandrescu:

The purpose of public inheritance is not for the derived class to reuse base class code to implement itself in terms of the base class's code. Such an implemented-in-terms-of relationship can be entirely proper, but should be modeled by composition -- or, in special cases only, by nonpublic inheritance [...]

A new derived class is a new special case of an existing general abstraction.[...]

New requirements should naturally be met by new code; new requirements should not cause rework on existing code.

(All the above from item 37 of C++ Coding Standards).

I realise that point 2 is an argument from authority, but all I would say is that this particular authority has always worked for me in the past, and I have found that following Sutters's advice on matters like this leads to much less bugfixing and fewer problems down the line.

[HighCommander4]

Point 2. Some more from Sutter and Alexandrescu:

The purpose of public inheritance is not for the derived class to reuse base class code to implement itself in terms of the base class's code. Such an implemented-in-terms-of relationship can be entirely proper, but should be modeled by composition -- or, in special cases only, by nonpublic inheritance [...]

A new derived class is a new special case of an existing general abstraction.[...]

New requirements should naturally be met by new code; new requirements should not cause rework on existing code.

(All the above from item 37 of C++ Coding Standards).

I realise that point 2 is an argument from authority, but all I would say is that this particular authority has always worked for me in the past, and I have found that following Sutters's advice on matters like this leads to much less bugfixing and fewer problems down the line.

First of all, I don't understand how deriving from vector leads to circumstances where new requirements cause rework on existing code... could you elaborate on that?

Second, what if the users of event_list expected all of vector's functionality to come with it (operator[], push_back(), insert(), erase(), size() and so on), yet we were to follow Sutter's advice and use containment or nonpublic inheritance... we would have to write 20 or so one-line functions in the event_list class that do nothing else but call the vector equivalents... Isn't one of the major features of object-oriented programming to reuse code as much as possibl? Yet Sutter seems to suggest that re-writing all that code is appropriate in this case?

You talk about making code less bug-prone...what about all the possibilities for introducing new bugs in the process of rewriting so much code for no reason? In my opinion the situation screams for public inheritance...

I do realize that other solutions (like using non-member functions) may be viable in this case, but definitely not containment or private inheritance.

[Graham]

If you look back, my original suggestion (or, rather, jlou's, which I agreed with) - and, indeed, one the first extracts I posted from Sutter - was to implement the new functionality as a standalone (nonmember) function. That has been my postion throughout as the best solution. I have never suggested that the OP's problem should be solved by making a new class, whether one that derives from vector, nor one that aggregates vector. The new code is one new function. No rewriting, no reams of pass-through functions: one new function that meshes well with the spirit and philosophy of STL containers.

Of course you run the risk of introducing bugs as you've suggested. That's why I have not advocated doing it that way. But I firmly disagree that it screams for public inheritance. It does not, for reasons that I outlined in the post you've just quoted: the situation does not model IS-A, and for the reasons given by Sutter and Alexandrescu. That posting was an argument against public inheritance, not for containment.

[NMTop40]

There is a "cheat" way to bring in all your functionality of vector without having to derive from it.

Overload operator-> (if it isn't already used).

So

class EventList
{
private:
   std::vector< Event > m_events;

public:
   std::vector< Event > * operator->() { return &m_events; }
   const std::vector< Event > * operator->() const { return &m_events; }
};

Ok, operator[] is now messy so overload that too. But the rest like push_back you get automatically.

class EventList
{
public:
   typedef std::vector< Event > vector_type;
   typedef vector_type::size_type size_type;
private:
   vector_type m_events;

public:
  
   vector_type * operator->() { return &m_events; }
   const vector_type * operator->() const { return &m_events; }
   Event& operator[] ( size_type i ) { return m_events[i]; }
   const Event & operator[] ( size_type i ) const { return m_events[i]; }
};

[wien]

and it would be great to get some comments from them about the things pointed out by SuperKoko.

Ask, and ye shall recieve.

No, public inheritance always means "IS-A", and it is known by the user, because the user can use the derived object like a base object. That means that the user can use all the member functions of the vector.

private inheritance can be an implementation detail, but public inheritance, is never an implementation detail.

I was talking about the CRTP (Curiously Recurring Template Pattern) classes in boost, not the event_list/vector relationship. They are used to implement a lot of member-function s "on behalf" of classes inheriting from them. boost::iterator_facade for example implements all the operators an STL iterator needs, based on four functions (increment, decrement, equal and dereference) implemented in the derived class. This is done without any kind of polymorphism (run-time that is), and the CRTP classes will never be used in client code, and certainly not to achieve any kind of polymorphism.

In those cases I would consider public inheritance an implementation detail, and thus, not a case of IS-A.

About virtual destructors, you must know that it is really useless to declare virtual destructors in classes that have no virtual functions.
Let me explain.<snip>

Well, yes. But to make a class meant to be used as a base class, without any virtual functions is somewhat of a design-flaw in my opinion. What would then be the point in deriving from it? Code reuse? In that case I refer to the quotes Graham posted.

Furthermore, nothing is preventing users from deleting a derived object through a pointer to the virtual-less base, so that could still lead to problems. (I admit the chance of that happening is very slim with no polymorphism possible, but as I have said before, that doesn't make it okay. People do strange things sometimes, and it's always better to try to limit their possibilities to do so.)

So, you may think. Why the std::vector implementation of the STL has not virtual members for all his members.
There are two responses:
1) Performance will be very, very bad.
2) A vector is not designed to be derived polymorphically.
Who wants to derive from std::vector, and redefine the operator[] and use polymorphically pointers to the old std::vector, and pointers to the new derived class? At least if there were an abstract base class containing the vector operations, it would have a meaning, but since all the implementation of std::vector is contained in the vector, you are constrained to loose all the memory space of the vector implementation if you want to derive from it and use another implementation.

The primary reason STL containers don't have virtual members, is that their design are not really based on OOP at all, but rather generic programming. The Container/Iterator/Algorithm concepts introduced in the STL give us a much better way of extending it's functionality, rendering inheritance more or less useless for that purpose.

[SuperKoko]

But to make a class meant to be used as a base class, without any virtual functions is somewhat of a design-flaw in my opinion. What would then be the point in deriving from it? Code reuse? In that case I refer to the quotes Graham posted.

But which functions must be virtual?
Consider the class complex which represents a complex number.

Which functions should be virtual?
To allow the best flexibility the solution is to define an abstract base class (not doing so don't allow to change the numbers representation) containing these virtual functions:
real, imag, conj, norm, arg, pow, operator+(), operator-(). abs, cos, sin, exp, log, log10, tan, atan, tanh, sinh, cosh, acos, asin.

The binary operators should also be defined.

Many of these functions can have a default implementation that use one of the base accessors : real, imag, arg, norm and conj.

For binary operators, that is more complex, because even if we let them pure in the base class, in the derived classes we must choose to return a representation depending on the first parameter of the operator (that is the this pointer), but not depending on the second parameter.

Now, we want to implement 4 derived classes.
ScalarFloatComplex (with a representation containing a float real part, and a float imaginary part)
PolarFloatComplex (containing floats for argument and magnitude).
ScalarDoubleComplex
PolarDoubleComplex

Note that the accessors of the base class, are all returning double.
Now the real problem comes in the implementation of binary operators.

We want that a ScalarFloatComplex+a ScalarDoubleComplex returns a ScalarDoubleComplex and not a ScalarFloatComplex.
But in the ScalarFloatComplex:perator*(complex &x) we cannot know if x uses floats or doubles without doing RTTI (but doing RTTI breaks the genericity), so we choose to return a ScalarDoubleComplex.
And, we can just do an implementation that use the complex::real and complex::imag virtual member functions.

In fact, if you look at all operators of all complex numbers you will see that there will be many conversions from float to double and polar to scalar representation or scalar to polar representation. And writing x+y is not the same as writing y+x if x and y are not using the same representation.

In fact, it is preferable to use only one representation for all complex numbers (or at least don't mix representations).

But, now consider extending the standard complex class.
Why can we extends this class?
Not to modify the representation, because it is already defined!

But, we can add new member functions, and no fields. But for that we should not derive, but just add non-member functions.

We can derive to add caching informations.
That is a true concrete application of derivation.
For example, we want to cache the magnitude of the complex number, because we write an application that needs many call to the norm functions.
The ComplexWithMagnitudeCached class is just deriving from complex, and redefines the norm class, and adds a double magnitude; field whose value is initiated to +NAN.

So, we can think that the best is to declare all functions as being virtual in the complex class, because derived classes can derive from them.

But, you don't need that!
You can redefine norm in the derived class without needing this function be virtual.
And it is really absolutely sure that you will not use this class polymorphically with a pointer that can points either to complex or to ComplexWithMagnitudeCached. You will use ComplexWithMagnitudeCached everywhere needed, and complex everywhere you don't need that the norm be computed fastly, and write a conversion operator from complex to ComplexWithMagnitudeCached, but you will never have polymorphic pointers. Moreover if we manipulate polymorphic pointers we cannot know if the norm function executes fastly or not. It is far better to don't use polymorphism here.

Moreover a ComplexWithMagnitudeCached can be used perfectly with functions (of a foreign library for example) that use pointers or references (or values) to the complex class.
The only thing you must know, is that the norm function of the base class will be called instead of the optimized function of the derived class. What is not really a problem, because this function do its work correctly. Yes, the optimization will not be used, but if the library do much computing that really needs to compute fastly magnitudes, be sure that there is no problem, because this library probably uses its own optimized representation in internal computings (if it is an optimal library).

Moreover in many situations we use complex values (and not pointers nor references). And in that case polymorphism is totally useless.
And polymorphism is really not cheap for complex numbers, because:
1) It needs a Vitual Table pointer which uses 4 bytes, and for alignment reasons the compiler (or the programmer) will align on 8 bytes boundary the structure, so it uses 24 bytes instead of 16 bytes.
2) since most of the frequently used functions of complex are very simple, making them virtual reduce by a not-negligible factor the speed (even if this factor is not exorbitant).

The memory space factor is probably the more important.

The complex class can be derived, but is cannot be polymorphically used, what does not means that its derived classes can't be polymorphically used.

If you need to use polymorphically a whole complex number hierarchy, you can. You just need to derive the base class of your hierarchy from complex, and to redefines as virtual, exactly all the functions you need to be virtual (including very probably the destructor).

So, by not putting any virtual functions in the complex class, the flexibility is maximized. Because you can choose, when you derive from it, to not define any virtual function (the most probable), or to defines exactly the functions you need as virtual (probably totally new functions, and probably not already existing functions in the complex class).

You must know that if an exisiting hierarchy is not polymorphic that don't means that all derived classes cannot be polymorphic, and that don't means also that the already existing hierarchy is bad. It just means that the already existing hierarchy has no need to be polymorphically used. Because, for example, all functions don't need to be redefined polymorphically. They are defined optimally and do exactly the job they need to do.

[SuperKoko]

An other application of derivation from complex, is defining the PureImaginary deriving from complex, with a one-argument constructor (the imaginary part of the complex number), and some new member functions (i don't know which functions we can put, but there are probably some member functions specific to pure imaginary numbers).
We don't need polymorphism.
We can redefine a few functions like norm for example, to have a faster function.

And, if we needed some optimized computing with pure imaginary numbers, by defining a non-member function:
complex &complex:perator*(const PureImaginary &);

And some few other functions.
And where we have a pointer to a complex number without knowing if it is a pointer to complex or PureImaginary, the base functions will be used, producing a little-less-performant code, but a code probably far more performant that a code using virtual functions. And we will probably not use many pointers to complex, instead we will probably use some complex values, or non-polymorphic (i means a pointer to complex that cannot be a pointer to PureImaginary, or a pointer to PureImaginary) references or pointers.

And, if there is one functions whose polymorphism is really needed because it is executed 10000 times faster with PureImaginary and there is code where there are pure imaginary and complex numbers mixed.

We can derive from complex, and this virtual function (and a virtual destructor), and derive PureImaginary from this new base class (named NewComplex for example), and not use the complex class at all in all the project (except for conversions from NewComplex to complex for calling already defined functions that works with complex in foreign libraries for example, but you can see that adding a virtual function don't limit the usage of NewComplex. NewComplex IS-A complex, and can be used as a complex).

But, probably a better thing to do (not the best solution), is deriving from complex just one class named ComplexOptimizedForPureImaginaryOperations for example, and redefine the function we optimize, and only this one, and in this function we just compare the real part of the complex to zero. And if it is zero, we use the optimized code, and invoke the old function if it is non-zero.
Now, we just use the ComplexOptimizedForPureImaginaryOperations class in all our project.
And this solution works if new Imaginary numbers appear (by doing operations on non-pure-imaginary complex numbers that produces a pure imaginary number)

In fact, the best solution is probably to define a non-member function named Fast[The operation name] that takes a complex argument and does the fast processing needed after comparing the real part to zero.
It follows the rule : only derive if the new class IS-A base class, and IS-MORE-THAN the base class.

I hope that these examples will show you that, even if polymorphism is one of the best thing ever, it is not needed everywhere, and must not be declared where really not needed.

[SuperKoko]

There is a "cheat" way to bring in all your functionality of vector without having to derive from it.

It is cute, but even if the derivation term don't apply, all what is implied by public derivation is implied.
I think that you are perfectly conscious of that.

[SuperKoko]

Ask, and ye shall recieve. I was talking about the CRTP (Curiously Recurring Template Pattern) classes in boost, not the event_list/vector relationship. They are used to implement a lot of member-function s "on behalf" of classes inheriting from them. boost::iterator_facade for example implements all the operators an STL iterator needs, based on four functions (increment, decrement, equal and dereference) implemented in the derived class. This is done without any kind of polymorphism (run-time that is), and the CRTP classes will never be used in client code, and certainly not to achieve any kind of polymorphism.

In those cases I would consider public inheritance an implementation detail,

Yes, it is an implementation detail, since it is possible to write a STL that don't derive iterators from iterator_facade, but the "IS-A" rule is respected.
The name iterator_facade is not well choosed. iterator is a better term to name this class. But because the name iterator is reserved to be typedefed in container classes, it is not used.

And you probably understand that vector<>::iterator IS-AN iterator, that is an object that basically accepts operator++ operator= and operator*

But, programmers can be aware of not of the existence of the base class iterator.

In the same order of idea : Humans are primates. And everybody know the member functions of primates, but there are (not much) people that don't know that humans are primates, but these people know all the member functions of primates, and just think that these member functions are part of the declaration of humans.

It is a classification. And in a classification you can choose to simplify the hierarchy, producing a less flexible hierarchy, and producing some duplicate declarations. But, even if more than one classification can be correct, and choosing one classification and not another can be arbitrary. the IS-A rule is never violated in a given classification.

To be more precise there are two possible rules:
public inheritance can means "IS-A" or "IS-AN"

[NMTop40]

iterators are designed to be copyable and therefore there is a problem if they derive from a base class because you may get a slicing problem.

The way to make a generic iterator copyable is:

- Have an abstract base class behind it that performs functionality such as increment(), decrement(), dereference() and isequal()

- Your iterator needs a pointer to the generic iterator and performs all its functionality through it. Thus your iterator is a concrete class.

- For RAII the pointer must be reference-counted and must also be copy-on-write.

- Most of the implementation is easy, except isequal(). However if you add in another function isend() then you can test for equality by seeing if &(dereference()) == &(rhs.dereference() ) when neither of them are end(). (This is not guaranteed, however).

if ( isend() )
{
   return rhs.isend();
}
else
{
   return ! rhs.isend()  && 
       &(dereference()) == &(rhs.dereference() );
}

This is not guaranteed to work either, especially for const iterators.