Remember how we say every item in an array had to be the same size? Let's dig into that a little more.
What if we want to store strings(which is already an array into array). We are trying to store arrays into array.
And what if these strings have different length, some may not fit in the size of array blocks and all the blocks have same size.
What we can do is store strings in large array, and mark the end of each string with a special character. '/0' is used to mark the end of strings.
But for short strings, the space will be wasted.
Instead of storing the strings right inside our array, let's just put the strings wherever we can fit them in memory. Then we'll have each element in our array hold the address in memory of its corresponding string. Each address is an integer, so really our outer array is just an array of integers.** We can call each of these integers a pointer, since it points to another spot in memory.**
Magic happended! right?
This fixes both the disadvantages of arrays:
The items don't have to be the same length—each string can be as long or as short as we want.
We don't need enough uninterrupted free memory to store all our strings next to each other—we can place each of them separately, wherever there's space in RAM.
Now we have a new tradeoff:
Remember how the memory controller sends the contents of nearby memory addresses to the processor with each read? And the processor caches them? So reading sequential addresses in RAM is faster because we can get most of those reads right from the cache?
Our original array was very cache-friendly, because everything was sequential. So reading from the 0th index, then the 1st index, then the 2nd, etc. got an extra speedup from the processor cache.
But the pointers in this array make it not cache-friendly, because the strings are scattered randomly around RAM. So reading from the 0th index, then the 1st index, etc. doesn't get that extra speedup from the cache.
That's the tradeoff. This pointer-based array requires less uninterrupted memory and can accommodate elements that aren't all the same size, but it's slower because it's not cache-friendly.
Thanks for reading <3
Top comments (0)