pythonlistsortingordereddictionarysortedcontainers

How to correctly use SortedSets by key in Python sortedcontainers


SortedListWithKey can sort a list using a lambda function:

from sortedcontainers import SortedListWithKey

SortedListWithKey([[4, 'last'], [1, 'first']], key=lambda x: x[0])
# Result: SortedListWithKey([[1, 'first'], [4, 'last']], key=<function <lambda> at 0x107f5d730>)

But let's say I need to use set() to have only unique values, the documentation says that it also accepts a key= param for sorting by a custom function, but I cannot get it to work:

from sortedcontainers import SortedSet

SortedSet([[4, 'last'], [1, 'first']], key=lambda x: x[0])

Will throw the following exception:

values = set(chain(*iterables))
TypeError: unhashable type: 'list'

Is there a way to achieve this?


Solution

  • The sorted set requires elements be hashable. Your elements are lists which don't support hashing. Change the elements to tuples and it will work:

    >>> from sortedcontainers import SortedSet
    >>> ss = SortedSet([(4, 'last'), (1, 'first')], key=lambda value: value[0])
    >>> ss
    SortedSet([(1, 'first'), (4, 'last')], key=<function <lambda> at 0x10fff4848>)
    

    This sorted set will order elements by the first index in the pair. The benefit of tuples is that they're hashable, the drawback is they're immutable.

    Consider using a sortedcontainers.SortedDict instead:

    >>> sd = SortedDict({4: 'last', 1: 'first'})
    >>> sd
    SortedDict({1: 'first', 4: 'last'})
    >>> sd[2] = 'second'
    >>> sd.pop(4)
    'last'
    

    The sorted dict will keep keys in sorted order and let you update the values to anything you like.