You’ll need to be able to work with groups or collections of items. A game that only has one character with one action that can be done and with one opponent isn’t going to win you any awards. You have choices and this episode begins more than a week long exploration of collection types available. You’ll learn when to use each type of collection and why. First up today is the array. I’ll explain what arrays are and then give you some guidance on when to use them.
Arrays place items in memory one after the other and also require that all the memory be allocated in one chunk even if it’s not all being used at the moment. The biggest benefit you get from this is that you can navigate directly to any item in the collection using just pointer arithmetic. This allows you to use arrays effectively for binary searches.
Adding and removing items to and from an array is slower and normally requires a Big-O (N) operation.
This episode also describes another benefit of using arrays called locality of reference. Because the items in arrays are next to one another, you can sometimes get large performance benefits because many of the items can fit in faster cache memory of modern processors.
Listen to the full episode or you can also read the full transcript below.
Transcript
We’re all very familiar with the array. If you’ve ever stood in line, then you already know how an array works. Just take a bunch of instances of anything and put them in memory one after the other.
They all need to be the same because you need to declare what type the array will hold when declaring it. Because they’re the same type, each one will occupy the same amount of memory. It’s not just a matter of size though. You can’t put an integer in line with one of your custom classes even if your class requires the same amount of memory.
This is true of all the collections and not just for an array. Imagine if you could put different item types into a collection. How would you know what type something was at a given location? You’ll be able to get access to a specific item but if you don’t know the type, then it’s just some zeros and ones. You might get creative and let’s say that you know your collection will only hold 5 different types. If so, then you put some value at the beginning so that zero means type1, one means type2, etc. Now you have something that’s consistent and will tell you how to interpret the rest of the bits. What you just did though was to put a single type in the collection. This type has a data member that tells you which of the other five data members is valid.
Many languages, especially those that evolved from the C language have the concept of arrays built-in to the language. It’s normally a very basic level of support though. For example, once you declare an array of some specific size, then that’s all it can ever hold. Sometimes, this is okay. And sometimes it causes space to be reserved that’s not needed, just in case. Have you ever been to a large amusement park like Disney? The popular rides have long lines. But take a look at how much space is reserved for the lines even on slow days. If there’s not many people in line, then the park will redirect people to bypass long sections. The main thing that makes the lines similar to programming is how the maximum length has to be reserved even if it’s not being used. And what happens when the maximum length is not enough? For the park, this causes problems because then people start blocking traffic and cutting the line. For programming, exceeding your array length is a good way to crash your program. It’s also an excellent way for an attacker to use the overflow to take over your computer. Many viruses work because they overflow a buffer. This is just another way of saying that the virus causes more items to be written to a fixed length array than the array was declared to be able to hold.
The C++ language has a class called a vector that manages an array of whatever type you want. The nice thing about using a vector is that it can grow bigger as you add more items. It does this by reserving room for a few more items than you currently need. It starts small and when it runs out of room, instead of overflowing the array, it’ll allocate a bigger array, move all the existing items to the new and bigger array, and then start making use of the new space.
Do you always have to put your object instances directly in your collections? No, and you probably already understand how this works too. It uses pointers. Have you ever gone to a busy restaurant where a crowd of people are waiting outside for a table? What do you do? Do you just start waiting also? Well, no. You first need to let the restaurant know that you’re waiting by going up to a reception area. You’ll be asked how many people are with you and for your name. Your name serves as a pointer. You then move away from the reception so other people can register. Where you wait doesn’t matter anymore. You don’t have to stand in line because the receptionist has some information, your name, that can be used to find you when needed.
You can get around the limitation that all the items in a collection have to be the same type by first using pointers. This makes sure that each item in the collection really is of the same type. But a pointer to what? If you use pointers to an interface, then any class that implements that interface can then be included in the collection and you can use polymorphism to get individual behavior for each item.
Now that you know what arrays are, I’ll explain when to use them right after this message from our sponsor.
( Message from Sponsor )
The first guidance I’ll give on selecting a collection type applies to all the collections you’ll learn about. It’s simple and yet rarely talked about in books. Test. That’s the best thing you can do. If you’re not sure which collection type to use, and it never hurts even if you think you are sure, try several types and test them. If you’ve designed your class to keep data members private, then you can change the implementation of your class to use a different collection type and see for yourself which one works best. Be careful that you don’t skip any important scenarios. So don’t test your implementation with just 5 items when your customers are likely to have 5,000 items. This will also help you realize how hard it is to sometimes keep an implementation private without exposing details that other code can come to rely on. Once other code from outside of your class makes use of your class in such a way that it relies on a particular collection type, then it’s much harder to change.
Let’s start with comparing what it takes to add and remove items from an array.
If you want to add an item to the end of an array and there’s room in the array to hold the new item, then you just add it. This is a Big-O of one operation because you can do this in constant time. What that time is doesn’t matter. Some computers will be faster than others. But the main thing is that it doesn’t depend on how many items are in the collection.
But what about adding an item when the array is already full? In this case, you need to find more memory big enough to hold all the existing items in the array plus some extra items. It’s always good to make room for some more because you don’t want to keep doing this for every single item that gets added. Once you’ve got the memory, you then need to copy all the existing items to their new home, then you can free up the memory used by the smaller array, and then add the new item to the end. There should be room now. This is a Big-O of N operation because you need to move each item already in the collection. This will slow down as the collection becomes larger.
What about adding an item to an array somewhere other than at the end? Anytime you add an item to an array, you need to make sure that there’s room for the item and if not, then follow the steps just described to relocate the array to a larger home in memory. Be aware that for a while at least, relocating an array requires enough memory to hold two copies plus some in memory. This is because until the first array is deleted, they both need to exist so that the items can be copied. If you have very tight memory constraints, then this might rule out arrays from even being considered.
Assuming you have room for a new item in an array and you want to add the new item somewhere other than at the end, you need to make room for the item by opening up a spot. Remember that arrays store items back-to-back with no extra space left between items. What you have to do is start at the last item and copy it one position ahead, then go to the item right before that and copy it one position ahead. You repeat this process from the end of the array working your way back until you reach the spot you want to use to insert the new item. Only then can you place the new item into this opening that you just created. This is a Big-O of N operation because you have to move individual items one by one until you get to the desired location. What if you only need to move a single item because you want to insert the new item just before the last item in the collection? Is this still a Big-O of N operation? Yes. Because the algorithm itself doesn’t know what specific location you want to use when adding your new item. It’s written to handle any number of items that need to be shifted to make room. And who knows, just because you get lucky and only need to shift a single item one time just remember that the next time might need to go all the way to the beginning.
Removing items in an array is similar to adding them. You don’t need to worry about growing the size of the array. But removing an item that’s not already at the end requires you to shift all the other items back one position to close the gap. So removing items from an array is also a Big-O of N operation.
Arrays have two extra advantages and only one of these is commonly talked about. The other one is subtle and even experienced professional programmers may not have ever thought about it.
The first advantage that arrays have is that because the items are all contiguous in memory and spaced back-to-back, it’s possible to navigate directly to any item. This is critical to being able to implement a binary search algorithm. If you find yourself needing to refer to various items by their position, then an array is a good choice.
The second advantage is something called locality of reference and has to do with how modern processors cache memory. A modern processor is extremely fast to the point that going out to memory and reading and writing values is much slower. What modern processor do to speed things up is they don’t just work with individual memory addresses but instead bring in many memory values at once and put those values in special cache memory that’s much faster. The only problem is this cache memory is also small and can’t hold a lot. Because items in an array are next to one another, then navigating one item at a time in an array can end up staying within the bounds of the cache more often.
I mentioned back-to-back storage earlier and I’ll end this episode with this final thought. Back-to-back doesn’t always mean that there’s no wasted memory. Many processors have optimized memory addressing so that they can easily read and write memory that’s aligned on certain boundaries. This could be every 4 bytes, 8 bytes, or some other value. If you need to read a four byte integer that spans this alignment, then it’s possible that the processor will need to make two memory reads before reconstructing the integer. To help prevent this, compilers can add padding to a class. So if you have a class that contains a single char data member and no virtual member methods, then the class will require a single byte. But add another data member of say type int and the compiler could decide to add a few unused bytes after the char and before the int. This increases the total size of the class to 8 bytes even though only 5 are used but it keeps the int aligned for faster performance.