[Python-ideas] Add dict.getkey() and set.get()

[Andrew Barnert]

From: Oscar Benjamin <oscar.j.benjamin at gmail.com>

Sent: Sunday, September 15, 2013 1:02 PM


> I don't know whether this is relying on undefined behaviour but the
> following is O(1) and seems to work:
> 
>>>>  def canonical_key(d, k):
> ...     k, = {k} & d.keys()
> ...     return k


I'm pretty sure it's undefined behavior.

It does seem to work with the CPython and PyPy 3.x versions I have around, with every test I throw at it, and if you look through the source you can see why… but there isn't any good reason it should.

set.intersection(other) and set & other don't appear to be documented beyond "Return a new set with elements common to the set and all others" (http://docs.python.org/3/library/stdtypes.html#set.intersection). dict_keys doesn't define what its methods do, beyond saying that the type is "set-like", and implements collections.abc.Set. (http://docs.python.org/3/library/stdtypes.html#dictionary-view-objects). And in fact, here you're relying on the fact that dict_keys doesn't actually do the same thing as set. {1} & {1.0, 2.0} gives you {1}, but {1} & {1.0: 0, 2.0: 0}.keys() gives you {1.0}.

As a side note, that "k, = " bit is going to give you an ugly "ValueError: need more than 0 values to unpack" instead of a nice "KeyError: 3" if k isn't in d, so you might want to wrap it in a try to convert the exception.


Meanwhile, there is something that seems like it _should_ be guaranteed to work… but it doesn't. intersection_update says "Update the set, keeping only elements found in it and all others", which seems to say you'll keep the elements in the original set. So this ought to work:

    s = set(d.keys())
    s &= {k}
    s, = s
    return s

But it doesn't. You have to do it the other way around, which seems to be incorrect:

    s = {k}
    s &= d.keys()
    s, = s
    return s

And in fact, that's the only reason your method works. Ultimately, what {k} & d.keys() does is to call dict_keys.np_and({k}, d.keys()). If you look at the source (http://hg.python.org/cpython/file/7df61fa27f71/Objects/dictobject.c#l3320), this is basically the backward version that works (except that it makes a copy tmp = set(s), and calls intersection_update instead of using &=).