On Wed, Nov 10, 2021 at 5:45 PM Steven D'Aprano steve@pearwood.info wrote:
On Wed, Nov 10, 2021 at 05:11:33PM +1100, Chris Angelico wrote:
Nothing's technically new. You could make an inefficient sorted dict like this:
class SortedDict(dict): def __iter__(self): return iter(sorted(self.keys()))
You would need more than that. You would want to ensure that the dict's repr shows it is sorted order. You would need popitem to pop items in the appropriate order. There may be other APIs that sorted dicts provide than merely sorting the keys on iteration.
Sure. That was a massively oversimplified one, to point out that the question of whether this is "truly new" is fairly meaningless. A thing can be extremely useful without actually being *new* per se.
You don't actually need to implement this to see how repeatedly sorting the keys would give terrible performance for anything above small sets of data.
And yes. That is exactly the problem.
IMO this is a great tool to have on PyPI. Someone can start the naive way, run into major performance problems, and then go "huh, maybe someone else has already solved this problem". Doesn't need to be in the stdlib for that.
You may have missed that this thread has already discussed two mature, good quality sorted dict implementations that have been on PyPI for years:
https://pypi.org/project/sortedcontainers/
https://pypi.org/project/treap-python/
Here are a few more:
https://pypi.org/project/ruamel.ordereddict/
I know it's on PyPI, in multiple forms. I'm saying that it's a great tool to keep there, not in the stdlib.
ChrisA