Most efficient pair-value data structure in Python with support for duplicates and sorting?

Question

What is the most efficient pair-value data structure in Python with support for duplicates and sorting?

I need a dictionary like structure but it must support duplicates, I am looking a solution that could be sorted fast based in the first value of each pair.

Answer 1

Keep a sorted list using the bisect module. With a list data, for each new pair (a,b), data.insert at the index returned by bisect(data,(a,LARGE_NUMBER)) to add a new entry after all existing entries starting with a. The list is always maintained in sorted order, so you don't worry about "sorting fast".

>>> from bisect import bisect
>>> from random import randint
>>> data = []
>>> for x in range(20):
...   a,b = randint(1,10),randint(1,100)
...   data.insert(bisect(data,(a,1000)),(a,b))
...
>>> for d in data: print (d)
...
(1, 67)
(1, 85)
(1, 38)
(2, 78)
(3, 57)
(3, 37)
(4, 76)
(4, 74)
(5, 47)
(5, 24)
(5, 59)
(5, 91)
(6, 85)
(6, 41)
(7, 18)
(7, 41)
(7, 24)
(9, 48)
(9, 77)
(9, 82)
(10, 80)