Issue 32792: ChainMap should preserve order of underlying mappings

This also applies to 3.6 because ChainMap can be used with OrderedDict.

An alternate implementation:

d = {}
for mapping in reversed(self.maps):
    d.update(mapping)
return iter(d)

Unfortunately both implementations work only with hashable keys. In general case mappings may be not hashtables.

See discussion on PR 5586 regarding backporting to 3.6.x.

Sorry, I was wrong. reversed() is not needed here.

The advantage of this implementation is that it can be faster because of iterating mappings in C code instead of Python code. But the side effect of it is that the iterator keeps references to all values. If this is not desirable, the code can be written something like:

    return iter(dict.fromkeys(itertools.chain.from_iterable(self.maps)))

New changeset 3793f95f98c3112ce447288a5bf9899eb9e35423 by Raymond Hettinger in branch 'master':
bpo-32792: Preserve mapping order in ChainMap() (GH-5586)
https://github.com/python/cpython/commit/3793f95f98c3112ce447288a5bf9899eb9e35423

On PR 5586 we discussed reverting the order of the iteration by mappings. There are reasons of doing this. But this adds a subtle behavior change. Currently list(ChainMap({1: int}, {1.0: float})) returns [1]. With reversed() it will return [1.0]. This change LGTM.

The code in msg311969 doesn't reuse hash values. The following implementations do this:

    return iter({**m for m in reversed(self.maps)})

or, without keeping reverences to values:

    return iter(list({**m for m in reversed(self.maps)}))

New changeset 170b3f79506480f78275a801822c9ff1283e16f2 by Raymond Hettinger (Miss Islington (bot)) in branch '3.7':
bpo-32792: Preserve mapping order in ChainMap() (GH-5586) (#GH-5617)
https://github.com/python/cpython/commit/170b3f79506480f78275a801822c9ff1283e16f2

> The code in msg311969 doesn't reuse hash values.

That doesn't make sense.  The dict.update() method reuses the hashes of the input mappings when possible.

    >>> from collections import ChainMap
    >>> class Int(int):
            def __hash__(self):
                    print(f'Hashing {self}', file=sys.stderr)
                    return int.__hash__(self)

            
    >>> import sys
    >>> d = { Int(1): 'f1', Int(2): 'f2' }
    Hashing 1
    Hashing 2
    >>> e = { Int(1): 's1', Int(3): 's3' }
    Hashing 1
    Hashing 3
    >>> c = ChainMap(d, e)
    >>> list(c)                     # Note, no calls to hash() were made
    [1, 3, 2]

I referred to msg311969, not msg311822.