python - Python 中支持重复和排序的最有效的对值数据结构？

Question

Python 中支持重复和排序的最有效的对值数据结构是什么？

我需要一个类似结构的字典，但它必须支持重复项，我正在寻找一个可以根据每对的第一个值快速排序的解决方案。

Answer 1

使用 bisect 保持排序列表模块。使用列表 data，对于每个新对 (a,b)，data.insert 位于 bisect(data ,(a,LARGE_NUMBER)) 在所有以 a 开头的现有条目之后添加一个新条目。该列表始​​终按排序顺序维护，因此您不必担心“快速排序”。

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