Arrays of derived objects

[Jack]

Hi,

Is there a general solution for the following problem:

I have an array of instances of class B. Class B is publicly derived from
class A. Then I have a class named Buffer that generally takes care of
allocating and deallocating arrays. Class Buffer knows only that the objects
contained in its internal array are derived from class A but not that they
are exactly of type B, so Buffer has a member variable of type A* that
points at the beginning of that array. I know that indexing the elements
will not work with this mechanism, so I should rather have one more level of
indirection, that is, an array of elements of type A* that point to each B
object. But I think (please correct me if I am wrong) that the need to
allocate each object B separately slows down the operation, so I would like
to use new[] once instead of new multiple times. Okay, I can use first new
B[...] and then set one A* element in the array to point at each instance of
B. But is that sensible? Is there another way? Will delete[] clean up the
memory correctly if the pointer type given to it does not exactly match the
type of the elements contained in the array? (I mean, if the array of
objects B is deleted in the destructor of Buffer that knows only that the
elements are derived from class A)

I don't want to use virtual functions in class Buffer, because they cause
overhead in speed. I don't want to templatize it either, because it should
be enough for it to know that the objects contained in its internal array
are derived from class A. But still it should be able to index the elements
and destroy them correctly. What is the best way to do it?

Thank you very much for your help in advance,

Jack

 

[Jack]

Hi again,

I decided to try to clarify my questions by a piece of code:

class A { ... };
class B : public A { ... };
template<typename T>
class Buffer
{
public:
Buffer(T* p, size_t i) : m_p(p), m_i(i) {}
~Buffer() {delete[] m_p;} // Is this okay?
T& operator[](int i) { /* How to implement this? */ }
private:
T* m_p;
size_t m_i;
};

int main()
{
Buffer b<A>(new B[5], 5);
return 0;
}

In contrast to what I said earlier, Buffer can (and probably should) take
the base class as a template parameter (in this case class A), but I meant
that I would like to leave it so that it does not take the derived class as
a template parameter (in this case class B).

Jack

 

[Ben Pope]

Hi again,

I decided to try to clarify my questions by a piece of code:
Excellent.

class A { ... };

This doesn't compile. The dots are really not necessary, it's much
better to have it compile. Do this is you REALLY want the dots:
class A {/* ... */};

class B : public A { ... };

And again.

template<typename T>
class Buffer
{
public:
Buffer(T* p, size_t i) : m_p(p), m_i(i) {}
~Buffer() {delete[] m_p;} // Is this okay?

If the argument p points to an array allocated with new[], and it hasn't
already been deleted[], yes. Otherwise you probably have undefined
behaviour.

Why don't you guarantee it, and do the allocation in the constructor?

T& operator[](int i) { /* How to implement this? */ }
private:
T* m_p;
size_t m_i;
};

int main()
{
Buffer b<A>(new B[5], 5);

OK, I think I see the above problem. Polymorphism.

return 0;
}

In contrast to what I said earlier, Buffer can (and probably should) take
the base class as a template parameter (in this case class A), but I meant
that I would like to leave it so that it does not take the derived class as
a template parameter (in this case class B).

I would probably make it like this:

#include <vector>

class A {};
class B : public A {};

template<class Base, class Derived>
class Buffer {
public:
Buffer(size_t size) : buffer_(size) {}
Base& operator[](size_t i) { return buffer; }
private:
std::vector<Derived> buffer_;
};

int main() {
Buffer<A, B> buf(5);
}

At the point of construction, you're using the derived type, anyway.

I don't see the point, since in operator[], you're returning a
reference, and that will be able to be used polymorphically, anyway.

Anyway, whatever you decide to do, you need to make sure that you cannot
construct an incorrect buffer, calling the following on your code would
be a problem:

Buffer b<A>(new B[5], 6)

It's simply not necessary to introduce that problem, so I've changed
(and simplified) the constructor.

Also, you'll notice I've captured the actual containing within a
std::vector, since I don't understand pointers and arrays.

Ben Pope

 

[Jack]

Ben,

Thank you for your reply. I think that you did not understand the motivation
of my questions, so please let me explain:

I said that class Buffer should not be aware of the type of the derived
class (in other words, a solution is not to put the derived class as a
template parameter. For the same reason std::vector cannot be used). The
reason for this is that Buffer is implemented in a static library, which
also contains other components that must be able to use the Buffer class. So
if the implementation of Buffer depends on the type of the derived class
(which is only known to the client code of the library) it cannot be used by
those other library components.

And also, my question regarding delete[] was about whether it works
correctly if the pointer type given to it is not an exact match of the type
of the elements contained in the array to be deleted.

Regards,

Jack

 

[Axter]

Ben,

Thank you for your reply. I think that you did not understand the motivation
of my questions, so please let me explain:

I said that class Buffer should not be aware of the type of the derived
class (in other words, a solution is not to put the derived class as a
template parameter. For the same reason std::vector cannot be used). The
reason for this is that Buffer is implemented in a static library, which
also contains other components that must be able to use the Buffer class. So
if the implementation of Buffer depends on the type of the derived class
(which is only known to the client code of the library) it cannot be used by
those other library components.

And also, my question regarding delete[] was about whether it works
correctly if the pointer type given to it is not an exact match of the type
of the elements contained in the array to be deleted.

It will work if the pointee is a derived type, and the base class has a
virtual destructor.
I still don't see why you can't use a vector.
I recommend you use a vector of smart pointers.
The following smart pointer should work for your requirements:
http://axter.com/smartptr

With above smart pointer, you can declare your vector like so:
std::vector<smart_ptr<A> > My_A_array;

It's not a good idea to make an array of a derived type without using
smart pointers.

 

[Jakob Bieling]

Jack wrote:

And also, my question regarding delete[] was about whether it works
correctly if the pointer type given to it is not an exact match of
the type of the elements contained in the array to be deleted.

It will work if the pointee is a derived type, and the base class has
a virtual destructor.

I do not agree. The following is undefined behaviour, according to
12.5/4 and the example given in 12.5/7:

"B* bp = new D;
delete[] bp; // undefined behavior"

In other words, even though D will have a virtual dtor (lets just
assume it does), D[] does not.

regards

 

[Ben Pope]

Ben,

Thank you for your reply. I think that you did not understand the motivation
of my questions, so please let me explain:

I said that class Buffer should not be aware of the type of the derived
class (in other words, a solution is not to put the derived class as a
template parameter. For the same reason std::vector cannot be used). The
reason for this is that Buffer is implemented in a static library, which
also contains other components that must be able to use the Buffer class. So
if the implementation of Buffer depends on the type of the derived class
(which is only known to the client code of the library) it cannot be used by
those other library components.

And also, my question regarding delete[] was about whether it works
correctly if the pointer type given to it is not an exact match of the type
of the elements contained in the array to be deleted.

Yes, I missed that, the answer is no, it will not work.

You can't really expect Buffer to manage the lifetime of objects it does
not know the type of (nor allocate).

I'm not sure what you really intend for Buffer. If it is a lightweight
as it appears, then I don't see it's usefulness over a std::vector. You
say it manages the the allocation and deallocation, yet your
implementation certainly does not manage the allocation.

Could you describe the problem you are trying to solve, rather than
describing the implementation (with Buffer)?

Ben Pope

 

[Jack]

Hi Axter,

Thank you for your reply.

Did you notice my very first posting? I accidentally sent it in a bit wrong
way in my news program so at least in my view it is not shown attached to
this discussion thread.

Anyway, I agree that using smart pointers is a preferred way, actually my
Buffer class is designed to be sort of a smart pointer (actually smart
array). That's why there is that delete[] code in the destructor. In my very
first posting I wondered whether it is equally efficient to have an array of
pointers to objects that are allocated by multiple calls to new instead of
having a single call to new[]. I assumed that new[] would be more efficient,
so smart pointers don't do. Safe arrays would do, but I was not sure whether
delete[] would work correctly if the array contained derived objects. I also
wondered if it would be reasonable to allocate the derived objects with
new[] and then have an extra array of base class pointers (safe pointers
won't do in this case if the array is allocated with new[]) point at each
object. I wondered if this was unnecessary waste of memory and speed because
the objects lay sequentially in the memory anyway (the container just
doesn't know there size).

So, to put it short: For efficiency reasons (if my assumption is correct)
new[] and delete[] should be used. The derived type is not known by the
container class (Buffer), so the client code has to do the allocation (i.e.
call new[]). The responsibilities of the Buffer class is to do indexing
(although it does not know the exact type of the contained object) and
deallocation.

I am sorry if my explanations have been unclear. Also English is not my
mother language. Please ask if I still couldn't express myself clearly.

Regards,

Jack

 

[Jakob Bieling]

I decided to try to clarify my questions by a piece of code:

class A { ... };
class B : public A { ... };
template<typename T>
class Buffer
{
public:
Buffer(T* p, size_t i) : m_p(p), m_i(i) {}
~Buffer() {delete[] m_p;} // Is this okay?
T& operator[](int i) { /* How to implement this? */ }
private:
T* m_p;
size_t m_i;
};

int main()
{
Buffer b<A>(new B[5], 5);
return 0;
}

In contrast to what I said earlier, Buffer can (and probably should)
take the base class as a template parameter (in this case class A),
but I meant that I would like to leave it so that it does not take
the derived class as a template parameter (in this case class B).

Obviously, 'Buffer' *must* know about the size of the object it is
managing. Just telling it about what it was derived from, will simply
not do. A work-around might be to give it the size of the object and a
set of construction destruction. Then 'Buffer' can reserve memory of
appropriate size and use in-place con-/destruction.

I honestly do not like the above approach very much, so maybe you
want to look out for a better solution.

hth

 

[Jakob Bieling]

set of construction destruction. [..]

"set of construction and destruction functions"

sorry about that

 

[Jack]

I'm not sure what you really intend for Buffer. If it is a lightweight

as it appears, then I don't see it's usefulness over a std::vector. You
say it manages the the allocation and deallocation, yet your
implementation certainly does not manage the allocation.

I am sorry if I have said that. It does not manage the allocation (only
deallocation). Because the client code is the only one that knows the exact
type of the managed objects, it must do the allocation.

The usefulness over a std::vector would be the ability of indexing objects
of the derived type. std::vector can index only objects that are exactly of
the type that is given as a template parameter to it.

Could you describe the problem you are trying to solve, rather than
describing the implementation (with Buffer)?

I am writing a library which should support code reuse. It contains a class
A which is a general interface for particular operations. All components in
this library shall be able to perform their tasks through this interface A
(so they shall not be aware of any classes derived from A). The library also
contains this Buffer class, which manages arrays of objects that implement
this interface A. But the actual implementation is client-dependent (class B
that is derived from class A) so the actual objects managed by the Buffer
are of type B (but the Buffer knows only that they implement the interface
A).

Regards,

Jack

 

[Jack]

Yes, I also thought of this solution. The problem is that either I would
need reinterpret_cast which may be unportable, or, if I give Buffer the
responsibility to do the allocation, I would need to give it the type of the
derived objects. Giving the type of the derived objects to Buffer as a
template parameter makes the whole Buffer useless because then the other
components in the library cannot use it any longer (they don't know how to
instantiate a Buffer object).

However, that is the best solution so far. If anybody knows a better one,
please let me know.

Jack

 

[Ben Pope]

I am sorry if I have said that. It does not manage the allocation (only
deallocation). Because the client code is the only one that knows the exact
type of the managed objects, it must do the allocation.

It is often prudent to tie allocation and deallocation of a resource
together, synchronised with the lifetime of an object. This principle
has spawned many a smart-pointer. (Look up RAII).

The usefulness over a std::vector would be the ability of indexing objects
of the derived type. std::vector can index only objects that are exactly of
the type that is given as a template parameter to it.

OK, well:

I am writing a library which should support code reuse. It contains a class
A which is a general interface for particular operations. All components in
this library shall be able to perform their tasks through this interface A
(so they shall not be aware of any classes derived from A).

OK, Fine.

The library also
contains this Buffer class, which manages arrays of objects that implement
this interface A.

If Buffer just manages arrays of, and allows polymorphic access to
elements of arrays, then it would seem somewhat of a utility; rather
orthogonal to the other part of the library.

That's not a problem in itself.

But the actual implementation is client-dependent (class B
that is derived from class A) so the actual objects managed by the Buffer
are of type B (but the Buffer knows only that they implement the interface
A).

OK, I'm pretty sure you want this to be irrelevant to the implementation
of Buffer.

Have you seen the boost pointer containers? I think they will solve
your problem.
http://www.boost.org/libs/ptr_container/doc/ptr_container.html

A ptr_array (statically sized) does pretty much what you want, I think.
The only thing missing is allocation-in-one.

I haven't checked this will work, but perhaps you could allocate a B
array, and then use ptr_array::replace to make it's pointers point to
the objects in your array.

You know what? Get it working first. If the x news are too slow, then
try new [x].

Ben Pope

 

[Jack]

It is often prudent to tie allocation and deallocation of a resource

together, synchronised with the lifetime of an object. This principle
has spawned many a smart-pointer. (Look up RAII).

I know.

OK, well:
std::vector<A*>

Yes, this is a "multiple calls to new with memory leaks" solution. With
smart pointers (for example, the ones in the Boost library) it is the
"multiple calls to new" solution.

If Buffer just manages arrays of, and allows polymorphic access to
elements of arrays, then it would seem somewhat of a utility; rather
orthogonal to the other part of the library.

True. Actually it is part of another library I am writing, but I thought
that that detail is irrelevant in the point of view of my problem.

OK, I'm pretty sure you want this to be irrelevant to the implementation
of Buffer.

True again.

Have you seen the boost pointer containers? I think they will solve
your problem.
http://www.boost.org/libs/ptr_container/doc/ptr_container.html

A ptr_array (statically sized) does pretty much what you want, I think.
The only thing missing is allocation-in-one.

I haven't checked this will work, but perhaps you could allocate a B
array, and then use ptr_array::replace to make it's pointers point to
the objects in your array.

No. ptr_array::replace handles only single elements, so this is just one
more variation of the "multiple calls to new" solution.

You know what? Get it working first. If the x news are too slow, then
try new [x].

Yes, trying should always be done before code optimization process. In this
case there will be tens of thousands of objects, so it is pretty obvious
that new[] will be more efficient. Generally, when you have to handle
multiple small objects the memory pool idiom should be used. The solution
presented by Jakob Bieling resembles that idiom, but its weakness is the
type unsafety.

I am thankful for your trying to help. But even better solutions will be
welcome

Regards,

Jack

 

[Ben Pope]

No. ptr_array::replace handles only single elements, so this is just one
more variation of the "multiple calls to new" solution.

....not if you preallocate the array, and replace the pointers... It's
one call to new and a bunch of pointer assignments

You know what? Get it working first. If the x news are too slow, then
try new [x].

Yes, trying should always be done before code optimization process. In this
case there will be tens of thousands of objects, so it is pretty obvious
that new[] will be more efficient. Generally, when you have to handle
multiple small objects the memory pool idiom should be used. The solution
presented by Jakob Bieling resembles that idiom, but its weakness is the
type unsafety.

Providing your own allocator and/or operator new for the derived type
could certainly help.

I am thankful for your trying to help. But even better solutions will be
welcome

OK, last ditch attempt

You seem to think that you cannot provide Buffer, templated on the
derived type to the user. I'm not sure this is the case, but I'll have
to accept your word on that.

The fundamental problem then, is knowing the size of the array to be
deallocated. If you know the size of an element (pretty sure you cannot
to that polymorphically, i.e., you need to know the derived type, or at
least sizoef(b)), you can allocate a block of memory, and call placement
new for each element.

In the destructor, you can call the destructor of each element in the
array, and then delete the block you allocated.

What that gains you over over providing the derived type in the
template, is that it is run time. A call to the constructor might look
like:

Buffer b<A>(sizeof(B), 5);

I see no way around requiring the derived type *somewhere*.

Ben Pope

 

[Daniel T.]

Hi,

Is there a general solution for the following problem:

I have an array of instances of class B. Class B is publicly derived from
class A. Then I have a class named Buffer that generally takes care of
allocating and deallocating arrays. Class Buffer knows only that the objects
contained in its internal array are derived from class A but not that they
are exactly of type B, so Buffer has a member variable of type A* that
points at the beginning of that array. I know that indexing the elements
will not work with this mechanism, so I should rather have one more level of
indirection, that is, an array of elements of type A* that point to each B
object. But I think (please correct me if I am wrong) that the need to
allocate each object B separately slows down the operation, so I would like
to use new[] once instead of new multiple times. Okay, I can use first new
B[...] and then set one A* element in the array to point at each instance of
B. But is that sensible? Is there another way? Will delete[] clean up the
memory correctly if the pointer type given to it does not exactly match the
type of the elements contained in the array? (I mean, if the array of
objects B is deleted in the destructor of Buffer that knows only that the
elements are derived from class A)

I don't want to use virtual functions in class Buffer, because they cause
overhead in speed. I don't want to templatize it either, because it should
be enough for it to know that the objects contained in its internal array
are derived from class A. But still it should be able to index the elements
and destroy them correctly. What is the best way to do it?

Thank you very much for your help in advance,

Unfortunately, as you have already deduced from earlier posts, you can't
get there.

If you insist on all the objects allocated in a C array, you will have
to know the exact type in order to delete [] the array, since you can't
know that...

Here is an idea... Have your static library hold a vector of A*s and
document that the user of your library must both new and delete the A*
objects. Then he can put them in a buffer or not at his whim.

 

[Jack]

Thank you Daniel, that sounds like a good idea. If I provide only
constructors that take a destructor function as a parameter, the user must
provide one in order to use my Buffer class. Do you think the following code
would be correct? Is it portable? Does memory alignment work in it?

using namespace std;
template<class T>
class Buffer
{
public:
Buffer(T* p, size_t ElemSize size_t ArraySize, void(*pfn)(T*)) :
_p(ArraySize), _i(ElemSize), _pfn(pfn)
{
void* u=reinterpret_cast<void*>(p);
for(size_t j=0;j<ArraySize;++j)
{
_p[j]=reinterpret_cast<T*>(u);
u+=ElemSize;
}
}
~Buffer() { (*pfn)(&_p[0]); }
T& operator[](size_t i) { return *_p; }
const T& operator[](size_t i) const { return *_p; }

private:
vector<T*> _p;
size_t _i;
void(*_pfn)();
};

Regards,

Jack

 

[Daniel T.]

I'm not sure what you really intend for Buffer. If it is a lightweight
as it appears, then I don't see it's usefulness over a std::vector. You
say it manages the the allocation and deallocation, yet your
implementation certainly does not manage the allocation.

I am sorry if I have said that. It does not manage the allocation (only
deallocation). Because the client code is the only one that knows the exact
type of the managed objects, it must do the allocation.

The usefulness over a std::vector would be the ability of indexing objects
of the derived type. std::vector can index only objects that are exactly of
the type that is given as a template parameter to it.[/QUOTE]

That's where you are confused, vector can do everything that a C array
can do. Since a C array cannot index objects of the derived type,
neither can vector.

Try it your self and see:

class A {
int X;
};

class B : public A {
int y;
};

int main() {
B array[2];
A* ptr = array;
assert( ptr == &array[0] );
++ptr;
assert( ptr == &array[1] ); // this will fail
}

I am writing a library which should support code reuse. It contains a class
A which is a general interface for particular operations. All components in
this library shall be able to perform their tasks through this interface A
(so they shall not be aware of any classes derived from A). The library also
contains this Buffer class, which manages arrays of objects that implement
this interface A. But the actual implementation is client-dependent (class B
that is derived from class A) so the actual objects managed by the Buffer
are of type B (but the Buffer knows only that they implement the interface
A).

The client will have to both create and destroy the B objects that the
buffer's elements point to.

If you insist on the buffer deleting the elements, then each element
must be allocated individually, not as part of a B array.

 

[Jack]

No, I do not mean that the Buffer class would do the indexing that (regular)
way. If it did, then there would not be any value in it, because a C array
(and a std::vector) can do the same. In the Buffer class the purpose is to
do some tricks so that the indexing will work. And my question is what the
best way to do those tricks is

Please take a look at the code in my reply posting to your other message.
There I have shown a sample code of what I mean. And yes, I know there are a
couple of syntax errors because I did not try to compile it, but anyway it
should illustrate the idea.

Jack

The usefulness over a std::vector would be the ability of indexing objects
of the derived type. std::vector can index only objects that are exactly of
the type that is given as a template parameter to it.

That's where you are confused, vector can do everything that a C array
can do. Since a C array cannot index objects of the derived type,
neither can vector.

Try it your self and see:

class A {
int X;
};

class B : public A {
int y;
};

int main() {
B array[2];
A* ptr = array;
assert( ptr == &array[0] );
++ptr;
assert( ptr == &array[1] ); // this will fail
}

 

[Jack]

Ben, if you take a very careful look at all these postings once again you
will notice that all those ideas had already been discussed in this thread.
Thanks for your help anyway

Jack