Hiya,

This is not so much a problem as it is a question. Consider this code:

struct coord
{ int x, y; };

void main()
{
coord **co;

co = new coord*;
co[0] = new coord;

co[0]->x = 1;
co[0]->y = 2;

// some usage of co

delete co[0];
delete co;
}

Since co[0] is only allocated because it is used (co[1] or co[2] ...co[n] can be allocated as necessary) is this considered as a form of dynamic memory allocation? If so, why is it not mentioned in most books which refer to dynamic memory allocation which almost always uses linked lists or binary trees or such. Wouldn't a pointer type array be faster than any other form of container?

If you're using the 'new' and 'delete' operators, or 'malloc' and 'free' in C, it's dynamic memory allocation, yes. I don't know about "most books" but the C/C++ books I've seen call it that.

You can use pointers without doing any dynamic memory allocation, though. For example:

px is a pointer to int, but it doesn't use dynamic memory allocation. So it's quite possible to have linked lists, binary trees, and the like without doing any dynamic allocation.

As for a pointer array being faster... it depends. It's faster to declare a fixed-length array of structs than it is to dynamically allocate another one every time it's needed, so if you know in advance that you'll need, say, 100 elements in the array, it's more effective to use a normal array.

If I got what you are asking correct, you are asking if an array is faster than other data structures? It depends upon what you are doing. For example, arrays have a massive overheads in insertion sorting, they are also not very suited to complex relationships between data. On the other hand, sorted arrays are the same as a perfectly balanced binary tree for binary searches and they are easy to traverse. However, in the case that you discuss, I see no relationship being held between data other than the fact that they are all co-ordinates - so, the possible benefits of more complex data structures would most likely not be reaped.

One thing is though, unless C++ is different (I am a C programmer), you need to be careful as `co = new coord*' will only allocate enough space for one pointer to a coord object pointer. If you understand how array notation breaks down ( x[i] => *(x + i) ), you can quite easily see that making co[1] will overwrite data you have not allocated for this purpose. The side effects of this are not defined. This is another area where the other data structures do better, the lack of need for a contiguous memory base.