python - Why does the OrderedDict keys view compare order-insensitive?

Question

Why does the OrderedDict keys view compare order-insensitive?

>>> from collections import OrderedDict
>>> xy = OrderedDict([('x', None), ('y', None)])
>>> yx = OrderedDict([('y', None), ('x', None)])
>>> xy == yx
False
>>> xy.keys() == yx.keys()
True

The OrderedDict keys view should arguably behave like an OrderedSet, but instead it behaves the same as dict.keys (i.e. like a usual set).

Same "issue" in python2:

>>> xy.viewkeys() == yx.viewkeys()
True

They are different types, (odict_keys is a subclass of dict_keys)

>>> type(xy.keys())
odict_keys
>>> type({}.keys())
dict_keys

And there is already an order-sensitive keys comparison available that they could have trivially used, but it's apparently only used as a post-check for the odict rich comparison.

Is this a design decision, or a bug? If it's a design decision, where could I find a discussion of the justification?

If you're keen to work around this behaviour because you need to compare the orders too, you could squirt the keys out into lists and compare those: list(xy) == list(yx). — Benjamin Hodgson♦
@BenjaminHodgson or all(x == y for x, y in zip(xy, yx)) if you want slightly lazier evaluation on python3.x — mgilson
@mgilson: You'd need to check len too, or use itertools.zip_longest with a sentinel, or that will return True if one set of keys is a truncated run of the other keys. You can also push more work to the C layer, running a titch faster for all but the smallest runs by importing at the top from operator import eq and then do len(xy) == len(yx) and all(map(eq, xy, yx)) at the test site, validating the length first then performing C level key comparisons as efficiently as possible. — ShadowRanger
Also note that other python implementations use ordered dictionaries by default (pypy). Making KeysView behave differently for ordered dict than for regular dict might make their implementation more difficult (which is sometimes considered in language decisions as far as I can tell). — mgilson
I posted on the Python-ideas mailing list to have more information: mail.python.org/pipermail/python-ideas/2015-December/… — Alexandre

ShadowRanger ShadowRanger · Accepted Answer · 2015-12-16T20:14:25

Looks like OrderedDict delegates the implementation of the various view objects to the common dict implementation; this remains the case even in Python 3.5 where OrderedDict gained a C accelerated implementation (it delegates object construction to _PyDictView_New and provides no override for the generic view's rich comparison function.

Basically, OrderedDict views iterate with the same order their backing OrderedDict would (because there is no cost to do so), but for set-like operations, they act like set, using content equality, subset/superset checks, etc.

This makes the choice to ignore ordering make sense to some extent; for some set operations (e.g. &, |, ^), the return value is a set without order (because there is no OrderedSet, and even if there were, which ordering do you use for something like & where the ordering may be different in each view?), you'd get inconsistent behaviors if some of the set-like operations were order sensitive and some weren't. And it would be even weirder when two OrderedDict keys views were order sensitive, but comparing OrderedDict views to dict views wasn't.

As I noted in the comments, you can get order sensitive keys comparison pretty easily with:

from operator import eq

# Verify that keys are the same length and same set of values first for speed
# The `all` check then verifies that the known identical keys appear in the
# same order.
xy.keys() == yx.keys() and all(map(eq, xy, yx))

# If you expect equality to occur more often than not, you can save a little
# work in the "are equal" case in exchange for costing a little time in the
# "not even equal ignoring order case" by only checking length, not keys equality:
len(xy) == len(yz) and all(map(eq, xy, yx))

python - Why does the OrderedDict keys view compare order-insensitive?

2 Answers