Add `OrderedSet` to stdlib

Ideas
85

I’m now encountering exactly this problem. Currently, we have 3 options:

self.agents = defaultdict(list)
self.agents[type(agent)].append(agent)

Performance for adding and removing 1000 agents: 2.06 ms ± 3.11 µs

self.agents = defaultdict(set)
self.agents[type(agent)].add(agent)

Performance for adding and removing 1000 agents: 439 µs ± 1.3 µs

self.agents = defaultdict(dict)
self.agents[type(agent)][agent] = None

Performance for adding and removing 1000 agents: 460 µs ± 2.11 µs

All options are imperfect:

  • Lists are slow (and allow duplicates)
  • Sets don’t keep insertion order (making runs non-deterministic)
  • dicts are ugly in usage (due to their redundant None values)

So I would really love to have a fast datastructure that keeps insertion order, doesn’t allow duplicates, and has a fast and nice user API without hacks like the dict with None values. OrderedSet sounds perfect for that.