Data structure like frozenset which maintains insertion order?

user_8935725 0
Viewed 315

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.

standard-library immutability set python
2 Answers

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.

user_685870

There is no such implementation in the standard library

user_89357250
Related