By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,851 Members | 1,001 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,851 IT Pros & Developers. It's quick & easy.

A deque containing different types of objects (with a common baseclass)

P: n/a
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.
Sep 14 '07 #1
Share this Question
Share on Google+
15 Replies


P: n/a
On Sep 14, 5:29 pm, Juha Nieminen <nos...@thanks.invalidwrote:
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.
Use a container of your favorite smart pointer (e.g boost) and you
won't
have memory leaks. Keeping pointers to base objects in containers is
a
common C++ idiom. I'd stick with what works unless there is a
compelling
reason to do otherwise.
Sep 14 '07 #2

P: n/a
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).
I usually use a container< copy_ptr<T, or I implement a class
Polymorphic_T that can hold values of type T and derived from T. Then, I
use container< Polymorphic_T and Polymorphic_T throughout my program.

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.
Why?
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.
Well, you first might want to try first to implement the most simple
container: a box that can hold at most one element. Already there, you run
into trouble. Consider

struct BaseA { some stuff };
struct BaseB { some stuff };

struct D1 : public BaseA, public BaseB { some more };
struct D2 : public BaseB, public BaseA { some more };

What is box< BaseA going to do. In some elements, the BaseA subobject
comes first in some others, it comes second. So, with each element, you
could store a method for accessing the BaseA subobject. That method would
be called each time you dereference the entry.
Best

Kai-Uwe Bux
Sep 14 '07 #3

P: n/a
"Juha Nieminen" <no****@thanks.invalidwrote in message
news:46**********************@news.song.fi...
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.
I understand that boost has something called any_typeor anytype. Perhaps
that would suit your purpose.
Sep 14 '07 #4

P: n/a
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 ( &copy<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 ( &copy<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
Sep 15 '07 #5

P: n/a
An**********@gmail.com wrote:
> I'm wondering if this could actually work, or if there's a gotcha I
can't see.
Use a container of your favorite smart pointer (e.g boost) and you
won't
have memory leaks. Keeping pointers to base objects in containers is
a
common C++ idiom. I'd stick with what works unless there is a
compelling
reason to do otherwise.
That didn't really answer my question.
Sep 15 '07 #6

P: n/a
Kai-Uwe Bux wrote:
> 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.

Why?
Does this work?

void foo(Base& b1, Base& b2)
{
b1 = b2;
}
Sep 15 '07 #7

P: n/a
Kai-Uwe Bux wrote:
Here is a proof of concept:
Basically you are allocating each element separately with new?
That's exactly what I wanted to avoid in the first place.

I was simply asking if the idea could work.
Sep 15 '07 #8

P: n/a

"Juha Nieminen" <no****@thanks.invalidwrote in message
news:46**********************@news.song.fi...
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).
....
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.
http://www.boost.org/libs/ptr_contai...container.html addresses
some of these issues out of the box.

Or using boost variant desribed at
http://www.boost.org/doc/html/variant.html you can accomplish your goal in a
typesafe manner without limitation on container type or their methods. Below
is an example for a specific set of base and derived classes. This could be
generalized in a safe manner using boost mpl and typetraits libraries.

#include <boost/variant.hpp>

#include <vector>
#include <string>

using std::string;
using std::vector;

struct b
{
virtual ~b(){}
virtual string f()const{ return "b"; }
};

struct d1 : b { string f()const{ return "d1"; } };
struct d2 : b { string f()const{ return "d2"; } };
struct d3 : d2 { string f()const{ return "d3"; } };

typedef boost::variant<b,d1,d2,d3types;

struct base_ref_visitor : boost::static_visitor<>
{
typedef b& result_type;

template< class Derived b& operator()(Derived & d) const
{
return d;
}
};

b& base_ref( types& t ){ return
boost::apply_visitor(base_ref_visitor(),t); }

int main()
{
vector< types ts;

ts.push_back(d3());
ts.push_back(d1());
ts.push_back(d2());
ts.push_back(b ());
ts.push_back(d1());

ts[4] = d3();

string val0 = base_ref(ts[0]).f();
string val1 = base_ref(ts[1]).f();
string val2 = base_ref(ts[2]).f();
string val3 = base_ref(ts[3]).f();
string val4 = base_ref(ts[4]).f();

return 0;
}


Sep 15 '07 #9

P: n/a
Juha Nieminen wrote:
Kai-Uwe Bux wrote:
>> 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.

Why?

Does this work?

void foo(Base& b1, Base& b2)
{
b1 = b2;
}
Probably not for the relevant values of "work". However, that just rules out
one implementation approach. You can store, for each container entry, some

void (*) ( void*, void* );

obtained from a template

template < typename D >
void copy_construct ( void* from, void* to ) {
do the right thing;
}

and then you use that one to copy the entries around. You can do a similar
thing for the assignment operator.
Best

Kai-Uwe Bux
Sep 15 '07 #10

P: n/a
Juha Nieminen wrote:
Kai-Uwe Bux wrote:
>Here is a proof of concept:

Basically you are allocating each element separately with new?
That's exactly what I wanted to avoid in the first place.
Sure, but your main argument against it was that using new and delete is
error prone. If you hide that away from the user, that objection
disappears. The efficiency concern is misplaced without profiling showing a
need for optimization.

I was simply asking if the idea could work.
a) You are engaged in premature optimization.

b) The proof of concept can be amended as follows:
#include <vector>
#include <algorithm>
#include <iterator>
#include <new>

template < typename T, typename AllignedPod >
class polymorphic_var {

typedef void (* copy_fct ) ( AllignedPod const &, AllignedPod & );
typedef T & (* ref_fct )( AllignedPod & );
typedef void ( *destr_fct ) ( AllignedPod & );

template < typename D >
static
void copy_construct ( AllignedPod const & from, AllignedPod & to ) {
new ( (void*)&to ) D ( reinterpret_cast<D const &>(from) );
}

template < typename D >
static
T & get_reference ( AllignedPod & d ) {
return ( reinterpret_cast< D& >( d ) );
}

template < typename D >
static
void destroy ( AllignedPod & d ) {
reinterpret_cast<D*>( &d )->~D();
}

AllignedPod the_data;
copy_fct the_copy_fct;
ref_fct the_ref_fct;
destr_fct the_destr_fct;

public:

polymorphic_var ( T const & t = T() )
: the_data ()
, the_copy_fct ( &copy_construct<T)
, the_ref_fct ( &get_reference<T)
, the_destr_fct ( &destroy<T)
{
the_copy_fct( reinterpret_cast<AllignedPod const &>(t), the_data );
}

polymorphic_var ( polymorphic_var const & other )
: the_data ()
, the_copy_fct ( other.the_copy_fct )
, the_ref_fct ( other.the_ref_fct )
, the_destr_fct ( other.the_destr_fct )
{
the_copy_fct( other.the_data, the_data );
}

template < typename D >
polymorphic_var ( D const & d )
: the_data ()
, the_copy_fct ( &copy_construct<D)
, the_ref_fct ( &get_reference<D)
, the_destr_fct ( &destroy<D)
{
the_copy_fct( 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_destr_fct( the_data );
}

T & me ( void ) {
return ( the_ref_fct( the_data ) );
}

T const & me ( void ) const {
return ( the_ref_fct( const_cast<AllignedPod&>(the_data) ) );
}

}; // polymorphic_var
template < typename T, typename AllignedPod >
class polymorphic_vector {

typedef polymorphic_var<T,AllignedPodmy_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();
}
*/
}
This assumes that AllignedPod is a type that is suitable for holding objects
of all the derived types you want to use. The behavior is at least
implementation defined and maybe undefined at some places. The code is
horrible, and I would prefer the first solution any day.
Note that in addition to the data, we need to store three function pointers.

Best

Kai-Uwe Bux
Sep 15 '07 #11

P: n/a
Kai-Uwe Bux wrote:
typedef void ( *destr_fct ) ( AllignedPod & );
destr_fct the_destr_fct;
~polymorphic_var ( void ) {
the_destr_fct( the_data );
}
Why? Ever heard of virtual destructors? They are needed for vectors
containing (smart) pointers to allocated objects too. Why would you want
to store a function pointer to a destructor function separately?

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. I think the container would still be useful.

The only memory required for this is size()*sizeof(LargestObject) +
some minor ancillary data required for a deque-type container.

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.
Sep 16 '07 #12

P: n/a
On Sat, 15 Sep 2007 00:29:20 +0300, Juha Nieminen wrote:
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).
AFAICS, your requirements can be split into two parts:
1. You want a container to store (pointers to) objects, i.e.
polymorphic, stateful, non-copyable objects in the meaning of OOP. Use
a container appropriate for objects (e.g.
http://www.codeproject.com/vcpp/stl/ptr_vecto.asp) instead of the
standard containers that are only suitable for values.

2. The 'container' (which then is more then just a container) should
also manage (create, delete, own) the objects in an efficient way. A
factory approach in combination with RAII using the above container is
one solution (see e.g.
http://www.codeproject.com/cpp/RAIIFactory.asp). You may improve
performance with memory pools inside the factory.
--
Roland Pibinger
"The best software is simple, elegant, and full of drama" - Grady Booch
Sep 16 '07 #13

P: n/a
Juha Nieminen wrote:
Kai-Uwe Bux wrote:
> typedef void ( *destr_fct ) ( AllignedPod & );
destr_fct the_destr_fct;
> ~polymorphic_var ( void ) {
the_destr_fct( the_data );
}

Why?
It's an idiom that I have seen quite often.
Ever heard of virtual destructors?
Yes.
They are needed for vectors containing (smart) pointers to allocated
objects too.
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.
Why would you want to store a function pointer to a
destructor function separately?
It's an idiom that arises from smart pointer implementations. It is used to
kill two birds with one stone: (a) one can support incomplete types and (b)
with a little more effort one can provide for custom deleters. That
explains how it sneaked into the code. I realzed shortly after I posted
that one can do without for the container type as long as there is no need
to support incomplete types.

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.

I think the container would still be useful.
Your choice. Your container then is also not copy-constructible and cannot
be based on a vector (because of reallocation). Provide a reference
implementation and some use cases, and we can discuss more meaningfully
whether that gadget is useful.

The only memory required for this is size()*sizeof(LargestObject) +
some minor ancillary data required for a deque-type container.
I still would like to see how you get the reference for the base type
without storing a function pointer per entry to do that. You cannot assume
that the base subobject is at the same offset in all derived types: you are
up against multiple inheritance as I pointed out elsethread.

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.
Best

Kai-Uwe Bux
Sep 16 '07 #14

P: n/a
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<BaseClassptr = 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.)

Since shared_ptr<BaseClassonly 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 realzed shortly after I posted
that one can do without for the container type as long as there is no need
to support incomplete types.
STL containers cannot be instantiated with incomplete types anyways,
so it's not a big deal if this special deque couldn't be either.
> 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.
Your choice. Your container then is also not copy-constructible
Big deal? I have seldom needed the copy constructor of any STL container.

Sure, it would not have *all* the properties of an STL container, but
many of them could be implemented.
and cannot
be based on a vector (because of reallocation).
That's exactly why I wrote about deque in the first place. I don't see
what's the big deal with that.
> 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.

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?
Sep 16 '07 #15

P: n/a
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<BaseClassptr = 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<Baseptr ( new Derived );
}
Second, there is not really a waste of memory since shared_ptr<Twas
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<Tfrom 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<BaseClassonly 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
Sep 16 '07 #16

This discussion thread is closed

Replies have been disabled for this discussion.