Data structure to implement a dictionary with multiple indexes?

Question

I am looking for a data structure that holds the same values under two different indexes, where I can access the data by either one.

Example:

x = mysticalDataStructure()
x.add(1,'karl', dog)
x.add(2,'lisa', cat)
$ x[1].age
2
$ x['karl'].age
2
$ x[1].age = 4
$ x['karl'].age
4

Is there anything prerolled, or what is the best approach to roll my own (I need access via an index (number going from 0 to n in increments of 1), and via a string).

collections.ordereddict does not seem to have fast random access via the position, as far as I see I can only walk it with the iterator until I reach element i (I can insert in the right order).

• martineau: If you change a value through one key, do you expect the new value to be retrieved with the other key?
• ted: @martineau : yes exactly
• formiaczek: See this answer / module: stackoverflow.com/questions/11449232/multiple-keys-per-value/…

Answer 1

class MultiKeyDict(object):
 def __init__(self, **kwargs):
 self._keys = {}
 self._data = {}
 for k, v in kwargs.iteritems():
 self[k] = v
 def __getitem__(self, key):
 try:
 return self._data[key]
 except KeyError:
 return self._data[self._keys[key]]
 def __setitem__(self, key, val):
 try:
 self._data[self._keys[key]] = val
 except KeyError:
 if isinstance(key, tuple):
 if not key:
 raise ValueError(u'Empty tuple cannot be used as a key')
 key, other_keys = key[0], key[1:]
 else:
 other_keys = []
 self._data[key] = val
 for k in other_keys:
 self._keys[k] = key
 def add_keys(self, to_key, new_keys):
 if to_key not in self._data:
 to_key = self._keys[to_key]
 for key in new_keys:
 self._keys[key] = to_key
 @classmethod
 def from_dict(cls, dic):
 result = cls()
 for key, val in dic.items():
 result[key] = val
 return result

Usage:

>>> d = MultiKeyDict(a=1, b=2)
>>> d['c', 'd'] = 3 # two keys for one value
>>> print d['c'], d['d']
3 3
>>> d['c'] = 4
>>> print d['d']
4
>>> d.add_keys('d', ('e',))
>>> d['e']
4
>>> d2 = MultiKeyDict.from_dict({ ('a', 'b'): 1 })
>>> d2['a'] = 2
>>> d2['b']
2

• martineau: Probably ought to have a __delitem__() too.
• Aleksei astynax Pirogov: @martineau, this is only sketch to explain the concept
• ted: perfect, this is pure awesome, while i need to do two list accesses I can also store instances of immutable types.
• ted: @martineau considering completness, yes, but I won't need that in my case
• Aleksei astynax Pirogov: @ted, i slightly modified the class - now changes by one key reflects to the other (value if the same)

Answer 2

Is there a particular reason you can't just use a dictionary:

x = {}
x[1] = x['karl'] = dog
x[2] = x['lisa'] = cat

Then you can access it by either.

If you really don't want to repeat your self you do this:

class MysticalDataStructure(dict):
 def add(self, key1, key2, value):
 return self[key1] = self[key2] = value
x = MysticalDataStructure()
x.add(1, 'karl', dog)
x.add(2, 'lisa', cat)

• Has QUIT--Anony-Mousse: This is also nice, using a shared index.
• Hans Z: wouldn't modifying x[1] not modify x['karl']?
• Aprillion: @Hans of course it would be modified, it is the same object - objects are passed as references in python (by value of the object reference - see stackoverflow.com/a/986145/1176601)
• Hans Z: x[1] = x['karl'] = 3, x[1] = 2 does not change x['karl']
• Aprillion: @Hans i guess this needs to be clarified - any answer including this one will only ever works for mutable types of course (3 is an immutable integer literal) - if you need to update 2 immutables of the same value at the same time, the best way is to put the immutable into an object and have 2 references to the 1 mutable object

Answer 3

Just use three maps.

maps = [dict(), dict(), dict()]
def insert(rec):
 maps[0][rec[0]] = rec
 maps[1][rec[1]] = rec
 maps[2][rec[2]] = rec

Changes to key attributes of the rec object will require reinsertion though. Just like any other map, when you change the key of an object.

The maps just map key -> object, after all. They don't actually store copies of the object (it just isn't garbage collected). So a map is an index, nothing more. If you want three indexes, use three maps. Write a couple of glue code functions to manage them.

As mentioned by Trevor, you can also use a shared dictionary:

index = dict()
def insert(rec):
 index[rec[0]] = rec
 index[rec[1]] = rec
 index[rec[2]] = rec

then you can access it by either.

Beware of key collisions though!

• ted: +1 answers my badly formulated example, but you forgot for example that I also have indices wich dont come from the object, e.g. 1 like an id for the dog