NSDictionary with ordered keys

Question

I have an NSDictionary (stored in a plist) that I'm basically using as an associative array (strings as keys and values). I want to use the array of keys as part of my application, but I'd like them to be in a specific order (not really an order that I can write an algorithm to sort them into). I could always store a separate array of the keys, but that seems kind of kludgey because I'd always have to update the keys of the dictionary as well as the values of the array, and make sure they always correspond. Currently I just use [myDictionary allKeys], but obviously this returns them in an arbitrary, non-guaranteed order. Is there a data structure in Objective-C that I'm missing? Does anyone have any suggestions on how to more elegantly do this?

Solution 1

The solution of having an associated NSMutableArray of keys isn't so bad. It avoids subclassing NSDictionary, and if you are careful with writing accessors, it shouldn't be too hard to keep synchronised.

Solution 2

I'm late to the game with an actual answer, but you might be interested to investigate CHOrderedDictionary. It's a subclass of NSMutableDictionary which encapsulates another structure for maintaining key ordering. (It's part of CHDataStructures.framework.) I find it to be more convenient than managing a dictionary and array separately.

Disclosure: This is open-source code which I wrote. Just hoping it may be useful to others facing this problem.

Solution 3

There is no such inbuilt method from which you can acquire this. But a simple logic work for you. You can simply add few numeric text in front of each key while you prepare the dictionary. Like

NSDictionary *dict = [[NSDictionary alloc] initWithObjectsAndKeys:
                       @"01.Created",@"cre",
                       @"02.Being Assigned",@"bea",
                       @"03.Rejected",@"rej",
                       @"04.Assigned",@"ass",
                       @"05.Scheduled",@"sch",
                       @"06.En Route",@"inr",
                       @"07.On Job Site",@"ojs",
                       @"08.In Progress",@"inp",
                       @"09.On Hold",@"onh",
                       @"10.Completed",@"com",
                       @"11.Closed",@"clo",
                       @"12.Cancelled", @"can",
                       nil]; 

Now if you can use sortingArrayUsingSelector while getting all keys in the same order as you place.

NSArray *arr =  [[dict allKeys] sortedArrayUsingSelector:@selector(localizedStandardCompare:)];

At the place where you want to display keys in UIView, just chop off the front 3 character.

Solution 4

If you're going to subclass NSDictionary you need to implement these methods as a minimum:

• NSDictionary
  • -count
  • -objectForKey:
  • -keyEnumerator
• NSMutableDictionary
  • -removeObjectForKey:
  • -setObject:forKey:
• NSCopying/NSMutableCopying
  • -copyWithZone:
  • -mutableCopyWithZone:
• NSCoding
  • -encodeWithCoder:
  • -initWithCoder:
• NSFastEnumeration (for Leopard)
  • -countByEnumeratingWithState:objects:count:

The easiest way to do what you want is to make a subclass of NSMutableDictionary that contains its' own NSMutableDictionary that it manipulates and an NSMutableArray to store an ordered set of keys.

If you're never going to encode your objects you could conceivable skip implementing -encodeWithCoder: and -initWithCoder:

All of your method implementations in the 10 methods above would then either go directly through your hosted dictionary or your ordered key array.

Solution 5

My little addition: sorting by numeric key (Using shorthand notations for smaller code)

// the resorted result array
NSMutableArray *result = [NSMutableArray new];
// the source dictionary - keys may be Ux timestamps (as integer, wrapped in NSNumber)
NSDictionary *dict =
@{
  @0: @"a",
  @3: @"d",
  @1: @"b",
  @2: @"c"
};

{// do the sorting to result
    NSArray *arr = [[dict allKeys] sortedArrayUsingSelector:@selector(compare:)];

    for (NSNumber *n in arr)
        [result addObject:dict[n]];
}

View more solutions

Comments

[Quinn Taylor]

One pitfall is that NS(Mutable)Dictionary makes copies of keys, so the objects in the key array will be different. This can be problematic if a key is mutated.

[Abizern]

That's a good point, but mitigated if the mutability is restricted to adding and removing object from the array rather than changing the items within them.

[Quinn Taylor]

Not sure how you'd restrict someone modifying a key for which they provided a pointer in the first place. The array just stores a pointer to that key, and won't know if it changes or not. If the key is changed, you may not even be able to remove the added entry from the array at all, which can be a real synchronization problem if you array keeps keys that are no longer in the dictionary, or vice versa... :-)

[Quinn Taylor]

BTW, my apologies if I sound overly critical. I've been dealing with this same problem myself, but since it's for a framework, I'm trying to design it to be robust and correct in every conceivable situation. You're correct that a separate array isn't so bad, but it's not as simple as a class that tracks it for you. Plus, there are numerous benefits if such a class extends NS(Mutable)Dictionary, since it could be used anywhere a Cocoa dictionary is required.

[Abizern]

I don't mind the discussion. My suggestion was just a workaround. Writing a framework is a different proposition entirely and it is something that needs careful thought. Personally, I find mutability troublesome for this very reason, and I try to minimise the use of those classes in my own programs.

[Ben Zotto]

@Quinn Taylor: Late to the party here, but couldn't you avoid this problem by having your mutable array for keys also copy the key object before inserting it, just as the dictionary does?

[Quinn Taylor]

Not really, because then you'd have two different copies (different pointers) in the dictionary and array. What you want is to store the same pointer in both collections, so you can accurately find and/or remove objects which have been added, and which might have been mutated subsequently. Otherwise, the object might be removed from the dictionary but not the array, or vice versa

[Ben Zotto]

@Quinn Taylor: You can't mutate the key object in the dictionary-- that's why it copies the key to begin with; you no longer own it after setting it. The comparisons for existence in the dictionary are not based on a pointer compare. You should therefore be able to copy the key into your dictionary and build the correct semantics around it.

[Ben Zotto]

"copy the key into your array..."

[whitneyland]

+1 - Haven't tried it yet but looked through the docs and it seems you've done some nice work here. I think it's a little embarrassing Apple is missing so many of these fundamentals.

[Quinn Taylor]

I don't think it's embarrassing, it's just a question of how they want their framework to develop. Specifically, new classes have to add a lot of value to be considered for inclusion in Foundation. It's not that complicated to pair a dictionary with a sorted array of keys, and Apple tries to contain the size (and maintainability) of the framework by not going overboard with stuff that some people might use.

[whitneyland]

It's not just that an ordered dictionary is missing, it's that so many useful CS101 collections are missing. I don't believe Objective-C would be a widely successful language without Apple, as opposed to C, C++, Java, C#, which have proved successful many times outside the purview of their creators.

[Dev Kanchen]

This. Is. Awesome. Shame I hadn't discovered this framework until now. This is gonna be a mainstay in most of the future projects. Thanks a LOT!

[user1046037]

if the key is an NSString, would it be a problem to do the following ? create a dictionary as well as an array and have a common method to add and remove the data. Array contains list of NSString keys (in the desired order) Dictionary contains the NSString keys and the values

[Alex Zavatone]

What about sortedArrayUsingSelector for the array order? developer.apple.com/library/ios/documentation/cocoa/Conceptu‌​al/…

[Leon]

This shows how to remove the first three characters: stackoverflow.com/questions/1073872/…

[Quinn Taylor]

Thanks for updating the links in my answer, @Dolbz! Perfectly done.

[Dolbz]

And thanks for the library @QuinnTaylor It makes what I was doing a lot cleaner 👍

[Motti Shneor]

Reading your Obj-C implementation, made me wonder - don't you lose the basic performance characteristics of an NSDictionary here? you search for items one-by-one, instead of using the hash? I think much better implementation is possible.

[Motti Shneor]

but why store the original key pointer in your array, why not obtain the copied key from the NSDictionary, and store (refcount) that in your array?

[Cœur]

@MottiShneor The "search" isn't part of the implementation of MutableOrderedDictionary. It was only an example usage of it for alphabetical key sorting: feel free to use your ordered dictionary in any other way you need.