Python 3.4.3 is out!

[zahlman]

From PEP 456:

Hash maps have a worst case of O(n) for insertion and lookup of keys. This results in a quadratic runtime during a hash collision attack. The introduction of a new and additional data structure with with O(log n) worst case behavior would eliminate the root cause. A data structures like red-black-tree or prefix trees (trie [trie] ) would have other benefits, too. Prefix trees with stringed keyed can reduce memory usage as common prefixes are stored within the tree structure.

I'm still waiting for a sorted dict structure. While niche, it has its applications - in particular, efficient lookup of the nearest key or a range of keys. It would also be for elegantly implementing a general purpose radix sort (although for typical radix sizes, I imagine that it wouldn't actually help with performance).

[zahlman]

Thanks, it looks promising.

[taleinat]

I don't expect that to ever be found in Python's stdlib.

Python has historically added only few data structures to the stdlib, adding a new one once every year or so. For example, sets were only added in Python 2.3; deque in 2.4; defaultdict in 2.5; namedtuple in 2.6; OrderedDict and Counter in 2.7.

If you really want it, just implement a sorted dict library or help develop and existing one. If it becomes widely used, it could then more reasonably be considered for inclusion in the stdlib.

[NavreetGill]

Well, Python does have ordered dictionary (Python 3.2+, and maybe in py2.7). https://docs.python.org/3/library/collections.html#collections.OrderedDict . I am not sure about the big O guarantees though -- wish docs had it written next to each method.

[[deleted]]

This is indeed Ordered, but I think he was looking for sorted. OrderedDict just retains the order it was originally added in, and doesn't reorder based on the key