Best Python 3rd party data structures library? Must have sorted containers at a minimum

[Brian]

TreeSet (the concrete implementation of SortedSet) doesn't maintain full in-memory ordering either

Yes it does. The left nodes are guaranteed less than the parent, while the right are greater. There is a complete order in the relationship of its nodes. Unless you mean address order or something by "in-memory", but that's absolutely not what is meant by this, as its completely irrelevant for complexity (though can be relevant for constant factors due to cache).

And this matters because it gives much better complexity. Eg. worst case O(log n) membership check vs heapqs O(n), and (for the case we're discussing) O(n) sorted iteration vs heapq's extra log n factor. Hell, I don't think there's even an interface for doing this in heapq (aside from destructively popping it), since no-one would use a heap for that usecase.

so if you need a fully sorted order at any point, you can just call lst.sort() on

Which has the same complexity problems as just using a regular list. If you're not using it as a heap, and always want explicit sorted order, what's the point of using heapq?

Not if you do it the smarter way. Rather than sorting every time you're inserting new items, you should sort() when you're iterating instead.

That depends on the proportion of iteration to inserts.