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).

If you change a value through one key, do you expect the new value to be retrieved with the other key? — martineau
– martineau, Commented Jun 19, 2012 at 16:39
See this answer / module: stackoverflow.com/questions/11449232/multiple-keys-per-value/… — formiaczek
– formiaczek, Commented Sep 9, 2013 at 18:56

Aleksei astynax Pirogov · Accepted Answer · 2012-06-22 11:28:18Z

13

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

edited Jun 22, 2012 at 11:28

answered Jun 19, 2012 at 17:12

Aleksei astynax Pirogov

2,50115 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

16 Comments

martineau Over a year ago

Probably ought to have a __delitem__() too.

Aleksei astynax Pirogov Over a year ago

@martineau, this is only sketch to explain the concept

ted Over a year ago

perfect, this is pure awesome, while i need to do two list accesses I can also store instances of immutable types.

ted Over a year ago

@martineau considering completness, yes, but I won't need that in my case

Aleksei astynax Pirogov Over a year ago

@ted, i slightly modified the class - now changes by one key reflects to the other (value if the same)

|

Trevor · Accepted Answer · 2012-06-19 16:28:52Z

12

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)

edited Jun 19, 2012 at 16:28

answered Jun 19, 2012 at 16:22

Trevor

9,6082 gold badges27 silver badges26 bronze badges

9 Comments

Has QUIT--Anony-Mousse Over a year ago

This is also nice, using a shared index.

Hans Z Over a year ago

wouldn't modifying x[1] not modify x['karl']?

Aprillion Over a year ago

@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 Over a year ago

x[1] = x['karl'] = 3, x[1] = 2 does not change x['karl']

Aprillion Over a year ago

@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

|

Has QUIT--Anony-Mousse · Accepted Answer · 2012-06-19 16:20:29Z

2

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!

answered Jun 19, 2012 at 16:20

Has QUIT--Anony-Mousse

77.8k14 gold badges146 silver badges198 bronze badges

1 Comment

ted Over a year ago

+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

Collectives™ on Stack Overflow

Data structure to implement a dictionary with multiple indexes?

3 Answers 3

16 Comments

9 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

16 Comments

9 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related