Python multimap

[brad]

Recently had a need to us a multimap container in C++. I now need to
write equivalent Python code. How does Python handle this?

k['1'] = 'Tom'
k['1'] = 'Bob'
k['1'] = 'Joe'
....

Same key, but different values. No overwrites either.... They all must
be inserted into the container

Thanks,
Brad

 

[Mike Kent]

Recently had a need to us a multimap container in C++. I now need to
write equivalent Python code. How does Python handle this?

k['1'] = 'Tom'
k['1'] = 'Bob'
k['1'] = 'Joe'
...

Same key, but different values. No overwrites either.... They all must
be inserted into the container

Thanks,
Brad

Python 2.5.2 (r252:60911, Jul 31 2008, 17:28:52)
[GCC 4.2.3 (Ubuntu 4.2.3-2ubuntu7)] on linux2
Type "help", "copyright", "credits" or "license" for more information.

k = {}
k['1'] = []
k['1'].append('Tom')
k['1'].append('Bob')
k['1'].append('Joe')

k['1'] ['Tom', 'Bob', 'Joe']

 

[Matt Nordhoff]

Recently had a need to us a multimap container in C++. I now need to
write equivalent Python code. How does Python handle this?

k['1'] = 'Tom'
k['1'] = 'Bob'
k['1'] = 'Joe'
...

Same key, but different values. No overwrites either.... They all must
be inserted into the container

Thanks,
Brad

I don't know if this is exactly equivalent, but what about using a
defaultdict like this?

from collections import defaultdict
k = defaultdict(list)
k['1'].append('Tom')
k['1'].append('Bob')
k['1'].append('Joe')
k['1']

['Tom', 'Bob', 'Joe']
--

 

[brad]

Python 2.5.2 (r252:60911, Jul 31 2008, 17:28:52)
[GCC 4.2.3 (Ubuntu 4.2.3-2ubuntu7)] on linux2
Type "help", "copyright", "credits" or "license" for more information.

k = {}
k['1'] = []
k['1'].append('Tom')
k['1'].append('Bob')
k['1'].append('Joe')

k['1']

['Tom', 'Bob', 'Joe']

There is only one '1' key in your example. I need multiple keys that are
all '1'. I thought Python would have something built-in to handle this
sort of thing.

I need a true multimap:

k['1'] = 'Tom'
k['1'] = 'Tommy'

without Tommy overwriting Tom and without making K's value a list of
stuff to append to. That's still just a regular map.

 

[Miles]

There is only one '1' key in your example. I need multiple keys that are all
'1'. I thought Python would have something built-in to handle this sort of
thing.

I need a true multimap ... without making K's value a list of stuff
to append to.

That's what a multimap is. If you really need the syntactic sugar,
it's simple to implement:

class multidict(dict):
def __setitem__(self, key, value):
try:
self[key].append(value)
except KeyError:
dict.__setitem__(self, key, [value])

-Miles

 

[castironpi]

Python 2.5.2 (r252:60911, Jul 31 2008, 17:28:52)
[GCC 4.2.3 (Ubuntu 4.2.3-2ubuntu7)] on linux2
Type "help", "copyright", "credits" or "license" for more information.

k = {}
k['1'] = []
k['1'].append('Tom')
k['1'].append('Bob')
k['1'].append('Joe')
k['1']

['Tom', 'Bob', 'Joe']

There is only one '1' key in your example. I need multiple keys that are
all '1'. I thought Python would have something built-in to handle this
sort of thing.

I need a true multimap:

k['1'] = 'Tom'
k['1'] = 'Tommy'

without Tommy overwriting Tom and without making K's value a list of
stuff to append to. That's still just a regular map.

I don't understand what a multimap does that a map of lists doesn't do.

 

[Fredrik Lundh]

That's what a multimap is.

iirc, a C++ multimap provides a flat view of the data, so you need to
provide custom enumeration and iteration methods as well.

</F>

 

[brad]

I don't understand what a multimap does that a map of lists doesn't do.

It counts both keys individually as separate keys. The Python workaround
does not... see examples... notice the key(s) that are '4'

Python output (using the k = [] idea):

Key: 4 Value: [[13, 'Visa'], [16, 'Visa']]
Key: 51 Value: [16, 'MC']
Key: 65 Value: [16, 'Discover']
Key: 2131 Value: [15, 'JCB']
Key: 300 Value: [14, 'Diners CB']
Key: 301 Value: [14, 'Diners CB']
Key: 302 Value: [14, 'Diners CB']
Key: 303 Value: [14, 'Diners CB']
Key: 304 Value: [14, 'Diners CB']
Key: 305 Value: [14, 'Diners CB']
Key: 35 Value: [16, 'JCB']
Key: 34 Value: [15, 'Amex']
Key: 55 Value: [16, 'MC or Diners US and CA']
Key: 36 Value: [14, 'Diners Intl']
Key: 37 Value: [15, 'Amex']
Key: 1800 Value: [15, 'JCB']
Key: 54 Value: [16, 'MC']
Key: 6011 Value: [16, 'Discover']
Key: 52 Value: [16, 'MC']
Key: 53 Value: [16, 'MC']
Key: 385 Value: [14, 'Diners CB']
21 is the size of the dict

A C++ multimap

Key: 1800 Value: JCB 15
Key: 2131 Value: JCB 15
Key: 300 Value: Diners_Club 14
Key: 301 Value: Diners_Club 14
Key: 302 Value: Diners_Club 14
Key: 303 Value: Diners_Club 14
Key: 304 Value: Diners_Club 14
Key: 305 Value: Diners_Club 14
Key: 34 Value: American_Express 15
Key: 35 Value: JCB 16
Key: 36 Value: Diners_Club 14
Key: 37 Value: American_Express 15
Key: 385 Value: Diners_Club 14
Key: 4 Value: Visa 16
Key: 4 Value: Visa 13
Key: 51 Value: MasterCard 16
Key: 52 Value: MasterCard 16
Key: 53 Value: MasterCard 16
Key: 54 Value: MasterCard 16
Key: 55 Value: MasterCard 16
Key: 6011 Value: Discover 16
Key: 65 Value: Discover 16
22 is the size of the multimap

 

[castironpi]

I don't understand what a multimap does that a map of lists doesn't do.

It counts both keys individually as separate keys. The Python workaround
does not... see examples... notice the key(s) that are '4'

Python output (using the k = [] idea):

Key: 4 Value: [[13, 'Visa'], [16, 'Visa']]

A C++ multimap

Key: 4 Value: Visa 16
Key: 4 Value: Visa 13

You are looking at a two-line workaround. A single Key-4 element is
always k[4][0], if 4 is in k. To remove k[4] is a little trickier.
If len( k[4] )> 1: k[4].pop( ), else k.pop( 4 )[ 0 ]. (Smooth.)

 

[Carl Banks]

Python 2.5.2 (r252:60911, Jul 31 2008, 17:28:52)
[GCC 4.2.3 (Ubuntu 4.2.3-2ubuntu7)] on linux2
Type "help", "copyright", "credits" or "license" for more information.

k = {}
k['1'] = []
k['1'].append('Tom')
k['1'].append('Bob')
k['1'].append('Joe')
k['1']

['Tom', 'Bob', 'Joe']

There is only one '1' key in your example. I need multiple keys that are
all '1'. I thought Python would have something built-in to handle this
sort of thing.

I need a true multimap:

k['1'] = 'Tom'
k['1'] = 'Tommy'

without Tommy overwriting Tom and without making K's value a list of
stuff to append to. That's still just a regular map.

What would you want to happen if you were to execute "print k['1']"?


Best I can tell, you want some sort of association list like this:

k = []
k.append(("1","Tom"))
k.append(("1","Tommy"))

which you can iterate through like this:

for key,value in k:
....

And if you need to retrieve items with a certain "key", probably it's
easiest to maintain sorted invariant, and to do insertion and lookup
with bisection algorithm (see bisect module).

I don't know of any class in the standard library that does all that
for you though.


Out of curiosity, what does a true multimap solve that a dictionary of
lists not solve?


Carl Banks

 

[brad]

Out of curiosity, what does a true multimap solve that a dictionary of
lists not solve?

Nothing really. I went with a variation of the suggested work around...
it's just that with Python I don't normally have to use work arounds and
normally one obvious approach is correct:

 

[Carl Banks]

Nothing really. I went with a variation of the suggested work around...
it's just that with Python I don't normally have to use work arounds and
  normally one obvious approach is correct:

Might I suggest that the C++ multimap is the workaround, rather than
the Python way of using dicts or lists or dicts of sets?

It was too much programming overhead and line noise confusion to
define nested templates to hold your nested data structures in C++, so
the STL provided a container that eliminated the nesting. In Python,
the obvious nested way to do it is easy, especially now with
defaultdicts, so there was no reason to provide a multimap.


Carl Banks