Python . List of unique ordered items

Question

Is there a lineal python structure that preserves insertion order and uniqueness of elements at the same time? I know that sets preserve uniqueness and list insertion order. By now I will implement this behavior with a class like:

class OrderedUniqueContainer:
    
    def __init__(self):
        self._data = []

    def add(self, object):
        # Assuming object has neccesary __hash__ and __eq__
        if object not in self._data:
            self._data.append(object) 

    def remove(self, object):
        try:
            self._data.remove(object)
        except ValueError:
            pass

I also need to implement union and difference. Is there a built-in structure to achieve this behavior?

If you have two equal elements in different sets, which element should come first in a union? — Dani Mesejo, Oct 06 '21 at 07:47
The left part of the operation. If A = {3, 4, 6} and B = { 2, 6, 5} then A.union(B) = { 3, 4, 6, 2, 5} — , Oct 06 '21 at 07:52
You don't really want to have a bare `except:` `pass` that could hide all sorts of nastiness. At least make it log something. Or maybe better to raise the exception if trying to remove an item that isn't in the object. — DisappointedByUnaccountableMod, Oct 06 '21 at 08:04
@balmy `{0}.discard(1)` doesn't complain, either. Why should this? — no comment, Oct 06 '21 at 08:05
@balmy It was an example. If I need to manage that condition from the caller class, I would re-raise or log or something like you cleverly note. — , Oct 06 '21 at 08:07
@don'ttalkjustcode Because ``{0}.discard([])`` does complain. — MisterMiyagi, Oct 06 '21 at 08:16
@MisterMiyagi I execute {0}.discard({1}) in python 3.9.1 and it does not complain. Any suggestions? — , Oct 06 '21 at 08:28
@02435324 That's because various ``set`` methods silently convert ``set`` input to ``frozenset`` to simplify set-of-frozenset operations. ["Note, the elem argument to the ``__contains__()``, ``remove()``, and ``discard()`` methods may be a set. To support searching for an equivalent frozenset, a temporary one is created from elem."](https://docs.python.org/3/library/stdtypes.html#frozenset.clear) — MisterMiyagi, Oct 06 '21 at 08:34
Related questions: [Does Python have an ordered set?](https://stackoverflow.com/questions/1653970/does-python-have-an-ordered-set); [Using ordered dictionary as ordered set](https://stackoverflow.com/questions/51145707/using-ordered-dictionary-as-ordered-set); [Are sets ordered like dicts in python3.6](https://stackoverflow.com/questions/45581901/are-sets-ordered-like-dicts-in-python3-6); [Why don't Python sets preserve insertion order?](https://stackoverflow.com/questions/61414947/why-dont-python-sets-preserve-insertion-order) — Stef, Oct 06 '21 at 09:31
Related question: [Converting a list to a set changes element order](https://stackoverflow.com/questions/9792664/converting-a-list-to-a-set-changes-element-order) — Stef, Oct 06 '21 at 09:32

MisterMiyagi · Accepted Answer · 2021-10-06T08:27:12.157

A dict is insertion ordered* and guarantees uniqueness of keys. Either use a plain dict and ignore values by convention or create a class with the desired interface.

For example, a basic set-like class would look like this:

class OrderedUniqueContainer:
    """Set-like container of unique items maintaining insertion order"""
    def __init__(self, initial=()):
        self._data = dict.fromkeys(initial)

    def copy(self):
        """Return a shallow copy of the set."""
        clone = type(self)()
        clone._data = self._data.copy()
        return clone

    def add(self, item):
        """Add element `item` to the set."""
        self._data[item] = None

    def discard(self, item):
        """Remove element `item` from the set if it is present."""
        self._data.pop(item, None)

    def update(self, *others: 'OrderedUniqueContainer'):
        """Update the set, adding elements from all others."""
        for other in others:
            self._data.update(other._data)

    def union(self, *others: 'OrderedUniqueContainer'):
        """Return a new set with elements from the set and all others."""
        clone = self.copy()
        clone.update(*others)
        return clone

    # additional desired methods

*Since Python 3.6 de-facto and since Python 3.7 guaranteed.

But that allows me to make a union and difference? I think I would lose order at the moment I execute set(self._data.keys()).union(other._data.keys()) in a hypothetic union method. — , Oct 06 '21 at 08:05
You would have to implement it yourself, but ``dict`` is fully capable of expressing unions and such. For example, a ``union`` corresponds to an ``update``. — MisterMiyagi, Oct 06 '21 at 08:09
I implemented union with the update method. I have implemented difference looping the right-hand set and removing every element in the left hand set ( I added __iter__ method also to let the class be target of the for loop): for item in other: self.remove(item) . Do you think is correct ? — , Oct 06 '21 at 08:26

Python . List of unique ordered items

1 Answers1