Sets in Python

[Tim Peters]

[Magnus Lie Hetland]
> Does that mean "maybe not" any of the features mentioned? Or only
> the ones in brackets?

Rather than make everyone suffer Quoting Hell, I left out the interesting
part <wink>.  The answer is that neither

    if x in dict:

nor

    for x in dict:

will be in 2.1.  There were too many arguments about it, so it got
reassigned to PEP Limbo (BTW, nobody yet has volunteered to own a PEP for
this).

Note Greg Wilson's PEP for adding a set type to Python:

    http://python.sourceforge.net/peps/pep-0218.html

Note that 2.1 does introduce a new dict.popitem() method, which selects,
returns, *and removes* an arbitrary (key, value) pair from the dict.  It
generally runs in O(1) time, and always O(1) space, and is crucial for
getting "the right" overall O() behavior for algorithms of the form:

    while dict:
        e = pick some element from dict
        del dict[e]
        muck around with e, possibly adding more stuff to dict

It wasn't possible to code such a loop to run in better than quadratic time
prior to 2.1 ("pick some element" couldn't do better than materialize all of
dict.keys(), unless you kept additional data structures in synch with the
dict).