-----------------------------------

mapleleafs

Mon Oct 15, 2007 6:01 pm


Dynamically resizing an array

-----------------------------------

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

Mon Oct 15, 2007 6:29 pm


RE:Dynamically resizing an array

-----------------------------------

Could you not just implement your own linked list?


-----------------------------------

md

Mon Oct 15, 2007 6:40 pm


RE:Dynamically resizing an array

-----------------------------------

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
/*
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
struct Array_Block
{
	T *elements;
	Array_Block *next, *prev;
	int start;
}

template
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