Keyed Collection in Python?

Question

Is there any equivalent to KeyedCollection in Python, i.e. a set where the elements have (or dynamically generate) their own keys?

i.e. the goal here is to avoid storing the key in two places, and therefore dictionaries are less than ideal (hence the question).

Answer 1

You can simulate that very easily:

class KeyedObject(object):
    def get_key(self):
        raise NotImplementedError("You must subclass this before you can use it.")

class KeyedDict(dict):
    def append(self, obj):
        self[obj.get_key()] = obj

Now you can use a KeyedDict instead of dict with subclasses of KeyedObject (where get_key return a valid key based on some object property).

Answer 2

Given your constraints, everyone trying to implement what you're looking for using a dict is barking up the wrong tree. Instead, you should write a list subclass that overrides __getitem__ to provide the behavior you want. I've written it so it tries to get the desired item by index first, then falls back to searching for the item by the key attribute of the contained objects. (This could be a property if the object needs to determine this dynamically.)

There's no way to avoid a linear search if you don't want to duplicate something somewhere; I am sure the C# implementation does exactly the same thing if you don't allow it to use a dictionary to store the keys.

class KeyedCollection(list):
     def __getitem__(self, key):
         if isinstance(key, int) or isinstance(key, slice):
             return list.__getitem__(key)
         for item in self:
             if getattr(item, "key", 0) == key:
                 return item
         raise KeyError('item with key `%s` not found' % key)

You would probably also want to override __contains__ in a similar manner so you could say if "key" in kc.... If you want to make it even more like a dict, you could also implement keys() and so on. They will be equally inefficient, but you will have an API like a dict, that also works like a list.