Re: A deque containing different types of objects (with a common base class)
Juha Nieminen wrote:
Kai-Uwe Bux wrote:
Not quite: shared_ptr<> does not require the base type to have a virtual
destructor. It will invoke the correct destructor for the derived type.
Let's see if I understand that. If you do this:
shared_ptr<BaseClass> ptr = new DerivedClass;
then 'ptr' will contain a BaseClass-type pointer (which points to an
object of type DerivedClass) and, I assume, a pointer to the destructor
function of DerivedClass (as a void(*)() function pointer)? (One could
wonder why waste memory to do this since that's exactly what virtual
functions are for, and if BaseClass does have a virtual destructor then
the pointer will be basically a useless waste of memory, but that's
besides the point.)
First, let's confirm that shared_ptr<> behaves as promised:
struct Base {
virtual
void id ( void ) {
std::cout << "calling base\n";
}
~Base ( void ) {
std::cout << "destroying Base\n";
}
};
struct Derived : public Base {
virtual
void id ( void ) {
std::cout << "calling derived\n";
}
~Derived ( void ) {
std::cout << "destroying Derived\n";
}
};
#include <tr1/memory>
int main ( void ) {
std::tr1::shared_ptr<Base> ptr ( new Derived );
}
Second, there is not really a waste of memory since shared_ptr<T> was
designed to work with incomplete types. Suppose shared_ptr looked like this
(ignoring custom deleters):
template < typename T >
class sharer_ptr {
T* t_ptr;
int* the_ref_count;
public:
...
void ~shared_ptr ( void ) {
-- *the_ref_count;
if ( *the_ref_count == 0 ) {
delete the_ref_count;
delete t_ptr;
}
}
};
Then, the destructor of T would have to be available at the time
shared_ptr<T>::~shared_ptr is used (i.e., as soon as you are using
variables of type shared_ptr<T>). If the destructor of T is not available
at that point, it will be assumed trivial. Moreover, the program will have
undefined behavior if that assumption turns out false.
It is somewhat tricky (if at all possible) to get around this problem
without using some additional memory. The obvious solution is to store some
pointer to a deleter function that is available once you construct
shared_ptr<T> from T* (at that point you call new T and T has to be
complete; thus a definition of ~T is available). See below for code
containing some details.
Also, since you have to use something that allows deferred lookup of the
destructor anyway, you can as well go all the way and support a custom
deleter.
Since shared_ptr<BaseClass> only knows the BaseClass type when it's
destroyed (I assume that it doesn't waste even more memory creating a
virtual "destructor object" of a sort which destroys the DerivedClass
object using the proper pointer type) then how does it actually call the
DerivedClass destructor, given that it only has a BaseClass type pointer
to the object? It cannot cast the pointer to DerivedClass since it
doesn't know DerivedClass when the shared_ptr is destroyed. The only
standard-compliant way of calling the DerivedClass destructor is to have
a DerivedClass pointer.
Calling the destructor function giving it the raw BaseClass pointer
would obviously be wrong (because it's not guaranteed that a pointer of
type BaseClass will be unchanged when it's cast to DerivedClass, and
thus if you call the DerivedClass destructor using an uncasted BaseClass
pointer it's perfectly possible for the pointer to point to the wrong
place). So how?
Please don't take this as arguing. I'm not arguing. I'm honestly
interested in knowing how it's done.
I don't take these questions as arguing.
You can do it this way (the following does not do any reference counting, it
just implements an object that holds a pointer to T or derived that will
call the right destructor to illustrate one possible implementation.)
template < typename T >
class delete_derived {
typedef T value_type;
typedef value_type * pointer;
typedef void (*destroy_fct) ( pointer );
template < typename D >
static
void destroy ( T * t_ptr ) {
delete ( static_cast<D*>( t_ptr ) );
}
pointer the_ptr;
destroy_fct the_fct;
public:
template < typename D >
delete_derived ( D * d_ptr )
: the_ptr ( d_ptr )
, the_fct ( &destroy<D> )
{}
delete_derived & operator= ( delete_derived const & other ) {
the_ptr = other.the_ptr;
the_fct = other.the_fct;
return ( *this );
}
template < typename D >
delete_derived & operator= ( D * d_ptr ) {
the_ptr = d_ptr;
the_fct = &destroy<D>;
return ( *this );
}
T * operator-> ( void ) {
return ( the_ptr );
}
T & operator* ( void ) {
return ( *the_ptr );
}
void deallocate ( void ) {
the_fct( the_ptr );
}
};
#include <iostream>
struct Base {
virtual
void id ( void ) {
std::cout << "calling base\n";
}
~Base ( void ) {
std::cout << "destroying Base\n";
}
};
struct Derived : public Base {
virtual
void id ( void ) {
std::cout << "calling derived\n";
}
~Derived ( void ) {
std::cout << "destroying Derived\n";
}
};
typedef delete_derived< Base > dd_base;
int main ( void ) {
dd_base b_ptr = new Base;
b_ptr->id();
b_ptr.deallocate();
dd_base d_ptr = new Derived;
d_ptr->id();
d_ptr.deallocate();
}
The output is
calling base
destroying Base
calling derived
destroying Derived
destroying Base
which shows that the derived constructor is called, which in turn calls the
destructor for the Base subobject.
[snip]
As for the copying function, I said in my original post that functions
requiring copying or assignment (such as erase()) could simply not be
implemented.
And I showed that they can.
The whole purpose of this idea was to save memory, not to waste it.
That may have been _your_ purpose. Since I do not consider that important,
your point about new/delete being prone to error was much more appealing.
But even if you specify the requirements so that copying of entries will
never happen, I think you will need at least one function pointer per entry
to handle the problem of getting the base type subobject.
[snip]
As for "you are using premature optimization", if my concern was not
memory usage then I would use some std::vector<SmartPointer<Base> > and
not worry about the memory usage. However, sometimes memory-efficient
data containers are useful. It's not "premature optimization" to use
one, given that it's easy to use, abstract, and has been thoroughly
tested.
Using it makes your code brittle because you have some alignment and size
requirements that the container imposes on the client code. One could
(should?) put in some compile time checks to catch violations. That may
require some serious template magic or be impossible (e.g., I don't see
off hand a compile time check for alignment requirements). This case is
no exception to the rule that the optimization is premature as long as it
has not been proved to be needed.
That argument doesn't make too much sense.
Now, you are just arguing. The technical points stand unrefuted.
Some STL containers impose some rules on their elements. For example,
a std::set requires that the elements are comparable and that the
comparison of two elements always gives the same result. No big deal,
but it's still an additional requirement compared to eg. a std::vector.
Is it "premature optimization" to use std::set?
You are comparing apples and oranges. Using std::set instead of std::vector
is different from replacing
polymorphic_container (implemented generically as per my first post)
by
polymorphic_container (as per the second version
of
polymorphic_container (using your even more restricted specs).
std::set and std::vector are doing very different things whereas the
different implementations of polymorphic_container strive to do the same,
just some of them ditch stuff and introduce dependencies into client code
for the sake of efficiency. Using that right away (not after need has been
demonstrated) is premature optimization. In the case of std::set versus
std::vector I have a hard time seeing it as optimization at all since there
is not really a choice as the semantics differ vastly.
However, it would be premature optimization, e.g., to use a small_set<>
template (providing the std::set interface using an implementation
optimized for small sets) instead of std::set without evidence from
profiling that suggests to do it.
Best
Kai-Uwe Bux