On the previous post we discussed about pointers. Pointers is a very important feature of C++ and it is something missing from other similar object oriented languages like Java and C#. While pointers is a great feature and a must for high performance it is also a source of great pain and agony. This power and agony both come from memory management.
Pointers provide direct access to memory. An array is the simplest data structure, since it is just a block of memory. It is also one of the most useful.
Arrays
Arrays are continuous memory blocks. Every array is a series of variables of the same type located one after the other in memory.
You can declare an array of 5 floats like this:
float A[5];You can iterate over the array like this:
for(int i=0;i<5;++i)
A[i] = i*2;
for(int i=0;i<5;++i)
std::cout << A[i] << "\n";
Notice that we start iterating from index 0 and stop at N-1. There is a reason for this.
‘A’ above is in reality a float *. It is a pointer that points to the address of the first float in the array. *A and A[0] are equivalent. [] operator is in reality a deference operator. A[i] is equivelant to *(A + i). The + operator with left operand being pointer and right being an integer returns the same type of pointer as the left operand with an offset of i*sizeof(*A) bytes. So A+2 returns a pointer pointing to the address of 2 sizeof(float) bytes after the beginning of the array A. *(A+2) is the float in that memory address.
Since pointers and arrays are of the same type, with pointers being more robust, when writing functions, we prefer using pointers as argument types for arrays almost exclusively. We also have to pass the size of the array as an argument.
float sum(float * A, int N){
float sum = 0;
for(int i=0; i<N; ++i)
sum += A[i];
return sum;
}
Arrays are great for “compressing” code. If you want to perform an operation for 3 players you could just ‘inline’ by hand the code for each of them, but this is very sub-optimal. First of all it is duplicated code. Second it is a lot more code than you need. Third, what if you wanted to perform the operation for 100000 players? The solution is arrays. You structure your data on arrays and iterate over them.
Memory
The array above is declared either in global scope (data segment of program) or in local scope (stack). You have to know the size of the array beforehand. But this is not very useful in a lot of situations. The solutions is dynamic allocation (in the heap).
The data segment of your program is known after compilation and it is reserved at program start. It is also most of the times initialized with zeroes. Globals are placed here.
The stack is also known at compile time and memory is simply allocated/de-allocated by changing the stack pointer. The available size of the stack is fixed. After leaving a scope, stack space no longer needed for the scope is marked unused by changing back the stack pointer. The problem with stack is that is limited and hence the stack overflow errors. That can be a problem in recursive function calls that include a lot of data in the stack (like big arrays). A few levels deep of something like this is a guaranteed stack overflow. Also keeping pointers to stack space is a guaranteed segmentation fault.
Last but not least, we have the heap. Heap is another section of memory where all dynamic allocations of memory happen. Generally the heap is managed by the operating system and we can request as much memory the system can provide. Allocated memory here is available until de-allocated. Back when RAM was a scarce resource, memory management and error checking of allocations was a lot more important.
Dynamic allocation
We can allocate arrays (and single variables) of dynamic size using dynamic allocation in the heap.
int * = new int();
std::cin >> *N;
int * nums = new int[*N];
It is also very important to clean after yourself. Any allocated memory no longer needed must be de-allocated to make room for other things in the system. This is achieved using delete. delete and delete[] are different operators and must be used to free memory allocated with new or new[] respectively.
delete N;
delete[] nums;
Memory allocated with dynamic allocation (in the heap) is not cleaned up when it gets out of scope. That means that you can use it in other places. One thing to keep in mind though is that if you lose track of the address (pointer) of this memory you will not be able to de-allocate it and you have what is called a memory leak.
If you want to create a function that allocates memory you have to keep in mind that the pointers passed as arguments are copies. Changing a copy does not change the caller argument. That means you have to add another pointer to the type.
void init(float ** A, int N){
A = new float[N];
}
...
float * B;
init(&B, 1000);
Changing contents of the array though works, because we change the memory directly.
In C we can perform similar allocations using malloc and free for the standard library. Since C++ is almost a superset of C, we can use malloc and free. BUT, malloc-ed memory must be free-d and new-ed memory must be delete-d. So it is best to stick to one allocation style. New/delete is prefered because it performs initialization and it
Multi-dimensional arrays
You can have arrays of any type. That means you can have arrays of arrays.
You can implement multidimensional arrays as arrays of arrays. You have to allocate the memory at 2 steps for 2d arrays, like this:
floor = new char [floor_size_x];//allocate row pointers
for(int i=0; i< floor_size_x; ++i){
floor[i] = new char[floor_size_y];//allocate memory for row
}
Essentially you have an array of pointers to char and every pointer is a an array of chars.
De-allocation happens in the reverse order. First delete all child memory blocks and then the parent.
for(int i=0; i< floor_size_x; ++i)
delete[] floor[i];
delete[] floor;
Applying this on our game
Using this new knowledge we can update our little game. You can download the source code below
