Is there a canonical way to check whether an iterable is ordered?

Fri Sep 19 06:59:08 EDT 2014

Chris Angelico wrote:
> On Fri, Sep 19, 2014 at 3:15 PM, Steven D'Aprano
> <steve+comp.lang.python at pearwood.info> wrote:
>> However, as far as I am aware, there are no built-ins that will fail that
>> test, yet. Although the iteration order of dicts and sets is arbitrary, I
>> think that (at least to date) it will be the same order every time you
>> iterate over the dict or set within a single run of the Python
>> interpreter. (Provided the dict or set hasn't changed.)
>>>> That's not a language guarantee though. It's an implementation detail. In
>> principle, it could be different each time:
>>>> s = set("abcd")
>> list(s)
>> => returns ['d', 'a', 'b', 'c']
>> list(s)
>> => returns ['c', 'a', 'd', 'b']
>> Possibly for the set, but the dict is guaranteed some measure of
> stability:
>> https://docs.python.org/3.4/library/stdtypes.html#dict-views
> """If keys, values and items views are iterated over with no
> intervening modifications to the dictionary, the order of items will
> directly correspond."""

Yes, but that doesn't mean that if you iterate over them twice, they will
necessarily be the same each time. The promise is that:
keys = list(mydict)
values = list(mydict.values())
assert keys == [item[0] for item in mydict.items()]
assert values == [item[1] for item in mydict.items()]
But *not* this:
keys1 = list(mydict)
keys2 = list(mydict)
assert keys1 == keys2
It's hard to think of an implementation which would support the first but
not the second, but if you did, Python would allow it :-)
[...]
> So if iterating over d.keys() and then d.values() with no mutations is
> guaranteed to give the same order, then so is iterating over d.keys(),
> then d.keys(), then d.values(), 

Not so! So long as the iteration of values() matched the *second* iteration
of keys(), it would be allowed. There's nothing which says that the first
iteration of keys() has to match the second.
Here's a proof of concept of what would be allowed:
import random
class MyDict:
 def __init__(self, items):
 self._items = list(dict(items).items())
 self._flags = [False, False, False]
 def keys(self):
 k = [item[0] for item in self._items]
 self._check(0)
 return k
 def values(self):
 k = [item[1] for item in self._items]
 self._check(1)
 return k
 def items(self):
 k = self._items[:]
 self._check(2)
 return k
 def _check(self, i):
 self._flags[i] = True
 if self._flags == [True, True, True]:
 random.shuffle(self._items)
 self._flags = [False, False, False]
-- 
Steven