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.

Perhaps just use tuples, and ensure they have no duplicate elements at creation time. — wim
– wim, Commented Feb 12, 2021 at 19:16
" both sets and frozensets sort elements" no, they do not. Both of those data structures have no inherent order. Anything you see is an implementation detail in this case, most -- but not all -- integers simply hash to themselves, hence the apparent sorting — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Feb 12, 2021 at 19:18
Anyway, what particular aspects of set objects do you require? Is fast-lookup the important part? that is the main set use-case. It sounds like you seem to only care about having no duplicates... — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Feb 12, 2021 at 19:25
For example, on Python 3.7+, you could just use tuples and use a function to ensure no duplicates and maintain order (as already alluded to), so just: def no_dupe(data): return tuple(dict.fromkeys(data)) — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Feb 12, 2021 at 19:34

John Kugelman · Accepted Answer · 2021-02-12 19:40:36Z

4

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.

answered Feb 12, 2021 at 19:40

John Kugelman

365k70 gold badges555 silver badges600 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

juanpa.arrivillaga Over a year ago

No need to call .keys

John Kugelman Over a year ago

Right, it's optional. I prefer to be explicit here. (I'm not a fan of how iterating over a dictionary iterates over its keys. One of Python's rare missteps.)

Octavio del Ser · Accepted Answer · 2022-06-30 09:40:24Z

2

There is no such implementation in the standard library

answered Jun 30, 2022 at 9:40

Octavio del Ser

7555 silver badges17 bronze badges

1 Comment

mara004 Over a year ago

correct, but a pity...

Collectives™ on Stack Overflow

Data structure like frozenset which maintains insertion order?

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related