Cocoa's NSDictionary: why are keys copied?

Question

All objects used as keys in NS(Mutable)Dictionaries must support the NSCopying protocol, and those objects are copied when they're used in the dictionary.

I frequently want to use heavier weight objects as keys, simply to map one object to another. What I really mean when I do that is effectively:

[dictionary setObject:someObject forKey:[NSValue valueWithPointer:keyObject]];

("When I come back and hand you this same key object instance again, get me that same value out.")

...which is exactly what I end up doing to get around this design sometimes. (Yes, I know about NSMapTable in desktop Cocoa; but e.g. iPhone doesn't support this.)

But what I don't really get is why copying the key is necessary or desirable in the first place. What does it buy the implementation or caller?

Gavelkind

Answer 1

The copy ensures that the values used as keys don't change "underhand" while being used as keys. Consider the example of a mutable string:

NSMutableString* key = ... 
NSMutableDictionary* dict = [[NSMutableDictionary alloc] init];

[dict setObject: ... forKey: key];

Let's assume that the dictionary did not copy the key, but instead just retained it. If now, at some later point, the original string is modified, then it is very likely that you are not going to find your stored value in the dictionary again even if you use the very same key object (i.e., the one key points to in the example above).

In order to protect yourself against such a mistake, the dictionary copies all keys.

Note, by the way, that it is simple enough to define -copyWithZone: as just doing return [self retain]. This is allowed and good code if your object is immutable, and the NSCopying contract is specifically designed such that the object returned has to be (sorta, kinda) immutable:

Implement NSCopying by retaining the original instead of creating a new copy when the class and its contents are immutable.

(from NSCopying Reference)

and

The copy returned is immutable if the consideration “immutable vs. mutable” applies to the receiving object; otherwise the exact nature of the copy is determined by the class.

(from -copyWithZone: Reference)

Even if your objects are not immutable, you might get away with that implementation if you only ever use identity-based equality/hash implementations, i.e., implementations which are not affected in any way by the object's internal state.

Gualtiero

Dirk: Thank you for this. I think the critical fact I was misunderstanding (that your answer led me to) was that the semantics of the key are not about the key object ref; they're about the contents of the key (so that the key is the string "foo", whether it's from a literal, constructed from chars, whatever)-- this implies a semantic compare, not a pointer one. But keys must then be copied because mutable keys could change. Where this leaves me is that when I really want to use an object for a key, and I'm really after the reference equality, my approach is not a hack; it's exactly right. – Gavelkind

Ben: Not quite. If you want keyObject to be retained, that code won't do it, since it treats keyObject as a pointer to anything, not necessarily an object, so it has no way of knowing that it could retain it. I'm not sure that value:withObjCType: would retain, either, even if passed @encode(id). To be absolutely sure it's retaining your keys, you'll need to either use NSMapTable (you imply that you can't do this because you're developing for iPhone), use CFDictionary instead of NSDictionary (everywhere you use the dict, not just at its creation), or make your own NSValue subclass. – Wadlinger

Good point. Thanks for the extra info. As I think about it, I never do need keys to be retained when I'm using this pattern. Usually some other collection actually "owns" the objects I'm using as keys; I'm just using the dictionary to map them efficiently to some other related object. The worst case is that the key object would get dealloc'd, leaving a turd entry in the dictionary. The only thing I'd have to be careful of is enumerating the actual keys and turning the pointers back into ids. But that code smells bad enough to know that you're doing something dangerous... – Gavelkind

Answer 2

If you want to store pointers as keys then you'll need to wrap them in a NSValue object with +valueWithPointer:.

Copalite

Correct me if I'm wrong, but when I tried to implement this it didn't work because the object my pointer referenced was released by the time I wanted to access it. I used +valueWithNonretainedObject: instead. – Cantata

Answer 3

Since iOS 6 if you want to use pointers as keys, you can use the NSMapTable object, see http://nshipster.com/nshashtable-and-nsmaptable/

You can specify whether keys and/or values are stongly or weakly held:

NSMapTable *mapTable = [NSMapTable mapTableWithKeyOptions:NSMapTableStrongMemory
                                         valueOptions:NSMapTableWeakMemory];

Another option that could be appropriate sometimes is to use NSCache, which holds keys strongly and is actually thread-safe.

Pappano