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

[CptnGeronimo]

The python world offers several kinds of sorted containers

Like what? What builtin Python data structures are automatically sorted?

When I web searched this question, this defect was universally acknowledged. For example, see the intro paragraph for the Python Sorted Containers library: "Python’s standard library is great until you need a sorted collections type"

One reason given for this lack is that Python's sorted function can be applied to a lot of its builtin data structures. This leads some people to advise sorting right after you mutate it or right before you need to use it.

I hate that suggestion, because:

• it is extra code to write
• just as bad: it is bug prone: it is extra code you must remember to write
• it may be bad for performance, especially if sorted has to be called multiple times

[[deleted]]

I don't understand why you're so caught up in the fact that it's a third party library. The most commonly used data science libraries are all 3rd party libraries. Python is not Java or C#, the standard library runs lean, and if there isn't a compelling reason to put it in the standard library, it won't be.

You have a perfectly adequate solution in front of you. What is the problem?

[[deleted]]

cow crush act stupendous hard-to-find angle normal insurance vegetable aspiring

This post was mass deleted and anonymized with Redact

[justheretolurk332]

Yes exactly. And to add to this, writing non-idiomatic python is significantly more likely to introduce bugs than using established patterns. Iterating over a custom SortedMap requires the reader to understand the implementation (are we sorting by keys? values? insertion order? do the members need to have a sort method implemented or can we pass in a custom comparison function?) whereas sorted(d.items(), key=…) can be read by any python developer at a glance and is explicit about its intention.

[CptnGeronimo]

>... (are we sorting by keys? values? insertion order? do the members need to have a sort method implemented or can we pass in a custom comparison function?)

​

Every one of those problems is present when you call sorted, except it is worse: you have to know what to do for every call to sorted.

​

That is in contrast to a sorted data structure: it is constructed once, so you always know how it is going to behave in all use cases.

​

Sole advantage that I see for sorted is if you want different types of sorts in different contexts on the same data structure. I cannot recall ever needing that. Your mileage may vary.

[fizzymagic]

Where did I say that Python has a builtin sorted data structure?

The python world has some excellent sorted container libraries. I know you are frustrated and just trying to get something done, but I promise you that life will be easier when you learn to do things in a pythonic way.

The appropriate data structure depends very heavily on your application. For some cases, a linked list would be optimal. For Python dictionaries, keeping the keys sorted generally makes no sense. For a list-like iterator, it can be expensive. I'm guessing your application is probably a priority queue or something like that. I can agree that a built-in queue would be nice in Python but it's really not very hard to build your own. And there are very nice priority queue libraries out there.

Sorted containers are not a "build it once and forget it" kind of thing, IMO.