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

[Steven D'Aprano]

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