Re: A deque containing different types of objects (with a common base class)
Juha Nieminen wrote:
I'm sure this is not a new idea, but I have never heard about it
before. I'm wondering if this could work:
Assume that you have a common base class and a bunch of classes
derived from it, and you want to make a deque which can contain any
objects of any of those types. Normally what you would have to do is to
make a deque or vector of pointers of the base class type and then
allocate each object dynamically with 'new' and store the pointers in
the deque/vector. This is a hassle, memoryleak-prone, and in many cases
wastes memory compared to the situation where you have a deque
containing objects of one single type (especially if all the different
objects you want to store are approximately equal in size).
How about this solution:
A special deque which can contain different types of objects in the
same way as std::deque stores objects of the same type, but in this case
it would be possible to store objects of different types, even if the
objects have different sizes.
The only extra requirement would be that you have to tell the deque
the size of the largest object you are going to store in it.
Why?
Here is a proof of concept:
#include <vector>
#include <algorithm>
template < typename T >
class polymorphic_var {
typedef T* (* copy_fct ) ( T * );
template < typename D >
static
T * copy ( T * ptr ) {
return ( new D ( *static_cast<D const *>( ptr ) ) );
}
T * the_ptr;
copy_fct the_copy_fct;
T * clone ( void ) const {
return ( the_copy_fct( the_ptr ) );
}
public:
void swap ( polymorphic_var & other ) {
std::swap( the_ptr, other.the_ptr );
std::swap( the_copy_fct, other.the_copy_fct );
}
polymorphic_var ( T const & t = T() )
: the_ptr ( new T ( t ) )
, the_copy_fct ( ©<T> )
{}
polymorphic_var ( polymorphic_var const & other )
: the_ptr ( other.clone() )
, the_copy_fct ( other.the_copy_fct )
{}
template < typename D >
polymorphic_var ( D const & d )
: the_ptr ( new D ( d ) )
, the_copy_fct ( ©<D> )
{}
// WARNING: [maybe too slick]
polymorphic_var operator= ( polymorphic_var rhs ) {
rhs.swap( *this );
return ( *this );
}
// WARNING: [no support for incompelte T]
~polymorphic_var ( void ) {
delete ( the_ptr );
}
T & me ( void ) {
return ( *the_ptr );
}
T const & me ( void ) const {
return ( *the_ptr );
}
}; // polymorphic_var
template < typename T >
class polymorphic_vector {
typedef std::vector< polymorphic_var<T> > container;
container the_data;
public:
typedef T value_type;
typedef value_type & reference;
typedef value_type const & const_reference;
typedef value_type * pointer;
typedef value_type const * const_pointer;
typedef typename container::size_type size_type;
template < typename D >
void push_back ( D const & d ) {
the_data.push_back( polymorphic_var<T>( d ) );
}
void pop_back ( void ) {
the_data.pop_back();
}
reference operator[] ( size_type i ) {
return ( the_data[i].me() );
}
const_reference operator[] ( size_type i ) const {
return ( the_data[i].me() );
}
size_type size ( void ) const {
return ( the_data.size() );
}
}; // polymorphic_vector
#include <iostream>
struct Base {
Base ( void ) {}
virtual
void id ( void ) const {
std::cout << "Base\n";
}
};
struct Derived : public Base {
Derived ( void )
: Base ()
{}
virtual
void id ( void ) const {
std::cout << "Derived\n";
}
};
int main ( void ) {
polymorphic_vector< Base > p_vector;
Base b;
Derived d;
p_vector.push_back( b );
p_vector.push_back( d );
p_vector.push_back( b );
p_vector.push_back( b );
p_vector.push_back( b );
p_vector.push_back( d );
p_vector.push_back( d );
p_vector.push_back( b );
p_vector.push_back( d );
for ( polymorphic_vector< Base >::size_type i = 0;
i < p_vector.size(); ++ i ) {
p_vector[i].id();
}
}
Now, there are tons of catches and shortcomings. For instance, this
implementation has no defence agains BadThings(tm) which might happen if
you do something like
p_cont[i] = b;
and
p_cont[i] = d;
should not even compile. That means, you need a special member template to
overwrite entries in the container.
So you instantiate this special deque by giving it the base class type
(which will be used to return references/pointers to the elements,
similarly to how a deque/vector of base class type pointers would work)
and the size of the largest object you will be storing in it (which can
also be a template parameter). I'm pretty sure that with template
metaprogramming it may even be possible to resolve the size of the
largest class by simply listing all the classes you are going to use in
some kind of template construct.
? This deque will then allocate space for the elements in the same way
as std::deque does, but allocating space for each element with the given
maximum object size (instead of the size of the base class). The
insertion functions will be template functions themselves and will use
placement new to put the objects in their places in the deque. Since a
deque never needs to move objects around after they have been created,
self-assignment (with its problem related to the deque only knowing the
base class) will not be needed.
? When this deque is accessed it will return references of the base
class type. The user can then do with them whatever is necessary (in the
same way as he would have to do with a vector of base class pointers).
? Not all methods of std::deque can be offered, obviously (for example
erase() would be rather impossible to implement, so it's not offered at
all) but in many cases that shouldn't matter.
? The largest advantage of this method would be that you don't need to
worry about memory management, as you would need if you used the
"traditional" method of allocating all the objects with 'new' and
storing pointers to them in the vector/deque, which is a hassle and
prone to memory leak errors. Also if most of the objects are
approximately the same size as the largest object, memory will be saved
compared to the "traditional" way. Yet this would allow storing objects
of different types inside the same deque.
? I'm wondering if this could actually work, or if there's a gotcha I
can't see.
Mabye, we need to think about the interface before we think about the
implementation. Returning Base& from methods like operator[] is not really
good (see above), but returning a proxy (that automatically converts to
Base& in certain contexts) is not good either because using that, we could
not do
p_cont[i].id()
The reason is that we cannot overload the dot-operator for the proxy class.
Best
Kai-Uwe Bux