[issue44555] Dictionary operations are LINEAR for any dictionary (for a particular code).

[Inada Naoki]

Inada Naoki <songofacandy at gmail.com> added the comment:

iterating whole over the dict is O(n) where n is the historical max size of the dict.

On the other hand, there are no guarantee about `next(iter(d))` is O(1). The guarantee is O(n) at worst case. And your example is the worst case. So this is not a bug.

As Dennis wrote, we won't add doubly linked list to the dict only for this purpose.
OrderedDict is for the use case.

I don't have any better idea than bpo-32623. More ideas are welcome.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue44555>
_______________________________________