Tuesday, July 19, 2011

Objective-C Tuesdays: arrays

Welcome back to Objective-C Tuesdays. Last time we wrapped up our series on strings by looking at regular expressions in Objective-C. Today we begin a new series: data structures. The first data structure that we will examine is the array.

Most languages have some concept of an array, though it is sometimes called a list. In general, an array is an ordered sequence: a collection of items that has a distinct order. The term "array" implies that each item in the collection is individually accessible in constant time; in other words, it takes the same amount of time to access items at the beginning, middle or end of the sequence.

Arrays in C
The C language includes the ability to define and create strongly typed arrays. You must always declare the type of the items that the array contains.
// declare an array of ints
int lotteryNumbers[6];
This declares an array that holds six integers. When the array variable is declared, the number between the square brackets indicates the number of items that the array can hold, usually referred to as the size, length or count.

C99 (which is the default for iOS projects) allows you to use a function parameter or other variable to determine the length of an array. This feature is naturally called "variable length arrays".
// use a variable as the length of an array
int length = 6;
int lotteryNumbers[length];
Unless you're an old time C programmer, you're probably thinking "yeah, so what?" In earlier versions of C, you could only declare arrays with constant length. In old C code (or code written old C hands), it's common to see code like this:
// constant array length

int lotteryNumbers[LOTTERY_NUMBERS_LENGTH];

C array initialization
You can optionally provide an array with an initializer. An array initializer uses curly braces and looks like this:
// array initializer
int lotteryNumbers[6] = { 7, 11, 19, 23, 29, 31 };
You can specify fewer items than the array can hold; the remaining items will be initialized to zero.
// array with partial initializer
int lotteryNumbers[6] = { 7, 11 };
You can even specify an empty initializer and all the items in the array will be set to zero.
// array with empty initializer
int lotteryNumbers[6] = {};
This is redundant for arrays declared at global scope since global variables are initialized to zero by default, but can be useful for local variables.

If you use an initializer list when you declare your array, you can leave the array length out of the declaration:
// array initializer without length
int lotteryNumbers[] = { 7, 11, 19, 23, 29, 31 };
The compiler will count the items in the initializer list and size your array to fit.

If you are initializing an array of chars, you can use a string literal as the initializer.
char favoriteColor[4] = "red";
char favoriteFlavor[] = "vanilla";
Remember that C strings contain an extra char, the null terminator, so when you initialize an array of chars with the string "red", it actually stores four items. You can make the equivalent initializers using character literals:
char favoriteColor[4] = { 'r', 'e', 'd', 0 };
char favoriteFlavor[] = { 'v', 'a', 'n', 'i', 'l', 'l', 'a', '\0' };

Accessing items in an array
You get items out of an array by using an array index number in square brackets:
int lotteryNumbers[6] = { 7, 11, 19, 23, 29, 31 };

NSLog(@"%i is at index 1", lotteryNumbers[1]);
NSLog(@"%i is at index 2", lotteryNumbers[2]);
The code snippet above produces this output:
11 is at index 1
19 is at index 2
If this is surprising, it's because the first item in a C array is always at index 0.

Assigning items to an array is naturally very similar:
int lotteryNumbers[6] = { 7, 11, 19, 23, 29, 31 };

lotteryNumbers[1] = 13;
lotteryNumbers[2] = 17;
NSLog(@"%i is at index 1", lotteryNumbers[1]);
NSLog(@"%i is at index 2", lotteryNumbers[2]);
which will print out:
13 is at index 1
17 is at index 2

Arrays automatically convert to pointers
Like all things in C, arrays are very low level constructs. Under the hood, an array is simply a block of memory managed by the compiler that's large enough to hold all its items. Because an array corresponds directly to a memory block, an array variable will automatically convert into a pointer to the first item in the array.
// automatic array to pointer conversion
int lotteryNumbers[6] = { 7, 11, 19, 23, 29, 31 };
int *luckyNumber = lotteryNumbers;

NSLog(@"My lucky number is %i", *luckyNumber
This will produce the output:
My lucky number is 7
You can set the pointer to items after the first by using pointer arithmetic:
// pointer arithmetic
int lotteryNumbers[6] = { 7, 11, 19, 23, 29, 31 };
int *luckyNumber = lotteryNumbers;

NSLog(@"My NEW lucky number is %i", *(luckyNumber + 1)
which prints out the
My NEW lucky number is 11
While pointer arithmetic is a perfectly cromulent way to access items in an array, you can use an index in square brackets on a pointer just as you can on an array:
// array index using a pointer variable
int lotteryNumbers[6] = { 7, 11, 19, 23, 29, 31 };
int *luckyNumber = lotteryNumbers;

NSLog(@"My NEW lucky number is %i", luckyNumber[1]
Under the hood, the compiler automatically converts uses of an array variable into a pointer to the first item in the array, then converts array index expressions into the equivalent pointer arithmetic. An expression like myArray[2] is converted to *(myArray + 2), or a pointer to the third item in the array. (Remember that the first item is myArray[0].)

While this is a very convenient way to work with low level memory in a structured way, it can also be very dangerous. The compiler won't stop you from accessing items past the end of your array. You can easily and efficiently read memory that may contain garbage values and overwrite memory belonging to other parts of your program. As with many things in C, with great power comes great responsibility.

Calculating the length of an array
The sizeof operator can be applied to an array variable to find out how many bytes of memory the array occupies.
// size of an array in bytes
int lotteryNumbers[6] = { 7, 11, 19, 23, 29, 31 };

NSLog(@"The array uses %lu bytes", sizeof lotteryNumbers);
This produces:
The lotteryNumbers array uses 24 bytes
ints in iOS use four bytes each, so an array of six ints uses 24 bytes. (The sizeof operator returns a value of type size_t, an unsigned long integer type.) To get the number of items the array contains, you can divide the size of the array by the size of its first item:
// size of an array in bytes
int lotteryNumbers[6] = { 7, 11, 19, 23, 29, 31 };

size_t length = sizeof lotteryNumbers / sizeof lotteryNumbers[0];
NSLog(@"The array contains %lu items", length);

Be careful to only use this on actual array variables—you won't get the answer you expect if you try this on a pointer.

C arrays have one big limitation: you can't resize them. We'll talk about using dynamically allocated memory blocks as arrays next time.

If you're ready for a safer, higher level way to manage an ordered sequence of items, it's time to get to know NSArray.

You can create an NSArray containing one item using +arrayWithObject: or -initWithObject:
// creating an NSArray with one item
NSArray *colors = [NSArray arrayWithObject:@"red"];
NSArray *flavors = [[NSArray alloc] initWithObject:@"vanilla"];
NSArray creation methods follow the common Cocoa and Cocoa Touch conventions. Class methods like +arrayWithObject: return a new autoreleased object. If you need to hold on to the object beyond the current method, remember to call -retain on it. Instance methods like -initWithObject: produce new objects that you own—don't forget to call -release or -autorelease on the object when you're done with it.

Sometimes an array containing one item is handy, but usually you want to hold onto multiple items. To do that, use +arrayWithObjects: or -initWithObjects::
// creating an NSArray with multiple items
NSArray *colors = [NSArray arrayWithObjects:@"red", 
NSArray *flavors = [[NSArray alloc] initWithObjects:@"vanilla", 
The +arrayWithObjects: or -initWithObjects: methods take a variable number of arguments, but have a special caveat: you must mark the end of the list with nil. If you forget the nil, your program will probably crash with an EXC_BAD_ACCESS error as it tries to add random memory locations to the NSArray. Fortunately, the LLVM 2.0 compiler in Xcode 4.0 will warn you if you forget the nil. Always pay attention to compiler warnings!

If you have a plain old C array of object pointers, you can use the +arrayWithObjects:count: or -initWithObjects:count methods to create an NSArray from the C array.
// creating an NSArray from a C array
NSString *colors1[] = { @"red", @"green", @"blue" };
NSArray *colors2 = [NSArray arrayWithObjects:colors1 count:3];

NSString *flavors1[] = { @"vanilla", @"chocolate", @"strawberry" };
NSArray *flavors2 = [[NSArray alloc] initWithObjects:flavors1 count:3];

Accessing an item in an array is done with the -objectAtIndex: method.
// my favorite color is green
NSArray *colors = [NSArray arrayWithObjects:@"red", 

NSLog(@"My favorite color is %@", [colors objectAtIndex:1]);
You can ask an NSArray object how many items it contains using the -count method.
NSArray *favoriteColors = [NSArray arrayWithObject:@"green"];
NSArray *favoriteFlavors = [NSArray arrayWithObjects:@"vanilla", @"chocolate", nil];

NSLog(@"I have %u favorite color(s) and %u favorite flavor(s)", 
      [favoriteColors count], [favoriteFlavors count]);

Only for objects, but heterogeneous
NSArray has one big limitation: it can only contain object types. If you try to create an NSArray of ints or a similar primitive C type, you'll get a warning like "Incompatible integer to pointer conversion sending 'int' to parameter of type 'id'". If you need to store numbers in an NSArray, you can store NSNumber objects instead.
// wrap primitive types in objects to store them in an NSArray
NSNumber *one = [NSNumber numberWithInt:1];
NSNumber *pi = [NSNumber numberWithDouble:3.14];
NSDate *today = [NSDate date];
NSString *foo = [NSString stringWithContentsOfCString:"foo" encoding:NSUTF8Encoding];

NSArray *myStuff = [NSArray arrayWithObjects:one, pi, today, foo, nil];
This example shows an interesting characteristic of NSArrays: they can hold items of many different object types in a single container. While occasionally this feature is useful, more often than not you'll only store items of one type in a given NSArray, and errors related to finding an unexpected type in your NSArrays are pretty rare.

NSArrays are immutable
Like plain old C arrays, once you create an NSArray, you can't change its size. But NSArrays are even more restrictive; you can't change the contents either. NSArrays are immutable. This is something of a pain in the rump, but it means that you can safely share an NSArray between threads, as long as the items in it are also immutable.

Next time, we'll look at using memory blocks as resizable C arrays, and NSArray's more flexible cousin, NSMutableArray.

No comments: