Need help in dynamic arrays of c++?

how can i increase the size of a dynamic array even though i dont know what its end size will be...please tell me this without the use of std vector thingy..only use the basic stuff like while,for loops etc to do it..

Need help in dynamic arrays of c++?
Not an uncommon question.





Usually what's done is instead of increasing the size every time you insert something (it causes a large load on the processor)


you do the easier and less intensive process of doubling the size when you see that you need more space.





let's assume we have a dynamic array of books?


so:





const int START_SIZE = 5





Book* myArray = new Book[START_SIZE]





ok, now we know that when we have a dynamic array we must always keep track of it's capacity and it's size (usually you store those in variables).


Our new array has a capacity of 5 and since we didn't add anything it has a size of 0.





so:


int capcacity(5);


int size (0);





great!


We're on a roll, now let's say we add a book.


so the process of adding a book to the Dynamic array is the following





1.) first you check that your new size does not equal your capacity.





in our case if we add one book our capacity is still 5 and our new size (after adding a book ) is now 1.





that's great, so just say:


Book treasure_island("Treasure Island") ;


myArray[size] = treasure_island;


size++;





(keep in mind the order! It's important! arrays start storing at 0...)





ok, that works great as long as we have space, what do we do if we dont have anymore space!?!?!





well, first we have to do a check for that, so before we add a book we do:





size++; //our new size





if (size == capacity)


{


//double the capacity (or increase it however u want)


capacity = capacity *2;





//make a temporary array of that size


Book* tempArray = new Book [capacity];





//copy the old values across to the temp array





for (int i=0 ; i %26lt; size; i++)


{


tempArray[i] = myArray[i];


}





//delete the old array (otherwise a memory leak!)


delete [] myArray;





//make our array pointer point at the tempArray


myArray = tempArray;





}


// all done! now, we can add the new book knowing we have //space for it!





myArray[size] = (the book you wanted);








Hope this helps!
Reply:Well, even though you said not to use it, an stl vector really is the fastest and easiest way to do this, I'd recommend that over reinventing the wheel.





To "roll your own" using just the new/delete, you'll just have to keep track of the current maximum size of the array, and the number of items you've added. Whenever you add an item to the array, check if it would push the number of items over the maximum. If it will, you'll have to double (doubling is the most common, but you could increment it by some other amount if you want) the maximum, allocate a new array of the entire new maximum size, copy all the old elements over, and then delete the old array. If you look at the vector source, you'll see this is pretty much what it does when it goes beyond its size limit.





// initialize


int maxItems=100


int numItems=0;


itemType *array=new itemType[maxItems];





// ...


//... add something to array ...


if(numItems+1%26gt;=maxItems)


{


maxItems*=2;


itemType *newArray=new itemType[maxItems];


// in practice, memcpy and a for loop usually take


// about the same time for me, but this looks nicer


memcpy( newArray, array, sizeof ( itemType ) * numItems );


delete array;


array=newArray;


// note that the location of the array is now a new address


// so anything that was passed the location of the old array


// by reference now has a BAD pointer


}


array[numItems]=something;


numItems++;


// note that numItems is incremented only AFTER using


// it as the index. This could be written in 1 step as


// array[++numItems]=something; but it makes it a little less


// readable IMO








Ideally, the above would be in some dynamic array class, which overloads the [] operators for access, and has some add_item(itemType) method. And if you want to use it for different types, you'd really want to make it a template class. But then, this would be really close to stl vector, which you requested not using. In that case, maybe you do want to go linked list or tree as suggested above.
Reply:This is a bit complicated as you are going to have to dynamical cast the array size on the fly; however, the code will look something like this:





char * myArray = NULL;


// Demonstrate increasing the array based on loop iterations


// This code would cause errors and should only be used as


// a basic example of how to create dynamic arrays, all data


// is lost when the size is increased!


for (int ndx = 0; ndx %26lt; 10; ndx++) {


myArray = new char[ndx];


}


// Release the memory used


delete [] myArray;
Reply:You can just call a function to copy the array into a temporary array of the same size, delete the original array, and create a new array that is the size of the old array + 50 or so.





void lengthenArray(int/char/whatever *array) {


length = length of array;


int/char/whatever temp[length];


copy(array, temp);


delete array;


create array[length of array + 50 or so];


}





I'm sure there are better ways, but that's the best I could think of off-hand.
Reply:The other answerers are dangerously wrong. JordTeic's idea is inefficient (copy the array to a temp, and then delete and recreate array?).





Rjzii is just plain wrong (that's not how new and delete work, and that's not what your link suggests. Read it carefully).





CrazyCoder thinks C and C++ are the same. Wrong language.





%26gt; how can i increase the size of a dynamic array even though i dont know what its end size will be





Actually, you might not know the precise end size, but you can make an educated guess as to how big it needs to be in the short term right? One thing you could do is allocate a new array that is big enough, and copy the old array to the new array. Depending on what your array contains (complex objects for example), this could end up being an expensive operation.





A btree or linked list of buffers may be a better technique, depending on what your array contains and how it being used. Just link up arrays, and you can keep extending your “array”.
Reply:first of all you should include the header file %26lt;stdio.h%26gt;


there is a funtion named malloc you can use that function to allocate more memory to your array.





if you still have problem send me an email at mr_sheikhazad@yahoo.co.in

flash cards