Arrays. They are beautiful.
In C, we always try to work through restrictions arrays have i.e the size of the array must be statically defined. We always want a dynamic array whose size can be decided at run-time. There are ways which we use widely for e.g by using pointers and then dynamically allocating memory to it using malloc or calloc. But depending on the situation, we might require more efficient and organizable ways. I will explain the concept with a series of examples as in how simple arrays evolved to the tricky expandable ones.
The classic way is to use pointers
This snippet will allocate a memory block of size = array_size(integer array).
Though this is not what I wanted to explain because this way is too clumsy. Imagine if you need 10 dynamic arrays in your program, you have to write these four lines each time and you have to keep track of all the 10 sizes.
A better way is to use structures:
We can simply create a structure containing two elements: array_size and a pointer variable. We can allocate memory to this pointer variable dynamically. This will save us from the headache of keeping track of different array sizes.
For a better understanding, visualize this:
- In this example, we have taken first and second as Array variable, so we don't need to free them. In the end, we only need to free memory of first.arr and second.arr
Its neat and evolved from the first method and this is widely used in software industries. Though I can assure you, expandable arrays are more interesting.
So, moving to our discussion:
What are expandable arrays?
Expandable arrays or stretchable arrays are a tricky way to create dynamic arrays with a pre-defined data structure and its quite very similar to above method.
See the following, and note the area which is marked as expanded memory:
This seems more complex, right? But its not!
- We created a structure which contains last element as a 1 element array.
- As the last element is an array with size 1 and not a pointer, so we can't allocate memory to this. The trick is to create a pointer variable to structure Array and allocate memory to it of whatever size we want.
- Typically, we should have allocated memory of size struct Array to its pointer, but here we allocate size of structure plus (array_size - 1). We subtract 1 because we already have memory for 1 variable.
- As you can see, now we have some extra memory at the tail of the structure, to which we can traverse using arr[].
- We can organise and wrap the functionality into more structured way, e.g, create a separate init function etc.
When you think clearly, this method will seem illegal. But that's the fun of it. :)
Why expandable arrays?
Generally, data has two parts: metadata + actual data.
Metadata is information about data viz. name, creation date, ownership, size etc. We can use expandable arrays beautifully in those scenarios in which we have to transfer data along with some metadata and the size of actual data is not certain.
For e.g, consider a system level software which is used to download data into your mobile phone. The size of file might be known(assume 1 GB), but the transfer rate depends on speed of your internet. At one moment, if the speed is 1 Mbps, the array_size will be 1 Mb for that second. For the next second, if the speed changes to 2 Mbps, we can transfer more data, so array_size will be 2 Mb. In this case, we can use a data structure as above, transferring variable sized data at each second, and utilizing memory with less chances of leaks and memory corruption.
Try writing a program to do this, you will learn a lot. :-)
--------------------------------
Let me know if you find any errors or something is not clear.
