resize array of objects

isgoed · 08-29-2009, 03:55 AM

I want to resize an array of objects. I found an earlier thread which requested the same, where post 14 suggested what to do. I made my custom operator new[] and delete[] as described in the article Customized Allocators with Operator New and Operator Delete by Andrei Millea on this site. In this way I can use realloc to resize my array, but the implementation of new[] offsets the address of the ptr by 4 bytes (most likely to store the length of the array). But this makes it completely ..........y to resize. Since I don't know the real address of the memory block. It may be that the offset is implementation dependent or is 8 bytes in 64-bit mode.

An example of code to illustrate the problem reads:

Code:

class Myclass
{
public:
        void* operator new[](size_t);
};

void* Myclass::operator new[](size_t size)
{
    void *storage = malloc(size);
    if(NULL == storage) {
            throw "allocation fail : no free memory";
    }
    return storage;
}

int main(void)
{
Myclass  *MyArrayOfMyClass,*ExpandedArrayMyOfClass;

MyArrayOfMyClass = new Myclass[10];

// I need to resize my array of objects

ExpandedArrayMyOfClass = (Myclass*)realloc (MyArrayOfMyClass, sizeof(Myclass)*((size_t)(20)) );

// <- So this is unsafe, because I allocate 4 bytes too less.
//      and the real base of the memoryblock of MyArrayOfMyClass is &(((char*)MyArrayOfMyClass)[-4])
}

Is this the proper approach to resizable arrays?
How to get the real memory address and required length for MyArrayOfMyClass?
On my system, memory is 16 byte alligned, so any ptr should have an address ending on 0 (example 0x1001c0), but can I rely on this?

And I don't want to use std::vector

**laserlight** · 08-29-2009, 04:02 AM

Quote:

Originally Posted by isgoed

And I don't want to use std::vector

Why not?

isgoed · 08-29-2009, 04:22 AM

Quote:

Originally Posted by isgoed

And I don't want to use std::vector

Quote:

Originally Posted by laserlight

Why not?

I want to be able to save my objects to disk in a way that handles arrays, classes and data uniformly. Since a vector is a struct I have to access the internal pointers of the array. The vector struct also requires quite some memory (32 bytes on 64 bit), which is a waste if you have many small arrays. And lastly: (I am not so sure about this point) in the vector implementation it cannot be controlled how much memory is allocated and the size of the allocated memory cannot be predicted (you might request it with vector->capacity() though)

**laserlight** · 08-29-2009, 04:35 AM

Quote:

Originally Posted by isgoed

I want to be able to save my objects to disk in a way that handles arrays, classes and data uniformly.

Have you considered using something like Boost.Serialization?

Quote:

Originally Posted by isgoed

The vector struct also requires quite some memory (32 bytes on 64 bit), which is a waste if you have many small arrays.

This is true, but you would have the same problem anyway if those small arrays are not of the same size since you would need to track the size and capacity with your own implementation. If those small arrays are of the same size, you could then "divide" a std::vector into pieces of equal length.

Quote:

Originally Posted by isgoed

And lastly: (I am not so sure about this point) in the vector implementation it cannot be controlled how much memory is allocated and the size of the allocated memory cannot be predicted (you might request it with vector->capacity() though)

I believe that you are correct since even a call to reserve() would only reserve to at least the given capacity. On the other hand, are you sure that this is actually a problem in the first place?

If you really do want to implement a dynamic array, I suggest that you look at the last option mentioned in that article that you linked to: placement new with a buffer. The tricky parts of needing to construct and destroy explicitly (and perform copying) would be hidden by your class interface.

cpjust · 08-29-2009, 02:23 PM

Have you actually tried using std::vector and done some performance measurements to verify that the vectors are actually a bottleneck for you?

isgoed · 08-31-2009, 04:27 AM

Well I have come up with a solution:

I just don't call new and delete any more, but use my own memory allocation and initialization. You can't invoke a constructor, but you can just use a member function (although it is said that it isn't proper to call a member function of an object that is not initialized).

anyways.. code like this:

Code:

// create my class
MyClass *MyInstance = malloc(sizeof(MyClass));
MyInstance->initMyClass(argument);

// resize my class
arraylength = 10;
MyInstance = (MyClass*)realloc ((void*)MyInstance, sizeof(MyClass)*arraylength);
for(i=1;i<arraylength;++i){
  MyInstance[arraylength].initMyClass(argument);}

// delete my class
for(i=0;i<arraylength;++i){
  MyInstance[i].deleteMyClass();}
free(MyInstance);
MyInstance = 0;

I notice that I like this much better. I can now create arrays and initialize them if needed and with arguments. I also loose the often required default constructor and destructor. This really helps in linked-lists situations. The deletion of one element should not delete the entire list, because deinitialization is not linked to deallocation any more.

Laserlight, thanks for the Boost.Serialization suggestion. This really sounds like the answer to everything related to resource management (But I need more

.)

I think that, now that i know that I can cast memory to an object, I can also cast memory to a vector and lose the need to copy the memory.

**laserlight** · 08-31-2009, 05:17 AM

Quote:

Originally Posted by isgoed

I just don't call new and delete any more, but use my own memory allocation and initialization. You can't invoke a constructor, but you can just use a member function (although it is said that it isn't proper to call a member function of an object that is not initialized).

Yes, you should not call a member function of an object that is not initialised. That article gave the use of a static member function as a workaround, with the premise that the implementation did not support new. If yours does, it might be better to just use placement new, but then it would be better to just use a standard container, because...

Quote:

Originally Posted by isgoed

I can now create arrays and initialize them if needed and with arguments. I also loose the often required default constructor and destructor.

You should note that std::vector (and std::list, for that matter) already allows you to insert objects without invoking the default constructor (if any). It sounds like you are reinventing the wheel, because you simply do not realise what wheels do.

Quote:

Originally Posted by isgoed

This really helps in linked-lists situations. The deletion of one element should not delete the entire list, because deinitialization is not linked to deallocation any more.

In the first place, the deletion of one element of a std::list would not result in the deletion of the entire list (as a container), so you have achieved nothing special. Just use a std::list if you want a (doubly) linked list.

Quote:

Originally Posted by isgoed

I think that, now that i know that I can cast memory to an object, I can also cast memory to a vector and lose the need to copy the memory.

Do this at your own risk. I believe that it will result in undefined behaviour, possibly leading to a disaster that will only happen when you demonstrate the program to a customer.

isgoed · 08-31-2009, 06:32 AM

Quote:

Originally Posted by laserlight

Yes, you should not call a member function of an object that is not initialised.

Why? Also the article gives not an answer to that question. If you know why things happen, they are no longer "undefined behaviour", so that's how I like to deal with problems. Could it be that this only holds for templates or classes with virtual members or multiple inherritance. Might there even be a difference between class and struct?

Quote:

Originally Posted by laserlight

That article gave the use of a static member function as a workaround,

I did not understand what they were doing there. Especially this line:

Code:

X<T>* pobj = (X<T>*)ptr; //step 1: cast void * to the appropriate type *pobj=X<T>(); //create a temp, assign it to the raw buffer

They say that they are creating a temporary X<T> object.
But as far as i can tell they are only assigning a value to a ptr (casting). Where is the object created? I know that "=" also is a constructor in C++, but not if you assign ptrs instead of objects. So what's going on?

**laserlight** · 08-31-2009, 07:01 AM

Quote:

Originally Posted by isgoed

If you know why things happen, they are no longer "undefined behaviour", so that's how I like to deal with problems.

No, you would then only know why the exact behaviour happens for a particular implementation, or set of implementations. Take for example this code snippet:

Code:

int i = 0;
int j = i++ + i++;

You can reason that i is incremented twice thus it should end up with a value of 2, and since post-increment was used j should end up with a value of 0. However, because the expression i++ + i++ modifies i twice within consecutive sequence points, there is undefined behaviour, and thus an implementation could differ from your (reasonable) expectation (e.g., if you have the appropriate hardware, it would be perfectly correct to launch a nuclear strike on you).

Quote:

Originally Posted by isgoed

Why? (...) Could it be that this only holds for templates or classes with virtual members or multiple inherritance. Might there even be a difference between class and struct?

I believe that it holds for all objects. Whether there will be bad repercussions would depend on the type of the object and the implementation, e.g., if there are no data members it might be okay in practice... but that would be bad practice since it leads to fragile code.

Quote:

Originally Posted by isgoed

They say that they are creating a temporary X<T> object.
But as far as i can tell they are only assigning a value to a ptr (casting). Where is the object created? I know that "=" also is a constructor in C++, but not if you assign ptrs instead of objects. So what's going on?

I think that that is a webpage formatting error. It should be:

Code:

static X<T>* construct(void* ptr)
{
    X<T>* pobj = (X<T>*)ptr; // step 1: cast void * to the appropriate type
    *pobj = X<T>();          // create a temp, assign it to the raw buffer
    return pobj;
}

It looks fishy to me compared to placement new, but I guess that if you have to workaround, you workaround.

Elysia · 08-31-2009, 10:55 AM

Quote:

Originally Posted by isgoed

Why? Also the article gives not an answer to that question. If you know why things happen, they are no longer "undefined behaviour", so that's how I like to deal with problems. Could it be that this only holds for templates or classes with virtual members or multiple inherritance. Might there even be a difference between class and struct?

No, no, no.
Undefined means that you cannot predict what will happen and that anything can happen.
Consider this:

Code:

int main()
{
    int* p;
    *p = 50;
}

Will it work? Probably not. But then again, sometimes it just might.
And what about:

Code:

int main()
{
    int n[5];
    n[5] = 50;
}

Will this work fine? Probably. Will it always work? Probably not.
That's the meaning of undefined. Don't ever do it.

isgoed · 09-01-2009, 03:45 AM

Quote:

Originally Posted by laserlight

If you really do want to implement a dynamic array, I suggest that you look at the last option mentioned in that article that you linked to: placement new with a buffer. The tricky parts of needing to construct and destroy explicitly (and perform copying) would be hidden by your class interface.

Ah, now I see how that's done. I thought that placement new only had a purpose for memory pools. But of course an array is also a memory pool. So a C++ recommended code would look like this:

Code:

// create my class
MyClass *MyInstance;
MyInstance = new(malloc(sizeof(MyClass)))    MyClass();

// resize my class
MyClass   *MyDummy;
int           arraylength = 10;
MyInstance = (MyClass*)realloc ((void*)MyInstance, sizeof(MyClass)*arraylength);
for(i=1;i<arraylength;++i){
  MyDummy = new(&MyInstance[i])    MyClass();}

// delete my class
for(i=0;i<arraylength;++i){
   // Explicitly call the destructor for the placed object
  MyInstance[i].~MyClass();}
free((void*)MyInstance);
MyInstance = 0;

This code is based on the excellent article:
What is "placement new" and why would I use it?. Note that you are explicitly calling the destructor here. But you have to be careful here; the article mentioned above will point out some pittfalls. And I want to make clear that you should be careful not to use placement new and new alongside each other. They could allocate memory differently (and there are many forms of new).

A real insightfull article is this one (on the same site)
[11.14] Is there a way to force new to allocate memory from a specific memory area?.
You cannot call a constructor explicitly, but you can call a destructor explicitly? The thing is that if you allow a programmer access to a class before it is initialized, he could access (private) members which are not yet available, in order to safeguard against mistakes. This particularly holds for objects with a virtual table/pointer as mentioned in the above article (a simple test shows that a class with virtual members will be 4 bytes longer). But since all this happens in the compiler and the compiler only makes code that might as well have been written in C, there is nothing stopping you from writing your own constructor. If you know what your object will look like, calling a member function before it is initialized is perfectly safe. This is the case if your object is a C-code compatible struct. Note that it is also not required to call your destructor, it is just common use.

Having said that, the code in my 6th post might be preferable in many cases. Fiddling with new and delete causes a lot of exceptions that easily lead to errors (see the articles for the solutions). The only thing that can go wrong with using unitialized objects is a failed call to malloc. Furthermore the new and delete call actually execute multiple lines of code, resulting in a performance hit and obfuscating code.

anon · 09-01-2009, 05:39 AM

I have no idea what you are talking about. In your code there is a potential memory leak with the realloc (if it fails it returns NULL and doesn't release original memory).

Quote:

Fiddling with new and delete causes a lot of exceptions that easily lead to errors (see the articles for the solutions). The only thing that can go wrong with using unitialized objects is a failed call to malloc.

I don't see why constructing objects with the constructor should throw exceptions whereas an init function that supposedly does the exact same thing wouldn't. Besides your code makes no attempt to handle failed calls to malloc / realloc. (The difference between new throwing an error is that leaving std::bad_alloc uncaught leads to std::terminate being called deterministically, whereas not handling malloc failures leads just to undefined behaviour / dereferencing NULL pointers.)

isgoed · 09-01-2009, 06:49 AM

Quote:

Originally Posted by anon

I have no idea what you are talking about.

Then why are you replying?

Quote:

In your code there is a potential memory leak with the realloc (if it fails it returns NULL and doesn't release original memory).

Sure, you should do error checking. As I've said that malloc could fail. And the code above is just functionality code. Right now the code wouldn't even compile.

Quote:

I don't see why constructing objects with the constructor should throw exceptions whereas an init function that supposedly does the exact same thing wouldn't. Besides your code makes no attempt to handle failed calls to malloc / realloc. (The difference between new throwing an error is that leaving std::bad_alloc uncaught leads to std::terminate being called deterministically, whereas not handling malloc failures leads just to undefined behaviour / dereferencing NULL pointers.)

Dereferencing null pointers can happen just as well if you use Class* instance = new Class;
Since with placement new you need to call the destructor explicitly, this can lead to many programmer errors. What happens if you accidently call delete anyway?
The avoidance of this situation can be implemented with pools as described in the article (11.14). This requires many *well considered* lines of code including good handling of try&catch. Now compare this to my code which only uses 1 line of code and can be made safe with 1 error check.
I am not talking about "throwing exceptions", hence your confusion. I am talking about inconsistent use of new and delete and their operation. The whole solution outlined in (11.14) again has to be rewritten if you want to do the same trick with an array. And from the problem in my first post, that doesn't even work. This was the point of this entire exercise. And even if it did work you wouldn't be able to use custom initialization. As you can see this leads to a plethora of redefinitions and careful deliberate thought of the consequences. Now compare this to my code.
(This point is speculation of mine, so correct me if I'm wrong) I am not aware of std::terminate. But as far as I understand you are not obliged to include std in your programming, so relying on this code seems not recommended.

anon · 09-01-2009, 07:31 AM

Quote:

Dereferencing null pointers can happen just as well if you use Class* instance = new Class;

Not really since new Class either succeeds or throws an exception.

Quote:

Since with placement new you need to call the destructor explicitly, this can lead to many programmer errors. What happens if you accidently call delete anyway?

And not calling destructor where it does something important is not as bad? And you suggest manual memory management + hacks that border on undefined behavior is any better?

Quote:

Now compare this to my code which only uses 1 line of code and can be made safe with 1 error check.

Exceptions for memory allocation failures are good since these failures tend not to happen and if they do happen the situation is so severe that you probably cannot handle it close to source anyway. With error codes it most likely will not be just one check in anything but trivial: you'll need to pass an error code to the caller, this will have to check for error codes etc. Also, without RAII, you'll also need to handle clean-up manually.

I suspect that what the FAQ demonstrates will be encapsulated away, so the user of that code never needs to worry about these things again. Another thing is, you'll do all this when you really know what you are after.

Quote:

I am not aware of std::terminate. But as far as I understand you are not obliged to include std in your programming, so relying on this code seems not recommended.

An uncaught exception means you're program will be forcefully terminated at the spot (the terminate function is called). IMO, this is preferable to stumbling on with undefined behavior if you failed to check for error codes.

**CornedBee** · 09-02-2009, 08:26 AM

Quote:

Originally Posted by laserlight

I believe that it holds for all objects. Whether there will be bad repercussions would depend on the type of the object and the implementation, e.g., if there are no data members it might be okay in practice... but that would be bad practice since it leads to fragile code.

The C++ rule is that you can treat objects as raw data if their type follows the POD (plain old data) rules. A type is a POD unless:
- It is a reference.
- It has a user-defined constructor, copy assignment operator, or destructor.
- It has a base class.
- It has a virtual function.
- It has a non-static member that is not a POD itself.

If any of these apply, the object is not a POD, and it's completely undefined what happens if you access it without calling the constructor first.
The core notion of a POD is that you are allowed memcpy it somewhere else, and the target memory contains a valid copy of the original object. You *must not* use memcpy (or memmove or realloc) on any other object.

(These rules will change in C++0x, which introduces the notion of a "standard layout type".)

08-29-2009, 03:55 AM	#1
isgoed Registered User Join Date: Aug 2009 Posts: 8	resize array of objects I want to resize an array of objects. I found an earlier thread which requested the same, where post 14 suggested what to do. I made my custom operator new[] and delete[] as described in the article Customized Allocators with Operator New and Operator Delete by Andrei Millea on this site. In this way I can use realloc to resize my array, but the implementation of new[] offsets the address of the ptr by 4 bytes (most likely to store the length of the array). But this makes it completely ..........y to resize. Since I don't know the real address of the memory block. It may be that the offset is implementation dependent or is 8 bytes in 64-bit mode. An example of code to illustrate the problem reads: Code: class Myclass { public: void* operator new[](size_t); }; void* Myclass::operator new[](size_t size) { void storage = malloc(size); if(NULL == storage) { throw "allocation fail : no free memory"; } return storage; } int main(void) { Myclass MyArrayOfMyClass,ExpandedArrayMyOfClass; MyArrayOfMyClass = new Myclass[10]; // I need to resize my array of objects ExpandedArrayMyOfClass = (Myclass)realloc (MyArrayOfMyClass, sizeof(Myclass)((size_t)(20)) ); // <- So this is unsafe, because I allocate 4 bytes too less. // and the real base of the memoryblock of MyArrayOfMyClass is &(((char)MyArrayOfMyClass)[-4]) } Is this the proper approach to resizable arrays? How to get the real memory address and required length for MyArrayOfMyClass? On my system, memory is 16 byte alligned, so any ptr should have an address ending on 0 (example 0x1001c0), but can I rely on this? And I don't want to use std::vector
isgoed is offline

08-29-2009, 02:23 PM	#5
cpjust and the hat of sweating Join Date: Aug 2007 Location: Toronto, ON Posts: 3,120	Have you actually tried using std::vector and done some performance measurements to verify that the vectors are actually a bottleneck for you? __________________ "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008
cpjust is offline

08-31-2009, 04:27 AM	#6
isgoed Registered User Join Date: Aug 2009 Posts: 8	Well I have come up with a solution: I just don't call new and delete any more, but use my own memory allocation and initialization. You can't invoke a constructor, but you can just use a member function (although it is said that it isn't proper to call a member function of an object that is not initialized). anyways.. code like this: Code: // create my class MyClass MyInstance = malloc(sizeof(MyClass)); MyInstance->initMyClass(argument); // resize my class arraylength = 10; MyInstance = (MyClass)realloc ((void)MyInstance, sizeof(MyClass)arraylength); for(i=1;i<arraylength;++i){ MyInstance[arraylength].initMyClass(argument);} // delete my class for(i=0;i<arraylength;++i){ MyInstance[i].deleteMyClass();} free(MyInstance); MyInstance = 0; I notice that I like this much better. I can now create arrays and initialize them if needed and with arguments. I also loose the often required default constructor and destructor. This really helps in linked-lists situations. The deletion of one element should not delete the entire list, because deinitialization is not linked to deallocation any more. Laserlight, thanks for the Boost.Serialization suggestion. This really sounds like the answer to everything related to resource management (But I need more .) I think that, now that i know that I can cast memory to an object, I can also cast memory to a vector and lose the need to copy the memory.
isgoed is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
array of objects	adam_no6	C++ Programming	2	04-04-2007 07:59 AM
Returning an Array of Pointers to Objects	randomalias	C++ Programming	4	04-29-2006 02:45 PM
accesing data in class objects (array of pointers to objects)	agony	C++ Programming	4	10-16-2003 11:26 AM
Struct *** initialization	Saravanan	C Programming	20	10-09-2003 12:04 PM
Adding objects to an array	Unregistered	C++ Programming	3	11-27-2001 09:24 AM