Ok, I have a slight problem here. I need to allocate an array but I will never know the maximum size the array will reach. I am using: Object_list = (o_list_type*)malloc(sizeof(o_list_type)); where Object_list is *o_list_type and o_list_type is a custom class I made. to allocate the first cell in the array but when I create the second cell I lose the first one. How can I prevent this. - *Naku*

If I understand you correctly you want to store an unknown number of your struct. Well, it sounds like you need a linked list. If you don''t know what one is try a search on google.com.
If you''ve never written on before it can be a little difficult to get working, there are pre-made linked-lists in C++, but you should learn to write one yourself before you use any of those.



Jason Mickela
ICQ : 873518
E-Mail: jmickela@pacbell.net
------------------------------
"Evil attacks from all sides
but the greatest evil attacks
from within." Me
------------------------------

Have you considered using a linked-list?

If you insist on using an array you implement a dynamic array.
That is - an array that gets reallocated when you want to add it a member and it doesn''t have enough room.

You can start with an array that contains exactly the needed amount of objects.

Whenever you want to add an object to it, you allocate a new array, one object bigger, copy the old arrays contents to the new one, free the old one and make your Object_list point to the new one:

object_type *dyn_array;
int size;

void add_object(object_type obj)
{
object_type new_array;

size++;
new_array = (object_type*)malloc(size*sizeof(object_type));

new_array[size-1] = obj;
}

void main()
{
size = 0;
object_type a, b, c;

add_object(a);
add_object(b);
add_object(c);
}


Note that this is a general implementation and it''s probably not the most efficient one for your needs.


If you don''t want to reallocate the array for any added object, you can consider allocating a bit more than you need.
Say, whenever your array is out of room, allocate another 500 objects and only when you have another 500 you need to allocate it again.


But as I said at the beginning, you might insist of using an array (and you can, there are many reasons to do so), but if you''re not familiar with linked-list I''d suggest you read about this data structure.


Feel free to ask more,
Oren.

http://qsoft.cjb.net

I thought about using a linked list but they are slower than an array so I was trying to avoid using one. Thanx anyway though.

- *Naku*

Then what you need to use is something like the built in vector or deque containers in C++ .... they have random access ability, and they can grow to hold more items.

vector has the most efficient access of any, but the least efficient growth.

deque is the most general purpose container, with good access speed and good size growth ... as long as you only add and remove items from the front or back it''s pretty efficient.

IF ... you access your items many hundreds or thousands of times per insert or delete, then dynamic arrays may be good ... but they get worse and worse the bigger it gets, because you have to copy every element into the new array when you resize it - this is what vector does too .. but it grows in blocks ... to reduce the cost somewhat.

Are you trying to create an array or a linked list?
If you are creating an array then use realloc. Realloc dynamically reallocates memory while expanding or contracting the block of memory that is being reallocated.

Object_list = (o_list_type*)realloc(nCells * sizeof(o_list_type));

You now have an expanded block of memory. The side effects of realloc are numerous and are notorious for causing bugs. I recommend that you read about it in the MSDN documentation as well as a good C programming book. The book "Writing Solid Code" by Steve Maguire is a good place to read about realloc and it''s side effects, not to mention a lot of other helpful tips.

If you are creating a linked list then your Object_list class needs to have a pointer to the next element in the list and you must set this pointer every time a new cell is allocated.

1. Allocate a new cell.
Object_list = (o_list_type*)malloc(nCells * sizeof(o_list_type));
2. Make this cell the head of the list.
Object_list_Head->next = Object_list

All of this is fine if you''re coding in the C language, but if you are using classes and C++ then you should use ''new'' to alloc memory and use the standard template library for linked lists. I can''t explain all of this in this reply, but there are numerous books on the C/C++, STL programming subjects. I''m sure you''ll find one that will give you the answers you are looking for.

You have to use realloc. Add_object only with mallocs just destroys the current memory space and creates a new array.

quote:

---

Original post by Xai
vector has the most efficient access of any, but the least efficient growth.

deque is the most general purpose container, with good access speed and good size growth ... as long as you only add and remove items from the front or back it''s pretty efficient.

---

A little off-topic, but my experience has been the opposite of this with deque. One of the first things I did with deque was try to make a character fifo out of it--using push_back and pop_front on single characters to create a stream, and doing many of these operations per second (e.g. a byte stream to/from sound card, serial port). The deque interface is perfect for this application, but the performance was horrible. I''m pretty sure this is due to the default allocator, and haven''t gotten around to writing my own.

Vector can be inefficient to grow, but if you know enough a priori to use reserve intelligently, it''s the fastest container period (since it''s just a single dynamic array).

Back OT: Naku, you should probably look into realloc like the darkening suggested, since you seem to be using C allocation routines.

A deque is implemented about the same way as a vector, with the only difference that it reserves some extra space before the actual items as well as after them. This makes growing a deque and a vector about equally complex. And makes accesses to a deque slightly slower than accesses to a vector (though it''s probably imperceptible in most applications), since an extra addition is involved (to add the index of the first element in the underlying array to the requested index).

(btw, all of the above is based on the docs for the SGI implementation of STL)