Naming a dictionary structure that stores keys in

Question

Note: Although my particular context is Objective-C, my question actually transcends programming language choice. Also, I tagged it as "subjective" since someone is bound to complain otherwise, but I personally think it's almost entirely objective. Also, I'm aware of this related SO question, but since this was a bigger issue, I thought it better to make this a separate question. Please don't criticize the question without reading and understanding it fully. Thanks!

Most of us are familiar with the dictionary abstract data type that stores key-value associations, whether we call it a map, dictionary, associative array, hash, etc. depending on our language of choice. A simple definition of a dictionary can be summarized by three properties:

1. Values are accessed by key (as opposed to by index, like an array).
2. Each key is associated with a value.
3. Each key must be unique.

Any other properties are arguably conveniences or specializations for a particular purpose. For example, some languages (especially scripting languages such as PHP and Python) blur the line between dictionaries and arrays and do provide ordering for dictionaries. As useful as this can be, such additions are not a fundamental characteristics of a dictionary. In a pure sense, the actual implementation details of a dictionary are irrelevant.

For my question, the most important observation is that the order in which keys are enumerated is not defined — a dictionary may provide keys in whatever order it finds most convenient, and it is up to the client to organize them as desired.

I've created custom dictionaries that impose specific key orderings, including natural sorted order (based on object comparisons) and insertion order. It's obvious to name the former some variant on SortedDictionary (which I've actually already implemented), but the latter is more problematic. I've seen LinkedHashMap and LinkedMap (Java), OrderedDictionary (.NET), OrderedDictionary (Flash), OrderedDict (Python), and OrderedDictionary (Objective-C). Some of these are more mature, some are more proof-of-concept.

LinkedHashMap is named according to implementation in the tradition of Java collections — "linked" because it uses a doubly-linked list to track insertion order, and "hash" because it subclasses HashMap. Besides the fact that user shouldn't need to worry about that, the class name doesn't really even indicate what it does. Using ordered seems like the consensus among existing code, but web searches on this topic also revealed understandable confusion between "ordered" and "sorted", and I feel the same. The .NET implementation even has a comment about the apparent misnomer, and suggests that it should be "IndexedDictionary" instead, owing to the fact that you can retrieve and insert objects at a specific point in the ordering.

I'm designing a framework and APIs and I want to name the class as intelligently as possible. From my standpoint, indexed would probably work (depending on how people interpret it, and based on the advertised functionality of the dictionary), ordered is imprecise and has too much potential for confusion, and linked "is right out" (apologies to Monty Python). ;-)

As a user, what name would make the most sense to you? Is there a particular name that says exactly what the class does? (I'm not averse to using slightly longer names like InsertionOrderDictionary if appropriate.)

Edit: Another strong possibility (discussed in my answer below) is IndexedDictionary. I don't really like "insertion order" because it doesn't make sense if you allow the user to insert keys at a specific index, reorder the keys, etc.

Answer 1

I vote OrderedDictionary, for the following reasons:

"Indexed" is never used in Cocoa classes, except in one instance. It always appears as a noun (NSIndexSet, NSIndexPath, objectAtIndex:, etc). There is only one instance when "Index" appears as a verb, which is on NSPropertyDescription's "indexed" property: isIndexed and setIndexed. NSPropertyDescription is roughly analogous to a table column in a database, where "indexing" refers to optimizing to speed up search times. It would therefore make sense that with NSPropertyDescription being part of the Core Data framework, that "isIndexed" and "setIndexed" would be equivalent to an index in a SQL database. Therefore, to call it "IndexedDictionary" would seem redundant, since indices in databases are created to speed up lookup time, but a dictionary already has O(1) lookup time. However, to call it "IndexDictionary" would also be a misnomer, since an "index" in Cocoa refers to position, not order. The two are semantically different.

I understand your concern over "OrderedDictionary", but the precedent has already been set in Cocoa. When users want to maintain a specific sequence, they use "ordered": -[NSApplication orderedDocuments], -[NSWindow orderedIndex], -[NSApplication orderedWindows], etc. So, John Pirie has mostly the right idea.

However, you don't want to make insertion into the dictionary a burden on your users. They'll want to create a dictionary once and then have it maintain an appropriate order. They won't even want to request objects in a specific order. Order specification should be done during initialization.

Therefore, I recommend making OrderedDictonary a class cluster, with private subclasses of InsertionOrderDictionary and NaturalOrderDictionary and CustomOrderDictionary. Then, the user simply creates an OrderedDictionary like so:

OrderedDictionary * dict = [[OrderedDictionary alloc] initWithOrder:kInsertionOrder];
//or kNaturalOrder, etc

For a CustomOrderDictionary, you could have them give you a comparison selector, or even (if they're running 10.6) a block. I think this would provide the most flexibility for future expansion while still maintain an appropriate name.

Answer 2

What about KeyedArray?

Answer 3

By decoupling the indexed order from the insertion order, doesn't this simply boil down to keeping an array and Dictionary in a single object? I guess my vote for this type of object is IndexedKeyDictionary

In C#:

public class IndexedKeyDictionary<TKey, TValue> { 

  List<TKey> _keys;
  Dictionary<TKey, TValue> _dictionary;
  ...

  public GetValueAtIndex(int index) {
    return _dictionary[_keys[index]];
  }

  public Insert(TKey key, TValue val, int index) {
    _dictionary.Add(key, val);

    // do some array massaging (splice, etc.) to fit the new key
    _keys[index] = key;
  }

  public SwapKeyIndexes(TKey k1, TKey k2) {
    // swap the indexes of k1 and k2, assuming they exist in _keys
  }
}

What would be really cool is indexed values...so we have a way to sort the values and get the new key order. Like if the values were graph coordinates, and we could read the keys (bin names) as we move up/down along the coordinate plane. What would you call that data structure? An IndexedValueDictionary?

Answer 4

Strong vote for OrderedDictionary.

The word "ordered" means exactly what you are advertising: that in iterating through a list of items, there is a defined order to selection of those items. "Indexed" is an implementation word -- it talks more to how the ordering is achieved. Index, linked list, tree... the user doesn't care; that aspect of the data structure should be hidden. "Ordered" is the exact word for the additional feature you are offering, regardless of how you get it done.

Further, it seems like the choice of ordering could be at the user's option. Any reason why you couldn't create methods on your datatype that allow the user to switch from, say, alphabetical ordering to insertion-time ordering? In the default case, a user would choose a particular ordering and stick with it, in which case implementation would be no less efficient than if you created specialized subclasses for each ordering method. And in some less-used cases, the developer might actually wish to use any of a number of different orderings for the same data, depending on app context. (I can think of specific projects I've worked on where I would have loved to have such a data structure available.)

Call it OrderedDictionary, because that's precisely what it is. (Frankly, I have more of a problem with the use of the word "Dictionary", because that word heavily implies ordering, where popular implementations of such don't provide it, but that's my pet peeve. You really should just be able to say "Dictionary" and know that the ordering is alphabetical -- because that's what a dictionary IS -- but that argument is too late for existing implementations in the popular languages.) And allow the user to access in what order he chooses.

Answer 5

As you said in your last paragraph, I think that InsertionOrder(ed)Dict(ionary) is pretty unambiguous; I don't see how it could be interpreted in any way other than that the keys would be returned in the order they were inserted.

Answer 6

I vote for InsertionOrderDictionary. You nailed it.