Is Cocoa's NSMutableArray sparse?

If I create an NSMutableArray开发者_C百科 that might have up to 2^16 elements, but will mostly be empty, will I be wasting space or is NSMutableArray implemented as a sparse array?

Elements in an NSArray can't be empty and there's no "default" value. To represent nil, you'd usually use the singleton [NSNull null], which is still a reference to an object so it consumes memory (the pointer). I'd consider using NSDictionary (or NSMutableDictionary) with numeric (NSNumber) keys instead.

No neither NSArray nor NSMutableArray are sparse arrays. If you have an array with 5000 entries with everything except 4999 set to [NSNull null] it is still taking the space of 5000 entries.

Similarly, an NSPointerArray will have the space for 5000 entries with all the entries NULL except index 4999.

I developed a sparse array object using an NSMutableDictionary as described by OMZ. With this there is only space for the one entry. This space, however, holds both the index and object, and there is the overhead of converting the index values to NSNumbers. So although they can be used anyplace an NSArray or NSMutableArray can be there would be a performance penalty. This is a classic speed / space tradeoff.

See https://github.com/LavaSlider/DSSparseArray

An NSArray object is static (or immutable) in the sense that it must be populated at the moment you create it, either by using -initWithObjects, +arrayWithObjects, or by using the contents of an already existing array with -initWithArray, etc. You cannot add objects later on.

There is a concrete mutable subclass (called NSMutableArray) which allows for adding and removing objects dynamically as needed. However when you initialize it in an empty state (either by -initWithCapacity: or +arrayWithCapacity:) what you specify as the initial length is just a hint (the array is created with enough memory to hold that number of objects), howerver it can be expanded as necessary. So yes, in this case, it'll be a sparse array.

Best,