[Sussex] C++ question

[Steve Dobson]

Afternoon Geoff

On 20 Jan 2003 Geoff Teale wrote:
> Here's a C++ question that's relevant to some work I'm doing at home at
> the moment.

Working at home; get a life ;-)

> What is the most effecient way of redimensioning a dynamic array of
> pointers to objects without erasing the existing contents?

How often are you re-sizing the array?  If this is happening a lot there
are two options:

  1).  If memory size is no problem (this is not an embedded system) then 
       double the array size each time you have to resize it.  This is the
       way classes like java.util.Vector work.  Add methods to pre-size the
       array, shrink to fit, and set the grow size.

  2).  Use a linked list.  Slowwer to search, but very fast to add and
remove 
       on the fly.  As you said this was a C++ question not a C question
I'll
       assume that you could hold a flag that marks if the pointer array is
       dirty or not with the (master) linked list structure.   Then you need
       only re-size the array when needed - don't bother keeping the array
in
       step with the linked list.

A lot here depends upon the way new elements will be
added/removed/searched/used.

> Anyone who knows clever method doesn't involve creating a new array,
copying
> everything to that array, deleting the original array and then setting
> the old array variable equal to the new array variable could you please
say
> so.  I'm so sure someone must have a better way to do this...

At the end of the day the above are going to have to be done by someone.  If
managing the area using the C routines malloc(2), calloc(2), and free(2)
then
Linux supports the realloc(2) routine as well.

If realloc(2) is called and there is free space in heap just after your
array then
realloc(2) will return the same address you gave it.  If space after the
array
isn't available then realloc(2) will find new space and do the copy for you.
The new address returned has the old size of the array already copied for
you.
IN either case it is your job to initialise the delta between (unless you're
down-sizing).  Finially, if realloc(2) return NULL either you ask of zero
bytes
of heap or you're run out of heap space.  So don't loss track of the orignal
array pointer.  The code will look something like this:

Vector::resize(size_t newSize)
{
   void *newArray = realloc((void *) elementArray, newSize);
   if (newArray == NULL && newSize) 
      throw OutOfMemoryException();

   if (arraySize < newSize)
       memset(newArray + arraySize, 0, newSize - arraySize);

   elementArray = (Element *) newArray;
}

Which looks cleaner, but there is still the allocation and copy going on but
it just got hidden in realloc(2)

Steve