Is there a "multimap" implementation in Python?

Question

I am new to Python and I am familiar with implementations of Multimaps in other languages . Does Python have such a data structure built-in or accessible in a commonly used library?

To illustrate what I mean by "multimap":

a = multidict() a[1] = 'a' a[1] = 'b' a[2] = 'c' print(a[1]) # prints: ['a', 'b'] print(a[2]) # prints: ['c'] 

Answer 1

There is no such thing in the standard library. You can use defaultdict though:

 >>> from collections import defaultdict >>> md = defaultdict(list) >>> md[1].append('a') >>> md[1].append('b') >>> md[2].append('c') >>> md[1] ['a', 'b'] >>> md[2] ['c'] 

(You can use set instead of list , in which case you would .add instead of .append .)

---

As an aside : look at these two lines that you wrote:

 a[1] = 'a' a[1] = 'b' 

This means that you want the expression a[1] be equal to two different values. This is not possible in dictionaries, because their keys are unique, and each of them is associated with a single meaning. However, you can extract all the values ​​inside the list associated with this key one by one. You can use iter and then consecutive next calls to do this. Or you can just use two loops:

 >>> for k, v in md.items(): ... for w in v: ... print("md[%d] = '%s'" % (k, w)) ... md[1] = 'a' md[1] = 'b' md[2] = 'c' 

Answer 2

Just for future visitors. There is currently a Python implementation for Multimap. It is available through pypi.

Answer 3

Stephan202 has the correct answer, use defaultdict . But if you want something with a C ++ STL multimap interface and much worse, you can do this:

 multimap = [] multimap.append( (3,'a') ) multimap.append( (2,'x') ) multimap.append( (3,'b') ) multimap.sort() 

Now, when you repeat multimap , you will get pairs, as in std::multimap . Unfortunately, this means that your loop code will start to look as ugly as C ++.

 def multimap_iter(multimap,minkey,maxkey=None): maxkey = minkey if (maxkey is None) else maxkey for k,v in multimap: if k<minkey: continue if k>maxkey: break yield k,v # this will print 'a','b' for k,v in multimap_iter(multimap,3,3): print v 

So defaultdict really cool and uses the power of python, and you have to use it.

Answer 4

Or a subclass of dict :

 class Multimap(dict): def __setitem__(self, key, value): if key not in self: dict.__setitem__(self, key, [value]) # call super method to avoid recursion else self[key].append(value) 

Answer 5

There is currently no multi-map in the standard Python libraries.

WebOb has a MultiDict class, used to represent HTML form values, and is used by several Python Web infrastructures, so the battle has been tested.

Werkzeug also has a MultiDict class for the same reason.

Answer 6

The standard way to write this in Python is with a dict whose elements are list or set . As stephan202 says , you can automate this somewhat with defaultdict, but you don't need to.

In other words, I would translate your code to

 a = dict() a[1] = ['a', 'b'] a[2] = ['c'] print(a[1]) # prints: ['a', 'b'] print(a[2]) # prints: ['c'] 

Answer 7

You can take a list of tuples and then sort them as if it were a multicard.

 listAsMultimap=[] 

Let me add some elements (tuples):

 listAsMultimap.append((1,'a')) listAsMultimap.append((2,'c')) listAsMultimap.append((3,'d')) listAsMultimap.append((2,'b')) listAsMultimap.append((5,'e')) listAsMultimap.append((4,'d')) 

Now figure it out.

 listAsMultimap=sorted(listAsMultimap) 

After listing you will receive:

 [(1, 'a'), (2, 'b'), (2, 'c'), (3, 'd'), (4, 'd'), (5, 'e')] 

This means that it works like a multimap!

Please note that, as in the case of several cards, here the values ​​are also sorted in ascending order if the keys are the same (for the same key = 2, "b" is before "c", although we did not add them in this order.

If you want to get them in descending order, just change the sorted () function as follows:

 listAsMultimap=sorted(listAsMultimap,reverse=True) 

And after you get output like this:

 [(5, 'e'), (4, 'd'), (3, 'd'), (2, 'c'), (2, 'b'), (1, 'a')] 

Similarly, here the values ​​are in descending order if the keys are the same.

Answer 8

I do not clearly understand the semantics of your example

 a[1] = 'a' a[1] = 'b' #?? 

The second line a[1] = 'b' should replace the element in [1]. If so, then you need to use a dictionary. If not, you need to use a dictionary of lists (as already suggested)