Is there a standard Python data structure that keeps things in sorted order?

Question

I have a set of ranges that might look something like this:

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

I would then add a range, say (250, 400) and the list would look like this:

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

I would then try to add the range (399, 450), and it would error out because that overlapped (250, 400).

When I add a new range, I need to search to make sure the new range does not overlap an existing range. And no range will ever be in the list that overlaps another range in the list.

To this end, I would like a data structure that cheaply maintained its elements in sorted order, and quickly allowed me to find the element before or after a given element.

Is there a better way to solve this problem? Is there a data structure like that available in Python? I know the bisect module exists, and that's likely what I will use. But I was hoping there was something better.

Edit: I solved this problem using the bisect module. Here is a link to the code. It's a bit longish, so I won't post it here:

Implementation of byte range list

Answer 1

Use SortedDict from the SortedCollection.

A SortedDict provides the same methods as a dict. Additionally, a SortedDict efficiently maintains its keys in sorted order. Consequently, the keys method will return the keys in sorted order, the popitem method will remove the item with the highest key, etc.

I've used it - it works. Unfortunately I don't have the time now to do a proper performance comparison, but subjectively it seems to have become faster than the bisect module.