[Python-3000] Default dict iterator should have been iteritems()

[Nicholas Bastin]

On 9/4/07, "Martin v. Löwis" <martin at v.loewis.de> wrote:
> > (assuming d[x] is  O(log n))
>
> In Python, d[x] is typically considered to be O(1) (unlike in C++,
> where it is O(log n)). Of course, with Python using a hashtable,
> performance may decrease in the presence of collisions. In the
> normal case, dict((x, d[x]) for x in d) will be O(n) in Python.

Even if we suppose that d[x] is O(1) (and I don't have real data to
say whether most uses of it actually conform to this, besides keyword
argument passing), that still makes:

[(x, d[x]) for x in d]

O(2n), which is O(n), but only pedantically.  In the real world, 2n is
still worse than n (and the hashtable means that it can devolve into
O(n**2) in the worst case).  However, all that said, you'd probably
never write the above line of code, and d.iteritems() will continue to
suffice if there are concerns about 'for (k,v) in d' being materially
different than 'if x in d'.

--
Nick