是否有标准的 Python 数据结构可以使事物保持有序？

Question

我有一组可能看起来像这样的范围：

 [(0, 100), (150, 220), (500, 1000)]

然后我会添加一个范围，比如 (250, 400) 列表如下所示：

 [(0, 100), (150, 220), (250, 400), (500, 1000)]

然后我会尝试添加范围 (399, 450) ，它会出错，因为重叠 (250, 400) 。

添加新范围时，我需要进行搜索以确保新范围不与现有范围重叠。列表中的任何范围都不会与列表中的另一个范围重叠。

为此，我想要一种 数据结构，它可以廉价地按排序顺序维护其元素，并且可以让我快速找到给定元素之前或之后的元素。

• 有没有更好的方法来解决这个问题？ Python 中是否有类似的数据结构？
• 我知道 bisect 模块存在，我可能会使用它。但我希望有更好的东西。
• 编辑：我使用 bisect 模块解决了这个问题。我有一个代码链接，因为它有点长。不幸的是，paste.list.org 被证明不是放置它的好地方，因为它已经不存在了。

原文由 Omnifarious 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

使用 SortedCollection 中的 SortedDict 。

SortedDict 提供与字典相同的方法。此外，SortedDict 有效地按排序顺序维护其键。因此，keys 方法将按排序顺序返回键，popitem 方法将删除具有最高键的项，等等。

我用过它 - 它有效。不幸的是，我现在没有时间进行适当的性能比较，但主观上它似乎比 bisect 模块更快。

原文由 Milind R 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

看起来你想要像 bisect 的 insort_right/insort_left 这样的东西。 bisect 模块适用于列表和元组。

 import bisect

l = [(0, 100), (150, 300), (500, 1000)]
bisect.insort_right(l, (250, 400))
print l # [(0, 100), (150, 300), (250, 400), (500, 1000)]
bisect.insort_right(l, (399, 450))
print l # [(0, 100), (150, 300), (250, 400), (399, 450), (500, 1000)]

您可以编写自己的 overlaps 函数，您可以在使用 insort 之前使用它进行检查。

我假设您的数字有误，因为 (250, 400) 重叠 (150, 300) 。 overlaps() 可以这样写：

 def overlaps(inlist, inrange):
    for min, max in inlist:
        if min < inrange[0] < max and max < inrange[1]:
            return True
    return False

原文由 Nick Presta 发布，翻译遵循 CC BY-SA 4.0 许可协议