Objective-C sparse array redux

First off, I've seen this, but it doesn't quite seem to suit my needs.

I've got a situation where I need a sparse array. Some situations where I could have, say 3000 potential entries with only 20 allocated, other situations where I could have most or all of the 3000 al开发者_运维问答located. Using an NSMutableDictionary (with NSString representations of the integer index values) would appear to work well for the first case, but would seemingly be inefficient for the second, both in storage and lookup speed. Using an NSMutableArray with NSNull objects for the empty entries would work fairly well for the second case, but it seems a bit wasteful (and it could produce an annoying delay at the UI) to insert most of 3000 NSNull entries for the first case.

The referenced article mentions using an NSMapTable, since it supposedly allows integer keys, but apparently that class is not available on iPhone (and I'm not sure I like having an object that doesn't retain, either).

So, is there another option?

Added 9/22

I've been looking at a custom class that embeds an NSMutableSet, with set entries consisting of a custom class with integer (ie, element#) and element pointer, and written to mimic an NSMutableArray in terms of adds/updates/finds (but not inserts/removals). This seems to be the most reasonable approach.

A NSMutableDictionary probably will not be slow, dictionaries generally use hashing and are rather fast, bench mark.

Another option is a C array of pointers. Allocation a large array only allocates virtual memory until the real memory is accessed (cure calloc, not malloc, memset). The downside is that memory is allocated in 4KB pages which can be wasteful for small numbers of entries, for large numbers of entries many may fall in the same page.

What about CFDictionary (or actually CFMutableDictionary)? In the documentation, it says that you can use any C data type as a key, so perhaps that would be closer to what you need?

I've got the custom class going and it works pretty well so far. It's 322 lines of code in the h+m files, including the inner class stuff, a lot of blank lines, comments, description formatter (currently giving me more trouble than anything else) and some LRU management code unrelated to the basic concept. Performance-wise it seems to be working faster than another scheme I had that only allowed "sparseness" on the tail end, presumably because I was able to eliminate a lot of special-case logic.

One nice thing about the approach was that I could make much of the API identical to NSMutableArray, so I only needed to change maybe 25% of the lines that somehow reference the class.

I also needed a sparse array and have put mine on git hub. If you need a sparse array feel free to grab https://github.com/LavaSlider/DSSparseArray