Hacker News Reader

Comment by paupino_masano | Hacker News Reader

I think this is a great article to refresh your knowledge as to how the underlying data structures actually work.

My only nitpick is ignoring the capacity variable in initWithCapacity. Really, a simple allocation of memory here and setting the _capacity variable is all that's needed. It IS an important implementation to write - especially if you know you're going to be working with a large array size right from the get go to avoid the memory copies.

But otherwise - I enjoyed that. I think I may just start following his blog to refresh my knowledge with other data structures!

View on HN

Make sure you follow the link to http://ridiculousfish.com/blog/posts/array.html. It tells you that, in this case, this is not how the "underlying data structures actually work".

This NSMutableArray subclass has O(1) access, as one expects from an array. NSMutableArray itself, however, only guarantees O(log n).

Underlining the fact that NSMutableArray may ignore your capacity hint is also important, though. Many people make false assumptions about how NSMutableArray manages memory.

The Cocoa documentation does not seem to suggest that the numItems parameter of the initWithCapacity message is in any way optionally handled by the runtime. It repeatedly states that the array will be initialised "with enough memory to hold numItems objects" in no uncertain language. It does not imply in any way that it is merely a hint. If the implementation behaves differently, that's either a problem with the documentation or the implementation, not with people's assumptions.

Interesting! You're right that it says that now. Thanks for the correction.

I'm nearly positive that the wording used to be much more vague on that point, as I remember thinking in my early days that it was so fuzzy as to be nearly pointless to go out of your way to give an accurate capacity. Mike is an old-time Cocoa guy, so if my memory is serving me well, he was probably thinking of the same old wording.

I too thought it was fuzzy. In fact, I'm still reasonably sure that the implementation still doesn't actually guarantee it reserves that space, despite how the documentation is now worded, although I am not an authority on this subject. It might be interesting to check out the CFArray implementation on opensource.apple.com and see what that does (although CFMutableArray treats capacity a bit differently than NSMutableArray to begin with).

I wonder just what such a guarantee means in an API contract, since there's no way whatsoever to actually check on that behavior from the outside.

Reply on news.ycombinator.com