Key collection in Python?

Question

Is there any equivalent of a KeyedCollection in Python, i.e. a collection in which elements have (or dynamically generate) their own keys?

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

Answer 1

@Mehrdad said:

Because semantically this does not make much sense. When an object knows its key, it makes no sense to put it in a dictionary - this is not a key-value pair. This is more of a semantic problem than anything else.

With this limitation in Python, nothing is done what you want. I suggest you use dict and not worry about this level of detail on semantics. @Gabi Purcaru's answer shows how you can create an object with the right interface. Why worry about how it works domestically?

It is possible that C # KeyedCollection does the same under covers: it requests an object for its key, and then saves the key for quick access. In fact, from the docs:

By default, KeyedCollection (Of TKey, TItem) includes a dictionary search, which can be obtained using the Dictionary property. When an item is added to the KeyedCollection (Of TKey, TItem), the item key is retrieved once and stored in the search dictionary for faster searches. This behavior is overridden by specifying a dictionary creation threshold when creating a KeyedCollection (Of TKey, TItem). A search dictionary is created for the first time items that exceed this threshold. If you specify -1 as a threshold, a search dictionary is never created.

Answer 2

You can very easily mimic:

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 KeyedDict instead of dict with KeyedObject subclasses (where get_key return a valid key based on some property of the object).

Answer 3

Given your limitations, anyone trying to implement what you are looking for with a dict will bark the wrong tree. Instead, you should write a subclass of list that overrides __getitem__ to provide the desired behavior. I wrote it so that he first tried to get the desired element by index, and then returned to searching for the element using the key attribute of the contained objects. (This may be a property if the object should determine this dynamically.)

The linear search cannot be avoided unless you want to duplicate something; I am sure that the C # implementation does the same if you do not permit the use of a dictionary to store 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 might also want to override __contains__ similar way so that you can say if "key" in kc... If you want to make it even more like a dict , you can 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.

Answer 4

I don't really like C #, but I think dictionaries are what you need.

http://docs.python.org/tutorial/datastructures.html#dictionaries

http://docs.python.org/tutorial/datastructures.html

Or maybe lists:

http://docs.python.org/library/functions.html#list

Answer 5

Why not just use a dict ? If the key already exists, the key reference will be used in the dict; it will not be pointlessly duplicated.

 class MyExample(object): def __init__(self, key, value): self.key = key self.value = value m = MyExample("foo", "bar") d = {} d[m.key] = m first_key = d.keys()[0] first_key is m.key # returns True 

If the key does not exist yet, a copy of it will be saved, but I do not see a problem in this.

 def lame_hash(s): h = 0 for ch in s: h ^= ord(ch) return h d = {} d[lame_hash(m.key)] = m print d # key value is 102 which is stored in the dict lame_hash(m.key) in d # returns True 

Answer 6

I'm not sure if this is what you had in mind, but this dictionary will create its own keys when you add to it ...

 class KeyedCollection(dict): def __init__(self): self.current_key = 0 def add(self, item): self[self.current_key] = item abc = KeyedCollection() abc.add('bob') abc.add('jane') >>> abc {0: 'bob', 1: 'jane'} 

Answer 7

What about set() ? Elements can have their own k

Answer 8

To find out more that the already correct answer from @Gabi Purcaru answers, here is a class that does the same as gabi, but also checks the correct given type for the key and value (like TKey and TValue.net KeyedCollection).

 class KeyedCollection(MutableMapping): """ Provides the abstract base class for a collection (:class:`MutableMappinp`) whose keys are embedded in the values. """ __metaclass__ = abc.ABCMeta _dict = None # type: dict def __init__(self, seq={}): self._dict = dict(seq) @abc.abstractmethod def __is_type_key_correct__(self, key): """ Returns: The type of keys in the collection """ pass @abc.abstractmethod def __is_type_value_correct__(self, value): """ Returns: The type of values in the collection """ pass @abc.abstractmethod def get_key_for_item(self, value): """ When implemented in a derivated class, extracts the key from the specified element. Args: value: the element from which to extract the key (of type specified by :meth:`type_value`) Returns: The key of specified element (of type specified by :meth:`type_key`) """ pass def __assert_type_key(self, key, arg_name='key'): if not self.__is_type_key_correct__(key) : raise ValueError("{} type is not correct".format(arg_name)) def __assert_type_value(self, value, arg_name='value'): if not self.__is_type_value_correct__(value) : raise ValueError("{} type is not correct".format(arg_name)) def add(self, value): """ Adds an object to the KeyedCollection. Args: value: The object to be added to the KeyedCollection (of type specified by :meth:`type_value`). """ key = self.get_key_for_item(value) self._dict[key] = value # Implements abstract method __setitem__ from MutableMapping parent class def __setitem__(self, key, value): self.__assert_type_key(key) self.__assert_type_value(value) if value.get_key() != key: raise ValueError("provided key does not correspond to the given KeyedObject value") self._dict[key] = value # Implements abstract method __delitem__ from MutableMapping parent class def __delitem__(self, key): self.__assert_type_key(key) self._dict.pop(key) # Implements abstract method __getitem__ from MutableMapping parent class (Mapping base class) def __getitem__(self, key): self.__assert_type_key(key) return self._dict[key] # Implements abstract method __len__ from MutableMapping parent class (Sized mixin on Mapping base class) def __len__(self): return len(self._dict) # Implements abstract method __iter__ from MutableMapping parent class (Iterable mixin on Mapping base class) def __iter__(self): return iter(self._dict) pass # Implements abstract method __contains__ from MutableMapping parent class (Container mixin on Mapping base class) def __contains__(self, x): self.__assert_type_key(x, 'x') return x in self._dict