Sort dict with key of user class

Python Help
1

Hi forum,

I’m trying to sort dict with key of type of user defined class type.

I’m not clear on something.

  1. Is dict ordered type in Python3.8. I mean preserve the insertion order may be not enough. It’ll be better that we can sort the dict in place. Not just sort’ed’ into list of tuple and get back to another dict. C++ has both std::map and std::unordered_map.

  2. It seems the __lt__, the < function is enough for a user class to be sort’ed’ on dict. Are __hash__, __eq__, __ne__ useful too?

  3. PyCharm gives hint on line 25 for the argument to dict(). I do not know how to fix it. Do I need to provide a GetItem() function?

Thanks

class Item:
    def __init__(self, name='', num=0):
        self.name = name
        self.num = num

    # def __hash__(self):
    #     return hash((self.name, self.num))

    # def __eq__(self, other):
    #     return (self.name, self.num) == (other.name, other.num)

    def __lt__(self, other):
        return (self.name, self.num) < (other.name, other.num)

    # def __ne__(self, other):
    #     return not self == other

    def __repr__(self):
        return self.name + ',' + str(self.num)


def hello():
    items = {Item('ccc', 3): 11, Item('bbb', 2): 12, Item('aaa', 1): 13}
    logging.info('%s, %s', type(items), items)
    items2 = dict(sorted(items.items(), key=lambda item: item[0]))  # line 25: PyCharm: Unexpected type(s)
    logging.info('%s, %s', type(items2), items2)

    # Unexpected type(s): (List[Item]) Possible type(s): (SupportsKeysAndGetItem[Item, _VT]) (Iterable[Tuple[Any, Any]])


    # output:
    # <class 'dict'>, {ccc,3: 11, bbb,2: 12, aaa,1: 13}
    # <class 'dict'>, {aaa,1: 13, bbb,2: 12, ccc,3: 11}
2

I think it is duplicate of this discussion:

3

As of Python 3.7, dicts preserve insertion order. You cannot sort a dict. Dict keys do not need to be orderable:

d = {1+2j: 'a', 3-2j: 'b'}
sorted(d.keys())  # raises TypeError

Keys only need to support two operations:

  • equality (the __eq__ method);

  • hash (the __hash__ method).

By default, all objects support both, since they are inherited from object, but they won’t necessarily give the right results. To give the right results, you must make sure that:

  1. If a == b, then hash(a) == hash(b).

  2. Needed only for efficiency: if a != b, then hopefully hash(a) !== hash(b) (but it is okay if sometimes the hashes are equal).

Normally, we only define hash for immutable objects. Otherwise, if the object mutates, the hash will change, and you can’t find it in the dict any more.

Classes only need to define __lt__ to support sorting, but read
the note in the documentation:

https://docs.python.org/3/library/functions.html#sorted

Also, just because you define __lt__ doesn’t mean that the results are sensible. Your class needs to define a “total order”, otherwise the results can be unexpected:

# Floats with NANs do not have a total order.
from math import nan
a = [1.0, nan, 3.0, 2.0, nan, 0.0]
sorted(a)  # returns [1.0, nan, 0.0, 2.0, 3.0, nan]

Floats without NANs do have a total order, even including INFs is okay, it is only NANs that throw the order out.

Complex numbers have no order at all; sets also support the < and > operator but they don’t define an order, that is subset and superset relations.

You say: “PyCharm gives hint on line 25 for the argument to dict().”

Please tell us what PyCharm says exactly. It may give an error code as well.

But my guess is that to make PyCharm happy, you should probably uncomment your defined __hash__ and __eq__ dunders.

1 Like
4

Thanks Steven,

PyCharm complaints on this line:

items2 = dict(sorted(items.items(), key=lambda item: item[0]))

Unexpected type(s): (List[Item]) Possible type(s): (SupportsKeysAndGetItem[Item, _VT]) (Iterable[Tuple[Any, Any]])

When I trying to retrieve a key from dict it requires __hash__, __eq__:

logging.info('%d', my_dict[Item('bbb', 2)])

As I understand, the two of __eq__, __lt__ satisfies total ordering. Others like __gt__ can be deduced from them.

So I’ll provide three of __hash__, __eq__, __lt__. Are these enough for a class type to work as the key in dict and other data structures in Python.

Thanks