Data structure like frozenset which maintains insertion order?

Question

I need set-like data structure with these properties:

• hashable
• no duplicate elements
• maintains order
• immutable
• iterable
• part of standard library? want to keep it simple

What is happening:

frozenset([3,1,2,2,3]) -> frozenset(1,2,3)

What I need:

frozenset*([3,1,2,2,3]) -> frozenset*(3,1,2)

I thought I could use frozenset but both sets and frozensets reorder elements. I assume this is for faster duplicate checks? But in any case I can't have a reordering.

Answer 1

As of Python 3.7 dicts no longer reorder elements and instead guarantee to preserve insertion order. You could use a dict where the keys are your set items and the values are ignored.

>>> dict.fromkeys([3,1,2,2,3])
{3: None, 1: None, 2: None}

Dicts aren't frozen, so if that's crucial then you could first put all the items into a dict and then build a tuple from the keys.

>>> tuple(dict.fromkeys([3,1,2,2,3]).keys())
(3, 1, 2)

This would be pretty close to a frozenset. The main difference is that it would take O(n) rather than O(1) time to check if an item is in the tuple.