Python multimap

**Mike Kent** · Aug 27 '08, 01:55 PM

Re: Python multimap

On Aug 27, 9:35 am, brad <byte8b...@gmai l.comwrote:

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** · Aug 27 '08, 02:15 PM

Re: Python multimap

brad wrote:

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(lis t)
>>k['1'].append('Tom')
>>k['1'].append('Bob')
>>k['1'].append('Joe')
>>k['1']

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

**Michele Petrazzo** · Aug 27 '08, 02:15 PM

Re: Python multimap

brad wrote:

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
>

Subclassing the builtin dict?

class d(dict):
def __setitem__(sel f, item, value):
if not item in self: super(d, self).__setitem __(item, [])
self[item].append(value)

>>D = d()
>>D[1] = "Hello"
>>D[1] = "World!"
>>D[1]

['Hello', 'World!']

Thanks,
Brad

Michele

**brad** · Aug 27 '08, 05:55 PM

Re: Python multimap

Mike Kent wrote:

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** · Aug 27 '08, 06:15 PM

Re: Python multimap

brad wrote:

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__(sel f, key, value):
try:
self[key].append(value)
except KeyError:
dict.__setitem_ _(self, key, [value])

-Miles

**castironpi** · Aug 27 '08, 06:15 PM

Re: Python multimap

On Aug 27, 12:52 pm, brad <byte8b...@gmai l.comwrote:

Mike Kent wrote:

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.

**brad** · Aug 27 '08, 06:45 PM

Re: Python multimap

castironpi wrote:

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_Expres s 15
Key: 35 Value: JCB 16
Key: 36 Value: Diners_Club 14
Key: 37 Value: American_Expres s 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

**Fredrik Lundh** · Aug 27 '08, 06:45 PM

Re: Python multimap

Miles wrote:

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>

**castironpi** · Aug 27 '08, 07:45 PM

Re: Python multimap

On Aug 27, 1:38 pm, brad <byte8b...@gmai l.comwrote:

castironpi wrote:

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** · Aug 28 '08, 04:25 AM

Re: Python multimap

On Aug 27, 1:52 pm, brad <byte8b...@gmai l.comwrote:

Mike Kent wrote:

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** · Aug 28 '08, 06:45 PM

Re: Python multimap

Carl Banks wrote:

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** · Aug 28 '08, 07:35 PM

Re: Python multimap

On Aug 28, 2:41 pm, brad <byte8b...@gmai l.comwrote:

Carl Banks wrote:

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:

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

Python multimap

Python multimap

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment