Welcome back to Objective-C Tuesdays. Last time we were talking about
dynamic arrays in C and NSMutableArray in Objective-C. We'll continue looking at both today.
We looked at using
malloc() or
calloc() to dynamically allocate a block of memory that you can treat like an array. This is very useful when you don't know the number of items you need to store until run time or when you need the array to exist longer than the current function call.
But what happens when you need to grow or shrink the memory block? Well, the straightforward way would be to allocate a new memory block, copy over the contents and free the old block. You use the
memcpy() function in the C standard library to do the copying.
// resizing a memory blockint *lotteryNumbers = malloc(sizeof(int) * 6);if ( ! lotteryNumbers) { // memory allocation failed exit(EXIT_FAILURE);}lotteryNumbers[0] = 7;// ...lotteryNumbers[5] = 29;// now we need to store more numbers// so allocate a bigger memory blockint *biggerMemoryBlock = malloc(sizeof(int) * 12);if ( ! biggerMemoryBlock) { // memory allocation failed exit(EXIT_FAILURE);}// copy lotteryNumbers into biggerMemoryBlockmemcpy(biggerMemoryBlock, lotteryNumbers, sizeof(int) * 6);// free old memory blockfree(lotteryNumbers);// replace old memory block pointer with new onelotteryNumbers = biggerMemoryBlock;lotteryNumbers[6] = 31;// ...lotteryNumbers[11] = 49;When copying blocks of memory, be careful to specify the correct size in bytes. In the example above, we use the same expression to calculate the size,
sizeof(int) * 6 for both the original call to
malloc() and to
memcpy(). Using the
sizeof operator like this serves two purposes. It makes the code portable, since the size of an
int may be different on some systems (it's four bytes on iOS). More importantly, it tells anyone reading the code that you intended to allocate six
ints. If you had specified simply
malloc(24) or even
malloc(6 * 4), your intention is not as clear.
Resizing a memory block with realloc()Allocating a larger or smaller memory block and copying over the contents works perfectly, but it is tedious. Fortunately, the C standard library includes the
realloc() function which does exactly this for you in one function call. It can operate on any memory block allocated with
malloc() or
calloc(). In addition, because it's part of the standard library,
realloc() can do things that you can't: it will try to grow or shrink the memory block in place, skipping the copy step. Sometimes the memory manager will give you a block of memory somewhat bigger than you requested, other times the memory area after your memory block is currently unused. Because
realloc() is privy to the implementation details of the memory manager, it can figure out when it's safe to grow your memory block in place.
The
realloc() function returns a pointer to either the original memory block or a new memory block on success, or
NULL if memory allocation fails. If the new memory block is bigger than the original, the new items will be set to zero, just as if you allocated the memory block with
calloc(). Like
malloc(),
realloc() requires you to calculate the size of the memory block in bytes.
// using realloc()int *lotteryNumbers = malloc(sizeof(int) * 2);if ( ! lotteryNumbers) { // out of memory exit(EXIT_FAILURE);}lotteryNumbers[0] = 7;lotteryNumbers[1] = 11;// ...int *resizedLotteryNumbers = realloc(lotteryNumbers, sizeof(int) * 6);if ( ! resizedLotteryNumbers) { // out of memory but lotteryNumbers memory block // is still valid and unchanged exit(EXIT_FAILURE);}// replace the old pointer with the new onelotteryNumbers = resizedLotteryNumbers;lotteryNumbers[2] = 19;// ...If
realloc() fails, it leaves the original memory block unchanged. Just as for
calloc() and
malloc(), you must remember to call
free() on the memory block when you're done with it.
Inserting items into a C arrayIt should be obvious by now how to add items to the end of a C array (if it's big enough) or a dynamically allocated memory block that you've enlarged using
realloc(). But how do you insert an item at the beginning or middle of an array while keeping all of the current items? There's no magic here, you have to shift items to higher indices to make space for the new one.
// insert an item at the start of a C arrayint lotteryNumbers[6] = { 11, 17 }; // has room for six items// shift current items uplotteryNumbers[2] = lotteryNumbers[1];lotteryNumbers[1] = lotteryNumbers[0];// array now holds { 11, 11, 17 }lotteryNumbers[0] = 7; // insert new item// array now holds { 7, 11, 17 }Note that you need to shift items starting at the end of the array, otherwise you'll overwrite items you want to preserve. Obviously writing a line of code for each item you need to shift isn't a practical solution. You might be tempted to use the
memcpy() function to shift items, but
memcpy() has an important restriction: the source and destination memory blocks may not overlap. (This is because
memcpy() may copy items front to back and thus overwrite items you want to preserve.) The
memmove() function is meant to be used when the memory blocks overlap and will always shift items in the correct order to preserve the contents.
// using memmove() to insert an itemint lotteryNumbers[6] = { 11, 17 }; // has room for six items// shift current items upint *destination = lotteryNumbers + 1;int *source = lotteryNumbers;size_t size = sizeof(int) * 2;memmove(destination, source, size);// array now holds { 11, 11, 17 }lotteryNumbers[0] = 7; // insert new item// array now holds { 7, 11, 17 }Because
memmove() can operate on any kind of array or memory block, we need to do some pointer arithmetic to determine the source and destination addresses and the number of bytes to move. Again, the
sizeof operator helps make our intentions clear. An alternate way specify the source and destination addresses is to use the address of operator (
&) on indexed items in the array.
// determine source and destination using address of// ...int *destination = &lotteryNumbers[1];int *source = &lotteryNumbers[0];size_t size = sizeof(int) * 2;memmove(destination, source, size);// array now holds { 11, 11, 17 }// ...These are equivalent notations and choosing one over the other is a matter of style.
You can use this technique to insert items into both C arrays and dynamically allocated memory blocks. Just make sure that there is enough space to move items around and that you don't write items past the end of your array or memory. As with all things in C, there is no safety net. To remove items from the beginning or middle of an array, follow the same procedure using
memmove(), only shift items down and intentionally overwrite the items you want to delete. I'll leave this one as an exercise for the reader ☺.
Inserting items into an NSMutableArrayWhile using
memmove() to shift items around isn't
too terrible, the equivalent operations using
NSMutableArray are naturally much more direct. To insert a single item at a particular index, you naturally use
-insertObject:atIndex:// inserting an item into an NSMutableArrayNSMutableArray *colors = [NSMutableArray arrayWithObjects:@"red", @"green", @"blue", nil];[colors insertObject:@"orange" atIndex:1];// colors now holds "red", "orange", "green" and "blue"
Inserting multiple items at one time is trickier. With the
-insertObjects:atIndexes: method, you can insert items from an
NSArray into your
NSMutableArray. The tricky part here is that you need to also pass in an
NSIndexSet (or
NSMutableIndexSet) along with the array. Here's how you would insert an
NSArray containing one item.
// inserting an item into an NSMutableArrayNSMutableArray *colors = [NSMutableArray arrayWithObjects:@"red", @"green", @"blue", nil];NSArray *newColors = [NSArray arrayWithObject:@"orange"];NSIndexSet *indexSet = [NSIndexSet indexSetWithIndex:1];[colors insertObjects:newColors atIndexes:indexSet];// colors now holds "red", "orange", "green" and "blue"
You must make sure that there is an index in the
NSIndexSet for each item you are inserting. If you want to insert the new items all in one spot, the
+indexSetWithIndexesInRange: method of
NSIndexSet makes this easy.
// inserting multiple items into an NSMutableArrayNSMutableArray *colors = [NSMutableArray arrayWithObjects:@"red", @"green", @"blue", nil];NSArray *rainbowColors = [NSArray arrayWithObjects:@"orange", @"yellow", @"indigo", @"violet", nil];NSIndexSet *indexSet = [NSIndexSet indexSetWithIndexesInRange:NSMakeRange(1, 4)];[colors insertObjects:rainbowColors atIndexes:indexSet];// colors now holds "red", "orange", "yellow", "indigo", "violet", "green" and "blue"
Sometimes you want to insert different items at different points in your
NSMutableArray. This is where
-insertObjects:atIndexes: really shines. You'll want to use
NSMutableIndexSet to create the index set in this case. Lets modify the previous example to insert the colors in standard rainbow order.
// inserting multiple items into an NSMutableArrayNSMutableArray *colors = [NSMutableArray arrayWithObjects:@"red", @"green", @"blue", nil];NSArray *rainbowColors = [NSArray arrayWithObjects:@"orange", @"yellow", @"indigo", @"violet", nil];NSMutableIndexSet *indexSet = [NSMutableIndexSet indexSet];[indexSet addIndex:1];[indexSet addIndex:2];[indexSet addIndex:5];[indexSet addIndex:6];[colors insertObjects:rainbowColors atIndexes:indexSet];// colors now holds "red", "orange", "yellow", "green", "blue", "indigo" and "violet"
To figure out the correct indices can be tricky. Inside the
-insertObjects:atIndexes: method, new items will be inserted one at a time, starting with the lowest index in the index set. While inserting a group of items is a very powerful capability of
NSMutableArray, often times I think it's easier and faster to write correct code that uses
-subarrayWithRange: to break the items up into contiguous blocks before inserting them, or even to use
-insertObject:atIndex: repeatedly to insert items one by one. But when it is straightforward to figure out the index set,
-insertObjects:atIndexes: makes your code very succinct.
Next time, we'll look at
sorting C arrays, NSArrays and NSMutableArrays.
Posts
