The motivating problem was the straightforward maintenance of a High Scores table for an arcade-style game, which has names of players (keys), and scores (values). This sort of table is also typically displayed in ascending order of values. And thus, OrderedMutableDictionary was born.

OrderedMutableDictionary.h

#import <Foundation/Foundation.h>

//  An OrderedMutableDictionary maps keys/values through the use of
//  NSMutableArrays.  The main benefit of this is that you can iterate
//  the dictionary in the order elements were added to it, as opposed
//  to an alternate ordering scheme.  
//
//  Copyright © 2013 Rogelio E. Cardona-Rivera <[email protected]>
//  This work is free. You can redistribute it and/or modify it under the
//  terms of the Do What The Fuck You Want To Public License, Version 2,
//  as published by Sam Hocevar. See http://www.wtfpl.net/ for more details.
//
@interface OrderedMutableDictionary : NSMutableDictionary
{
    NSMutableArray* _keys;
    NSMutableArray* _values;
}

// Returns an enumerator over the collection of values in |_dictionary|.
// Order is determined by order in which key/value pairs were added.
- (NSEnumerator *)valueEnumerator;

// Returns an enumerator over the collection of keys in |_dictionary|.
// Keys will be ordered according to the order of values as determined
// by [self valueEnumerator].
- (NSEnumerator *)keyEnumerator;

@end

OrderedMutableDictionary.m

#import "OrderedMutableDictionary.h"

//  Copyright © 2013 Rogelio E. Cardona-Rivera <[email protected]>
//  This work is free. You can redistribute it and/or modify it under the
//  terms of the Do What The Fuck You Want To Public License, Version 2,
//  as published by Sam Hocevar. See http://www.wtfpl.net/ for more details.
//
@implementation OrderedMutableDictionary

- (id)init
{
    return [self initWithCapacity:0];
}

- (id)initWithCapacity:(NSUInteger)numItems
{
    if ((self = [super init])) 
    {
        _keys   = [[[NSMutableArray alloc] initWithCapacity:numItems] retain];
        _values = [[[NSMutableArray alloc] initWithCapacity:numItems] retain];
    }
    
    return self;
}

- (void)dealloc
{
    [_keys release];
    [_values release];
    
    _keys = nil;
    _values = nil;
    
    [super dealloc];
}

- (id)copy
{
    return [self mutableCopy];
}

- (NSEnumerator *)valueEnumerator
{
    return [_values objectEnumerator];
}

#pragma mark NSDictionary Overriden Primitive Methods
- (id)initWithObjects:(NSArray *)objects forKeys:(NSArray *)keys
{
    return self;
}

- (NSUInteger)count
{
    return [_values count];
}

- (id)objectForKey:(id)aKey
{
    if ([_keys containsObject:aKey]) 
    {
        NSUInteger indexForValue = [_keys indexOfObject:aKey];
        return [_values objectAtIndex:indexForValue];
    }
    
    return nil;
}

- (NSEnumerator *)keyEnumerator
{
    return [_keys objectEnumerator];
}


#pragma mark NSMutableDictionary Overriden Primitive Methods
- (void)setObject:(id)anObject forKey:(id)aKey
{
    if (![_keys containsObject:aKey]) 
    {
        [_keys addObject:aKey];
        [_values addObject:anObject];
    }
}

- (void)removeObjectForKey:(id)aKey
{
    if ([_keys containsObject:aKey]) 
    {
        id objToRemove = [self objectForKey:aKey];
        [_keys removeObject:aKey];
        [_values removeObject:objToRemove];
    }
}


@end