2d arrays (reloaded)

[Fedeb]

Ive read a recent post about 2d array and i decided to try it myself. The code writes 2d arrays using different methods and although is working as expected i want to know if im doing some extra coding (mainly i have doubts with: arr2=new int*[4];).
Another question is if the advantage of using ** to define a 2d array is that it uses free memory while using int myvar[2][2] uses stack memory?

thx in advance!

#include <stdlib.h>
#include <iostream>

using namespace std;

int main()
{

int arr[][2]={{2,3},{4,5}};
int (*arr1)[4]=new int[4][4];
int **arr2;

arr2=new int*[4];

for (int i=0; i<4; i++)

{
arr2[i]=new int[4];
}

arr1[0][0]=2;
arr2[0][0]=41;



cout	<<	arr[1][1]	<<endl;
cout	<<	**arr1		<<endl;
cout	<<	arr2[3][4]	<<endl;





return 0;
}

[Disch]

The code writes 2d arrays using different methods and although is working as expected i want to know if im doing some extra coding (mainly i have doubts with: arr2=new int*[4];).

Any time you are manually using new[] you are doing extra coding. Container classes exist so you do not have to manually allocate/free memory like this. IE instead of using an array that you allocate with new[], you could just use a vector.

That said:

int arr[][2]={{w,x},{y,z}};
Storage:
- Memory is stored congruently. IE, this is simply stored as {w,x,y,z}

Pros:
- On stack, so it will be automatically cleaned up
- Simple allocation and initialization
- Congruent memory means no pointer indirection which means it's ever-so-slightly-faster.

Cons:
- On stack, so cannot have extraordinarily large arrays or you'll exhaust stack space
- Must have fixed array dimensions. Cannot size array dynamically.


int (*arr1)[2]=new int[2][2];
Storage:
- Not congruent. Outer array stored as {ptr1,ptr2} with two other arrays stored separately as {w,x} and {y,z}

Pros:
- Bulk of data stored on the heap, so you can have fairly large arrays.
- Non-congruent memory means it can be fragmented which means less chance of allocation failure.

Cons:
- Inner array size is fixed. Cannot be changed dynamically
- Potential for memory leak if you forget to delete[] arr1;
- Not as easy to initialize data

int **arr2;
Storage:
- Not congruent at all. arr2 is a single pointer stored as {arr2}, with it pointing to another array of pointers stored as {ptr1,ptr2}, each of which pointing to an array stored as {w,x} and {y,z}.

Pros:
- All data except for a single pointer stored on heap. Arrays can be freaking huge.
- Non congruent memory means it can be fragmented. Less chance of allocation failure
- Both dims are dynamic

Cons:
- Allocation is a disaster. The initial new[] plus another set of new[]s in a loop
- Cleanup is equally disasterous. A set of delete[]s in a loop, followed by the outer delete[]. High risk of memory leak if not done properly.
- Double indirection means CPU has to follow two sets of pointers to reach actual data... which is the slowest of all mentioned options so far.


vector<vector<int>> vec(2,2) = {{w,x},{y,z}};
Storage:
- Same as arr2

Pros:
- All pros of arr2
- Simple allocation and initialization
- Automatic cleanup, no risk of memory leak.

Cons:
- Double indirection, same as arr2. Not the fastest.
- Vector might allocate more memory than you actually need in anticipation of the array growing. It's possible this might use more memory than other approaches.







Overall there is little if any reason to favor natural arrays over a vector... vectors are pretty much just better. If speed is that much of a concern, you can mimic a 2D array by using a 1D vector and just doing some math before accessing elements, as I illustrate with the 'Array2D' class in this thread: http://www.cplusplus.com/forum/articles/17108/#msg85595

[Fedeb]

Wow, you just made my day. I was troubling with this concept since the past few days and couldnt find a clear explanation like this one.
I can only add two more questions although i consider the previous answer more than enough.
1) Dynamic dims (or dynamic memory alloc.) is usefull if your program depends on user input? (i cant think of another utility)
2) Stack memory < heap memory yet acces to stack memory > access to heap memory?

Seriously thanks a lot.

[Disch]

1) Dynamic dims (or dynamic memory alloc.) is usefull if your program depends on user input? (i cant think of another utility)

Dynamic size is useful for anything not known at compile time.

Examples include:
- user input
- input from any other external source, like the contents of a file or a database
- any kind of runtime computation. IE, for something like a compression algorithm where you don't know the size of the compressed data until you actually try to compress it.

It is also useful just because it does not restrict you to an upper bound. For example, if you're making a game and you want to keep track of various enemies on the screen, you could keep it in an array like Enemy enemies[10];... but then you are restricting yourself to having 10 enemies maximum. Dynamically sizing that would allow you to have any number of enemies.

2) Stack memory < heap memory yet acces to stack memory > access to heap memory?

Short answer: yes, but the access difference is not nearly as big as you might think it is.

This is actually an extremely complex question to answer accurately, so take this answer with a grain of salt. I am breaking this down into extremely simple terms and might be fudging some technicalities in order to get the idea across.

So this answer might not be 100% accurate, but it will hopefully give you the general idea.



All memory starts out as heap memory. Your computer essentially has a giant pool of memory available to it. When your program starts, it will allocate a chunk of that memory to use as stack space. From that point on, that memory becomes "stack memory".

This obviously means you typically have more heap memory available than stack memory... since stack memory is just a small subset of heap memory.



The CPU keeps track of where the stack is with a special "stack pointer" register. And reading/writing values to the stack use a different subset of instructions which are typically ever-so-slightly faster than reading/writing to the heap because they can take advantage of that stack pointer register. Whereas when you read from the heap, you have to do a separate read to load the actual pointer before you can read from whatever address it points to. (Basically... the stack pointer is already loaded)



Allocating heap memory sends out a request to the OS, which checks to see how much memory is available on the system, and hands a portion of it back to your program to use.

On the other hand, using more stack memory is "free" because your program already allocated all of it up front. You're not requesting more memory from the OS, you're just using more of the memory you already grabbed. So stack memory is "free until you run out" -- at which point 'bad things happen'.



But the speed differences we're talking about here are very, very, very small. You are very unlikely to notice any kind of performance difference in your program, and unless you are doing extremely high performance and high demand programming, you should not concern yourself with the details.


Very general rule of thumb: Use stack space when you can, use heap space when you have to. But at the same time, don't bend over backwards and write sloppy code just to favor stack space over heap space. Just use whatever is more practical and don't worry so much about it.

Also, extraordinarily large arrays or objects (ie: several hundred KB in size) should typically be put on the heap, since putting them on the stack risks burning your stack space. You do not want to run out of stack space -- and you won't unless you wastefully burn it like that.

Seriously thanks a lot.

Happy to help.