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.
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.
Here is another proof of concept. This one uses an overhead of one object
pointer per entry. I doubt that one can do better in terms of memory
overhead (the reason being that in order to return base references, one
somehow needs to at least keep track of where in the derived objects the
base subobjects are located).
The implementation also supports operations that require to copy objects
around.
#include <vector>
#include <algorithm>
#include <iterator>
#include <new>
template < typename T, typename AllignedPod >
class polymorphic_var {
struct functions {
virtual
void copy ( AllignedPod const &, AllignedPod & ) = 0;
virtual
T & ref ( AllignedPod & ) = 0;
virtual
void destroy ( AllignedPod & ) = 0;
};
template < typename D >
struct d_functions : functions {
void copy ( AllignedPod const & from, AllignedPod & to ) {
new ( (void*)&to ) D ( reinterpret_cast<D const &>(from) );
}
T & ref ( AllignedPod & d ) {
return ( reinterpret_cast< D& >( d ) );
}
void destroy ( AllignedPod & d ) {
reinterpret_cast<D&>(d).~D();
}
static
d_functions * instance ( void ) {
static d_functions dummy;
return ( &dummy );
}
};
AllignedPod the_data;
functions * the_fcts;
public:
polymorphic_var ( T const & t = T() )
: the_data ()
, the_fcts ( d_functions<T>::instance() )
{
the_fcts->copy( reinterpret_cast<AllignedPod const &>(t), the_data );
}
polymorphic_var ( polymorphic_var const & other )
: the_data ()
, the_fcts ( other.the_fcts )
{
the_fcts->copy( other.the_data, the_data );
}
template < typename D >
polymorphic_var ( D const & d )
: the_data ()
, the_fcts( d_functions<D>::instance() )
{
the_fcts->copy( reinterpret_cast<AllignedPod const &>(d), the_data );
}
polymorphic_var operator= ( polymorphic_var rhs ) {
if ( this != &rhs ) {
this->~polymorphic_var();
new (this) polymorphic_var ( rhs );
}
return ( *this );
}
~polymorphic_var ( void ) {
the_fcts->destroy( the_data );
}
T & me ( void ) {
return ( the_fcts->ref( the_data ) );
}
T const & me ( void ) const {
return ( the_fcts->ref( const_cast<AllignedPod&>(the_data) ) );
}
}; // polymorphic_var
template < typename T, typename AllignedPod >
class polymorphic_vector {
typedef polymorphic_var<T,AllignedPod> my_var_type;
typedef std::vector< my_var_type > 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( my_var_type( 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() );
}
class iterator : public container::iterator {
friend
class polymorphic_vector;
typedef typename container::iterator base;
iterator ( base pos )
: base( pos )
{}
public:
typedef typename polymorphic_vector::value_type value_type;
typedef typename polymorphic_vector::reference reference;
typedef typename polymorphic_vector::pointer pointer;
reference operator* ( void ) const {
return ( base::operator*().me() );
}
pointer operator-> ( void ) const {
return ( & operator*() );
}
};
iterator begin ( void ) {
return ( the_data.begin() );
}
iterator end ( void ) {
return ( the_data.end() );
}
class const_iterator : public container::const_iterator {
friend
class polymorphic_vector;
typedef typename container::const_iterator base;
const_iterator ( base pos )
: base( pos )
{}
public:
const_iterator ( iterator pos )
: base ( pos )
{}
typedef typename polymorphic_vector::value_type value_type;
typedef typename polymorphic_vector::const_reference reference;
typedef typename polymorphic_vector::const_pointer pointer;
reference operator* ( void ) const {
return ( base::operator*().me() );
}
pointer operator-> ( void ) const {
return ( & operator*() );
}
};
const_iterator begin ( void ) const {
return ( the_data.begin() );
}
const_iterator end ( void ) const {
return ( the_data.end() );
}
typedef std::reverse_iterator< iterator > reverse_iterator;
reverse_iterator rbegin ( void ) {
return ( reverse_iterator( end() ) );
}
reverse_iterator rend ( void ) {
return ( reverse_iterator( begin() ) );
}
}; // 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";
}
};
typedef polymorphic_vector< Base, int > poly_vect;
int main ( void ) {
poly_vect 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 ( poly_vect::size_type i = 0;
i < p_vector.size(); ++ i ) {
p_vector[i].id();
}
std::cout << '\n';
poly_vect p_vect_2 ( p_vector );
for ( poly_vect::const_iterator iter = p_vect_2.begin();
iter != p_vect_2.end(); ++iter ) {
iter->id();
}
/*
for ( poly_vect::reverse_iterator iter = p_vect_2.rbegin();
iter != p_vect_2.rend(); ++iter ) {
iter->id();
}
*/
}
If you think you can get away with less memory overhead (even for just
push_back() and operator[]), please show me how.
Best
Kai-Uwe Bux