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. 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. Here's Java's standard SortedMap: https://docs.oracle.com/javase/7/docs/api/java/util/SortedMap.html That should give you some idea of the interface a sorted dict would likely provide.
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/ https://github.com/surenkov/PySortedDict https://pypi.org/project/sorteddict/ -- Steve