39: Collections: Array.

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