Dynamically resizing an array

[mapleleafs]

Hi all,

How would one go about resizing an array, once its capacity limit is reached? This must be accomplished in O(1) time (i.e. constant time).

One method I thought of was to create an array that was double the size of the initial array, copy the elements over, and delete the initial array. However, this is not an O(1) operation, as it relies on the number of elements that are in the array.

Another method I thought of was to create a new array of the same size, and get the last element of the 1st array to point to the first element of the 2nd array. Would this work?

Also, unfortunately, I am not allowed to use vectors.

[rdrake]

Could you not just implement your own linked list?

[md]

I do not believe it to be possible, even in C with ralloc() there is no guarantee that it'll complete in O(1) time.

There is a way to do it using templates, classes and linked lists however. You'd need to overwrite operator[] for the class, and when something outside of the allocated range is accessed simply request some more memory with new. Here's some spiffy psudo code for you to mull over

[change-of-plans]
I was originally going to write psudo code, but it was fun to write it, so I present you with a completely untested spur of the moment array-to-linked list class. It may or may not compile/run/kill everything.

c++:

/* This code is NOT public domain, it's released under a Creative Commons attribution, non-commercial license (version 2.5) Copyright 2007, John Blackwood */ template<class T> struct Array_Block {         T *elements;         Array_Block *next, *prev;         int start; } template<class T> class Array { public:         Array(int block_size)         {                 base = 0;                 this->block_size = block_size;                 block_count = 0;         }                 Array_Block new_block(int start, int size)         {                 Array_Block *b = new Array_Block;                 b->next = b->prev = 0;                 b->elements = new T[size];                 b->start = start;         }                 void delete_list(Array_Block *b)         {                 delete [] b->elements;                 if( b->next != 0)                         delete_list(b->next);                 delete b;         }                 Array_Block *get(int index)         {                        Array_Block *b = base;                 bool found = true;                 while( !(b->start <= index && b->start + block_size > index) )                 {                         if( b->next != 0)                                 b = b->next;                         else                         {                                 found = false;                                 b = 0;                                 break;                         }                        }                                 if( found )                         return b;                 else                 {                         int start = index / block_size;                         b = new_block(start, block_size);                         b->next = base;                         base = b;                         return b;                 }                                 // look! code that never EVER executes, but it's fun to put here anyways :D                 return 0;         }                 ~Aray(void)         {                 delete_list(base);         }                 T operator[](int index)         {                 Array_Block b = get(index);                 int offset = index % block_size;                 return b->elements[offset];         }                 void operator[](int index, T value)         {                 Array_Block b = get(index);                 int offset = index % block_size;                 b->elements[offset] = value;         }         private:         Array_Block *base;         int block_count, block_size; };