Thread: how to double an array size?

Originally Posted by laserlight

this guy claims that Placement-New Requires Heap-Allocated Buffers,

That's nonsense. This "requirement" is derived from the requirement of aligned storage, but "new char[sizeof(Foo)]" is no more guaranteed to be suitably aligned for Foo than "char buffer[sizeof(Foo)]". By the letter of the standard, anyway. However, operator new is required to return storage aligned for any type, so in practice this is a non-issue for new.

For the stack, you have to align the memory. You do that either by over-allocating and adjusting the address:

Code:

char buffer[sizeof(Foo) + alignof(Foo) - 1];
new ((buffer + alignof(Foo) - 1) % alignof(Foo)) Foo;

Or by making sure the alignment is right in the first place.

Code:

typedef ... type_with_foo_alignment;
union { type_with_foo_alignment aligner; char mem[sizeof(Foo)]; } buffer;
new (buffer.mem) Foo;

this has worked well for me so far.

I suggest that you read Stroustrup's answer to the FAQ: Why doesn't C++ have an equivalent to realloc()?

I am not sure what are the effects of using realloc() with new[] even when you take pains to copy back, so I shall not comment on that.

However, I note that you did not match the new[] with delete[] (but with delete, which is incorrect), and that if the new size is less than the old size, you might as well return immediately. The realloc() does not seem useful in the first place: if you have a pointer to a temporary array, you might as well create that array with the new size, and then copy over the elements, then assign the pointer to the original (or in this case, return the pointer to the "temporary" array). At the moment you are copying back and forth, which is a waste of time.

You might want to read the "Allocating Arrays Using Placement new" article, especially the "Performance Tuning" section. Also, note that this is dotz02x's thread, so perhaps you would like to give dotz02x a chance to post an attempted solution.

sorry. is this a homework assignment or something? i can't tell.

i'm posting because i've recently confronted the issue myself and i suspected, as you've confirmed, i was doing it wrong.

anyway, your other points are well taken. i'll stfu now i guess.

I am not sure what are the effects of using realloc() with new[]

It's undefined. Always.

arr = (T *)realloc(arr,sizeof(T)*newSize);

Note that the pattern p = realloc(p, size); is always, without exception, wrong.

The pattern must always be

Code:

T *tmp = realloc(p, size);
if(tmp == 0) {
  // error out
  return 1;
}
p = tmp;

That's because if realloc cannot find enough memory, it returns null and leaves the original block untouched. If you do p = realloc(p, size) in such a case, you'll overwrite the pointer to the old block with null. So not only did you not get a new block, you also lost the pointer to the old block (which then leaks).

Since in most programs and most parts of most programs, out-of-memory is not a recoverable situation, you can use something like this, though:

Code:

void *realloc_a(void *in, size_t newsize)
{
  void *t = realloc(in, newsize);
  if(!t) {
    fprintf(stderr, "Failed to reallocate %d bytes of memory.\n", newsize);
    abort();
  }
  return t;
}

Now you may do

Code:

p = realloc_a(p, size);

because realloc_a never returns null.



This is all only relevant to C, though. In C++, use a std::vector.

Well, thanks for all the feedback but i found my own way to attack this problem and it was by creating a temporary array that is doubled the size, copying the old array to new then deallocating the old and then dynamically allocating the new array again at a larger size and copy the new array to the old array. Then deallocating the new array.

That is a possible solution

However, it would be even simpler to:
1. Create a new array twice the size.
2. Copy the old array to the new array.
3. Deallocate the old array.
4. Point the old array to the new array.

I do not think it is necessary to copy back and forth, as in citizen's suggestion, because you can assign pointers.